Introduction to the AKS Primality Test

A presentation I gave as a part of the Theory Seminar Group

1. The AKS Primality Test Pranshu Bhatnagar Chennai Mathematical Institute Indraprastha Institute of Information Technology 11 th June 2015

2. Introduction to Primality Testing Goal: given an integer n > 1, determine whether n is prime Most people know the smallest primes 2, 3, 5, 7, 11, 13, 17, 19, 23, … What about: 38,476? No, because it is even 4,359? No, because the sum of the digits is 21, a multiple of 3 127? Yes, because it does not have any factors < √127 ≈ 11.27 2 57,885,161  − 1? This has over 17 million digits. We need better tests… <number>

3. 3 Categories For some arithmetic statement S which is easy to check: n is prime ⇒ S(n) pseudoprimes strong pseudoprimes S(n) ⇒ n is prime n-1 test (Lucas Theorem) n+1 test (Lucas-Lehmer) S(n) ⇔ n is prime AKS test 3

4. n is prime ⇒ S(n) S(n): n = 2 or n is odd S(n): n = 3 or sum of digits of n is not divisible by 3 ¬ S(n) ⇒ n is composite S(n) ⇒ ? 5

5. Pseudoprimes n prime ⇒ S(n) S-pseudoprime: n is composite but S(n) holds S(n): n = 2 or n is odd n = 15 is a pseudoprime 7

6. Intro to Modular Arithmetic a ≡ b (mod n) Formally n|(a-b) a/n leaves remainder b Clocks keep time (mod 12) 16:30 (military time) ≡ 4:30 pm 8:00 am + 7 hours = 15:00 ≡ 3 pm Subtract the modulus until the result is small enough 11 ≡ 4 (mod 7) 35 ≡ 0 (mod 5) 2 3 = 8 ≡ 2 (mod 3) 11

7. Fermat Pseudoprimes n prime ⇒ S(n) S is based on Fermat’s Little Theorem: If n is prime then a n ≡ a (mod n), ∀a∈ℤ S(n): a n ≡ a (mod n) Fermat pseudoprime: n is composite but a n ≡ a (mod n) for some a 13

8. Examples n prime ⇒ a n ≡ a (mod n) Let n = 91 Composite: 91 = 7 * 13 3 91 ≡ 3 (mod 91) 91 is a Fermat pseudoprime base 3 2 91 ≠ 2 (mod 91) 91 is not a Fermat pseudoprime base 2 (91 is composite) Note: Most probably, ∃ infinite Carmichael numbers, composites with a n ≡ a (mod n) for every a 17

9. S(n) ⇒ n is prime n is composite ⇒ ¬ S(n) ¬ S(n) ⇒ ? 1 <number>

10. The n-1 Test S is based on the Lucas Theorem: If a n-1 ≡ 1 (mod n) but a (n-1)/q ≠ 1 (mod n) ∀ prime q|n-1, then n is prime (for some a∈ℤ) S(n): a n-1 ≡ 1 (mod n) but a (n-1)/q ≠ 1 (mod n) 23

11. Example [a n-1 ≡ 1 (mod n) but a (n-1)/q ≠ 1 (mod n)] ⇒ n prime Let n = 19 n-1 = 18 = 2 * 3 2 Let a = 2 2 18 ≡ 1 (mod 19) 2 9 ≡ 18 (mod 19) 2 6 ≡ 7 (mod 19) So 19 is prime 29

12. Another Example [a n-1 ≡ 1 (mod n) but a (n-1)/q ≠ 1 (mod n)] ⇒ n prime S(n) ⇒ n is prime ¬ S(n) ⇒ ? Let n = 13, a = 5 n-1 = 12 = 2 2 * 3 5 12 ≡ 1 (mod 13) 5 6 ≡ 12 (mod 13) But 5 4 ≡ 1 (mod 13) S(n) is false, but n = 13 is prime 31

13. S(n) ⇔ n is prime S(n) ⇒ n is prime ¬ S(n) ⇒ n is composite Theorem: Given some a with gcd(a,n) = 1: n is prime iff (x + a) n ≡ x n + a (mod n) S(n): (x + a) n ≡ x n + a (mod n) 37

14. Example S(n): (x + a) n ≡ x n + a (mod n) (x+4) 7 = x 7 + 28x 6 + 336x 5 + 2240x 4 + 8960x 3 + 21504x 2 + 28672x + 16384 ≡ x 7 + 4 (mod 7) 7 is prime (x+3) 4 = x 4 + 12x 3 + 54x 2 + 108x + 81 ≡ x 4 + 2x 2 + 1 (mod 4) ≠ x 4 + 3 4 is composite 41

15. Improvement: The AKS Theorem Agrawal-Kayal-Saxena (AKS) Theorem: n is prime iff n is not a power, n has no small factors, (x + a) n ≡ x n + a (mod n, x r - 1) for certain r and small values of a 43

16. The AKS Algorithm 47 Input: n ≥ 1 STEP 1. If ∃a, b > 1 ∈ N such that n = a b , then Output COMPOSITE; STEP 2. Find the minimal r ∈ N such that o r (n) > log 2 (n); STEP 3. For a = 1 to r do if 1 < (a, n) < n, then Output COMPOSITE; STEP 4. if r ≥ n, then Output PRIME ; STEP 5. For a = 1 to do if (x + a) n ≡ x n + a (mod x r − 1, n), then Output COMPOSITE; STEP 6. Output PRIME;

17. Proof Of Correctness

18. n is prime ⇒ S(n) n is certainly not of the form a b for any a, b > 1, so STEP 1 will not output COMPOSITE. Since n is prime, we also know that ∀x ∈ N, (n, x) = 1 or n. Hence STEP 3 will not output composite either. We have seen that for any prime n, (x+a) n ≡ x n +a (mod n), so STEP 5 will not output COMPOSITE. Therefore the algorithm will output PRIME

19. S(n) ⇒ n is prime If the algorithm returns PRIME during STEP 4, then we know that ∀m < n, (m, n) = 1 (this was checked in STEP 3), meaning n is prime. The remaining case, in which the algorithm returns PRIME during STEP 6, will take considerably more effort and require some extra machinery.

20. Runtime Analysis

21. Notation

22. Basic Operations Let n, m ∈ N. Then Computing m + n takes O(||n|| + ||m||) = O(log(n) + log(m)) bit operations. Computing m · n takes O(||n|| · ||m||) = O(log(n) · log(m)) bit operations. Computing the quotient n div m and the remainder n mod m takes O((||n|| −||m|| + 1) · ||m||) bit operations.

23. Basic Operations Let m, n ∈ N with at most k bits each. Then: m and n can be multiplied with O(k(log(k))(loglogk)) = O ~ (k) bit operations. n div m and n mod m can be computed using O(k(log(k))(log logk)) = O ~ (k) bit operations. Multiplication of two polynomials of degree d with coefficients at most m bits in size can be done in O ~ (d · m) bit operations.

24. Euclidean Algorithm Input: m, n ∈ Z 0: a, b integer; 1: if |n| ≥ |m| 2: then a ← |n|; b ← |m|; 3: else b ← |m|; a ← |n|; 4: while b > 0 repeat 5: (a, b) ← (b, a mod b); //i.e., a i = b i−1 , b i = a i−1 mod b i−1 6: return a; This algorithm runs in O(log(n) · log(m)).

25. Fast Modular Exponentiation Let n = 2 a 1 + 2 a 2 + · · · + 2 a l where a 1 > a 2 > · · · > a l . Define f := (x + a), f i+1 (x) = f i (x) 2 (mod x r − 1, n). Then f aj (x) = (x + a) aj . If we further define g 1 (x) := f a1 (x) and g k (x)≡g k−1 (x) f k (x) (mod x r − 1, n), then we see that g l (x) ≡ (x + a) 2a 1 +···+2a l = (x + a) n (mod x r − 1, n). We have therefore computed (x + a) n (mod x r − 1, n) in a 1 + l ≤ 2log(n) steps, where a step consists of multiplying two polynomials of degree less than r with coefficients in Z/nZ. This leads to a total runtime of O ∼ (r·log 2 (n)).

26. Perfect power Test Input : n ∈ N 0: a, b, c, m integer 1: b ← 2 2: while (b ≤ log(n)) do 3: a=1;c=m; 4: while c − a ≥ 2 do 5: m ← (a + c) div 2; 6: p ← min {m b , 1}; 7: if p = n then return "n is a perfect power"; 8: if p < n then a ← m else c ← m; 9: b ← b + 1; 10: return "n is not a perfect power." Loop 1 will run at most log(n) times. Also, it will take at most log(n) iterations of loop 2 before |c − a| ≤ 1. During each iteration of loop 2, we calculate (a + c) div 2 and m b , which can be done in O ~ (log(n)) bit operations. The complexity of the entire algorithm is therefore O ∼ (log 3 (n)).

27. Overall STEP 1 At most O ∼ (log 3 (n)) bit operations. STEP 2 We know that there exists an r< log 5 (n) such that o r (n) > log 2 (n) .The easiest way to find such an r is simply to calculate n k (mod r) for k = 1, 2, ..., log 2 (n). This involves O(log 2 (n)) multiplications modulo r for each r, so STEP 2 takes O ∼ (log 7 (n)) bit operations. STEP 3 While determining whether (a,n)> 1 for some a ≤ r, computing each gcd takes O ∼ (log 2 (n)) bit operations using the Euclidean Algorithm, resulting in a total of O ∼ (log 7 (n)) bit operations

28. Overall STEP 5 Given a ≤ , calculating (x + a) n in the ring Z/nZ as reducing modulo x r − 1 is trivial (simply replace x s by x (s−r) ). In order to calculate (x+a) n , we must perform O(log(n)) multiplications of polynomials of degree<r with coefficients of size O(log(n)) (as the coefficients are written modulo n; recall that all polynomials are reduced modulo x r −1 during Fast Modular Exponentiation).Each congruence therefore takes O ∼ (log 7 (n)) bit operations to verify. This step therefore takes O ∼ ( log(n) log 7 (n)) = O ∼ ( log 8 (n)) = O ∼ (log 21/2 (n)) bit operations. The complexity of STEP 5 clearly dominates the complexity of the other steps, so the overall complexity of the algorithm is O ∼ (log 10.5 (n)), which is indeed polynomial.

29. Example Is n = 1993 prime? 1993 is not a power ✓ 53

30. Example Continued (Is n = 1993 prime?) (i) Find “certain r:” Really finding the least integer r > log 2 n with order of n in ℤ r * We find r = 5. (ii) Check that n has no “small factors” Really checking no factors in [2, log n * √φ(r)] = [2, log(1993)*√4] = [2, 21.92]) 2, 3, 4, 5, …, 21 are not factors ✓ Note: √1993 ≈ 44.643 – AKS checks less than half as many numbers as possible factors 59

31. Example Continued (Is n = 1993 prime?) Check (x + a) n ≡ x n + a (mod n, x r - 1) for a up to the same value (log n* √φ(r)) So for 1 ≤ a ≤ 21 check (x + a) 1993 ≡ x 1993 + a (mod 1993, x 5 - 1) ✓ Result: n = 1993 passed all 3 tests. So 1993 is prime. 61

32. Significance Determines whether n is prime or composite in polynomial time AKS Test is an iff statement If pass the test then n is definitely prime If fail the test then n is definitely composite 67

33. Work Cited Linowitz, Benjamin. An Exposition of the AKS Polynomial Time Primality Testing Stay, Michael, Primes is in P, slowly. Crandall, Richard, and Carl Pomerance.  Prime Numbers: A Computational Perspective . New York: Springer, 2005. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" 71