Transcript f07
Analyzing and Testing
justified Prime Numbers
Concrete Mathematics
Final Presentation
20032047 Jeong-Kyu YANG
20032003 Seok-Kyu Kang
OUTLINE
Introduction
The Primality Testing Algorithms
Probabilistic Algorithms
Deterministic Algorithms
Analyzing
Solovay-Strassen Algorithm
Miller-Rabin Algorithm
AKS Algorithm
Implements & Experiments
Conclusion & Future Works
References
Information Security Group
2
Introduction
What is Prime Number & Primality Testing?
Prime Number
Primality Test
The importance of testing primality
Applications in cryptography
RSA, etc. uses primality testing algorithm in the part of key generation.
How fast and efficient?
Brief History
200 BC: Eratosthenes Sieve
1976: NP(Nondeterministic Polynomial-time), Pratt
1977: coRP(Complementary Randomized Polynomial-time), Solovay
and Strassen
1987: RP(Randomized Polynomial-time), adleman and Huang
1992: UP(Unambiguous Polynomial-time), Fellows and Koblitz
2002: PRIMES is in P(Polynomial-time), Agrawal et al.
Information Security Group
3
The Primality Testing Algorithms
Probabilistic Algorithms
Lehamann-Peralta
Solovay-Strassen
Miller-Rabin
Deterministic Algorithms
Eratosthenes Sieve
Euclidean algorithm
gcd( p1 p2 pr , n) 1 n is not prime
Fermat’s Theorem
n : prime if (b, n) 1, then b n1 1 mod n
Wilson’s Theorem
n : prime (n 1)! 1 mod n
AKS
Information Security Group
4
Analyzing of Solovay-Strassen
Probabilistic Algorithms
Solovay-Strassen Algorithm (Cont.)
Based on Euler Pseudoprime
If N P1P 2 Pn, ( N ) ( P1 1)( P 2 1) ( Pn 1)
and GCD(a, N ) 1, then a ( N ) 1 mod N .
More effective than the simpler Fermat’s test
If P is a prime number and GCD(a, P) 1, then a P 1 1mod P.
A number N called an Euler Pseudoprime to base b,
if b(N-1)/2 =(b/N) (mod N).
((b/N) is the Jacobi symbol)
Legendre symbol, L(a,P) =
Information Security Group
0, a divides P
1, a is quadratic residue mod P
- 1, a is a nonquadrat ic residue mod P
5
Analyzing of Solovay-Strassen
Probabilistic Algorithms
Solovay-Strassen Algorithm
Input:an odd integern 3 and parameter t 1
Legendre’s
symbol, L(a, n)
Output :"Prime" or "Composite"
1. For 1 from to t do the following
1.1 Choose a random integera,2 a n 2
1.2 Compute
r a ( n 1) / 2 mod n
1.3 Ifr 1 and r 1 then return("Composite" )
a
the Jacobi symbol s
n
1.5 Ifr s (mod n) then return("Composite" )
1.4 Compute
Jacobi’s
symbol, J(a,n)
is generalized
from
Legendre’s
symbol, L(a, n)
2. Return("Prime" )
Information Security Group
6
Analyzing of Miller-Rabin
Probabilistic Algorithms
Miller-Rabin Algorithm (Cont.)
More efficient than Solovay-Strassen Algorithm
Emerged by Miller in 1976, modified by Rabin in 1980
Definitely correct if it returns COMPOSITE, input a maybe
a pseudoprime if it returns PRIME
The probability of Miller-Rabin is not greater than (1/4)s
Strong primality test of pseudoprime
Information Security Group
7
Analyzing of Miller-Rabin
Probabilistic Algorithms
Miller-Rabin Algorithm
Let bk bk 1 b0 be the binaryrepresentationof (n-1)
1 .d 1
2. For i k down to 0
2.1 do x d
2.2 d (d d ) mod n
2.3 Ifd 1 and x 1 and x n-1 then
return“Composite ”
Reducing the
probability of
misjudgment
Reducing the
probability of
misjudgment
2.4 If bi 1 then d (d a) mod n
2.5 Ifd 1 then return“Composite ”
2.6 Return “Prime”
Information Security Group
8
Analyzing of AKS
Deterministic Algorithm
AKS Algorithm
By Manindra Agrawal, Neeraj Kyal and Nitin Saxena
August 2002
Always returns right answer
Works in polynomial time
Basic Idea
(x – a)n ≡ xn – a (mod n)
» a, n: relatively prime
» if n is prime: true
» if n is composite: false
Compare n coefficients – O(n) = O(2lg n)
Information Security Group
9
Analyzing of AKS
Deterministic Algorithm
AKS Algorithm
Find Useful
Prime
Brute force can
be used
Set of congruence
Information Security Group
10
Analyzing of AKS
Deterministic Algorithm
AKS Algorithm
Filter 1
Filter 2
Filter 3
Information Security Group
11
Analyzing of AKS
Complexity
Filter 1: O(log n)3
Filter 2: O(log n)3
Filter 3:
Computation: ai mod n=0 for all 0<i<n.
Using square and multiply method requires O(log n)
multiplications of polynomials of degree smaller than r
Multiplication of 2 such polynomials, takes O(r2)
operations in Z/nZ, whereas, multiplication in Z/nZ is
O(log n)2 additions.
Then the for loop requires
O(s* r2*log n*(log n)2)=O(2sqrt r log n* r2*log n*(log n)2),
r is O((log n)6) => O((log n)19)
O((log n)12f(log log n)), where f is a polynomial function
Information Security Group
12
Implementations – SS, MR and AKS
Environment
Hardware
Pentium III 550mhz, 384 RAM
Language: Java (j2sdk1.4.0_02), Boland Jbuilder 6.0
The way to implement
Solovay-Strassen & Miller-Rabin
Run simultaneously with a same random number generator
Same iterations to check better performance
Same bit lengths
Demo Program-1
AKS
Testing with far smaller lengths (Long integer operation is for further
works)
Testing for polynomial time of AKS
Demo Program-2, Program-3
Information Security Group
13
Experiments - Probabilistic
Comparison of primality between Solovay-Strassen and Miller-Rabin
[Testing the Extracted Prime Number
4
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
Solovay Strassen
Miller-Rabin
Extracting Mean Time
Number of Prime
[Tesing the Extracted Prime Number]
3.5
Solovay Strassen
Miller-Rabin
3
2.5
2
1.5
1
0.5
0
50
100 150 200 500 1000 1500 2000
Bit Length
Information Security Group
50
100
150
200
500 1000 1500 2000
Bit Length
14
Experiments - Deterministic
Testing for polynomial time of AKS
Limitations: with no memory fluctuation
[Poly nominal Time of AKS
35000
CPU Time(ms)
30000
25000
20000
15000
10000
5000
975
921
867
813
759
705
651
597
543
489
435
381
327
273
219
165
111
57
3
0
Odd Integer
n = 524287
powerTest output: r=23159, s=5784
polyTest: each “for-loop” iteration of the for-loop takes about 355sec
(about 6mins). So, overall runtime is 6mins*5784 (value of s in this
case), which is about 34704mins = 578.4hours = 24 days!!!
Solovay-Strassen & Miller-Rabin: less than 1 sec.
Information Security Group
15
Experiments – Comparison
Primality Comparisons among tree algorithms
Limitations
The range of Positive Odd Integers: 3 ~ 499
Iterations: 130 (SS & MR also has 50 iterations internally)
[Comparis on of Primality ]
AKS
Solovay -Stras s en
Miller-Rabin
No. of Explicited Prime
115
110
105
100
95
90
127
118
109
100
91
82
73
64
55
46
37
28
19
10
1
85
Iteration
Information Security Group
16
Conclusion
The importance of strong & very big prime numbers from the
experiments of this project
Miller-Rabin has better performance than Solovay-Strassen
However, two algorithms probably declare lots of pseudoprimes
AKS is a breakthrough result
Always declares real primes
Solves a long-standing theoretical problem
AKS has no practical relevance
Prohibitively slow runtimes
Not likely to change any time soon
Polynomial computations are just too inefficient
Theoretically correctness V.S. practical efficiency?
Depend on purposes
Information Security Group
17
Future Works
More analysis of complexity for each algorithms
Further Experiments for AKS
Find useful prime numbers and analyze its characteristics
Further Implementation for AKS
Try to get over inefficiency of AKS Algorithm
Improving to handle very long integers
Continue to compare results of each algorithms
Information Security Group
18
References
[1] M.Agrawal, N.Kayal and N.Saxena, “PRIMES is in P”, August 6,
2002
[2] William Stallings, “Cryptography and Network security”, second
edition. Prentice Hall, 1998
[3] J.Menezes, C.vaz Oorschot and A.Vanstone, “Handbook of
Applied Cryptography” CRC,1977
[4] Takeshi Aoyama, “Polynomial Time Primality Testing Algorithm”, 2003
[5] Frontline. “Volume19-Issue 17”, August 17-30.2002
[6] http://www.javastudy.co.kr/docs/techtips/020821.html
[7] http://www-fs.informatik.uni-uebingen.de/~reinhard/krypto/primzt.html
[8] http://www.cse.iitk.ac.in/news/primality.html
[9] http://random.mat.sbg.ac.at/generators/
Information Security Group
19