Transcript A polynomial time algorithm for testing primality

PRIMES is in P
Manindra Agrawal
Neeraj Kayal
Nitin Saxena
Dept of CSE, IIT Kanpur
The Problem
Given number n, test if it is prime
efficiently.
Efficiently = in time a polynomial in number
of digits
= (log n)c for some constant c
In Complexity Theory
Terminology
is PRIMES in P?
• PRIMES : set of all prime numbers
• P : class of efficiently solvable problems
All problems that can be solved in time which
grows as polynomial in the input size of the
problem instance.
The Trial Division Method
Try dividing by all numbers up to n1/2.
– Already known since ~230 BC (Sieve of
Eratosthenes)
– takes exponential time: (n1/2).
– Also produces a factor of n when it is
composite.
Trial Division is Too Slow
• Trial division method is too
inefficient for large numbers:
A supercomputer working at 100
–teraflops
For a 100 digit
number, it
will require
will require
more
than
50 divisions.
about
10
the life of the universe to do this!
Is There a Faster Method?
• Many attempts were made to find an
efficient characterization of primes.
• None succeeded.
– For example, Wilson (18th century)
showed:
N is prime iff (n-1)! = -1 (mod n)
– This requires n-3 multiplications
Fermat’s Little Theorem
if n is prime then for any a:
an = a (mod n).
It is easy to check:
Compute a2, square it to a4, square it to a8,
…
Needs only O(log n) multiplications.
A Potential Test
• For a “few” a’s test if an = a (mod n);
• if yes, output PRIME else output
COMPOSITE.
This fails!
– For n = 561 = 3 * 11 * 17, all a’s satisfy
the equation!!
The Class NP
• NP: A set is in NP if every member of
the set has an efficiently verifiable
proof of membership.
– It may not be possible to find such a
proof efficiently.
– Example: set of graphs that contain a
cycle covering all vertices
• coNP: the complements of sets in NP.
PRIMES in NP  coNP
• A trivial algorithm shows that the set
is in coNP: given a factor of n it is
easy to verify that n is composite.
• [1974] Vaughan Pratt designed an NP
algorithm for testing primality.
PRIMES in P (conditionally)
• [1973] Miller designed a test based
on Fermat’s Little Theorem:
– It was efficient: O(log4 n) steps
– It was correct assuming Generalized
Riemann Hypothesis.
PRIMES in coRP
• Soon after, Rabin modified Miller’s
algorithm to obtain an unconditional
but randomized polynomial time
algorithm.
– This algorithm might give a wrong answer
with a small probability when n is
composite.
• [1973] Solovay-Strassen gave another
algorithm with similar properties.
PRIMES in P (almost)
• [1983] Adleman, Pomerance, and
Rumely gave a deterministic algorithm
running in time (log n)c log log log n.
PRIMES in RP
• [1986] Goldwasser and Kilian gave a
randomized algorithm that
– works almost always in polynomial time
– errs only on primes.
• [1992] Adleman and Huang improved
this to an algorithm that is always
polynomial time.
PRIMES is in P
[2002] We gave a deterministic and
unconditional polynomial-time
algorithm for primality testing.
Main Idea
• Start from Fermat’s Little Theorem.
• However:
r–1,
– Numbers
modulo n (ring
Z/nZ)
doesXnot
Consider
polynomials
modulo
n and
r-1).
seem
to Z/nZ[X]/(X
have nice structure
to exploit.
or the
ring
– So extend the ring to a larger ring in the
hope for more structure.
Generalized FLT
If n is prime
then for any a:
(X + a)n = Xn + a (mod n, Xr-1).

n
i
Proof: If n is prime, n divides
for every
i, 0 < i < n.
If n is composite, then n does not divide
n
for any prime p dividing n.
 
p
A Potential Test
For a “small” r and a “few” a’s, test
the Generalized FLT equation.
It Works (Almost)!
• We prove:
If
(X + a)n = Xn + a (mod n, Xr-1)
for every 0 < a < 2 r log n
and for suitably chosen “small” r
then
either n is a prime power or has a prime
divisor less than r
The Algorithm
• Input n.
1. Output COMPOSITE if n = mk, k > 1.
2. Find the smallest number r such that
Or(n) > 4 (log n)2. O (n) = smallest k with n = 1 (mod r).
3. If any number < r divides n, output
PRIME/COMPOSITE appropriately.
4. For every a  2 r log n:
r
–
k
If (X+a)n  Xn + a (mod n, Xr – 1) then output
COMPOSITE.
5. Output PRIME.
Correctness
• If the algorithm outputs COMPOSITE, n
must be composite:
– COMPOSITE in step 1  n = mk, k > 1.
– COMPOSITE in step 3  a number < r divides n.
– COMPOSITE in step 4  (X+a)n  Xn + a (mod n,
Xr-1) for some a.
• If the algorithm outputs PRIME in step 3,
n is a prime number < r.
When Algorithm Outputs
PRIME in Step 5
• Then (X+a)n = Xn + a (mod n, Xr-1) for
0 < a  2 r log n.
• Let prime p | n with Or(p) > 1.
• Clearly, (X+a)n = Xn + a (mod p, Xr-1)
too for 0 < a  2 r log n.
• And of course, (X+a)p = Xp + a (mod p,
Xr-1) (according to Generalized FLT)
Introspective Numbers
• We call any number m such that g(X)m
= g(Xm) (mod p, Xr-1) an introspective
number for g(X).
• So, 1, p and n are introspective
numbers for X+a for 0 < a  2 r log n.
Introspective Numbers Are
Closed Under *
Lemma: If s and t are introspective for
g(X), so is s * t.
Proof:
g(X)st = g(Xs)t (mod p, Xr – 1), and
g(Xs)t = g(Xst) (mod p, Xsr – 1)
= g(Xst) (mod p, Xr – 1).
So There Are Lots of Them!
• Let I = { ni * pj | i, j  0}.
• Every m in I is introspective for X+a
for 0 < a  2 r log n.
Introspective Numbers Are
Also For Products
Lemma: If m is introspective for both
g(X) and h(X), then it is also for g(X)
* h(X).
Proof:
(g(X) * h(X))m = g(X)m * h(X)m
= g(Xm) * h(Xm) (mod p, Xr-1)
So Introspective Numbers
Are For Lots of Products!
• Let Q = { a=1, 2r logn (X + a)ea | ea  0}.
• Every m in I is introspective for
every g(X) in Q.
• So there are lots of introspective
numbers for lots of polynomials.
Finite Fields Facts
• Let h(X) be an irreducible divisor of
rth cyclotomic polynomial Cr(X) in the
ring Fp[X]:
– Cr(X) divides Xr-1.
– Polynomials modulo p and h(X) form a
field, say F.
– Xi  Xj in F for 0  i  j < r.
Moving to Field F
• Since h(X) divides Xr-1, equations for
introspective numbers continue to
hold in F.
• We now argue over F.
Two Sets in Field F
• Let G = { Xm | m  I }.
– Every element of G is an rth root of
unity.
– |G|  Or(n) > 4 log2n.
• Let H = { g(X) (mod p, h(X)) | g(X) 
Q }.
– H is a multiplicative group in F.
H is large …
• Let Qlow be set of all polynomials in Q of
degree < |G|.
Lemma: There are > n2|G| distinct polynomials
in Qlow:
– Consider all products of X+a’s of degee < |G|.
 | G |  2 r log n  1 
– There are  2 r log n  1  >
> n2|G| of these
(since r > |G| and |G| > 2 log n).
 4 | G | log n 


 2 | G | log n 


… because Qlow injects into F
• Let f(X), g(X) in Qlow with f(X)  g(X).
• Suppose f(X) = g(X) in F. Then:
• For every Xm in G, f(Xm) = f(X)m = g(X)m =
g(Xm) in F.
• So polynomial P(Y) = f(Y) – g(Y) has |G| roots
in F.
• Contradiction, since P(Y)  0 and degree of
P(Y) is < |G|.
… implies that I has few
small numbers
• Let m1, m2, …, mk be numbers in I 
n2|G|.
• Suppose k > |G|.
• Then, there exist mi and mj, mi > mj,
such that
mi
mj
X = X (in F)
I: set of introspective numbers
F = Fp[X]/(h(X)), h(X) | Xr-1
Q: set of introspective polynomials
G = XI
H = Q (mod h(X))
• Let g(X) be any element of H. Then:
mi
mi
mj
mj
g(X) = g(X ) = g(X ) = g(X) (in F)
• Therefore, g(X) is a root of the
mi
mj
polynomial P(Y) = Y – Y in the field
F.
• Since H has more than n2|G|
polynomials in F, P(Y) has more than
n2|G| roots in F.
• Contradiction, since P(Y)  0 and
degree of P(Y) = mi  n2|G|.
I: set of introspective numbers
F = Fp[X]/(h(X)), h(X) | Xr-1
Q: set of introspective polynomials
G = XI
H = Q (mod h(X))
… so n must be a prime!
• Consider numbers na * pb with 0  a, b 
|G|.
• Each such number is  n2|G| (“small”).
• So there are  |G| (“few”) such numbers.
• This gives a, b, c, d with
(a,b)  (c,d) and na * pb = nc * pd
• Therefore, n = pe which implies n = p.
t = Or(n,p)
I: set of introspective numbers
I: set of introspective numbers
Q: set of introspective polynomials
F = Fp[X]/(h(X)), h(X) | Xrr-1
F = Fp[X]/(h(X)), h(X) | X -1
Qlow: polynomials
of deg < t
G = XI
H = Q (mod h(X))
The Choice of r
• We need r such that Or(n) > 4 (log n)2.
• Any r such that Or(n)  4 (log n)2 must
divide
k=1, 4 log2n (nk-1) < n16 log4n = 216 log5n.
• By Chebyshev’s prime deensity estimates:
lcm of first m numbers is at least 2m (for m
> 7).
• Therefore, there must exist an r that we
desire  16 (log n)5 + 1.
Time Complexity
• Step 4 dominates running time.
•Using a result of Fouvry, one can show
– It needs to verify
O(r log n) equations.
3
that r = O(log n) is enough.
2n) time to
–•The
Each result
equationshows
needs that
O~(r log
primes r
verify.
such that r-1 has a large prime
~(r1.5 log3n) =
• So
time
complexity
is
O
divisor have high density.
~(log10.5n).
O
•This brings time complexity down to
O~(log7.5n).
Further work
• [Lenstra-Pomerance] r = O(log2n) is
enough with a different polynomial.
– This improves time complexity to
O~(log6n).
• [Berrizbeitia-Bernstein] Randomized
primality proving algorithm with time
complexity O~(log4n).
Further Improvement?
• Conjecture: If n  1 (mod r) for some
prime r > log n and (X-1)n = Xn –1 (mod
n, Xr – 1) then n must be a prime
power.
• Yields a O~(log3n) time algorithm.