A Deterministic Polynomial-time Primality Test : A Deterministic Polynomial-time Primality Test Manindra Agrawal
Neeraj Kayal
Nitin Saxena
Brought to you by Amit Chakrabarti
Slide2 : “Turns out, Primes are in P”
-- Slashdot post, Aug 7, 00:08
“If this is true, they could have easily taken over the infrastructure of a modernized computer-bent, encryption-shielded society such as the US or Japan. If that is indeed the case, these guys deserve a Nobel Peace Prize for giving this powerful tool to all and not using it as a weapon of war.”
-- Slashdot comment, Aug 7, 00:20
“If this turns out to be true, then you can bet the NSA has had this algorithm for decades.”
-- Slashdot comment, Aug 7, 00:26
Slide3 : “Turns out, Primes are in P”
-- Slashdot post, Aug 7, 00:08
“If this is true, they could have easily taken over the infrastructure of a modernized computer-bent, encryption-shielded society such as the US or Japan. If that is indeed the case, these guys deserve a Nobel Peace Prize for giving this powerful tool to all and not using it as a weapon of war.”
-- Slashdot comment, Aug 7, 00:20
“If this turns out to be true, then you can bet the NSA has had this algorithm for decades.”
-- Slashdot comment, Aug 7, 00:26
The Problem : The Problem Given integer n, decide whether or not n is prime in time poly(log n).
Previously:
Randomized poly(log n)-time test
Deterministic poly((log n)log log log n)-time test
Deterministic poly-time test assuming ERH
The Test : The Test Easy: the identity
(x - a)n = xn – a (mod n)
holds for all a iff n is prime.
Concern: identity takes Q(n) time to verify even for a single a. And there are Q(n) a’s.
Key new result: if
(x – a)n = xn – a (mod n, xr-1)
for a “small” r and all “small” a, then n is prime.
Notation : Notation Pmin(n) = smallest prime factor of n
Pmax(n) = largest prime factor of n
or(n) = order of n mod r
= min { t > 0: nt = 1 (mod r) }
The Test in More Detail : The Test in More Detail Let t = 2r1/2 log n
Suppose r is prime; r < Pmin(n)
Suppose q = Pmax(r-1) satisfies
q > 2t
q | or(n)
Suppose (x – a)n = xn – a (mod n, xr-1) for all a in {1,2,…,t}
Then n is a prime power.
In Full Detail : In Full Detail if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r-1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME;
In Full Detail : In Full Detail if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r-1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME; Loop 1
In Full Detail : In Full Detail if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r- 1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME; Loop 2
What We Must Prove : What We Must Prove THE HARD PARTS
Lemma 1: The first loop finishes with a “small” value for r . . . r = O(log6n).
Theorem 1: If n is composite, the algorithm outputs COMPOSITE.
What We Must Prove : What We Must Prove THE EASY PARTS
Theorem 2: If n is prime, the algorithm outputs PRIME.
Theorem 3: The algorithm runs in poly(log n) time.
Proof of Lemma 1 : Proof of Lemma 1 Enough to show:
∃ c1,c2 and prime r [c1log6n, c2log6n] s.t.
q = Pmax(r-1) satisfies q > 2t and q | or(n).
There are W(x/log x) primes p < x s.t.
Pmax(p-1) > x2/3. [Fouvry’85]
Thus, W(log6n/log log n) primes r satisfy the
first condition . . . use r2/3 > 4r1/2log n = 2t.
Proof of Lemma 1 : Proof of Lemma 1 Enough to show:
∃ c1,c2 and prime r [c1log6n, c2log6n] s.t.
q = Pmax(r-1) satisfies q > 2t and q | or(n).
There are W(x/log x) primes p < x s.t.
Pmax(p-1) > p2/3. [Fouvry’85]
Thus, W(log6n/log log n) primes r satisfy the
first condition . . . use r2/3 > 4r1/2log n = 2t.
Proof of Lemma 1 : Proof of Lemma 1 Enough to show:
∃ c1,c2 and prime r [c1log6n, c2log6n] s.t.
q = Pmax(r-1) satisfies q > 2t and q | or(n).
There are W(x/log x) primes p < x s.t.
Pmax(p-1) > p2/3. [Fouvry’85]
Thus, W(log6n/log log n) primes r in the range
satisfy q > r2/3 > 4r1/2log n = 2t.
Proof of Lemma 1, cont’d : Proof of Lemma 1, cont’d Let x = c2log6n.
Take any such r which does not divide
N = (n - 1) (n2 - 1) … (nx1/3 - 1)
Exists, because log N < x2/3log n = O(log5n).
Then, (r-1)/q < r1/3 < x1/3
So, n(r-1)/q ≢ 1 (mod r)
So, q | or(n).
Proof of Theorem 2 : Proof of Theorem 2 if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r-1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME;
Proof of Theorem 3 : Proof of Theorem 3 if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r-1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME; Loop 1
Proof of Theorem 3 : Proof of Theorem 3 if(n = ab, b>1) output COMPOSITE;
for(r = 2 to n)
if(gcd(n,r) ≠ 1) output COMPOSITE;
if(r is prime)
q = Pmax(r- 1);
if(q 2t && n(r-1)/q ≢ 1 (mod r)) break;
for(a = 1 to t)
if((x-a)n ≢ xn-a (mod n,xr-1))
output COMPOSITE;
output PRIME; Loop 2
Finally… Proof of Theorem 1 : Finally… Proof of Theorem 1 To prove: if n is composite, the algorithm outputs COMPOSITE.
Assume that it outputs PRIME. Then
(x – a)n = xn – a (mod n, xr-1)
for all a in {1,2,…,t}. Also, q = Pmax(r-1) is s.t.
q > 2t and q | or(n)
Also,
r < Pmin(n)
Our goal: to prove that n is a prime power.
Two Key Inequalities : Two Key Inequalities Suppose n = p1k1 . p2k2 . . . psks
Then or(n) = lcm{ or(piki) } | lcm{ or(pi) }
.
Two Key Inequalities : Two Key Inequalities Suppose n = p1k1 . p2k2 . . . psks
Then q | or(n) = lcm{ or(piki) } | lcm{ or(pi) }
So, n has a prime factor p s.t. q | or(p)
Let d = or(p)
Then, d > q > 2t.
Also, p > Pmin(n) > r > q > 2t > t.
Our goal: to prove that n is a power of p.
Algebra : Algebra For integer m and f(x)Z[x], say (f,m) is nice if
f(xm) = f(x)m (mod p, xr-1)
If (f,m) and (g,m) are nice, then so is (fg,m).
If (f,m) and (f,m’) are nice, then so is (f,mm’).
Algebra : Algebra For integer m and f(x)Z[x], say (f,m) is nice if
f(xm) = f(x)m (mod p, xr-1)
If (f,m) and (g,m) are nice, then so is (fg,m).
If (f,m) and (f,m’) are nice, then so is (f,mm’).
Proof… f(xmm’) = f(xm)m’ (mod p, xmr-1)
f(xmm’) = f(xm)m’ (mod p, xr-1)
f(xmm’) = f(x)mm’ (mod p, xr-1)
More Algebra : More Algebra In Fp[x], xr-1 has an irreducible factor h(x) with deg(h) = or(p) = d.
Fix h(x); let K = Fp[x]/h(x).
Constructions : Constructions Ŝ =
S = image of Ŝ in K = Ŝ mod p, h(x)
Use the key inequalities:
Since p > t, |S| = |Ŝ| = > (d/t)t.
Since d > 2t, |S| > 2t = 22r1/2log n = n2r1/2.
Constructions, cont’d : Constructions, cont’d Let E = { nipj: 0 < i,j < r1/2 }
For all mE, m < n2r1/2 < |S|
Assume n is not a power of p
Then, |E| > (1 + r1/2)2 > r, so
E contains m,m’ such that m = m’ (mod r)
i.e., xm = xm’ (mod xr-1)
i.e., xm = xm’ in the field K.
The Nice Property : The Nice Property For any ĝŜ and mE, (ĝ,m) is nice, i.e.,
ĝ(xm) = ĝ(x)m (mod p, xr-1)
Enough to consider ĝ(x) = x – a.
Enough to consider m = n and m = p.
Now it’s trivial…
(x – a)n = xn – a (mod xr-1).
(x – a)p = xp – a (mod p) .
Corollary: in the field K,
for gS and mE, g(xm) = g(x)m.
The Nice Property : The Nice Property For any ĝŜ and mE, (ĝ,m) is nice, i.e.,
ĝ(xm) = ĝ(x)m (mod p, xr-1)
Enough to consider ĝ(x) = x – a.
Enough to consider m = n and m = p.
Now it’s trivial…
(x – a)n = xn – a (mod xr-1).
(x – a)p = xp – a (mod p) .
Corollary: in the field K,
for gS and mE, g(xm) = g(x)m.
The Nice Property : The Nice Property For any ĝŜ and mE, (ĝ,m) is nice, i.e.,
ĝ(xm) = ĝ(x)m (mod p, xr-1)
Enough to consider ĝ(x) = x – a.
Enough to consider m = n and m = p.
Now it’s trivial…
(x – a)n = xn – a (mod xr-1).
(x – a)p = xp – a (mod p) .
Corollary: in the field K,
for gS and mE, g(xm) = g(x)m.
The Nice Property : The Nice Property For any ĝŜ and mE, (ĝ,m) is nice, i.e.,
ĝ(xm) = ĝ(x)m (mod p, xr-1)
Enough to consider ĝ(x) = x – a.
Enough to consider m = n and m = p.
Now it’s trivial…
(x – a)n = xn – a (mod xr-1).
(x – a)p = xp – a (mod p) .
Corollary: in the field K,
for gS and mE, g(xm) = g(x)m.
The Nice Property : The Nice Property For any ĝŜ and mE, (ĝ,m) is nice, i.e.,
ĝ(xm) = ĝ(x)m (mod p, xr-1)
Enough to consider ĝ(x) = x – a.
Enough to consider m = n and m = p.
Now it’s trivial…
(x – a)n = xn – a (mod xr-1).
(x – a)p = xp – a (mod p) .
Corollary: in the field K,
for gS and mE, g(xm) = g(x)m.
The Contradiction : The Contradiction Let G = S, multiplicative subgroup of K*.
Since K* is cyclic, G is cyclic. Suppose G = g.
Recall: distinct m,m’E s.t. xm = xm’ in K. So,
g(x)m = g(xm) = g(xm’) = g(x)m’.
Thus, m = m’ (mod |G|).
But |G| > |S| > m,m’. Contradiction.
The Contradiction : The Contradiction Let G = S, multiplicative subgroup of K*.
Since K* is cyclic, G is cyclic. Suppose G = g.
Recall: distinct m,m’E s.t. xm = xm’ in K. So,
g(x)m = g(xm) = g(xm’) = g(x)m’.
Thus, m = m’ (mod |G|).
But |G| > |S| > m,m’. Contradiction.
Another Way [Kalai,Sahai,Sudan] : Another Way [Kalai,Sahai,Sudan] As before, distinct m,m’E s.t. xm = xm’ in K.
For any fS,
f(x)m = f(xm) = f(xm’) = f(x)m’.
So, f is a root of the polynomial
Q(z) = zm - zm’ K[z]
But deg(Q) = max(m,m’) < |S|. Contradiction.
Another Way [Kalai,Sahai,Sudan] : Another Way [Kalai,Sahai,Sudan] As before, distinct m,m’E s.t. xm = xm’ in K.
For any fS,
f(x)m = f(xm) = f(xm’) = f(x)m’.
So, f is a root of the polynomial
Q(z) = zm - zm’ K[z]
But deg(Q) = max(m,m’) < |S|. Contradiction.
Another Way [Kalai,Sahai,Sudan] : Another Way [Kalai,Sahai,Sudan] As before, distinct m,m’E s.t. xm = xm’ in K.
For any fS,
f(x)m = f(xm) = f(xm’) = f(x)m’.
So, f is a root of the polynomial
Q(z) = zm - zm’ K[z]
But deg(Q) = max(m,m’) < |S|. Contradiction.
That’s All, Folks : That’s All, Folks “This is highly unlikely. It will only be a matter of time before somebody finds a flaw in the paper. I suppose I will give it a bash.”
-- Slashdot comment, Aug 7, 05:37
What do you think?