Transcription

1 15 2

2 Fermat Solovay-Strassen Miller-Rabin Lucas-Lehmer Frobenius-Grantham Proth-Pocklington-Lehmer-Selfridge(PPLS) Kraitchik-Lehmer Elliptic Curve Primality Proving (ECPP) Cohen-Lenstra Agrawal-Kayal-Saxena-Lenstra(AKSL) AKS Random Choice Incremental Search FIPS DSS Shawe-Taylor Maurer

3 Miller-Rabin RSA DSA ANSI FIPS CRYPTREC CMVP

4 RSA. DSA.. RSA. e-japan. RSA RSA 3 4 PC. RSA. 1.2 URL R. Crandall C. Pomerance [19] H. C. Williams [69]. ANSI RSA DSA 4

5 , 1. n, Cond i ( i =1, 2,...)..,, Cond i. 1. 1, t Cond i, probable prime ( ). n Cond i ( n. Cond i ). ( ) n (false witness) ([23]. [43] liar. ). 1, (1) (c pp) ( probable prime 1 probable prime,. 5

6 1 n, t probable prime composite 1: for i =1tot do 2: if n i Cond i then 3: composite. 4: end if 5: end for 6:,, probable prime. ), (2) ( ). [ ] n probable prime (c pp) := Prob n (1) ( { }) n max (2) n: Cond i, (2) (c pp), (c pp), (2), ( ) (c pp)., (1), (2) ( ) Fermat (F ) [3, 35, 43] 2.3 Solovay-Strassen (SS ) [35, 43, 65] 2.4 Miller-Rabin (MR ) [4, 7, 23, 35, 43, 46, 47, 59] 2.5 Lucas-Lehmer (LL ) [4, 5, 8, 19, 54, 55, 56, 60] 2.6 Frobenius-Grantham (FG ) [4, 29, 30, 51, 55] 1: Fermat Fermat 1 n, 1 a<n a ( gcd(a, n) 1) a n 1 1 mod n (3). 6

7 , Fermat., a Cond i 1 Fermat.,, O((log n) 3 ),. 1 n, (3) a(1 a<n) (Fermat-)., n a (Fermat-). n FW(n), #FW(n) ( # ). 2, Fermat n. 2 ([3]) n, #FW(n) =ϕ(n) n. ϕ(n) a (1 a<n,gcd(a, n) 1)., Fermat (2) (c pp),. n Carmichael., 561 = Carmichael. Fermat,,,. 2.3 Solovay-Strassen Fermat Carmichael Solovay-Strassen. Solovay-Strassen, (Euler ). 3 n, 1 a<n a ( gcd(a, n) 1), ( a a (n 1)/2 mod n (4) n). ( a n) Jacobi. ( ) a n p, Jacobi p / a, x 2 a mod p 1 x<p p 1, 1, p a 0. n = p e i i, ( ) ( ) ei ( a n = a p i. Jacobi a n) (1 a<n), O((log n) 3 ) ([35] )., 2.1 Cond i, a 3, 1. 7

8 FWs(n) FWe(n) FW(n) 1: ([43] ) 2 n, (4) a (1 a n, gcd(a, n) 1) Euler-., n a Euler-. n Euler- FW e (n)., n, #FWe(n) ϕ(n) 1, t a Solovay- 2 Strassen (c pp) ( 1 2) t ([35] )., n, FW e (n) FW(n) ([35, 43], 1 ) Solovay-Strassen Fermat., Solovay-Strassen Miller-Rabin. 2.4 Miller-Rabin Miller-Rabin. 4 n, n 1=2 s t ( t ), 1 a<n a ( gcd(a, n) 1), a t 1 mod n i (0 i<s) a t2i 1 mod n. (5) Fermat, Solovay-Strassen, a Cond i,. 3 n, (5) a (1 a n, gcd(a, n) 1) (MR- )., n a. n FW s (n)., n, #FWs 1, t a Miller- ϕ(n) 4 Rabin (c pp) ( 1 t 4) ([35] )., n, FW s (n) FW e (n) ([35, 43], 1 ). 8

9 ,,.,, Fermat.,,. Miller-Rabin ([23]), , Solovay-Strassen, Miller-Rabin (GRH),1<a<min{n, 2(log n) 2 } a probable prime ([7, 46]). 2.5 Lucas-Lehmer Lucas-Lehmer. 5 n, P, Q =P 2 4Q n / 2Q ( gcd(2q,n) 1) U n ( n ) 0 mod n (6)., U i U 0 =0,U 1 =1,U i = PU i 1 QU i 2 (i 2)., P, Q Cond i,., U n ( n ) mod n, P, Q, n, n 2 ( [4] ). [5],. 6 ([5]) n, P, Q :=P 2 4Q n / 2Q ( gcd(2q,n) 1) n ( n ) =2 s t ( t ) U t 0 mod n i (0 i<s) V 2 i t 0 mod n. (7)., U i 5, V i V 0 =2,V 1 = P, V i = PV i 1 QV i 2 (i 2). 5, 6. 4 n, n, (6) (P, Q) (1 P, Q < n, gcd(q, n) 1, P 2 4Q mod n) Lucas-., n (P, Q) Lucas-. n Lucas- FW l (n)., (6) (7), Lucas-, Lucas-, FW sl (n). 9

10 , n n, #FW sl(n) 4 (t n 15 Lucas-Lehmer (c pp) ( 4 t 15) ) [5].,, ( ), #FWs(n) ( ) (2.1 n )., Lucas-Lehmer 2.2, 2.3, 2.4. Fermat, Solovay-Strassen, Miller-Rabin FW s (n) FW e (n) FW(n).,, Miller-Rabin., Lucas-Lehmer,., , P, Q Lucas-Lehmer ([56] )., 2 Lucas.,, Miller-Rabin Lucas-Lehmer., ANSI X9.80[4], Miller-Rabin, Lucas-Lehmer 1., 5 2 3, 2, (P, Q) =(1, 1) Lucas ([54] ). 2.6 Frobenius-Grantham Frobenius-Grantham. 7 n, f(x) F n d, gcd(f(0),n) 1. f 0 (X) :=f(x),f i (X) := gcd(x ni X, f i 1 (X)),f i (X) := f i 1 (X)/F i (X) (1 i d), i (1 i d), n i 1=2 r s, F i,0 (X) := gcd(f i (X),X s 1),F i,j (X) := gcd(f i (X),X 2j 1s +1) (1 j i), S := 2 i., deg(f i (X)) i f d (X) =1 i deg(f i (X)) (1 i d) (8) F i (X) F i (X n ) (2 i d) (9) ( 1) S = ( ) n (Jacobi ) (10) r j=0 F i,j(x) =F i (X) i deg(f i,j (X)) (0 j i) (11), f(x) 7 (8), (9), (10) Cond i Frobenius-Grantham, Cond i (11) Frobenius-Grantham. [29], d =2 Frobenius-Grantham 2 Frobenius ( [29] )., ANSI X9.80[4], d =2 f(x). 10

11 (d = 2), 1 f(x), 1 Miller-Rabin 3 ([29] )., [51], Miller-Rabin n, M(n) = (P, Q) Z 2 ( 0 P, Q ) < n, P 2 +4Q n = 1 ( Q n ) =1 1 < gcd(p 2 +4Q, n) <n 1 < gcd(q, n) <n, (8) (11) (P, Q) M(n)( 2 f(x) =X 2 PX Q) Frobenius-., n (P, Q)( 2 f(x) =X 2 PX Q) Frobenius-. n Frobenius- FW sf (n). Frobenius-Grantham, #FW sf, t #M(n) Frobenius-Grantham (c pp) (1/7710) t , 3 Miller-Rabin (c pp) 1/4 3 =1/64., 1 f(x), , 2 f(x) Frobenius, Lucas ([30] ), ,., Frobenius-Grantham, ( 4.3.2, 5.2 )., [51], (c pp) ( [51] ) , [55]., ANSI X 9.80[4].,. n Assump, Cond,n. (12).,, 3.2, 3.6, 11

12 Cond log n ( ), 3.6, [4, 34] 3.3 Proth-Pocklington-Lehmer- Selfridge (PPLS ) [4, 19, 55] 3.4 Kraitchik-Lehmer (KL ) [4, 55, 57] 3.5 Elliptic Curve Primality Proving (ECPP ) [4, 6, 26, 37, 48, 49, 63] 3.6 Cohen-Lenstra (CL ) [1, 4, 17, 18, 44, 45, 55, 67] 3.7 Agrawal-Kayal-Saxena- Lenstra (AKSL ) [2, 10, 50, 55, 66] 3.8 AKS[2] (AKS ) [2, 32] 2: n p n 1/2, n., n,., n 1/2,.,.,, n 0.35 ([34]).,,,. 3.3 Proth-Pocklington-Lehmer-Selfridge(PPLS) PPLS n 1 n +1 ([55] ). ANSI X9.80[4], n 1. 9 n>1, a, F 1 (F 1 n 1) a n 1 = 1 mod n q F 1 gcd(a (n 1)/q 1,n) = 1 (13) 12

13 ., P, Q (gcd(q, n) =1, :=P 2 4Q ( n ) = 1) F 2 (F 2 n +1) U n+1 0 mod n q F 2 U (n 1)/q (Z/(n)) (14), F =lcm[f 1,F 2 ] >n 1/2, n. 3.1 Assump F 1 n 1,F 2 n +1, F =lcm[f 1,F 2 ] >n 1/2 F 1,F 2, Cond (13) (14)., [55], (13), (14) n 1, n +1. ANSI[4], P, Q, =5, 7, 9, 11, 13, 15, 17,..., (P, Q) =(1, 1 4 ). 3.4 Kraitchik-Lehmer Kraitchik-Lehmer, n>1, n 1. n 1 q, a, n. a n 1 1 mod n, a (n 1)/q / 1 mod n (15), Assump, n 1, Cond (15). Assump Kraitchik-Lehmer,, n 1, (15) a. [55], n ϕ(n 1) > n 2 log log n ϕ( ) 2. n, ϕ(n 1) n q (15) a, a (1 <a<n) (15) 2 log log n a. Kraitchik-Lehmer PPLS,, PPLS., [57], 10 NP( ). NP,., n 1 q a., q,., q. 10, n 13 (16)

14 , [57],. (primality certificate). 3.5 ECPP,, 3.5,., (3.5 )., [2] P ( ) (3.7 ). 3.5 Elliptic Curve Primality Proving (ECPP),. n a, b Z (0 a, b < n, 4a 3 +27b 2 / 0), E a,b Y 2 = X 3 + ax + b. E a,b (n) (17) (x, y) F n O ( )., [6, 26, 37, 55],., M P =(x, y) E a,b (n), MP P M P } {{ P } M., ([26] ). 11 gcd(n, 6) = 1 n Z >1 gcd(4a 3 +27b 2,n)=1 a, b Z, P =(x, y) (Z/nZ) 2 y 2 x 3 + ax + b mod n., F Z F>(n 1/4 +1) 2. n n, P., FP, F q (F/q)P n,, n. FP = O, F q (F/q)P O (17) 10 (15) 11 (17) (15), (17).,. 11 (12), Assump, ( ) a, b ( P ) F, Cond (17). 14

15 3.4 n, n 1 Assump, ECPP F. F, 11 F = q., 11 F>(n 1/4 +1) 2 (17), E a,b (n), [63]., 3.4 ((17) ), ( ). 11 (Goldwasser-Kilian )ECPP, [26],, log n 1 O(2 log n1/ log log log n ) ( ). [63], [6] O((log n) 6+ɛ )(, ɛ ) ([37] ). [48], DEC 3000 (125 MHz), , 68.53, Cohen-Lenstra Cohen-Lenstra,, 12.,. p, q p k q 1, χ q,p : F q Q[ζ p k] χ q,p(f q )=< ζ p k >., a, b ab(a + b) / 0 mod p (a + b) p / a p + b p mod p 2 ( a, b )., J(χ a q,p,χb q,p ). q 1 J(χ a q,p,χ b q,p) := χ a q,p(y)χ b q,p(1 y) y=0, Q(ζ p k)/q G =Gal(Q(ζ p k)/q) Z[G] α., n (> 1), y Q, [y] y. p k [ ] nx α = σx 1 Z[G] x=1,p / x p k, σ x G, σ x : ζ p k ζ x p. k, ( ) E p E a p > 0. t := 2 p E pap, s := q,q 1 t qvq(t)+1 (v q q ) s>n 1/2. 15

16 12 ([67]) 4, n,. 1. s q q (n 1)/2 ±1( mod n) 2. s q q 1 p J(χ a q,p,χb q,p )α ζ mod n. (, ζ 1 p k ). 3. s q c (q 1)/2 1 mod n c Z. 4. n r, i (0 i<t) r n i mod s 12.,, (12) Assump, Cond., 2, Solovay-Strassen. 2 log n O(log log log n),., ( ),. [1, 17, 18, 39], (cyclotomy primality proving), [45], DEC Alpha n, 23.83, 41.40, , [45] p.106 3, ECPP, ECPP [48]. H/W, H/W ECPP 9 (, [45] H/W [48] ). 3.7 Agrawal-Kayal-Saxena-Lenstra(AKSL) [2], ( ). [10]. Agrawal-Kayal-Saxena-Lenstra(AKSL).. 13 n, r. S( Z) ( ). n. 1. n a c (, a, c Z,c>1). 2. n (Z/rZ). 3. ( b b ) b, b S gcd(n, b b )=1 ϕ(r)+#s 1 4. n ϕ(r) #S 5. b S, (x + b) n = x n + b (Z/nZ)[x]/(x r 1). 16

17 , (12) Assump, Cond. s = #S, [2, 10],, Õ(rs(log n)2 ). Õ(t(n)) := O(t(n)poly(log(t(n)))). 13 r, s, r = O((log n) 6 ),s = O((log n) 4 )., r = O((log n) 2 ),s= O((log n) 2 ) ([10] ),, Õ((log n)12 ), Õ((log n)6 ). [50], 700MHz PC, 10 9, AKSL , 65., AKSL,., ( [11, 66] ).,,. 3.8 AKS [2] 6, AKS.. 1 n Z >1, r Z >0 (r / n) n. (x 1) n x n 1 mod (x r 1,n) n 2 / 1 mod r, Õ((log n)3 ) ([2]). 1, 13 S = {1}, r r / n n 2 / 1 mod r, 13 4, r. r [2, 4 log n] ([2]). [32], r 100 n 10 10, 1. ( AKSL ),,,

18 2, 3 (4.3 ) (4.4 )..,,,,, 4.2, [24] DSA Random Choice (RC ) [4, 16, 22, 23, 33] Incremental Search(IS ) [4, 12, 13] FIPS DSS [24] Shawe-Taylor (ST ) [4, 43, 64] Maurer (M ) [4, 41, 42, 43] 3: [24] Appendix 3, [20] 5.3.1, CRYPTREC 2002 [58]., [24], SHA-1 DES 2., [20], SHA-1., [20] 160 SHA-1,, NIST SHA(SHA-256, SHA-384, SHA-512) SHA , , 3 Miller-Rabin probable prime, (18) (pp c). [ (pp c) := Prob n n probable prime [9]., 2.1 (c pp) (pp c). ] (18) 18

19 [33], log n, log n α, (2) β, (19) (pp c). (pp c) (1 α)β α +(1 α)β (19), (19), (pp c)., π(x) (x ) x, π(x) x log x (x ) ( ).,, x log x.,.,. (pp c), ([12, 23], (19) α ) Random Choice Random Choice , Miller-Rabin Random Choice Miller-Rabin Random Choice k, t n (k probable prime 1: repeat 2: k n. 3: n, t Miller-Rabin. 4: until n probable prime. 5: n. 2 n (pp c) p k,t 4. 4, log 2 p k,t., [16],, (pp c) 2 80 p 600, t 2..,

20 , Miller-Rabin (pp c), [22] Frobenius-Grantham (2.6 ).,. k\t : Random Choice log 2 p k,t Incremental Search Incremental Search,, Miller-Rabin Incremental Search, 3. [13], Incremental Search 25% ([13], H/W, 10 ). 3 (pp c) q k,t,c k., [12] 4 log 2 q k,t,c k., Incremental Search log 2 q k,t,c k, 4 log 2 p k,t., [12], log 2 q k,t,c k.,, c =1,k = 100,t=1 0. q 100,1,100 1,., [12] FIPS DSS FIPS DSS[24], Miller-Rabin,,.,, 20

21 3 Miller-Rabin Incremental Search k, t ), c ( ) n (k probable prime 1: k n 0 (= n). 2: while n<n 0 + c k do 3: n, t Miller-Rabin. 4: n probable prime n. 5: n n +2. 6: end while 7: fail., Shawe-Taylor Shawe-Taylor, (13).. 14 n, n 1 q (q >n 1/2 ) a, n. a n 1 1 mod n gcd(a (n 1)/q 1,n) = 1 (20) q, 2R<q R ( ) n =1+2Rq, n, q, (20) a Z. 14 n., q 2 n., (20) a, 3.4 (16)., Shawe-Taylor. ANSI X9.80[4] [64]., Maurer 4 4 r 1/2 Shawe-Taylor., [4], q = (3.2 ), R = (R <q), n =1+2Rq = (40 )., a = , (20), 40 n. 21

22 3.5 ECPP,,., , 10 (PPLS, Kraitchik-Lehmer ) Maurer Maurer Shawe-Taylor, 14, 4, r(0.5 r 1), n, n 1 q. x R, n [1,x], r(0.5 r 1) n n 1 x r s = s(r), 1 + log r ([42])., 4(MRandom Prime) s = 1 + log r,., 0.5 r 1 r, s = s(r) = Prob[n 1 x r n R [1,x]] 1 + log r (x ) (21). 4 Maurer (M Random Prime) b Z >0 b y 1: if b<20 then 2: b,. 3: else 4: s [0, 1] (21) r (0.5 r 1) 5: q M Random Prime( r b +1) 6: R n =2Rq +1 b, (20) n, n,. 7: end if 5 5.1, 5.,., 22

23 ( ), (, 4.2 ( ) ). ( ) ( ), (c pp) (512, 1024 ) (primality certificate) 5.1, , :,,, Cohen-Lenstra, AKSL, AKS. 5.2 n ( ) log n, log n (log n) 2.,, (, AKSL, AKS, 3.7, 3.8 )., AKSL, O((log n) 2 ),. AKS, AKSL ,, 7,., 2,3., AKS, 3.8 1, 2.4 Solovay-Strassen, Miller-Rabin, AKSL 7., Fermat, Solovay-Strassen, Miller- Rabin ((c pp), (pp c) ). 23

24 F SS MR LL FG t (c pp) ( 3 + o(1))t(log 2 n)3, 1 (GRH) MR ( 3 + o(1))t(log 2 n)3, ( 1 2(log n) 5 MR 2 )t ( o(1))t(log n)3, ( 1 4 )t 2(log n) 5 (3 + o(1))t(log n) 3, ( 4 15 )t ( 9 + o(1))t(log 2 n)3, ( )t Pentium IV 1.8 GHz, 1024 ( 2 ), 70m. 1 MR 2 1 MR 4.5 6:, Lucas-Lehmer,, Miller-Rabin,, Miller-Rabin, 2.5 Miller-Rabin. Frobenius-Grantham, (c pp) Miller-Rabin, (pp c), (19)., 2.6, [22], (pp c),,,., Miller-Rabin,,. (Assump) O(n 1/2 (log n) 2 ) n 1,n , PPLS O((log n) 4 ) MR 1000 (1.8GHz 70 ) KL O((log n) 4 ) n , MR 1000 (1.8GHz 70 ) 24

25 ECPP AM O((log n) 6+ɛ ). O(2 (log n) 1 log log log n ). DEC 3000, , 68.53, O((log n) 6 ) DEC Alpha 500, c,, 41.40, CL O((log n) c log log log n ) MHz PC, Õ((log n) ). AKSL 3, Õ((log, 65 n)7 ).. Pentium IV, 1.8GHz, r 100, 1024 AKS 3 Õ((log n) ), 62. r :, ( ),,. PPLS, Kraitchik-Lehmer, 7,, ( ) ( ). ECPP, Cohen-Lenstra, [48, 45] 1998, PC 7 512, 1024.,,.,., 5.4., Cohen-Lenstra ( ), ECPP ([45]), ECPP ([48] 3.5 ). 2 [36] , (608 ) log log log 512 = ,log log log 1024 = , log log log n c log log log n, ,

26 ,, Maurer, [43], t =1 Miller-Rabin,., Maurer., Random Choice Incremental Search,. 5.3., log n ( 10 ), PC,. PPLS Kraitchik-Lehmer, PC.,,. ECPP,,, [6], ( 2 ) (, ). [49] 2244, 10M., ECPP, PC. Cohen-Lenstra, [44] 12 q, PC, [36] n 512, 1024,. PC [36], (Windows XP,), 3M 512, Cohen-Lenstra,. AKSL, ( ), 512,1024 n,. [10] 26

27 13 r (log n) 2, r (log n) 2, n 1024, r 10 6, 1024( 10 3 ),, 10 9 ( = M ) (, )., (, AKSL, 5.2 ). AKS, r, PC. 5.4, 5.2 6, 7, Miller-Rabin., Cohen-Lenstra ( ) ECPP,, [4],,., Maurer,., [43], 4.4, Miller-Rabin Miller-Rabin 8 Miller-Rabin Miller-Rabin Miller-Rabin 27

28 Miller-Rabin Miller-Rabin Miller-Rabin 4 RSA 3 Miller-Rabin RSA Miller-Rabin [61] Miller-Rabin Miller-Rabin RSA [28, 43] Sliding Window 1 Sliding Window Miller-Rabin Binary 5 5 Binary x n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) y x k mod n 1: A x 2: for i from t 2downto0do 3: A A 2 4: if k i =1then 5: A A x 6: end if 7: end for 8: A x k k 1 S M k t Binary (t 1)S + t 2 M 28

29 Binary 1 Ary [28, 43] Ary Sliding Window 6 [28, 43] 6 Sliding Window x n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) Window w y x k mod n 1: 2: x 1 x, x 2 x 2 3: for i from 1 to (2 k 1 1) do 4: x 2i+1 x 2i 1 x 2 5: end for 6: 7: A 1, i t 1 8: while i 0 do 9: if k i =0then 10: A A 2, i i 1 11: else 12: i l +1 w e l =1 k i k i 1 k l 13: A A 2i l+1 x (ki k i 1 k l ) 2 14: i l 1 15: end if 16: end while 17: A Ary Sliding Window window w window x window w window w window window n x 29

30 window Sliding Window Window w 1 Binary Miller-Rabin Miller-Rabin 2 2 Binary Binary 2 n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) y 2 k mod n 1: A 2 2: for i from t 2downto0do 3: A A 2 4: if k i =1then 5: A A 2( ) 6: end if 7: end for 8: A 1 Binary Sliding Window 2 7 Miller-Rabin 2 (Sliding Window 2 ) [61] Miller-Rabin 2 (Random Choice) 3(Incremental Search) Miller-Rabin Random Choice [13] r, 30

31 . r = R 2 D log(r 2 /D) (22) R 2 2 Miller-Rabin 1 D window 8 CPU Pentium IV 1.6 GHz C OS RedHat Linux 8.0 gcc version 3.2 -O2 GNU MP version RAM 512 MB 8: 10,000 10,000 1 CRYPTREC [58] SHA Sliding Window window window 1 Binary 9 10 window 512 window window 6 31

32 Window (m ) ( ) , , , ,192 9: y x k mod n (512 ) Window (m.) ( ) , , , , ,384 10: y x k mod n (1024 ) x x PC IC window Sliding Window Miller-Rabin 2 32

33 Miller-Rabin (m ) : 2 y 2 k mod n Miller-Rabin 512 window 5 Sliding Window 1024 window 6 Sliding Window Miller-Rabin (22) Miller-Rabin 2 Miller-Rabin1 2 2 ( 11) µ µ 12: ( ) (22) Random Choice Incremental Search Random Choice Incremental Search Random Choice 2500 Incremental Search

34 (m ) Random Choice Incremental Search : Miller-Rabin (512 bit =6) ( ) Random Choice Incremental Search : Miller-Rabin (1024 bit =3) 6.3 Miller-Rabin 15 GMP ( 8) 15 IC 15 34

35 Sliding Window Window Random Choice Kbyte Kbyte Incremental Search Kbyte Kbyte 15: Miller-Rabin ( : ) window 6.4 GNU MP version 4.1.2(GMP)[25] GMP GMP GMP Miller-Rabin mpz probab prime p() Incremental Search mpz nextprime() n Miller-Rabin (n /30) 2 Miller-Rabin GMP ( ) GMP bit : m 1024 bit : m 35

36 7 RSA DSA RSA DSA RSA RSA 2 p q n p q n RSA RSA p q n(= pq) n ( ) n p ( ) 2 [38] [40] Fermat [14] Pollard p 1 [53] Williams p +1 [68] RSA p q p q ( ) p q (Fermat ) 36

37 p 1 q 1 (p 1 ) p +1 q +1 (p +1 ) O(exp(c(log e n) 1/3 (log e log e n) 2/3 )), c=1.901 O(exp(c log e plog e log e p) (log 2 n) 2 ),c=1.414 [20] n p RSA n = pq p q 2 p 1 p +1 p 1 p +1 p p 1 p +1 [62] p 1 p +1 [62] 2 p q n = pq n n = pq (Fermat [14]) 2 Fermat CRYPTREC CRYPTREC p q 512 n = pq 1024 [20] RSA p q n(= pq) 1024 CRYPTREC Report 2001( )[20] CRYPTREC Report 2001( )[20] CRYPTREC Report 2002( ) 37

38 7.2 DSA DSA NIST [24] DSA G 6( ) G G g u = g x (x Z) x [20] G DSA Pohlig-Hellman [52] Index-Calculus [27] DSA 2 p q [24] DSA DSA p q DSA p q p 1024 q 160 p 1 q DSA [24] p 1024 p 1024 DSA DSA 7.3 p p p p 38

39 p p (p ) CRYPTREC p 160 [20] p p ANSI ANSI ANSI X 9.80 American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates [4] 8.2 FIPS NIST FIPS Digital Signature Standard (DSS) DSA Miller-Rabin SHA-1 DES 8.3 CRYPTREC e-japan CRYPTREC [21] CRYPTREC [58] 16 CRYPTREC 39

40 RSASSA-PKCS-v1 5, RSA-PSS, RSA-OAEP, RSAES-PKCS-v1 5 DSA, DH ECDSA, ECDH, PSEC-KEM 16: ( ) 7 RSA DSA CMVP 9.1 Miller-Rabin ( ) Cohen-Lenstra 40

41 Miller-Rabin Miller- Rabin CRYPTREC [58] window IC ( ) IC RAM 6 window CRYPTREC 7 RSA DSA 41

42 ( ) Miller-Rabin Solovay-Strassen AKSL AKS Miller-Rabin Miller-Rabin 9.5 Miller-Rabin Solovay-Strassen Miller-Rabin Solovay-Strassen Miller-Rabin ( ) 1 AKSL (3.7 ) AKSL AKSL [2] AKS

43 AKS Miller-Rabin Random choice Miller-Rabin Incremental search Solovay-Strassen Random choice Solovay-Strassen Incremental search AKSL Random choice AKSL Incremental search AKS Random choice AKS Incremental search Random choice Incremental search (6 ) CRYPTREC [58] AKS [2] RSA DSA CRYPTREC RSA DSA 3 3 p p RSA RSA 43

44 DSA 7 RSA DSA 7 RSA p q p q DSA p q p 1024 q 160 p 1 q 9.5 CMVP Cryptographic Module Validation Program(CMVP) 1995 NIST( ) CSE( ) CMVP FIPS FIPS / Miller-Rabin CMVP Miller-Rabin 1 Miller-Rabin Solovay-Strassen (2.3 ) ( ) 44

45 CMVP RSA DSA FIPS FIPS DSA (SHA-1) SHA-1 10 Miller-Rabin Miller-Rabin ( ) AKSL AKS AKSL AKS 45

46 [1] L. M. Adleman, C. Pomerance and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. Math. 117 (1983), [2] M. Agrawal, N. Kayal, N. Saxena, Primes is in P, preprint, available at http: // [3] W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 140 (1994), [4] ANSI X 9.80, American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates, American National Standard Institute, [5] F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Math. Comp. 66 (1997), [6] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), [7] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 35 (1990), [8] R. Bailie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), [9] P. Beauchemin, G. Brassard, C. Crepeau, C. Goutier and C. Pomerance, The generation of random numbers that are probably prime, Journal of Cryptology 1 (1988), [10] D. J. Bernstein, An exposition of the Agrawal-Kayal-Saxena primality-proving theorem, preprint. [11] P. Berrizbeitia, Sharpening Primes is in P for a large family of numbers, preprint, available at [12] J. Brandt, I. Damgard, On generation of probable primes by incremental search, CRYPTO 92 (1992), LNCS 740, [13] J. Brandt, I. Damgard and P. Landrock, Speeding up prime number generation, ASIACRYPT 91 (1991), LNCS 739, [14] J. Brillhart, Fermat s factoring method and its variants, Congressus Numberantium, vol. 32, (1981),

47 [15] J. Brillhart, D. H. Lehmer, J. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of bn 1 for b = 2,3,5,6,7,10,11,12 up to high powers, Contemporary Mathematics, vol. 22, American Mathematical Society, Second Edition, [16] R. J. Burthe, Jr., Further investigations with the strong probable prime test, Math. Comp. 65 (1996), [17] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), [18] H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), [19] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, [20] CRYPTREC Report 2001 ( ), (IPA) (TAO). [21] IPA, TAO, CRYPTREC, enc/cryptrec/ [22] I. Damgard, G. S. Frandsen, An extended quadratic Frobenius primality test withaverage case error estimates, BRICS Report, RS-01-45, Univ. of Aarhus, Denmark, [23] I. Damgard, P. Landrock and C. Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), [24] FIPS 186-2, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, U.S. Department of Commerce/ N.I.S.T., January [25] GNU MP home page, [26] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC. (1986), [27] D. M. Gordon, Discrete logarithm in GF (p) using the number field sieve, SIAM Journal on Discrete Math., vol. 6 (1993), [28] D. M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, vol. 27, (1998), [29] J. Grantham, A probable prime test with high confidence, Journal of Number Theory 72 (1998),

48 [30] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), [31] J. Grantham, There are infinitely many Perrin pseudoprimes, preprint, available at [32] N. Kayal, N. Saxena, Towards a deterministic polynomial-time primality test, Technical Report, IIT Kanpur, 2002, available at research/btp2001/primality.html. [33] S. -H. Kim and C. Pomerance, The probability that a random probable prime is composite, Math. Comp. 61 (1989), [34] D. E. Knuthand L. T. Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci., 3 (1976), [35] N. Koblitz, A Course in Number Theory and Cryptography, GTM 114, Springer Verlag, Second Edition, [36] Y. Kida, Cohen-Lenstra method UBASIC program, available at rkmath.rikkyo.ac.jp/~kida/ubasic.htm. [37] A. K. Lenstra and H. W. Lenstra, Jr, Algorithms in number theory, J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Elsevier Science Publishers, 1990, [38] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The number field sieve, Proc. 22nd STOC, (1990), [39] H. W. Lenstra, Jr, Primality testing algorithms (after Adleman, Rumely and Williams), Séminaire Bourbaki 33 (1980/1981), no. 576, LNM Vol. 901, Springer. 1981, [40] H. W. Lenstra, Jr., Factoring integers withelliptic curves, Ann. Math., vol. 126, (1987), [41] U. Maurer, Some number-theoretic conjectures and their relation to the generation of cryptographic primes, C. Mitchell. Editor, Cryptography and Coging II, volume 33 of Institute of Mathematics & Its Applications (IMA), , Clarendon Press, [42] U. Maurer, Fast generation of prime numbers and secure public-key cryptographic parameters, Journal of Cryptology 8 (1995), [43] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC press,

49 [44] P. Mihăilescu, Cyclotomy of rings and primality testing, dissertation 12278, ETH Zürich, 1997 available at [45] P. Mihăilescu, Cyclotomy primality proving - recent developments, ANTS III, LNCS Vol. 1423, Springer. 1998, [46] G. L. Miller, Riemann s hypothesis and tests for primality, Journal of Computer and System Sciences, 13 (1976), [47] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci., 12 (1980), [48] F. Morain, Primality proving using elliptic curves: an update, ANTS III, LNCS Vol. 1423, Springer. 1998, [49] F. Morain, ECPP package, available at polytechnique.fr/labo/francois.morain/prgms/ecpp.english.html. [50] F. Morain, Primalite theorique et primalite pratique ou AKS vs. ECPP, available at Francois.Morain/aks-f.pdf [51] S. Müller, A probable prime test withvery highconfidence for n 1 mod 4, ASIACRYPT 2001 (2001), LNCS 2248, [52] S. C. Pohlig, M. E. Hellman, An improved algorithm for computing logarithm over GF (p) and its Cryptographic Significance, IEEE Trans. Information Theory, IT-24, No. 1, (1978), [53] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambr. Philos. Soc, vol. 76, 1974, [54] C. Pomerance, Are there counter-examples to the Baillie-PSW primality test, Letter to A. Lenstra, available at [55] C. Pomerance, Primality testing: variations on a theme of Lucas, to appear in the proceedings of an MSRI workshop, J. Buhler and P. Stevenhagen, eds. available at [56] C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to , Math. Comp. 35 (1980), [57] V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput., 4 (1975), [58], , 5.html. 49

50 [59] M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), [60] P. Ribenboim, The Book of Prime Number Records, Springer Verlag, Second Edition, [61] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, Second Edition, [62] R. L. Rivest, R. D. Silverman, Are strong primes needed for RSA?, Cryptology eprint Archive, Report 2001/007, (2001), available at [63] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44, 1985, [64] J. Shawe-Taylor, Generating strong primes, Electronics Letters 22 (July 31, 1986), [65] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput., 6 (1977), 84-85, Erratum in 7 (1978), 118. [66] J. F. Voloch, Improvements to AKS, preprint, available at utexas.edu/users/voloch/preprint.html. [67] L. C. Washington, Introduction to Cyclotomic Fields, GTM 83, Springer Verlag, Second Edition, [68] H. C. Williams, A p + 1 method of factoring, Math. Comp., vol. 39, No. 159, (1982), [69] H. C. Williams, Edouard Lucas and Primality Testing, Can. Math. Soc. series of monographs and advanced text, Wiley-Interscience,