15 2

1 4 1.1........................... 4 1.2.............................. 4 1.3.............................. 5 2 5 2.1....................................... 5 2.2 Fermat.................................... 6 2.3 Solovay-Strassen............................... 7 2.4 Miller-Rabin................................. 8 2.5 Lucas-Lehmer................................ 9 2.6 Frobenius-Grantham............................. 10 3 11 3.1....................................... 11 3.2................................... 12 3.3 Proth-Pocklington-Lehmer-Selfridge(PPLS)................ 12 3.4 Kraitchik-Lehmer.............................. 13 3.5 Elliptic Curve Primality Proving (ECPP)................. 14 3.6 Cohen-Lenstra................................ 15 3.7 Agrawal-Kayal-Saxena-Lenstra(AKSL)................... 16 3.8 AKS.......................... 17 4 17 4.1....................................... 17 4.2................................. 18 4.3............................ 18 4.3.1................................... 18 4.3.2 Random Choice............................. 19 4.3.3 Incremental Search........................... 20 4.3.4 FIPS 186-2 DSS........................ 20 4.4............................ 21 4.4.1 Shawe-Taylor............................. 21 4.4.2 Maurer................................ 22 5 22 5.1....................................... 22 5.2................................... 23 5.3................................. 26 5.4...................................... 27 2

6 27 6.1................................... 27 6.1.1............................. 28 6.1.2 Miller-Rabin................. 30 6.1.3....................... 30 6.2..................................... 31 6.2.1.......................... 31 6.2.2 2........................ 32 6.2.3.............................. 33 6.3............................ 34 6.4......................... 35 7 36 7.1 RSA.................................... 36 7.1.1........................ 36 7.1.2................ 37 7.2 DSA.................................... 38 7.3.................................. 38 8 39 8.1 ANSI....................................... 39 8.2 FIPS....................................... 39 8.3 CRYPTREC.................................. 39 9 40 9.1............. 40 9.2................................ 41 9.3................. 41 9.4................... 42 9.4.1......................... 42 9.4.2......................... 43 9.4.3.................. 43 9.5 CMVP............................ 44 10 45 3

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

1.3 2 4 2 3 4 5 6 7 8 9 10 2 2.1, 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

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) ( ). 1. 2.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: 2 2.2 Fermat Fermat 1 n, 1 a<n a ( gcd(a, n) 1) a n 1 1 mod n (3). 6

, Fermat., a 1 2.1 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 = 3 11 17 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

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

,,.,, Fermat.,,. Miller-Rabin ([23]), 4.3.2., 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

, 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,., 25 10 9 2, 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

(d = 2), 1 f(x), 1 Miller-Rabin 3 ([29] )., [51], Miller-Rabin 4.5. 5 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 2.2 2.5., 3 Miller-Rabin (c pp) 1/4 3 =1/64., 1 f(x), 2.2 2.4, 2 f(x) Frobenius, Lucas ([30] ), 2.2 2.5,., Frobenius-Grantham, ( 4.3.2, 5.2 )., [51], (c pp) ( [51] ). 3 3.1, [55]., ANSI X 9.80[4].,. n Assump, Cond,n. (12).,, 3.2, 3.6, 11

Cond log n ( ), 3.6,. 2. 3.2 [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: 3 3.2 8 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], 3.4 10 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

., 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, 10. 10 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],. 200560490131 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)

, [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

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), 512 50 35.81, 68.53, 18.17. 3.6 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

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 500 10 200 n, 23.83, 41.40, 13.70., [45] p.106 3, ECPP, ECPP [48]. H/W, 10 160 H/W ECPP 9 (, [45] H/W [48] 2. 5.2 7 ). 3.7 Agrawal-Kayal-Saxena-Lenstra(AKSL) 2002 8 [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

, (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 6 9. 1024, 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 ),,,. 4 4.1. 17

2, 3 (4.3 ) (4.4 )..,,,,, 4.2, [24] DSA. 3. 4.3.2 Random Choice (RC ) [4, 16, 22, 23, 33] 4.3.3 Incremental Search(IS ) [4, 12, 13] 4.3.4 FIPS 186-2 DSS [24] 4.4.1 Shawe-Taylor (ST ) [4, 43, 64] 4.4.2 Maurer (M ) [4, 41, 42, 43] 3: 4 4.2 [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-1. 4.3 4.3.1, 4.3.2 4.3.3 2, 3 Miller-Rabin probable prime, (18) (pp c). [ (pp c) := Prob n n probable prime [9]., 2.1 (c pp) (pp c). ] (18) 18

[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) α ). 4.3.2 Random Choice Random Choice 2 3 1., Miller-Rabin Random Choice. 2. 2 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],, 2 600 (pp c) 2 80 p 600,2 2 82 t 2.., 6.1. 19

, Miller-Rabin (pp c), [22] Frobenius-Grantham (2.6 ).,. k\t 1 2 3 4 5 6 7 8 9 10 100 7 17 23 28 32 35 38 41 44 46 150 11 22 30 36 41 46 50 53 56 60 200 14 27 36 43 49 54 59 63 67 71 250 16 32 42 49 56 62 68 72 77 81 300 19 36 46 55 63 69 75 81 86 90 350 28 39 51 60 69 76 82 88 94 99 400 37 46 55 65 74 82 89 95 101 107 450 46 54 62 70 79 88 95 102 108 114 500 56 63 70 78 85 93 101 108 115 121 550 65 72 79 86 93 100 107 114 121 128 600 75 82 88 95 102 108 115 121 128 135 4: Random Choice log 2 p k,t 4.3.3 Incremental Search Incremental Search,, 4.3.2. 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]. 4.3.4 FIPS 186-2 DSS FIPS 186-2 DSS[24], Miller-Rabin,,.,, 20

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.,. 4.4 4.4.1 Shawe-Taylor Shawe-Taylor, 3.3 9 (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], 40. 21 q = 1832371 (3.2 ), R = 263840 (R <q), n =1+2Rq = 96690559281(40 )., a = 41767655812, (20), 40 n. 21

3.5 ECPP,,., 3.5 14 9, 10 (PPLS, Kraitchik-Lehmer ). 4.4.2 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

( ), (, 4.2 ( ) ). ( ) ( ), (c pp) (512, 1024 ) (primality certificate) 5.1, 5.2 5.1, 5.2 5.2 5.2 5.3 5.4 5.2 5.4 5:,,, 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. 5.2 6,, 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

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 ( 3 2 + 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, ( 1 7710 )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+1 1024, PPLS O((log n) 4 ) MR 1000 (1.8GHz 70 ) KL O((log n) 4 ) n 1 1024, MR 1000 (1.8GHz 70 ) 24

ECPP AM O((log n) 6+ɛ ). O(2 (log n) 1 log log log n ). DEC 3000, 512 35.81, 68.53, 18.17. O((log n) 6 ) 1024 2292 DEC Alpha 500, 10 200 23.83 c,, 41.40, 13.70 CL O((log n) c log log log n ).. 1024 455.95. 2 700MHz PC, Õ((log n) 13 10 9 ). AKSL 3, 6 9. 1024 Õ((log, 65 n)7 ).. Pentium IV, 1.8GHz, r 100, 1024 AKS 3 Õ((log n) 4 3.8 1 ), 62. r 4000 2. 7:, ( ),,. 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] 512 47, 1024 10 8 (608 ) log log log 512 = 0.604...,log log log 1024 = 0.6606..., log log log n c log log log n, 3.6933.... 3, 5.1. 25

,, 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, 1024. Cohen-Lenstra,. AKSL, ( ), 512,1024 n,. [10] 26

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

Miller-Rabin Miller-Rabin Miller-Rabin 4 RSA 3 Miller-Rabin RSA Miller-Rabin [61] Miller-Rabin 6.1.1 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

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

window Sliding Window Window w 1 Binary 6.1.2 Miller-Rabin Miller-Rabin 2 2 Binary 5 7 7 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 2 2 2 Sliding Window 2 7 Miller-Rabin 2 (Sliding Window 2 ) 6.1.3 [61] Miller-Rabin 2 (Random Choice) 3(Incremental Search) Miller-Rabin Random Choice [13] r, 30

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

Window (m ) ( ) 1 0 0 511 255.75 7.03 64 2 1 1 511 170.43 6.28 128 3 1 3 511 127.84 5.79 256 4 1 7 511 102.44 5.60 512 5 1 15 511 85.52 5.50 1,024 6 1 31 511 73.29 5.55 2,048 7 1 63 511 64.22 5.77 4,096 8 1 127 511 57.12 6.35 8,192 9: y x k mod n (512 ) Window (m.) ( ) 1 0 0 1023 511.76 45.46 128 2 1 1 1023 340.96 40.12 256 3 1 3 1023 255.98 37.42 512 4 1 7 1023 204.90 35.93 1,024 5 1 15 1023 170.84 35.08 2,048 6 1 31 1023 146.40 34.85 4,096 7 1 63 1023 128.25 35.21 8,192 8 1 127 1023 113.98 36.83 16,384 10: y x k mod n (1024 ) x x 512 1 1024 4 PC IC window 6.2.2 2 2 7 11 512 1024 Sliding Window Miller-Rabin 2 32

Miller-Rabin (m ) 512 511 256.14 4.50 1024 1023 512.07 29.11 11: 2 y 2 k mod n 6.2.3 Miller-Rabin 512 window 5 Sliding Window 1024 window 6 Sliding Window 2 2 7 Miller-Rabin (22) Miller-Rabin 2 Miller-Rabin1 2 2 ( 11) 12 512 0.609 µ 1024 1.215 µ 12: (512 1024 ) 12 11 (22) 512 1898 1024 5475 13 14 Random Choice Incremental Search 2 80 512 Random Choice Incremental Search 500 1024 Random Choice 2500 Incremental Search 4200 33

(m ) Random Choice Incremental Search 10 128.790 121.478 100 80.257 76.061 400 71.977 67.939 500 71.932 63.630 600 71.989 68.242 1000 74.677 70.447 10000 167.063 151.133 13: Miller-Rabin (512 bit =6) ( ) Random Choice Incremental Search 10 3.375 3.408 1000 1.449 1.409 2400 1.393 2500 1.391 2600 1.393 4100 1.331 4200 1.330 4300 1.333 5000 1.445 1.438 10000 1.569 1.560 14: Miller-Rabin (1024 bit =3) 6.3 Miller-Rabin 15 GMP ( 8) 15 IC 15 34

Sliding Window Window Random Choice 512 5 500 1.5 Kbyte 1024 6 2500 6.5 Kbyte Incremental Search 512 5 500 1.5 Kbyte 1024 6 4200 8.2 Kbyte 15: Miller-Rabin ( :512 6 1024 3) 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 2 2 512 GMP ( ) GMP 1 512 bit : 182.660 m 1024 bit : 1961.600 m 35

7 RSA DSA RSA DSA 3 7.1 RSA RSA 2 p q n p q n RSA RSA p q n(= pq) 7.1.1 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

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 2 7.1.2 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

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

p p (p ) CRYPTREC p 160 [20] p p 160 8 8.1 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 186-2 Digital Signature Standard (DSS) DSA 4.3.4 Miller-Rabin SHA-1 DES 8.3 CRYPTREC e-japan CRYPTREC [21] CRYPTREC 2002 11 [58] 16 CRYPTREC 39

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

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

9.1 9.4 ( ) 9.4.1 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 ) 512 3.7 AKSL AKSL [2] AKS 3.8 42

AKS 9.4.2 9.4.1 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] 9.4.3 7 RSA DSA CRYPTREC RSA DSA 3 3 p p RSA RSA 43

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 140-2 FIPS 140-2 / Miller-Rabin CMVP Miller-Rabin 1 Miller-Rabin Solovay-Strassen (2.3 ) ( ) 44

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

[1] L. M. Adleman, C. Pomerance and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. Math. 117 (1983), 173-206. [2] M. Agrawal, N. Kayal, N. Saxena, Primes is in P, preprint, available at http: //www.cse.iitk.ac.in/primality.pdf. [3] W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 140 (1994), 703-722. [4] ANSI X 9.80, American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates, American National Standard Institute, 2001. [5] F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Math. Comp. 66 (1997), 861-881. [6] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68. [7] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 35 (1990), 355-380. [8] R. Bailie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. [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), 53-64. [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 http://xxx.yukawa.kyoto-u.ac.jp/abs/math.nt/0211334. [12] J. Brandt, I. Damgard, On generation of probable primes by incremental search, CRYPTO 92 (1992), LNCS 740, 358-370. [13] J. Brandt, I. Damgard and P. Landrock, Speeding up prime number generation, ASIACRYPT 91 (1991), LNCS 739, 440-449. [14] J. Brillhart, Fermat s factoring method and its variants, Congressus Numberantium, vol. 32, (1981), 29 48. 46

[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, 1988. [16] R. J. Burthe, Jr., Further investigations with the strong probable prime test, Math. Comp. 65 (1996), 373-381. [17] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103-121. [18] H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297-330. [19] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, 2001. [20] CRYPTREC Report 2001 ( ), (IPA) (TAO). [21] IPA, TAO, CRYPTREC, http://www.ipa.go.jp/security/ 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, 2001. [23] I. Damgard, P. Landrock and C. Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), 177-194. [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 27 2000. [25] GNU MP home page, http://www.swox.com/gmp/. [26] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC. (1986), 316-329. [27] D. M. Gordon, Discrete logarithm in GF (p) using the number field sieve, SIAM Journal on Discrete Math., vol. 6 (1993), 124 138. [28] D. M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, vol. 27, (1998), 129 146. [29] J. Grantham, A probable prime test with high confidence, Journal of Number Theory 72 (1998), 32-47. 47

[30] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), 873-891. [31] J. Grantham, There are infinitely many Perrin pseudoprimes, preprint, available at http://www.pseudoprime.com/jgpapers.html. [32] N. Kayal, N. Saxena, Towards a deterministic polynomial-time primality test, Technical Report, IIT Kanpur, 2002, available at http://www.cse.iitk.ac.in/ research/btp2001/primality.html. [33] S. -H. Kim and C. Pomerance, The probability that a random probable prime is composite, Math. Comp. 61 (1989), 721-741. [34] D. E. Knuthand L. T. Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci., 3 (1976), 321-348. [35] N. Koblitz, A Course in Number Theory and Cryptography, GTM 114, Springer Verlag, Second Edition, 1994. [36] Y. Kida, Cohen-Lenstra method UBASIC program, available at http://www. 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, 674-715. [38] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The number field sieve, Proc. 22nd STOC, (1990), 564 572. [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, 243-257. [40] H. W. Lenstra, Jr., Factoring integers withelliptic curves, Ann. Math., vol. 126, (1987), 649 673. [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), 173-191, Clarendon Press, 1992. [42] U. Maurer, Fast generation of prime numbers and secure public-key cryptographic parameters, Journal of Cryptology 8 (1995), 123-155. [43] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC press, 1997. 48

[44] P. Mihăilescu, Cyclotomy of rings and primality testing, dissertation 12278, ETH Zürich, 1997 available at http://www.inf.ethz.ch/~mihailes. [45] P. Mihăilescu, Cyclotomy primality proving - recent developments, ANTS III, LNCS Vol. 1423, Springer. 1998, 95-110. [46] G. L. Miller, Riemann s hypothesis and tests for primality, Journal of Computer and System Sciences, 13 (1976), 300-317. [47] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci., 12 (1980), 97-108. [48] F. Morain, Primality proving using elliptic curves: an update, ANTS III, LNCS Vol. 1423, Springer. 1998, 111-127. [49] F. Morain, ECPP package, available at http://ultralix. polytechnique.fr/labo/francois.morain/prgms/ecpp.english.html. [50] F. Morain, Primalite theorique et primalite pratique ou AKS vs. ECPP, available at http://www.lix.polytechnique.fr/labo/ 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, 87-106. [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), 106 110. [53] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambr. Philos. Soc, vol. 76, 1974, 521 528. [54] C. Pomerance, Are there counter-examples to the Baillie-PSW primality test, Letter to A. Lenstra, available at http://www.pseudoprime.com/dopo.ps. [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 http://cm.bell-labs.com/cm/ms/who/carlp/pub.html. [56] C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25 10 9, Math. Comp. 35 (1980), 1003-1026. [57] V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput., 4 (1975), 214-220. [58], 2002.11.28, http://www.soumu.go.jp/s-news/2002/021128_ 5.html. 49

[59] M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), 128-138. [60] P. Ribenboim, The Book of Prime Number Records, Springer Verlag, Second Edition, 1989. [61] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, Second Edition, 1994. [62] R. L. Rivest, R. D. Silverman, Are strong primes needed for RSA?, Cryptology eprint Archive, Report 2001/007, (2001), available at http://eprint.iacr.org. [63] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44, 1985, 483-494. [64] J. Shawe-Taylor, Generating strong primes, Electronics Letters 22 (July 31, 1986), 875-877. [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 http://www.ma. utexas.edu/users/voloch/preprint.html. [67] L. C. Washington, Introduction to Cyclotomic Fields, GTM 83, Springer Verlag, Second Edition, 1996. [68] H. C. Williams, A p + 1 method of factoring, Math. Comp., vol. 39, No. 159, (1982), 225 234. [69] H. C. Williams, Edouard Lucas and Primality Testing, Can. Math. Soc. series of monographs and advanced text, Wiley-Interscience, 1998. 50