200 Miller-Rabin 2002 3 Rabin-Solovay-Strassen self-contained RSA RSA RSA ( ) Shor 996 2 RSA RSA Solovay-Strassen Miller-Rabin [3, pp. 8 84] Rabin-Solovay-Strassen 2 Miller-Rabin 3 4 Miller-Rabin 5 Miller-Rabin
2 Miller-Rabin Miller-Rabin n 0 < b < n b Miller-Rabin. n < b < n b 2. n = 2 s t t s t n 2 3. b t (mod n) 0 r < s b 2rt = (mod n) 4. Yes? No! 4 n Yes? No! n Yes? n Miller-Rabin Yes? No! Yes? n b Miller-Rabin Yes? n n Yes? b Miller-Rabin 0 < b < n b n 5 2 n Miller-Rabin Yes? b 0 < b < n 4 n 0 < b < n Miller-Rabin Yes? 4 2 Yes? 4 2 k Yes? 4 k n k Yes? Miller-Rabin 2 2
3 3. Z Z = {, 2,, 0,, 2, } 3.. 2 a b n a b n a b (mod n) a n b n n 0,, 2,, n 0,, 2,, n 2 n k n k n k k n 0,, 2,, n n Z/nZ Z/nZ = {0,, 2,, n } 3.2. n = 3 0 = 3 = 6 = a b (mod 3) a = b Z/3Z = {0,, 2} k 3.3. a b n a + b = a + b, a b = a b 3.4. a a (mod n) b b (mod n) a ± b = a ± b (mod n). a a (mod n) a = a + kn b b (mod n) b = b + ln k, l a ± b = (a + kn) ± (b + ln) = (a ± b) + (k ± l)n a ± b a ± b (mod n) +. a + 0 = 0 + a = a 2. a + a = a + a = 0 3. (a + b) + c = a + (b + c) 4. a + b = b + a 3 4 Z/nZ + n 3
3.2 3.5. a b n ab = ab 3.6. a a (mod n) b b (mod n) ab a b (mod n). a a (mod n) a = a + kn b b (mod n) b = b + ln k, l a b = (a + kn)(b + ln) = ab + aln + knb + kln 2 = ab + (al + kb + kln)n ab a b (mod n) a(b + c) = a b + a c Z/nZ n 2 3 2 3 3 3 3 b b b 3 3 3 3 3x = x a a x = x a a x = b ax b (mod n) 2 a n (a, n) (a, n) = a n d b d b 3.7. ax b (mod n) (a, n) = n (a, n) = d d b n d d b. (a, n) = n Z/nZ = {x, x 2,, x n } b ax i ax j (mod n) a(x i x j ) 0 (mod n) a n x i x j 0 (mod n) {x, x 2,, x n } = {ax, ax 2,, ax n } 4
ax i b ax b (mod n) (a, n) = n (a, n) = d a = a d n = n d a n ax b (mod n) a dx b (mod n d) b d b d d b b = b d ax b (mod n) a dx b d (mod n d) x a x = b (mod n ) (a, n ) = n n = n d n n d n d b = 3.7.. ax (mod n) (a, n) = n. (a, n) = d > d n a x = (a, n) = a (a, n) = 3.3 (Z/nZ) (Z/nZ) = {a (a, n) = } a b (Z/nZ) (a, n) = (b, n) = (ab, n) = ab (Z/nZ) (Z/nZ) (Z/nZ). (Z/nZ) a = a = a 2. a (Z/nZ) a b = b a = b 3. (a b)c = a(b c) 4. a b = b a 5
(Z/nZ) n (Z/nZ) ϕ(n) n n 3.8. ϕ() =, ϕ(2) =, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, p ϕ(p) = p ϕ(p 2 ) = p(p ),,ϕ(p k ) = p k (p ) 3.9. (a, n) = a ϕ(n) (mod n). {x, x 2,, x ϕ(n) } (a, n) = {ax, ax 2,, ax ϕ(n) } a ϕ(n) x x 2 x ϕ(n) x x 2 x ϕ(n) (mod n) (x i, n) = i =, 2,, ϕ(n) (x x 2 x ϕ(n), n) = a ϕ(n) (mod n) p ϕ(p) = p 3.9.. p a p a p (mod p) p a < p a p (Z/pZ) Z/pZ 3.4 Z/nZ x k (mod n) Miller-Rabin (Z/nZ) 3.0. p (Z/pZ) p 3.. p p 2 (Z/p 2 Z) p(p ) 2 G G G g g m = m m G g G = {, g, g 2, g 3,, g m } g m = G g Miller-Rabin p p 2 x k = x k = 3.2. m(> 2) G x k = d = (k, m) 6
. g G = {(= g 0 ), g, g 2, g 3,, g m } g j x k = (g j ) k = g jk = m jk (m/d) ( jk/d) m/d k/d (m/d) j 0 j < m m/d j d x k = d 3.2.. p (Z/pZ) x k = (k, p ) (Z/p 2 Z) x k = (k, p(p )) 3.2.2. p (Z/pZ) x 2 =, 2., (2, p ) = 2 2 p, q pq 2 m n 3.3. m n f : Z/mnZ (Z/mZ) (Z/nZ) f (x) = (x, x) : f x 3 f (x) x mn (x, x) m n f f : 3.4. m, n 2 mn x a (mod m) x b (mod n). a =, b = 0 (m, n) = 3.7 mx (mod n) k x 0 = + mk m x 0 n x 0 0 a = 0, b = x x 0 (mod m) x (mod n) x a, b x = ax 0 + bx x x x x m n 0 x x m n m n x x mn x x mn mn 3.3 3.3 f (a, m) = (a, n) = (a, mn) = 3.5. m, n 2 3.3 f : f : (Z/mnZ) (Z/mZ) (Z/nZ) 7
: 3.6. m, n 2 A (Z/mZ) B (Z/nZ) s t (Z/mnZ) x x (mod m) A x (mod n) B st. (Z/mnZ) x x (mod m) A x (mod n) B 3.5 f f (x) A B A B st f : x st 4 Miller-Rabin Yes? n b 0 < b < n n b n (mod n) 3.9. n n (n )/2 b (n )/2 (mod n) b n (mod n) b (n )/2 (mod n) 2 (mod n) n ± (mod n) 2 n ± (mod n) 2 (mod n) 4.. n = 5 4 = 4 2 4 2 = 6 = 2 = 2 = n = 35, 6, 29, 34 4 2 n 2 ± 3.3 : n n 2 n = 2 s t q b t 2 b t, b 2 t,, b 2st = b n n n 8
n n b 0 < b < n. b t (mod n) 2. r 0 r s b 2rt (mod n) Miller-Rabin n n b t, b 2t,, b 2st = b n 5 2 Miller-Rabin Miller-Rabin Miller-Rabin b n Miller-Rabin b 2 2 2 n Miller-Rabin Yes? b 0 < b < n 4 n 5. n n p p 2 b n Miller-Rabin b n (mod n) p 2 n p 2 b n (mod p 2 ) (Z/p 2 Z) p(p ) 3.2 b p 2 d = (n, p(p )) p n p n p d d p b p 2 b p 2 p p 2 = p + 4 n (p )/(p 2 ) n/p 2 9
5.2 n n = p p p l n = pq 2 3.3 f (Z/pZ) (Z/qZ) p = 2 s t q = 2 s t t, t p q s s (i)s < s b n Miller-Rabin. b t (mod n) 2. r 0 r < s b 2rt (mod n) b Z/pqZ f (Z/pZ) (Z/qZ). b t (mod p) b t (mod q) 2. r 0 r < s b 2rt (mod p) b 2rt (mod q) b t (mod p) b p 3.2. (t, p ) b t (mod q) b q (t, q ) b pq 3.6 (t, p )(t, q ) p = 2 s t q = 2 s t t, t t (t, p ) = (t, t ) (t, q ) = (t, t ) (t, t ) t (t, t ) t b pq t t 0 r < s r b 2rt (mod p) b 2rt (mod q) b pq 5.. (Z/pZ) x 2rt (mod p) r s 0 r < s 2 r (t, t ). (Z/pZ) g g j 0 g < p g (p )/2 (mod p) (g j ) 2rt (mod p) (g j ) 2rt g (p )/2 (mod p) g 2r t j g 2s t (mod p) 2 r t j 2 s t (mod 2 s t ) r s 2 s (t 2 r s + t j) 0 (mod 2 s t ) t 2 r s + t j 2 s (t 2 r s + t j) 2 s r < s d = (t, t ) 2 r d (t/d) j 2 s r (t /d) (mod 2 s r (t /d)) t/d 2 s r (t /d) 2 s r (t /d) 2 s r (t /d) 2 s t 2 r d 2 s t 2 r d = 2 r (t, t ) 0
3.6 b 2rt (mod p) b 2rt (mod q) b pq 2 r (t, t ) 2 r (t, t ) 2 r (t, t ) 2 r (t, t ) 4 r t t 4 r t t t t 2 r 0 r < s 4 r t t n = pq > (p )(q ) = 2 s +s t t b 0 < b < n n = pq Miller-Rabin t t + t t + 4t t + 4 2 t t + + 4 s t t ( ) 2 s +s t t = 2 s s + 4s 4 /4 (ii)s = s ( ) ( ) 2 s s + 4s 2 2s 2 4 3 + 4s 2 3 2 3 3 + 6 = 4 (t, t ) t (t, t ) t 2 < (t, t ) = t (t, t ) = t t t t t t t t n n = pq q (mod t ) t q t t t t t = t p = q p q (t, t ) < t (t, t ) < t (t, t ) < t t t /(t, t ) 3 (t, t ) t /3 (i) (t, t )(t, t ) t t (t, t )(t, t ) t t /3 b ( ) s 3 2 s + 4s 3 ( ) 23 4 2 2s + 4s 3 8 + 9 = 6 < 4 n = pq n 3 n = p p 2 p k k > 3 p i = 2 s i t i t i s i s n = pq n Miller-Rabin b ( 2 s s 2 s k + 2ks ) ( 2 ks 2 k ) 2 2 k 2 k + 2ks 2 k = 2 ks 2k 2 2 k + 2 k 2 k 2k 2 2 k + 2 k = 2 k 2 4 6 p p 2 3.0 3. 2
(Z/pZ) (Z/pZ) g g m p 6.. G H H G g G g G. g G gh = {gh h H} gh g H gh = g H gh = g h h H h H g = ghh gh g H gh gh g H gh = g H g, g 2,, g k G = g H g 2 H g k H G g i H H H G 6.2. p m x m (mod p) p m. m m = 3.7 f (x) = x m x a a g(x) R f (x) = (x a)g(x) + R a x m 0 (mod p) R 0 (mod p) f (x) 0 (mod p) (x a)g(x) 0 (mod p) p x a 0 (mod p) g(x) 0 (mod p) 3.7 m m f (x) 0 (mod p) m (Z/pZ) (Z/pZ) g m < p x m 0 (mod p), g, g 2,, g m x m 0 (mod p) m p g i g j (mod p) g i j 0 (mod p) p i j 6. m < p 0 i, j m i = j x m 0 (mod p) m 6.2 (Z/pZ) p g i h h n n > h x m 0 (mod p) n m i (m, n) = gh m (gh) t (mod p) (gh) tm g tm g tm g tm g tm (mod p) g n 6. n tm n m n t (gh) tn m t t m n (m, n) = t mn t > m m m = p (Z/pZ) g ii (m, n) = d > m n l l = mn/d (m/d, n/d) = d = d e de 2 2 de k k de i i m/d n/d d e i m/d n/d i 2
m 0, n 0 (m 0, n 0 ) = m 0 n 0 = l i g m/m 0 h n/n 0 l = m 0 n 0 n m m n l m m m = p (Z/pZ) g (Z/pZ) (Z/p 2 Z) (Z/pZ) g p p 2 g g (mod p) g (mod p) g p (mod p) 0 < i < p g i (mod p) g p 2 g (mod p 2 ) g p(p ) (mod p 2 ) g p(p ) s p s < p g s (mod p 2 ) p 2 2 p g s (mod p) g p g ps (mod p) p g ps (g p ) s g s (mod p) g p g (mod p 2 ) p p(p ) p(p ) g (mod p 2 ) p g = (p + )g g g (p + )g g (mod p) g (mod p) p g p {(p + )g} p (p + ) p p + (p )p + 2 p2 + p (mod p 2 ) p (mod p 2 ) p p 2 g p g p(p ) (Z/p 2 Z) [] 2 97[ 93] [2] 996 [3] N. 997[ 987] 3