GENERATING LARGE PRIMES USING AKS“PRIMES Is In P”An Old Math Problem SolvedWhat is P?AKS ALGORIHTMPolynomial ComplexityAKS AlgorithmAKS AlgorithmUseful Prime rDependence on rImplementing AKSGenerating Large Pseudo-Random-NumbersProblems EncounteredTime ComplexitySpeed Of AKS In JAVAReasons For SlownessImproving AKS PerfomanceConclusionThank-youGENERATING LARGE PRIMES USING AKSby Kunjan Shah“PRIMES Is In P”An Old Math Problem SolvedS K AManindra Agrawal, Neeraj Kayal and Nitin Saxena 3 researchers of Indian Institute of Technology Kanpur.What is P?Complexity ClassesBPP RP coRP PNP ZPP UPAKSAKS ALGORIHTMIs n prime?Output: PRIMEOutput: COMPOSITEYESNOIN POLYNOMIAL TIMEPolynomial Complexity N is the prime number. C is the constant. NC=Polynomial complexity. CN= Exponential complexity. For example C=2. NC = 1,4,9,16,25,36,49,64,81,100…….COMPARE CN=2,4,8,16,32,64,128,256,512,1024AKS Algorithm1. Input: Integer n > 12. if (n has the form abwith b > 1) then output COMPOSITE;3. r := 2; 4. while (r < n) {5. if (gcd(n,r) is ≠ 1) then output COMPOSITE; 6. if (r is prime > 2) { 7. let q be the largest factor of r-1; 8. if (q > 4sqrt(r)log n) and (n(r-1)/qis not 1 (mod r)){9. break;}}10. r := r + 1;} 11. for a := 1 to 2sqrt(r)log n{12. if ( (x-a)n!≅ (xn-a) (mod xr-1,n) ) { 13. output COMPOSITE;}}14. output PRIME; Filter 1Filter 1Filter 2Filter 2Filter 3Filter 3AKS Algorithm1. Input: Integer n > 12. if (n has the form abwith b > 1) then output COMPOSITE;3. r := 2; 4. while (r < n) {5. if (gcd(n,r) is ≠ 1) then output COMPOSITE; 6. if (r is prime > 2) { 7. let q be the largest factor of r-1; 8. if (q > 4sqrt(r)log n) and (n(r-1)/qis not 1 (mod r)){9. break;}}10. r := r + 1;} 11. for a := 1 to 2sqrt(r)log n{12. if ( (x-a)n!≅ (xn-a) (mod xr-1,n) ) { 13. output COMPOSITE;}}14. output PRIME; Find rCheck set of CongruencesUseful Prime rKN=2kUseful prime R64 264262127128 21281047587256 22564192547512 2512167734791023 2102366970103Dependence on rfor a := 1 to 2sqrt(r)log n {if ( (x-a)n! ≅ (xn-a) (mod xr-1,n) ) then output COMPOSITE;}Output Prime;Note :Thus r ≃(log2n)6 assures the algorithm works in P.Old Idea(x - a)p≅(xp- a) (mod p) If and only if a and p are relatively prime and p is prime. If p is prime, then p divides the binomial coefficients pCrfor r = 1, 2, ... p-1. If p is prime and a is relatively prime to p then all coefficients of p will be divisible by p except the first term xpand last term –ap The problem is that it still takes exponential time to determine if p is prime using this test, because we have to calculate p-1 coefficients and divide all by p to see if there is a remainder. Time complexity O(n)=O(2logn)New Idea(x-a)p! ≅ (xp-a) (mod xr-1,n) "lets just look at the last r terms of (x - a)p" Three methods suggested to check this congruence : Fast Fourier Transform. Square and multiply. Use of available library or API for polynomial calculations.Implementing AKS JDK 1.4.2 Class java.math.*; Contains two class BigInteger & BigDecimal. Arbitary large but slow. BigInteger provides methods for GCD calculation, primality testing, probable prime generation.Generating Large Pseudo-Random-Numbers java.security.SecureRandom; SHA-1PRNG provided by sun packed with jdk 1.4.2 free.Problems Encountered Java does not provide power, log, mod functions over BigInteger class. Special thanks to www.optimtika.se (package org.ojalgo)Time Complexity Number of elementary operations on single processor system. Filter 1 is used to check whether n is perfect power takes O(log(n))3 time. The while loop used to find r takes O(log(n))6time. Time taken by for loop does modular computation over polynomials and takes timeO(log(n))12.Speed Of AKS In JAVAK(bits) N=2kTime1 2 0.06(secs)2 2 0.06(secs)3 7 0.09(secs)4 13 0.13(secs)5 31 0.29(secs)6 61 0.97(secs)7 127 5.57(secs)8 251 31.99(secs)9 499 206.41(secs)10 1019 1304.74(secs)64 Estimated Years128 Estimated Years256 Estimated Years516 Estimated Years1023 Estimated YearsProcessor AMD Athlon2.4 GHZRam 256 MBOS Windows XPReasons For Slowness Java can provide only one-tenth of the speed of native language. BigInteger class is arbitary slow. Java does not provide API for modular calculation over polynomials. Original AKS is slower than other Variants of AKS.Improving AKS Perfomance Use of AKS variant or using revised version of AKS. Generating Efficient version of AKS by merging good classical algorithms at different steps. Parallel processing at for loop could be targeted to reduce time. All the above mentioned ways are described in great depth with available options in paper “On the implementation of AKS-class primality tests”By R. CrandallConclusion Much importance in complexity theory as a solution but, no practical impact on cryptography. Very slow compared to other probable methods with very less probability of error and even more slow in java. Still new and maturing. With efficient implementation with less complexity and available support in libraries it could become practical solution.Thank-you
View Full Document
Unlocking...