Transcript Xiaosi Zhou

PRIMES is in P
Agrawal-Kayal-Saxena
Presented by: Xiaosi Zhou
Outline
• Introduction
1. What is PRIMES
2. Algorithms for PRIMES before AKS
• AKS algorithm
1. Basic idea
2. Notation and Preliminaries
3. The algorithm and its correctness
4. Time complexity analysis
5. Conclusions
Introduction
•
What is PRIMES:
 The decision problem of efficiently determining
whether or not a given integer n is prime.
 Efficiently means in polynomial time, i.e, O(logn) the size of the input.
 Referred to as primality testing problem.
Algorithms before AKS (1)
•
The ancient method
 Try dividing n by every number m  n
 If any m divides n then n is composite otherwise
prime
 Inefficient-- O ( n )
Algorithms before AKS (2)
•
Fermat Little Theorem — incorrect testing
 For any prime number n, and any number a which
has no common divisors with n,
a
n 1
 1 (mod n)
Efficient — O(logn)
41
 Counterexample: 5  1 (mod 4) , but 4 is
composite
 However, it became the basis of many efficient
primality tests.

Algorithms before AKS (3)
• In 1975, Pratt showed that PRIMES is in NP.
• In 1976, Miller obtained a deterministic polynomial-time algorithm
based on Fermat’s Little Theorem assuming Extended Riemann
Hypothesis (ERH).
• In 1977, Solovay and Strassen came up with a randomized algorithm
which has a probability of error that can be made arbitrarily small for
all inputs.
• Rabin modified Miller’s algorithm to yield an unconditional but
randomized polynomial-time algorithm.
• In 1986, Goldwasser and Killian proposed a randomized algorithm
based on elliptic curves, running in expected polynomial-time on
almost all inputs.
• In 1992, Adleman and Huang modified the Goldwasser-Killian
algorithm to obtain a randomized polynomial time algorithm that
always produced a certificate of primality.
AKS algorithm
• There does exist a polynomial-time algorithm
for proving primality before AKS algorithm.
• But what is surprising is that AKS algorithm is
a relatively simple deterministic algorithm
which relies on no unproved assumptions.
AKS algorithm – the idea
• This test is based on the generalization of Fermat’s
Little Theorem.
• Theorem: Suppose that a and p are relatively
prime integers with p > 1. p is prime if and only if
( X  a)  X  a (mod p)
p
p
• The theorem suggests a simple test: given input p,
choose an a and test whether the above congruence
is satisfied.
• Too many coefficients to check, O(n)
The idea (Cont’d)
• A simpler condition to reduce the coefficients,
test if the following equation is satisfied
( X  a) p  X p  a (mod X r  1, p)
• This must hold if p is prime
• The problem now is that some composites n may
satisfy the equation for a few values of a and r.
• n must be a prime power if the equation holds for
several a’s and an appropriately chosen r.
Notation and Preliminaries
•
or (n)
denotes the order of a modulo r,
which is the smallest number k such that
a  1 (mod r )
k
•
 (r )
is Euler’s totient function giving the
number of numbers less than r that are
relatively prime to r.
AKS algorithm
Input: integer n > 1.
1. If (n  ab for a  N and b  1) , output COMPOSITE;
2. Find the smallest r such that or (n)  4 log 2 n
3. If 1 < (a, n) < n for some a  r , output
COMPOSITE;
4. If n  r , output PRIME;
5. For a=1 to 2  (r ) log n do
if ( ( X  a) n  X n  a mod ( X r  1, n)), output
COMPOSITE;
6. Output PRIME;
Correctness (1)
•
Theorem. The algorithm returns PRIME if and
only if n is prime.
Proof. [if] If n is prime, steps 1 and 3 can never
return COMPOSITE. By the modified Fermat
Little Theorem, the for loop also cannot return
COMPOSITE. Therefore the algorithm will
identify n as PRIME either in step 4 or in step
6.
Correctness (2)
Proof. [only if] If the algorithm returns
PRIME in step 4 then n must be prime since
otherwise step 3 would have found a nontrivial factor of n.
How about the algorithm returns PRIME in
step 6 ? We need more lemmas.
Correctness (3)

Let p be a prime divisor of n. Also, let   2  (r ) log n
Two sets:
I  {n  p | i, j  0}
i
i
and
P  {a 1 ( X  a) | ea  0}

ea

Correctness (4)
• Define two groups based on the two sets.
1. The first group G is the set of all residues of
numbers in I modulo r. We have |G| = t > 4 log 2 n
2. The second group U is the set of all non-zero
residues of polynomials in P modulo h(X) and p,
where h(X) is one irreducible factor of degree
or ( p) of X r  1
Correctness (5)
• Lemma. | U |  t    2 


 t 1

• Lemma. If n is not a power of p then | U |
1 2
n
2
t
• Lemma. If the algorithm returns PRIME then n is prime.
Proof. We have t=|G| and   2  (r ) log n
t    2
1
...  n 2
| U | 
2
 t 1

t
Therefore, n  p k for some k>0. If k>1 then the algorithm
will return COMPOSITE in step 1. Thus, n=p.
QED
Time complexity
O(t (n)  poly (log t (n)))
We use the symbol
O ~ (t (nfor
))
~
k
k
k 
Ex. O (log n)  O(log n  poly (log log n))  O(log n) for any   0
Theorem. The asymptotic time complexity of the algorithm is
O ~ (log 10.5 n)
Time complexity (Cont’d)
Input: integer n > 1.
1. If (n  ab for a  N and b  1) , output
COMPOSITE;
2
o
(
n
)

4
log
n
2. Find the smallest r such that r
3. If 1 < (a, n) < n for some a  r , output
COMPOSITE;
4. If n  r , output PRIME;
5. For a=1 to 2  (r ) log n do
if ( ( X  a) p  X p  a mod ( X r  1, p) ), output
COMPOSITE;
6. Output PRIME;
1
O ~ (log 3 n)
2
O ~ (log 7 n)
3
O ~ (log 6 n)
4
O ~ (log n)
5
O ~ (log 10.5 n)
Conclusions
• AKS algorithm is an unconditional deterministic
polynomial-time algorithm for primality testing.
• The complexity of the original algorithm of
AKS is O ~ (log 10.5 n) , and can be improved to
O ~ (log 7.5 n) by improving the estimate for r. This
algorithm can be further reduced to O ~ (log 3 n) if
one additional number theoretical conjecture can
be proved.
Thank you very much!