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 n1  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