30 2018.4.25 30 1 nuida@mist.i.u-tokyo.ac.jp 2018 4 11 2018 4 25

30 2018.4.25 1 1 2 8 3 21 4 28 5 37 6 43 7 47 8 52

30 2018.4.25 1 1 Z Z 0 Z >0 Q, R, C a, b a b a = bc c 0 a b b a b a a, b, c a b b c a c a a 1 a 1.1 ( ). p Z >0 p 1 p 1 p 1 2, 3, 5, 7, 11, 13, 17,... a a a a a Z 1.1. a, b, c b a c a b + c a. b b + c a c = (b + c) b a c a b + c a 1.2. n 2 n. n n n = 2 n n n n 1 n d

30 2018.4.25 2 2 d < n d n 1.1.. p 1, p 2,..., p k 2 k 1 p 1,..., p k 2 n = p 1 p 2 p k + 1 n 3 p i p 1 p 2 p k p i 1 p i p i 2 1.1 n p i 1.2 n p 1,..., p k p 1,..., p k a b c a b c a b c a b c 1.2 ( ). a b gcd(a, b) a = 0 b = 0 gcd(a, b) = 0 a 0 b 0 a b 1 a b 0 gcd(a, b) gcd(a, b) = 1 a b 1.3 ( ). a b lcm(a, b) a = 0 b = 0 lcm(a, b) = 0

30 2018.4.25 3 a 0 b 0 a b ab a lcm(a, b) gcd(a, b) = gcd(b, a) lcm(a, b) = lcm(b, a) 1.3. a b a b r 0 r < b gcd(a, b) = gcd(r, b). a b r b d b d a d r r a b q a = qb + r d b qb d r d a = qb + r d a d r = a qb d 1.3 a, b a > b > 0 a b r gcd(a, b) = gcd(b, r) r = 0 gcd(b, r) = b gcd(a, b) = b gcd(a, b) r 0 gcd(a, b) gcd(b, r) b > r > 0 r a gcd(a, b) a b ca+db = gcd(a, b) c, d cb+dr = gcd(b, r) = gcd(a, b) c, d a = bq + r q Z gcd(a, b) = cb + dr = cb + d(a bq) = da + (c dq)b c a + d b = gcd(a, b) c = d d = c dq r = 0 gcd(a, b) = b 0 a + 1 b = gcd(a, b)

30 2018.4.25 4 c, d 1.2. a, b ca+db = gcd(a, b) c, d a, b m a b m a m b a b (mod m) 1.2 1.1. a m ba m gcd(a, m) b a m ba m 1 b. 1.2 a m ba + cm = gcd(a, m) b, c Z cm m gcd(a, m) = ba + cm m ba 1.2. p 2 1. p 2. a, b p a p b p ab. 1 2 p p a 1 p p a p p a 1 gcd(a, p) = 1 1.2 ca + dp = 1 c, d Z b c b + d p = 1 c, d Z (ca + dp)(c b + d p) = 1 (ca + dp)(c b + d p) = cc ab + (cad + dc b + dd p) p

30 2018.4.25 5 cc ab = (cad + dc b + dd p) p + 1 1 p 2 p 1.1 cc ab p ab p 2 2 1 a p ab = p b b p p p = ab 2 p a p b p a a p a = p p b b = p ap = p a = 1 p p 1 p 1 1.3. n 1. k 0 p 1,..., p k e 1,..., e k e1 e n = p 1 p k k k = 0 1 e1 e n = p 1 p k k n e1 e 2. n = p 1 p k f1 f k n = q 1 q l l n k = l (q 1, f 1 ),..., (q k, f k ) p i = q i e i = f i i = 1,..., k. 1 n n n = 1 n n 2 n n = n 1 n n n a, b n = ab a b

30 2018.4.25 6 e1 e a = p 1 p k k b = p 1 e 1 p k e k n = ab p 1,..., p k, p 1,..., p k q 1,..., q l i = 1,..., l f i q i = p j q i {p 1,..., p k } f i = e j q i = p j q i {p 1,..., p k } f i = e j q i = p j = p j f i = e j + e j n = q 1 f1 q l f l n 2 n n n = 1 n 1 n 2 n = p 1 e1 p k e k n = q 1 f1 q l f l p k n f1 p k q 1 q f l l 1.2 q i p k q i q i p k 2 p k = q i n n = q 1 f1 q l f l i = l e k f l e k f l e k f l n = n/p k e k = n/q l e k n e1 e = p 1 p k 1 f1 f k 1 = q 1 q l 1 f l 1 p l e k k f l e k > 0 p k n p k {p 1,..., p k 1 } p 1,..., p k f l e k = 0 n = p 1 e1 p k 1 e k 1 = q 1 f1 q l 1 f l 1 n n < n 2 n k 1 = l 1

30 2018.4.25 7 k = l (q 1, f 1 ),..., (q k 1, f k 1 ) p j = q j e j = f j j = 1,..., k 1 k = l p k = q k e k = f k 2 n

30 2018.4.25 8 2 n a, b n a b a n b a n a mod n a n q Z a = qn + (a mod n) a mod n {0, 1,..., n 1} a n (a mod n) n 2.1. n a 1, a 2, b 1, b 2 a 1 n b 1 a 2 n b 2 a 1 + a 2 n b 1 + b 2, a 1 a 2 n b 1 b 2, a 1 a 2 n b 1 b 2. a 1 b 1 = cn c a 2 b 2 = dn d (a 1 + a 2 ) (b 1 + b 2 ) = (a 1 b 1 ) + (a 2 b 2 ) = cn + dn = (c + d)n a 1 + a 2 n b 1 + b 2 (a 1 a 2 ) (b 1 b 2 ) = (a 1 b 1 ) (a 2 b 2 ) = cn dn = (c d)n a 1 a 2 n b 1 b 2 a 1 a 2 b 1 b 2 = a 1 (a 2 b 2 ) + (a 1 b 1 )b 2 = a 1 dn + cnb 2 = (a 1 d + cb 2 )n a 1 a 2 n b 1 b 2 2.1 n n n = 7 (3 4 3 + 2 6) mod 7 4 2 = 16 7 2,

30 2018.4.25 9 4 3 = 4 2 4 7 2 4 = 8 7 1, 3 4 3 7 3 1 = 3, 2 6 = 12 7 5, 3 4 3 + 2 6 7 3 + 5 = 8 7 1 (3 4 3 + 2 6) mod 7 = 1 2.1 n n = 11 7 29 mod 11 29 29 = (11101) 2 (1) 2 = 1 (11) 2 = 3 (111) 2 = 7 (1110) 2 = 14 (11101) 2 = 29 7 29 mod 11 7 1 11 7, 7 3 = (7 1 ) 2 7 11 7 2 7 = 49 7 11 5 7 = 35 11 2, 7 7 = (7 3 ) 2 7 11 2 2 7 = 4 7 11 4 7 = 28 11 6, 7 14 = (7 7 ) 2 11 6 2 = 36 11 3, 7 29 = (7 14 ) 2 7 11 3 2 7 = 9 7 11 9 7 = 63 11 8. Z/nZ Z/nZ = {a mod n a {0, 1,..., n 1}} 2.1 Z/nZ (a mod n) + (b mod n) = (a + b) mod n, (a mod n) (b mod n) = (a b) mod n, (a mod n) (b mod n) = (a b) mod n Z/nZ Z/nZ Z/nZ a mod n a

30 2018.4.25 10 2.1 ( ). G G G a, b G a b G 1. G a, b, c (a b) c = a (b c) G a, b a b = b a G G G G 2. G e G a a e = a e a = a e G G G 3. e G a G a b = e b a = e G b b a 2.2 ( ). R R + 1. R + 0 a a a + ( b) a b 2. R a b a b ab 3. + R a, b, c a (b + c) = (a b) + (a c) (b + c) a = (b a) + (c a) R R R R

30 2018.4.25 11 4. R \ {0} 1 R R \ {0} R R \ {0} R R R R 0 a = 0 a 0 = 0 Z, Q, R, C 0 1 Z/nZ 0 = 0 mod n n 2 Z/nZ 1 = 1 mod n n = 1 Z/nZ 0 Z ±1 a Z Z a = 0 a 1 Q Z/nZ 1 ( 1 mod n) = n 1 Z/nZ n 2.2. n 2 a Z/nZ a gcd(a, n) = 1. gcd(a, n) = 1 1.1 ab n 1 b b b mod n a b n a ab n 1 ab + cn = 1 c Z gcd(a, n) ab cn 1 gcd(a, n) = 1 2.2 n p (Z/pZ) = (Z/pZ) \ {0} Z/pZ 0 p Z/pZ Z/pZ F p 2.3 ( ). K K = K \ {0} K

30 2018.4.25 12 F p Q, R, C Z 2.3. R R R R R R. a, b R ab R R R R a, b R R a 1, b 1 (ab) (b 1 a 1 ) = a(bb 1 )a 1 = a 1 a 1 = aa 1 = 1 b 1 a 1 ab ab R R 1 = 1 1 1 R 1 R R a R aa 1 = a 1 a = 1 a 1 a a 1 a 1 R a 1 R a a R R 2.4 ( ). G 1, G 2 φ: G 1 G 2 g 1, g 2 G 1 φ(g 1 g 2 ) = φ(g 1 ) φ(g 2 ) φ G 1 G 2 2.5 ( ). R 1, R 2 φ: R 1 R 2 r 1, r 2 R 1 φ(r 1 + r 2 ) = φ(r 1 ) + φ(r 2 ) r 1, r 2 R 1 φ(r 1 r 2 ) = φ(r 1 ) φ(r 2 ) 1 R1 1 R2 R 1 R 2 φ(1 R1 ) = 1 R2

30 2018.4.25 13 φ R 1 R 2 m 1,..., m k Z/m i Z a i i = 1,..., k (a 1,..., a k ) Z/m 1 Z Z/m k Z Z/m 1 Z Z/m k Z Z/m 1 Z,..., Z/m k Z Z/m 1 Z Z/m k Z (a 1,..., a k ) + (b 1,..., b k ) = (a 1 + b 1,..., a k + b k ), (a 1,..., a k ) (b 1,..., b k ) = (a 1 b 1,..., a k b k ), (a 1,..., a k ) (b 1,..., b k ) = (a 1 b 1,..., a k b k ) Z/m 1 Z Z/m k Z (0, 0,..., 0) (1, 1,..., 1) 2.1 ( ). m 1,..., m k k 1 2 m = m 1 m k Z/mZ a Z/m 1 Z Z/m k Z (a mod m 1,..., a mod m k ) f 1. f Z/mZ Z/m 1 Z Z/m k Z 2. a Z/mZ f(a) = (a 1,..., a k ) a (Z/mZ) a i (Z/m i Z) i = 1,..., k f (Z/mZ) (Z/m i Z). f well-defined a m a f(a) = f(a ) a a = cm c i a a = cm 1 m i 1 m i+1 m k m i a mi a a mod m i = a mod m i f(a + b) = f(a) + f(b) f(ab) = f(a)f(b) Z/m 1 Z Z/m k Z f(1) = (1, 1,..., 1)

30 2018.4.25 14 f Z/m 1 Z Z/m k Z m 1 m k = m Z/mZ f f 1 f m 1,..., m k i m i m/m i 2.2 m i m/m i c i i a i Z/m i Z a Z/mZ a = (m/m 1 ) c 1 a 1 + (m/m 2 ) c 2 a 2 + + (m/m k ) c k a k i j i m/m j m i (m/m j ) c j a j mi 0 a mi (m/m i ) c i a i c i Z/m i Z m/m i a mi a i a mod m i = a i f(a) = (a 1,..., a k ) f 1 2 a (Z/mZ) 2.2 a m i a m i 2.2 a m i a i = a mod m i (Z/m i Z) i a i (Z/m i Z) Z/m i Z a i b i 1 f f(b) = (b 1,..., b k ) b Z/mZ f(ab) = f(a)f(b) = (a 1,..., a k ) (b 1,..., b k ) = (a 1 b 1,..., a k b k ) = (1,..., 1) f(1) = (1,..., 1) f(ab) = f(1) 1 f ab = 1 a (Z/mZ) n totient φ(n) φ(n) = (Z/nZ)

30 2018.4.25 15 e1 e 2.2. n = p 1 p k k n e φ(n) = (p 1 1)p 1 1 e 1 (p k 1)p k 1 k. 2.1 φ(n) = (Z/nZ) e = (Z/p 1 1 Z) e (Z/p k k Z) e = φ(p 1 e 1 ) φ(p k k ) n p e 1 p e n n = p e 2.2 φ(p e ) p e a {0, 1,..., p e 1} a a p e a p p e a 1 1/p p e (1 1/p) = p e p e 1 = (p 1)p e 1 φ(p e ) = (p 1)p e 1 n = p e φ 2.3 ( ). G H H G G H G. G a ah ah = {ah G h H} ah bh ah = bh ah bh g g = ah 1 g = bh 2 h 1, h 2 H g = ah 1 = bh 2 a = bh 2 h 1 1 b = ah 1 h 1 2 ah ah h H ah = bh 2 h 1 1 h H G h 2 h 1 1 h H ah bh bh bh h H bh = ah 1 h 1 2 h H G h 1 h 1 2 h H bh ah ah = bh a G ah G G

30 2018.4.25 16 ah G ah ah H G G H 2.3 2.4 ( ). n 2 a n a φ(n) n 1. a a mod n a Z/nZ 2.2 a (Z/nZ) a k k Z (Z/nZ) a a (Z/nZ) a (Z/nZ) a k = a l k 0 l > k (k, l) (Z/nZ) l k = 0 k > 0 (k 1, l 1) a l = a 0 = 1 m a m = a m mod l a = {1 = a 0, a 1,..., a l 1 } l l a = l 2.3 φ(n) = (Z/nZ) a = l a l = 1 a φ(n) = 1 Z/nZ 2.1 ( ). p p a a p 1 p 1. 2.4 φ(p) = p 1 2.4. K G K G G a G a k k Z a G. a G ord(a) = min{k Z >0 a k = 1} a G 2.4 a G a a = ord(a) ord(a) = G a G ord(a) G a

30 2018.4.25 17 ord(a) = G ord(a) < G x ord(a) 1 K ord(a) b ord(a) = 1 K b ord(a) G b ord(a) 1 b G b ord(a) 1 b ord(b) = 1 ord(b) ord(a) ord(a) ord(b) p ord(a) p e ord(b) p f a = a pe b = b ord(b)/pf ord(a ) = ord(a)/p e ord(b ) = p f k = ord(a b ) k 1 (a b ) k = (a ) k (b ) k = 1 (a ) k = (b ) k a b 2.3 a ord(a ) = ord(a)/p e b ord(b ) = p f ord(a)/p e p f a b 1 (a ) k = (b ) k = 1 (b ) k = 1 k ord(a ) = ord(a)/p e ord(b ) = p f ord(a ) ord(b ) k ord(a )ord(b ) = ord(a) p f e ord(a b ) = k ord(a) p f e > ord(a) f > e a, b G a b G ord(a) a G 2.2. K K K K 2.6 ( ). n n a a n b 2 n a b Z n a a 2.7 ( ). p a

30 2018.4.25 18 ( ) a { 1, 0, 1} p ( ) a = p 0 gcd(a, p) 1 1 gcd(a, p) = 1 a p 1 gcd(a, p) = 1 a p e1 e n > 1 n = p 1 p k ( k a n) ( a 0 gcd(a, n) 1 ( ) = e1 ( ) ek a a n) gcd(a, n) = 1 p 1 p k ( ) a 2.1. p a p p a (p 1)/2 p. b F p ord(b) = p 1 F p c c = b k k Z k k c c c = b k ( ) k a a = 1 p a = b 2k k Z p a (p 1)/2 = b (p 1)k = (b p 1 ) k = ( 1 k ) = 1 a 2.1 a = 1 p p a = b 2k+1 k Z a (p 1)/2 = b (p 1)k+(p 1)/2 = (b p 1 ) k b (p 1)/2 = b (p 1)/2 b b (p 1)/2 1 (b (p 1)/2 ) 2 = b p 1 = 1 b (p 1)/2 = 1 a (p 1)/2 = b (p 1)/2 = 1 ( ) ab ( a ) ( ) b 2.5. a, b n > 1 = n n n

30 2018.4.25 19. ab n a b n 0 ab n a b n n = p 1 e1 p k e k n ( ) ( ) e1 ( ) ek ab ab ab = n p 1 p k ( ) ( ) ( ) ab a b i = ab n a b p i p i = 2 p i ( a ) b ( ) ( ) 2 ab a b = 1 = p i p i 2.1 ( ) ( ) ( ) ab pi (ab) (pi 1)/2 = a (pi 1)/2 b (pi 1)/2 pi api bpi p i p i p i p i p i ( ) ( ) ( ) ( ) ab ab pi ±1 = ( ) ( ) p i api bpi p i a b p i p i 2.5 ( ). ( a b 1. a b 1 ) ( ) b a = ( 1) a 1 b 1 2 2 2. a 1 ( ) { 1 1 a = ( 1) a 1 4 1 2 = a 1 a 4 3

30 2018.4.25 20 3. a 1 ( ) { 2 = ( 1) a2 1 1 a 8 1, 7 8 = a 1 a 8 3, 5 2.5 2.5 ( ) ( ) ( ) ( ) 38 2 19 = = ( 1) (1272 1)/8 ( 1) 19 1 127 1 127 2 2 127 127 127 19 ( ) ( ) ( ) 13 = 1 ( 1) = ( 1) ( 1) 13 1 19 1 19 6 2 2 = ( 1) 1 19 13 13 ( ) ( ) ( ) 2 3 = ( 1) = ( 1) ( 1) (132 1)/8 ( 1) 3 1 13 1 13 2 2 13 13 3 ( ) 38 = 1 127 = ( 1) ( 1) 1 ( ) 1 = 1 1 = 1 3

30 2018.4.25 21 3 primality test primality certificate primality proof n > 1 2 n 1 n n n n n n 2 n 1 n n n 2

30 2018.4.25 22 3.1 ( ). n > 1 1 n 1. 1 2. n k 3 k k 3. n > 1 n 1 n n n n n 1 n n 2.1 n > 1 n n a a n 1 n 1 a n 1 n 1 a a n

30 2018.4.25 23 3.2 ( ). n > 1 1. a 1 n 1 gcd(a, n) gcd(a, n) 1 n 2. a n 1 n 1 n n 2 a n 1 n log 2 n n a n n n n a n n 1 n > 1 n a a n 1 n 1 561 n 1 R. D. Carmichael: Note on a new number theory function. Bulletin of the American Mathematical Society, vol.16, no.5, pp.232 238 (1910). doi:10.1090/s0002-9904-1910-01892-9

30 2018.4.25 24 3.3 ( ). n > 1 n 1. n 1 2 n 1 = 2 s d s 1 d 2. a 1 n 1 gcd(a, n) 1 n 3. a d n 1 i = 0, 1,..., s 1 a 2id n 1 n n 3.1. n. n 1 a n 1 gcd(a, n) = 1 a 2sd = (a 2s 1d ) 2 n 1 F n F n 1 1 1 a 2s 1d n ±1 3 a 2s 1d n 1 n a 2s 1d n 1 s 1 = 0 n s 1 > 0 a 2s 2d n ±1 i a 2id n 1 a d n 1 n n n n a n 1 n n n n 3/4 n

30 2018.4.25 25 3.1. n 2 1/2 n e1 e. n n = p 1 p k k k 2 f : (Z/nZ) e (Z/p 1 1 Z) e (Z/p k k Z) n 1 = 2 s d d ( 1) d n 1 i = 0 b 2id n 1 b (Z/nZ) b 2id n 1 b (Z/nZ) s 1 i n a a d n 1 j = 0, 1,..., i a 2jd n 1 a a 2id n 1 a 2id n 1 A 1 = {b (Z/nZ) b 2id n 1} A 1 = {b (Z/nZ) b 2id n 1} A 1 A 1 1/2 A 1 A 1 b f(b) = (b 1,..., b k ) b 2id n 1 f(b 2id ) = f( 1) = ( 1,..., 1) (b 1,..., b k ) 2id 2 = (b id 2 1,..., b id k ) = ( 1,..., 1) f(c) = (b 1, 1,..., 1) c (Z/nZ) a A 1 f((ac) 2id ) = f(a 2id )f(c 2id ) = f(1) (b 1, 1,..., 1) 2id = ( 1, 1,..., 1) ac A 1 A 1 k = 2 a A 1 f((ac) 2id ) = f(a 2id )f(c 2id ) = f( 1) (b 1, 1,..., 1) 2id = (1, 1,..., 1) ac A 1 A 1 A 1 A 1 a A 1 A 1 ac A 1 A 1 (Z/nZ) /2 (n 1)/2 n a 1/2

30 2018.4.25 26 a a generalized Riemann hypothesis GRH n a n 2 GRH 1976 Miller 2 1980 Rabin GRH 3 Pratt 1975 4 3.2. n > 2 a 1. a n 1 n 1 2. p n 1 a (n 1)/p n 1 n. n 1 a n 1 n 1 a (Z/nZ) a φ(n) n 1 n φ(n) < n 1 n a ord(a) n 1 ord(a) < n 1 n 1 p ord(a) (n 1)/p a (n 1)/p n 1 2 3.2 n 2 G. L. Miller: Riemann s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, vol.13, no.3, pp.300 317 (1976). doi:10.1145/800116.803773 3 M. O. Rabin: Probabilistic algorithm for testing primality. Journal of Number Theory, vol.12, no.1, pp.128 138 (1980). doi:10.1016/0022-314x(80)90084-0 4 V. Pratt: Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214 220 (1975)

30 2018.4.25 27 e1 e n 1 n 1 = p 1 p k k p 1,..., p k a n 1 n 1 i a (n 1)/pi n 1 a n 1 n

30 2018.4.25 28 4 2002 Agrawal, Kayal, Saxena 2004 5 AKS AKS AKS n n AKS AKS 4 (X + a) n X r 0 1,n X n + a Z/nZ X r 0 1 4.1 (AKS ). n > 1 1. n a k a > 0 k 2 n 2. r = 2, 3,..., n 1 (a) gcd(r, n) > 1 n (b) i = 1, 2,..., (log 2 n) 2 n i r 1 r r 0 3. r 0 n 5 M. Agrawal, N. Kayal, N. Saxena: PRIMES Is in P. Annals of Mathematics, vol.160, pp.781 793 (2004)

30 2018.4.25 29 4. a = 1, 2,..., φ(r 0 ) log 2 n (X + a) n X r 0 1,n X n + a n 5. n 1 n = a k n O((log n) 3 poly(log log n)) 2(a) gcd(r, n) > 1 r < n 1 < gcd(r, n) < n n 3 r 0 r = 2, 3,..., n 1 gcd(r, n) = 1 n 4 ( ) ( n n (X + a) n = X n + ax n 1 + 1 2 ) a 2 X n 2 + + ( ) n a n 1 X + a n n 1 n ( ) ( n 1,..., n n 1) n a n n a Z/nZ (X +a) n = X n + a (X + a) n X r 0 1,n X n + a a (X + a) n X r 0 1,n X n + a n n n X r 0 1

30 2018.4.25 30 r 0 r 0 φ(r 0 ) r 0 r 0 r 0 φ(r 0 ) r 0 2 r 0 4 n n 4.1. n > (log 2 n) 5 + 1 1 r (log 2 n) 5 r 2(a) n 2(b) r 0. B = (log 2 n) 5 n 2 B d r 0 r d 2(a) n n 2 B r 2(a) r 0 2 r B r n i 1 i (log 2 n) 2 (log 2 n) 2 P = (n i 1) P 2 B i=1 P < (log 2 n) 2 i=1 n (log 2 n)2 n (log 2 n)4 = 2 (log 2 n)5 2 B lcm(2,..., B) P < 2 B [Nai] 6 m 7 lcm(2,..., m) 2 B n > (log 2 n) 5 +1 6 M. Nair: On Chebyshev-Type Inequalities for Primes. Amer. Math. Monthly, vol.89, pp.126 129 (1982)

30 2018.4.25 31 n > 2 B (log 2 3) 5 (log 2 2 2) 5 = (3/2) 5 = 243/32 > 7 2 n r 4.1 r (log 2 n) 5 4 n r 0 n (Z/r 0 Z) ord(n) (log 2 n) 2 n p p (Z/r 0 Z) ord(p) > 1 p 2(a) p > r 0 4.2 (introspective). f(x) m > 0 m f(x) introspective f(x) m X r 0 1,p f(x m ) 4.1. 1. m m f(x) introspective mm f(x) introspective 2. m f(x) g(x) introspective m f(x)g(x) introspective. 1 m introspective f(x) mm X r 0 1,p f(x m ) m m introspective f(x) m X r 0 1,p f(x m ) X X m f(x m ) m X mr 0 1,p f(x mm ) X r 0 1 X mr 0 1 f(x m ) m X r 0 1,p f(x mm ) f(x) mm X r 0 1,p f(x mm )

30 2018.4.25 32 mm f(x) introspective 2 m f(x) g(x) introspective (f(x)g(x)) m = f(x) m g(x) m X r 0 1,p f(x m )g(x m ) m f(x)g(x) introspective l = φ(r 0 ) log 2 n 4.2. 1 a l n, p, n/p X + a introspective. 4 (X + a) n X r 0 1,n X n + a p n (X + a) n X r 0 1,p X n + a n X + a introspective p (X + a) p p X p + a (X + a) p X r 0 1,p X p + a p X + a introspective n/p c i = ( ) n/p i a n/p i (X + a) n/p = X n/p + n/p 1 i=0 c i X i (X + a) p X r 0 1,p X p + a (X + a) n = ((X + a) p ) n/p X r 0 1,p (X p + a) n/p = X n + n/p 1 (X + a) n X r 0 1,p X n + a X n + n/p 1 i=0 n/p 1 i=0 c i X pi X r 0 1,p X n + a c i X pi X r 0 1,p a 0 j r 0 1 0 i<n/p pi mod r 0 =j c i p { a j = 0 0 j > 0 i=0 c i X pi

30 2018.4.25 33 p (Z/r 0 Z) r 0 p p pi mod r 0 = j i mod r 0 = p j mod r 0 j = 0 p j mod r 0 = 0 0 j r 0 1 c i p 0 i<n/p i mod r 0 =j (X + a) n/p = X n/p + { a j = 0 0 j > 0 n/p 1 i=0 c i X i X r 0 1,p X n/p + a n/p X + a introspective I = {(n/p) i p j i, j Z 0 } P = { l a=0 (X + a)ea e 0,..., e l Z 0 } G = {m mod r 0 m I} n p r 0 G (Z/r 0 Z) G g G r 0 g φ(r 0) = 1 g G G (Z/r 0 Z) n = (n/p) p I ord(n) > (log 2 n) 2 G > (log 2 n) 2 d 1 Φ d (X) Φ 1 (X) = X 1, Φ d (X) = X d 1 d d, d d Φ d (X) Φ d (X) Φ d (X) F p 4.2. F p Φ r0 (X) ord(p) h(x) h(x) F = F p [X]/(h(X)) F F p m 1, m 2 m 1 r0 m 2 F X m1 X m 2

30 2018.4.25 34. F p ord(p) K 2.2 K x K = p ord(p) 1 ord(p) p ord(p) r0 1 r 0 K y = x K /r 0 y r 0 1 y 1 r 0 y r 0 = 1 y X r 0 1 d r 0 1 d < r 0 Φ d (X) X d 1 y 1 r 0 y d 1 y Φ d (X) y Φ r0 (X) y F p h(x) h(x) y Φ r0 (X) h(x) Φ r0 (X) y F p ord(p) h(x) ord(p) h(x) ord(p) d y F p d p d 1 y r 0 r 0 p d 1 p d r0 1 d < ord(p) h(x) ord(p) K = F p (y) F = F p [X]/(h(X)) X y F K F p y X F 1 r 0 m 1, m 2 m 1 r0 m 2 F X m1 X m 2 h(x) F 4.2 P F F G ord(p) > 1 p X, X + 1,..., X + l F 0 G F F G 4.3. G ( G +l G 1). f(x), g(x) P G f(x) p g(x) F f(x) g(x) F f(x) = g(x) m I F f(x) m = g(x) m m p, n/p f(x) g(x) X, X + 1,..., X + l 4.2 4.1 m

30 2018.4.25 35 f(x) g(x) introspective f(x) m X r 0 1,p f(x m ) g(x) m X r 0 1,p g(x m ) 4.2 h(x) F p Φ r0 (X) X r 0 1 f(x) m h(x),p f(x m ) g(x) m h(x),p g(x m ) F f(x) m = f(x m ) g(x) m = g(x m ) F f(x m ) = g(x m ) Q(Y ) = f(y ) g(y ) mod p m I X m F Q(Y ) 4.2 m mod r 0 X m F G m X m F Q(Y ) Q(Y ) G f(y ) g(y ) G f(y ) p g(y ) Q(Y ) G F f(x) g(x) l = φ(r 0 ) log 2 n < r 0 log 2 n r 0 > ord(n) > (log 2 n) 2 r 0 > log 2 n l < r 0 r 0 < p l < p X, X +1,..., X +l F p 1, X, X +1,..., X +l G 1 ( ) ( ( G 1)+(l+2 1) l+2 1 = G +l ) ( l+1 = G +l ) G 1 F p G G ( G +l G 1) 4.4. n p G n G. n p i, j G (n/p) i p j I ( G + 1) 2 > ( G ) 2 = G G r 0 I m 1 > m 2 m 1 r0 m 2 X m 1 X r 0 1 X m 2 f(x) P 4.2 4.1 m 1, m 2 I f(x) introspective f(x) m 1 X r 0 1,p f(x m 1 ) X r 0 1,p f(x m 2 ) X r 0 1,p f(x) m 2 h(x) X r 0 f(x) m 1 1 F = f(x) m 2 f(x) G F Y m 1 Y m 2 Y m 1 Y m 2 G

30 2018.4.25 36 m 1 (n/p) G p G = n G G n G n p n G G ( ) G + l G 1 G > (log 2 n) 2 G > G log 2 n G 1 G log 2 n G (Z/r 0 Z) = φ(r 0 ) l = φ(r 0 ) log 2 n G log 2 n G > (log 2 n) 2 G log 2 n > (log 2 n) 2 1 ( ) G + l G 1 ( ) l + 1 + G log2 n G log 2 n ( ) 2 G log2 n + 1 G log 2 n = 2 G log 2 n + 1 G log 2 n G log 2 n + 3 2 > 2 2 4 = 2 G log 2 n 1 4 = 2 G log 2 n +1 > 2 G log2 n = n G n G G ( ) G + l > n G G 1 ( G log 2 n + 2) n p 1 2 n = p n 4 5 n

30 2018.4.25 37 5 5.1 ( ). Gen(1 λ ) λ pk sk λ 1 λ 1 λ pk M C sk pk Enc(m, pk) m M pk c C c [[m]] Dec(c, sk) c C sk m M (pk, sk) Gen(1 λ ) m M Dec(Enc(m, pk), sk) = m RSA 7 7 R. Rivest, A. Shamir, L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, vol.21, no.2, pp.120 126 (1978)

30 2018.4.25 38 λ λ p q N = pq φ(n) e φ(n) d (N, e) d M = (Z/NZ) C = M m (Z/NZ) c = m e (Z/NZ) c (Z/NZ) m = c d (Z/NZ) RSA d ed φ(n) 1 m (Z/NZ) m ed 1 N 1 m ed N m m c = m e c d N m m m RSA c = [[m]] pk m RSA RSA N N p q φ(n) = (p 1)(q 1) e φ(n) φ(n) e d RSA N

30 2018.4.25 39 RSA RSA RSA RSA c m c m c RSA RSA RSA Goldwasser Micali 8 λ p q ( ) x N = pq N x = ( ) p x = 1 (N, x) (p, q) q M = F 2 C = (Z/NZ) m F 2 m 0 1 (Z/NZ) y c = y 2 x m (Z/NZ) ( ) c c (Z/NZ) m = 1 p 8 S. Goldwasser, S. Micali. Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. In: Proceedings of STOC 1982, pp.365 377 (1982)

30 2018.4.25 40 ( ) c m = 0 = 1 m = 1 p Goldwasser Micali x y 2.5 ( ) c = p ( y p ) 2 ( ) { m x 1 m = 0 = ( 1) m = p 1 m = 1 RSA semantic ( security a ) = 1 a N N N Goldwasser Micali m, m c, c (Z/NZ) cc m + m c = y 2 x m c = y 2 x m cc = (yy ) 2 x m+m m = m = 1 (yy x) 2 x 0 Goldwasser Micali 0 1 1 Paillier

30 2018.4.25 41 9 λ p q N = pq p 1 q 1 µ N µ M = Z/NZ C = (Z/N 2 Z) m Z/NZ m 0 N 1 N 1 N 1 r c = (1 + N) m r N (Z/N 2 Z) c (Z/N 2 Z) c µ (Z/N 2 Z) c c µ 0 N 2 1 c µ 1 N c µ 1 N 0 N 1 Z/NZ Z/NZ µ Paillier (Z/N 2 Z) (Z/p 2 Z) (Z/q 2 Z) φ(p 2 ) = p(p 1) (Z/p 2 Z) p(p 1) φ(q 2 ) = q(q 1) (Z/q 2 Z) q(q 1) µ p 1 q 1 (Z/N 2 Z) pqµ = Nµ c = (1 + N) m r N r Nµ N 2 1 c µ N 2 (1 + N) mµ (1 + N) mµ (mµ)(mµ 1) = 1 + (mµ)n + N 2 + + N mµ N 2 1 + (mµ)n 2 c µ N 2 1 + (mµ)n c µ 1 N c µ 1 N mµ Z/NZ µ m Z/NZ 9 P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Proceedings of EUROCRYPT 1999, pp.223 238 (1999)

30 2018.4.25 42 Paillier c = (1 + N) m r N c = (1 + N) m r N cc = (1 + N) m+m (rr ) N m + m Paillier N

30 2018.4.25 43 6 Pollard p 1 10 N N Pollard p 1 1. 1 N 1 a gcd(a, N) gcd(a, N) > 1 gcd(a, N) N 1 N gcd(a, N) 2. M gcd(a M 1, N) 1 < gcd(a M 1, N) < N gcd(a M 1, N) N gcd(a M 1, N) a M Pollard p 1 N N 6.1. p N M p 1 p gcd(a M 1, N). a p 1 p 1 M p 1 a M p 1 a M 1 p N p p gcd(a M 1, N) N p p 1 M 6.1 gcd(a M 1, N) > 1 N q q 1 M 10 J. M. Pollard. Theorems on Factorization and Primality Testing. Proc. Cambridge Phil. Soc., vol.76, pp.521 528 (1974)

30 2018.4.25 44 M a gcd(a M 1, N) < N N N p p 1 M M N M N p 1 M M M M M M B M B M = B! M p 1 M p 1 smooth Pollard p 1 p 1 smooth N p N p p 1 smooth 6.1. M = 10! = 3628800 N = 1331909 a = 2 Pollard p 1 N a M = 2 M M = (1101110101111100000000) 2

30 2018.4.25 45 2 M mod N 2 2 4 2 8 2 64 2 4096 2 8192 2 67108864 1331909 513414 2 1026828 2 1054375741584 1331909 615641 2 1231282 2 1516055363524 1331909 620911 2 385530469921 1331909 86508 2 173016 2 29934536256 1331909 1213390 2 1472315292100 1331909 441047 2 882094 2 778089824836 1331909 574217 2 1148434 2 1318900652356 1331909 407559 2 815118 2 664417353924 1331909 1208819 2 2417638 1331909 1085729 2 1178807461441 1331909 69082 2 138164 2 19089290896 1331909 371108 2 137721147664 1331909 425155 2 180756774025 1331909 739817 2 547329193489 1331909 1168574 2 1365565193476 1331909 184955 2 34208352025 1331909 933178 2 870821179684 1331909 428758 2 183833422564 1331909 678566 a M N 678566 a M 1 N 678565 gcd(a M 1, N) (1331909, 678565) (678565, 653344) (653344, 25221) (25221, 22819) (22819, 2402) (2402, 1201) (1201, 0) gcd(a M 1, N) = 1201 N = 1331909 N = 1109 1201 Pollard p 1 p = 1201 p 1 = 1200 M = 10! N = 1356841 M a

30 2018.4.25 46 2 M mod N 2 2 4 2 8 2 64 2 4096 2 8192 2 67108864 1356841 623655 2 1247310 2 1555782236100 1356841 1208680 2 2417360 1356841 1060519 2 1124700549361 1356841 119210 2 14211024100 1356841 828307 2 1656614 1356841 299773 2 89863851529 1356841 272099 2 74037865801 1356841 479795 2 959590 2 920812968100 1356841 964496 2 1928992 1356841 572151 2 327356766801 1356841 1236618 2 2473236 1356841 1116395 2 1246337796025 1356841 640747 2 1281494 2 1642226872036 1356841 147665 2 295330 2 87219808900 1356841 712579 2 507768831241 1356841 937493 2 878893125049 1356841 724140 2 524378739600 1356841 398330 2 158666788900 1356841 516042 2 266299345764 1356841 303740 2 92257987600 1356841 940646 2 884814897316 1356841 1242283 a M N 1242283 a M 1 N 1242282 gcd(a M 1, N) (1356841, 1242282) (1242282, 114559) (114559, 96692) (96692, 17867) (17867, 7357) (7357, 3153) (3153, 1051) (1051, 0) gcd(a M 1, N) = 1051 N = 1356841 N = 1051 1291 Pollard p 1 p = 1051 p 1 = 1050 M = 10! M a N Pollard p 1

30 2018.4.25 47 7 Pollard p 1 p 1 smooth p N Pollard p 1 11 K K 2 3 K 1 + 1 0 1 + 1 + 1 0 7.1 ( ). A, B K 16(4A 3 + 27B 2 ) 0 E : y 2 = x 3 + Ax + B K 7.1. K = F 11 A = 3 B = 2 K 16(4A 3 + 27B 2 ) = 16 7 0 E : y 2 = x 3 + 3x + 2 K E 7.2 ( ). E : y 2 = x 3 + Ax + B K E K (a, b) O E K K- E K E(K) E K Mordell Weil E(K) = {(a, b) K 2 b 2 = a 3 + Aa + B} {O} 11 H. W. Lenstra Jr. Factoring Integers with Elliptic Curves. Annals of Mathematics, vol.126, no.3, pp.649 673 (1987)

30 2018.4.25 48 7.2. 7.1 E a K = F 11 E K 1 2 b 2 b K 3 E(K) 12 (a, b) O 13 1: 7.1 (a, b) a 0 1 2 3 4 5 6 7 8 9 10 a 3 + 3a + 2 2 6 5 5 1 10 5 3 10 10 9 b 4, 7 4, 7 1, 10 4, 7 5, 6 3, 8 E(K) E(K) 7.3 ( ). E K P Q E K- P + Q E(K) P = O P + Q = Q Q = O P + Q = P P, Q O P = (a, b) Q = (a, b) P + Q = O P, Q O P = (a 1, b 1 ) Q = (a 2, b 2 ) a 1 a 2 λ = b 2 b 1 a 2 a 1 P + Q = (a 3, b 3 ) a 3 = λ 2 a 1 a 2, b 3 = λ(a 3 a 1 ) b 1 P, Q O P = Q = (a, b) b 0 µ = 3a2 + A 2b P + Q = (a, b ) a = µ 2 2a, b = µ(a a) b

30 2018.4.25 49 P, Q P Q P Q P = Q P E E P Q x P + Q y E x P + Q E P + Q = Q + P O + P = O P + O = O O + + 7.1. E E(K) + (P + Q) + R = P + (Q + R) E(K) O 7.1 + + E(K) 17 7.3. 7.1 E : y 2 = x 3 + 3x + 2 K = F 11 K- 7.2 P = (2, 4) Q = (3, 4) R = (4, 1) (P + Q) + R K 4 4 3 2 K 1 7 4 6 = 0 P + Q = (6, 7) = 3 (P + Q) + R = (10, 3) P + (Q + R) K 1 4 4 3 = 8 Q + R = (2, 4) = P K 3 22 + 3 = 6 P + (Q + R) = (10, 3) 2 4 (P + Q) + R = P + (Q + R)

30 2018.4.25 50 N p q N = pq p > 3 q > 3 N E : y 2 = x 3 + Ax + B P = (a, b) gcd( 16(4A 3 + 27B 2 ), N) = 1 b 2 N a 3 + Aa + B (a, b) E E p q F p F q E p E q P p q P p P q P p E p (F p ) P q E q (F q ) Z/NZ P Z/NZ E M P M Z/NZ 0 c c N c N gcd(c, N) N N M P p q p 2 Q = (a 1, b 1 ) R = (a 2, b 2 ) Q p + R p = O a 1 a 2 p Q + R a 2 a 1 N N E P M M P p E p (F p ) E p (F p ) M (M P ) p = O p E E p (F p ) Pollard p 1 M E

30 2018.4.25 51 E p (F p ) smooth M N N N 7.4. N = 77 E : y 2 = x 3 + 3x + 2 P = (2, 4) P E Z/NZ N M = 13 N 11 7.2 E 11 (F 11 ) 13 M = (1101) 2 Z/77Z P P + P = 2P = (32, 36), 2P + P = 3P = (26, 32), 3P + 3P = 6P = (40, 17), 6P + 6P = 12P = (68, 18) 12P + P = 13P λ λ = 4 18 2 68 = 14 66 = 7 33 gcd(33, N) = 11 N = 77 11

30 2018.4.25 52 8 Pollard 1988 Pollard 4 1990 12 9 F 9 = 2 29 + 1 155 13 8.12 N > 0 x, y x 2 N y 2 x N ±y x 2 y 2 = (x y)(x + y) N x y x + y N gcd(x ± y, N) N f(x) Q α f(α) = 0 m f(m) N 0 m 12 A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, J. M. Pollard. The Number Field Sieve. In: Proceedings of STOC 1990, pp.564 572 (1990) 13 https://openaccess.leidenuniv.nl/handle/ 1887/2149

30 2018.4.25 53 C C Q α Q(α) Q(α) 8.1 ( ). K F (x) G(x) K F (x) G(x) gcd(f (x), G(x)) F = 0 G = 0 gcd(f, G) = 0 F 0 G 0 F G K 1 gcd(f, G) 8.1. K F (x) G(x) K A(x)F (x) + B(x)G(x) = gcd(f, G) K A(x) B(x). F = 0 G = 0 F 0 G 0 F deg F G deg G F = GQ + R R 0 deg R < deg G Q R R 0 G G R R 0 F G deg(f, G) G c 1 deg(f, G) = 0 F + c G F G A B 8.1. K F (x) 0 K K G(x) F (x) H(x)G(x) 1 F (x) K H(x) H(x) F (x) G(x). F (x) gcd(f (x), G(x)) 1 F (x) G(x) F (x)

30 2018.4.25 54 gcd(f (x), G(x)) = 1 8.1 K H(x) A(x) AF + HG = 1 HG 1 = AF F 8.2. α f(x) f(x) d Q(α) = {a d 1 α d 1 + + a 1 α + a 0 a 0, a 1,..., a d 1 Q}. K Q α C K K K 0 d 1 g(x) g(α) K K K g(x)h(x) f(x) r(x) f(α) = 0 g(α)h(α) = r(α) K K K 0 g(α) g(α) 0 g(x) f(x) 8.1 f(x) g(x) h(x) h(x)g(x) 1 f(x) h(α)g(α) 1 = 0 h(α)g(α) = 1 h(α) K g(α) K Q(α) = K 8.2 C Z α Z[α] Z[α] = {a d 1 α d 1 + + a 1 α + a 0 a 0, a 1,..., a d 1 Z} d f(x) φ: Z[α] Z/NZ φ(a d 1 α d 1 + + a 1 α + a 0 ) = a d 1 m d 1 + + a 1 m + a 0 mod N f(m) N 0 8.2 ( ). R

30 2018.4.25 55 1. R 0 r 1, r 2 r 1 r 2 0 R 2. a, b R ac = b c R b a a b 3. R p R \ R R a, b p ab p a p b p R 4. R R 0 r c R 0 p 1,..., p k R r = cp 1 p k R r = cp 1 p k r 1. Q(α) Z[α] 2. Z[α] Z[α] x Z/NZ φ(x) x φ Z/NZ x Z[α] φ Z/NZ φ(x) x, y 8.1. N = 2117 f(x) f(x) = x 2 + 1 m = 46 f(m) = N f(m) N 0 α = 1 C f(α) = 0 α Z[α] = Z[ 1]

30 2018.4.25 56 a + bα a, b Z Z[α] φ(a + bα) = a + bm mod N β 1 = 1 + α, β 2 = 1 + 2α, β 3 = 2 + 3α, β 4 = 2 + α, β 5 = 3 + α, β 6 = 3 + 4α, β 7 = 5 + α, β 8 = 7 + α, β 9 = 11 + 2α Z[α] π 1 = 1 + α, π 2 = 1 + 2α, π 3 = 2 + α, π 4 = 2 + 3α α 2 = 1 β 1 = α π 1 β 2 = α π 3 β 3 = π 4 β 4 = α π 2 β 5 = α 3 π 1 π 2 2 β 6 = π 3 β 7 = α 3 π 1 π 4 2 β 8 = π 1 π 2 3 β 9 = α π 3 α 4 = 1 β 1 β 9 = α 10 π 4 1 π 4 2 π 6 3 π 2 4 = (απ 2 1 π 2 2 π 3 3 π 4 ) 2 Z/NZ φ(β 1 β 9 ) = ( φ(α)φ(π 1 ) 2 φ(π 2 ) 2 φ(π 3 ) 3 φ(π 4 ) ) 2

30 2018.4.25 57 φ(β 1 ) = 45 = 3 2 5 φ(β 2 ) = 91 = 7 13 φ(β 3 ) = 140 = 2 2 5 7 φ(β 4 ) = 44 = 2 2 11 φ(β 5 ) = 49 = 7 2 φ(β 6 ) = 187 = 11 17 φ(β 7 ) = 51 = 3 17 φ(β 8 ) = 39 = 3 13 φ(β 9 ) = 81 = 3 4 φ(β 1 β 9 ) = φ(β 1 ) φ(β 9 ) = 2 4 3 8 5 2 7 4 11 2 13 2 17 2 = (2 2 3 4 5 7 2 11 13 17) 2 ( (2 2 3 4 5 7 2 11 13 17) 2 N φ(α)φ(π1 ) 2 φ(π 2 ) 2 φ(π 3 ) 3 φ(π 4 ) ) 2 x = 2 2 3 4 5 7 2 11 13 17, y = φ(α)φ(π 1 ) 2 φ(π 2 ) 2 φ(π 3 ) 3 φ(π 4 ) x = 192972780, y = 46 47 2 93 2 48 3 140 = 13607275958599680 x 2 N y 2 x N ±y gcd(x + y, N) = gcd(13607276151572460, 2117) = 29 N 29 N = 29 73

30 2018.4.25 58 β 1 β 2 Z[α] φ(β 1 )φ(β 2 ) β 1, β 2, Z[α] φ(β i ) β i Z[α] a + bα a b