2008 (2008/09/30)

1 ISBN 7 1.1 ISBN................................ 7 1.2.......................... 8 1.3................................ 9 1.4 ISBN.............................. 12 2 13 2.1..................... 13 2.2................................. 16 2.3....................... 17 2.4....................... 19 2.5.......................... 27 2.6.......................... 29 3 33 3.1................. 33 3.2............................... 34 3.3 RSA................................... 38 3.4 (1)............ 40 3.5 (2)................ 43 3.6............................. 45 4 47 4.1........................... 47 4.2..................... 48 4.3........... 49 4.4 (Solovay Strassen )..................... 52 3

10,000 1,000,000 (code) (cryptography) 5

Chapter 1 ISBN ISBN (International Standard Book Number, ) ( ) ISBN 2007 2006 ISBN 4-7973-0148-1 ISBN 10 ( ) 9 04S1099Z ISBN 1.1 ISBN ISBN 10 9 ISBN 4-7973-0148-?? 9 1 9 4 1 + 7 2 + 9 3 + 7 4 + 3 5 + 0 6 + 1 7 + 4 8 + 8 9 = 199 199 11 18 1 1 1.1.1. ISBN 479730267? 479790267? 084933988? 11 0 10 10 10 X ISBN 10 X 7

8 CHAPTER 1. ISBN 1.2 ISBN ISBN a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 1,, a 9 0 9 a 10 0 10 ( X 10 ) ( 9 1=1 ia i ) 11 =? a 10? 9 ia i a 10 1=1 11 11 a 10 11 9 10 ia i + 10 a 10 = ia i 1=1 11 n a, b n a b (mod n) a b n a b (mod n) l a = b + nl a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 ISBN 10 ia i 0 (mod 11) 1=1 4797a 5 01481 ( 5 ) a 5 5a 5 + 249 5a 5 + 7 0 (mod 11) 1=1

1.3. 9 4 5a 5 4 (mod 11) 5 a 5 4 5 a 5 0 9 5 3 = 15 4 (mod 11) a 5 = 3 1.2.1. ISBN 123?567890 123456?890? 1.3 ISBN ax b (mod 11) x x 1.3.1. 3x 1 (mod 10). x 0, 1, 2, 3, 3 7 1 (mod 10) 3 17 1 (mod 10) 3 27 1 (mod 10) x = 7, 17, 27, l x = 7 + 10l 3 (7 + 10l) = 21 + 30l 1 (mod 10) 1.3.2. ax b (mod n) x 0 x 1 x 0 (mod n) x 1. x 1 x 0 (mod n) l x 1 = x 0 + ln ax 1 = a(x 0 + nl) = ax 0 + anl ax 0 b (mod n)

10 CHAPTER 1. ISBN n 0 n 1 0 n 1 (n ) 1.3.3. 4x 1 (mod 9) (9 ) 1.3.4. 2x 4 (mod 6), 2x 1 (mod 6). 6 0 5 2 0 0 (mod 6) 2 1 2 (mod 6) 2 2 4 (mod 6) 2 3 0 (mod 6) 2 4 2 (mod 6) 2 5 4 (mod 6) 2x 4 (mod 6) x = 2, 5 2x 1 (mod 6) ISBN ax b (mod n) ax + ny = b x, y 1.3.5. a, b d a b x, y ax + by = d ( x, y ) a b (greatest common divisor) gcd(a, b) m d = gcd(a, b) m = dl ax 0 + by 0 = d x 0, y 0 a(x 0 l) + b(y 0 l) = dl = m ax + by = m x = x 0 l, y = y 0 l m d ax + by = m d d x, y

1.3. 11 1.3.6. a, b d = gcd(a, b) ax + by = m x, y d m 1.3.7. ax b (mod n) gcd(a, n) b ax b (mod n) d = gcd(a, n) d 1 a = a o d, n = n 0 d 0 < n 0 < n x 0 ax b (mod n) a(x 0 + n 0 ) = ax 0 + a 0 dn 0 = ax 0 + a 0 n ax 0 b (mod n) x = x 0 + n 0 0 < n 0 < n x 0 + n 0 x 0 (mod n) d = gcd(a, n) = 1 x 0, x 1 ax b (mod n) ax 0 b (mod n), ax 1 b (mod n) a(x 0 x 1 ) 0 (mod n) a(x 0 x 1 ) n a n x 0 x 1 n x 0 x 1 (mod n) ax b (mod n) n 1.3.8. ax b (mod n) gcd(a, n) = 1 n a 0 (mod n) ax b (mod n) 1.3.9. 7x + 9y = 1 x, y 1.3.10. 14x + 6y = 4 x, y 1.3.11. 14x + 6y = 1 x, y ISBN 11 ISBN 10 9 11 10 = 9 + 1 12 = 11 + 1 ax b (mod n) a, b, n

12 CHAPTER 1. ISBN 1.4 ISBN ISBN ISBN ISBN 1234567890 ISBN ISBN 123456789X 2234567890 ISBN ( ISBN ISBN 10 10 X 10 1 ISBN ISBN ) ISBN ( ) ISBN

Chapter 2 ISBN ( ) (Hamming code) 2.1 0 1 0 1 F 2 = {0, 1} 0 1 F 2 F 2 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 0 0 = 0, 0 1 = 0, 1 0 = 0, 1 1 = 1 1 + 1 = 2 2 0 0 1 + =, + =, + =, + = =, =, =, = 2 = 1 + 1 = 0 a + a = 2a = 0 a = 0 a = a 0 1 13

14 CHAPTER 2. F 2 2 n n {0, 1,, n 1} ax b (mod n) ( a ) n 1.3.8 n ax 1 (mod n) c c 1 a c a p F p = {0, 1,, p 1} p F 2 p 2 ( ) p n n ( 1 2 3 4 ), 4 3 0 0 ( 1 2 3 4 ) + ( 1 1 0 2 ) = ( 2 1 3 6 ) (1 2 3 4) (1 1 0 2) 1 1 + 2 ( 1) + 3 0 + 4 2 = 7 u, v (u, v) (u, v) = (v, u) (u, v) = 0 u v 2.1.1. O xy- A(a, b), B(c, d) OA OB ( ) (a b) (c d) 3 1 2 3

2.1. 15 2.1.2. (u, v + w) = (u, v) + (u, w) ( (u, v) = (u, w) = 0 (u, v + w) = 0 ) m n m n 2 3 ( 1 2 ) 3 4 5 6 1 2 1 2 1 2 3 1 1 1 1 2 2 3 4 3 3 2 3 i j (i, j)- 0 0 m n A A t A t A n m (i, j)- A (j, i)- m n l m M m n N MN l n (i, j) M i N j ( ) ( ) ( 1 2 3 4 5 4 ) 1 0 0 1 1 1 = ( 2 5 0 9 2 3 3 2 2 2 2.1.3. 1 0 0 1 1 1 ( 1 2 3 4 5 4 ) n 1 n n n 1 m n n (n 1 ) m (m 1 ) F 2 )

16 CHAPTER 2. 2.1.4. F 2 ( 1 0 1 0 1 0 2.1.5. ) 1 0 1 : (AB)C = A(BC) : (A + B)C = AC + BC, A(B + C) = AB + AC n n 1, 0 n I n 2.1.6. l n M, n m N MI n = M, I n N = N 2.2 ( ) 1 4 ( 0 1 4 ) 7 7 F 2 G, H G = H = 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 G H F 2 0 1 4 ( 4 4 1 R. W. Hamming, 1915 1998,

2.3. 17 ) v = (1 0 1 0) vg (1 0 1 0) 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 = (1 0 1 0 1 0 1) 4 7 3 ( 4 ) 3 (1 0 0 0 1 0 1) ( ) H 011 2 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 1 = 0 2 2 + 1 2 1 + 1 2 0 = 0 + 2 + 1 = 3 3 ( ) 3 (1 0 1 0 1 0 1) ( 4 ) (1 0 1 0) 0 2.2.1. v vg 2.2.2. 0 1 1 2.3 G, H G, H 1. H 1 7 2

18 CHAPTER 2. H 0 0 0 1 1 1 1 H = 0 1 1 0 0 1 1 1 0 1 0 1 0 1 2. G 4 1 0 ( ) vg 4 v 4 H 7 3 3. G H G G 1 (1000abc) H a + b + c = 0 b + c = 0 1 + a + c = 0 (a, b, c) = (0, 1, 1) 2.3.1. G G H v 1 0 1 1 1 0 0 0 0 1 1 (1 0 0 0) 0 1 0 0 1 0 1 0 0 1 0 1 1 0 = (1 0 0 0 0 1 1) 0 0 0 1 1 1 1 G 1 v = (1 0 1 0) vg G 1 3 (1 0 1 0) 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 = (1 0 1 0 1 0 1) = (1 0 0 0 0 1 1) + (0 0 1 0 1 1 0) vg H H G 0

2.4. 19 = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 + 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 = 0 0 0 0 w (7 ) i 1 0 7 e i i w + e i (F 2 1 0 1 1 0 ) w Hw = 0 H(w + e i ) = Hw + He i = He i H e i H i 1 10 2.4 F 2 x + y + z = 6 (1) 2x + 3y + 4z = 20 (2) 3x + 2y + 3z = 16 (3) x = y = z =

20 CHAPTER 2. x + y + z = 6 (1) = (1) y + 2z = 8 (2) = (2) (1) 2 y = 2 (3) = (3) (1) 3 x + y + z = 6 (1) = (1) y + 2z = 8 (2) = (2) + 2z = 6 (3) = (3) + (2) x + y + z = 6 (1) = (1) y + 2z = 8 (2) = (2) z = 3 (3) = (3) (1/2) x = 1 (1) (2) (3) y = 2 (2) (3) 3 z = 3 x = 1, y = 2, z = 3 (1) (0 ) (2) (3) ( ) 1 1 1 6 2 3 4 20 3 2 3 16 1 1 1 2 3 4 3 2 3 0 1 1 1 6 1 1 1 6 1 1 1 6 2 3 4 20 0 1 2 8 0 1 2 8 3 2 3 16 0 1 0 2 0 0 2 6 1 1 1 6 0 1 2 8 0 0 1 3 1 0 0 1 0 1 0 2 0 0 1 3

2.4. 21 (1) (0 ) (2) (3) ( ) 1 1 1 6 2 3 4 20 3 4 5 26 1 1 1 6 0 1 2 8 0 0 0 0 1 1 1 6 0 1 2 8 0 1 2 8 1 0 1 2 0 1 2 8 0 0 0 0 3 { x z = 2 y + 2z = 8 (x, y, z) = ( 2, 8, 0), ( 3, 10, 1) 1 1 1 6 1 1 1 6 2 3 4 20 0 1 2 8 3 4 5 27 0 1 2 9 1 1 1 6 0 1 2 8 0 0 0 1 3 0 = 1 1 0 1 2 0 1 2 8 0 0 0 1 (1) 0 1 2 3 4 0 1 2 3 0 0 0 2

22 CHAPTER 2. 1 2 3 0 1 2 0 2 0 0 0 1 (2) 1 1 2 3 4 0 1 2 3 0 0 0 1 (3) 1 0 1 0 3 0 0 1 2 0 0 0 0 1 0 0 ( ) Step 1. 1 0 1 1 0 2 2 0 3 1 0 0 2 2 0 2 0 3 4 (1) Step 2. a 1/a 1 Step 3. (i, j) (i, j) a 0 i i a (i, j) 0

2.4. 23 Step 1, 2, 3 (1), (2), (3) ( ) x 1,, x n 1 0 0 b 1 0 1 0 b 2......... 0 0 1 b n 0 0 0... 0 0 0 (x 1,, x n ) = (b 1,, b n ) 0... 0 0 1 0 0 0... 0 0 0 ( ) 0 = 1 1 0 1 0 1 2 0 1 2 0 2 0 0 0 0 1 3 3 0 0 0 0 0 0 3 5 x 3 x 5 x 3 = s x 5 = t 1 x 1 + x 3 + x 5 = 2 x 3 = s x 5 = t x 1 = s t + 2

24 CHAPTER 2. x 1 = s t + 2 x 2 = 2s 2t x 3 = s (s, t ) x 4 = 3t + 3 x 5 = t s, t 2.4.1 ( ). x + y + z = 3 x y + z = 1 x + z = 2 1 1 1 1 1 1 1 0 1 x y z = s x = 2 s y = 1 z = s x y = z 2 1 0 + s 2.4.2 ( ). 0 0 1 1 1 1 1 1 1 0 1 x + y + z = 0 x y + z = 0 x + z = 0 x y z = 0 0 0,, 1 0 1 3 1 2 x = s y = 0 z = s x y z = s 1 0 1

2.4. 25 2.4.3. x + y + z = 4 (1) 2x + y + z = 6 x y + 2z = 3 (3) (5) x + y + z = 3 x + y + 2z = 6 x + y + z = 3 x + y + 2z + 2u = 2 2x + y + z + 2u = 4 x + 2y + 5z + 5u = 6 (2) (4) (6) x + y + z = 3 x + y + 2z = 6 x y + z = 2 { x + 2y + 3z = 4 2x + 3y + 4z = 5 x + 2y + z = 0 2x 3y 3z = 0 3x + y + 2z = 0 4x + y z = 0 2.4.4. F 2 x + y + z = 1 x + y = 1 (1) x + y = 0 (2) x + z = 1 x + z = 0 y + z = 1 R n ( ) n R n F 2 F 2 n F 2 n F 2 R n ( ) a v = (v 1 v n ) av = (av 1 av n ) R n V R n (1) v, w V v + w V (2) v V a av V 2.4.5. v 1,, v r n r i=1 a iv i (a i ) R n v 1,, v r 2.4.6. r i=1 a iv i (a i ) R n v 1,, v r V v r = 0 V v 1,, v r 1 V V V V V 2.4.7. V = R n R n e i i 1 0 e 1,, e n V V n

26 CHAPTER 2. v 1,, v r V v 1,, v r r n M M M M V M M 0 V V M ( 0 r ) 2.4.8. v 1 = (1 1 0), v 2 = (1 0 1), v 3 = (2 1 1) 1 1 0 1 0 1 2 1 1 1 0 1 0 1 1 0 0 0 (1 0 1), (0 1 1) 2 ( v 1, v 2 ) 2.4.9. v 1 = (1 2 3), v 2 = (4 5 6), v 3 = (7 8 9) 2.4.10. F 2 v 1 = (1 1 0), v 2 = (1 0 1), v 3 = (0 1 1) 2.4.11 ( ). x 1 x 2. = s 1 + s 2 + + s m a 11 a 12. a 21 a 22. a m1 a m2. x n a 1n a 2n a mn s 1, s 2,, s m R n r m n r m = n r V R n V V V 2.4.12. V R n

2.5. 27 V ( ) V ( ) V r V r n M w V w n Mw = 0 V M x 1. x n = 0 n r 2.4.13. (1 1 1) R 3 V V 2.4.14. (1 1 1 1) F 2 4 V V 2.5 k n (n, k) (n, k) H 1. H (n k) n n k H n k H V H n k V F 2 n n k C = V ( C ) C k 2. G k n C (k ) v vg G vg C H vg H 0 0 (vg ) w i 1 0

28 CHAPTER 2. n e i w + e i Hw = 0 H(w + e i ) = He i H i H H 0 2.5.1. H H 0 2.5.2. n 1 2 n 1 2 H H n (2 n 1) n H 0 H (2 n 1, 2 n n 1) ( ) F 2 1 1 1 t w w + e e t H(w + e) = He t e He He e t H t e He 2.5.3. (23, 12) 3 3 4 7 4 G 1 0 0 0 1 0.. G =........ 0 0 1 G C

2.6. 29 2.5.4. G m n m n m K GK = I m (I m m ). x = x 1. x n e i i 1 n G m Gx = e i y i K = (y 1 y n ) GK = I m 2.5.4 K vgk = v K 2.5.5. 2 2 3 G = ( 1 1 1 0 1 1 ) GK = I 2 3 2 K 2.6 0 1 YES NO 100 100 100 1 m 50 cm

30 CHAPTER 2. 50 cm (n, k) k n 2 k 2 k 2 n F 2 n u, v 2 k d d t = d/2 1 t = (d 1)/2 t F 2 n t n k n F 2 n t ( ) (Singleton ) n k + 1 d n k d (7, 4) 2 7 2 4 1 1 7 8 2 4 8 = 2 7 2.6.1. 2.5.2

2.6. 31 2.6.2. 2.5.3 (23, 12) 3 2

Chapter 3 3.1 3 SHINSHUUNIVERSITY ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC VKLQVKXXQLYHUVLWB 1 3.1.1. QDJDQRNHQPDWVXPRWRVKL n SHINSHUUNIVERSITY 10 1 J. Caesar, BC100 BC44, CRSXCREEXSFOBCSDI 33

34 CHAPTER 3. n 25 (26 ) 26 A Z, B H, C T e z NAGANO A 1, 2, 3 14, 1, 7, 1, 14, 15 1 14 2 1 3 7 4 1 5 14 6 15 7 14 10 3.1.2. 10?? 3.1.3 ( ). 3.2 RSA 2 1 2 2 m, n mn

3.2. 35 m 1 3.2.1. 100 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 RSA 3.2.2.. p 1 < p 2 < < p r n = p 1 p 2 p r + 1 p r n m n p i 3.2.3. 100 3.2.4 ( ). n 2 n 1 1 3.2.5. 2 n 1 ( ) n. x m 1 = (x 1)(x m 1 + x m 2 + + x + 1) n n = lm, l 2, m 2 2 n 1 = (2 l ) m 1 = (2 l 1)((2 l ) m 1 + (2 l ) m 2 + + (2 l ) + 1) 1 < 2 l 1 < 2 n 1 2 n 1 n 2 n 1 2 11 1 = 2047 = 23 89 3.2.6. 6 6 1, 2, 3 1 + 2 + 3 = 6 6 1 Mersenne, 1588 1648,

36 CHAPTER 3. 2 n 1 2 n 1 (2 n 1) ( ) 3.2.7 ( ). n 2 n + 1 1 n = 1, 2, 4, 8, 16 ( 2 n + 1 = 3, 5, 17, 257, 65537) n n n 7 3.2.8. 2 n + 1 ( ) n 2 (2 e ). m x m + 1 = (x + 1)(x m 1 x m 2 + x + 1) n m n = lm 2 n + 1 = (2 l ) m + 1 = (2 l + 1)((2 l ) m 1 (2 l ) m 2 + 2 l + 1) 1 < 2 l + 1 < 2 n + 1 2 n + 1 n 2 2 n + 1 2 32 + 1 = 4294967297 = 641 6700417, 2 64 + 1 = 18446744073709551617 = 274177 67280421310721 5 3.2.9 ( ). n (n 1)! 1 (mod n) ((n 1)! = 1 2 (n 2) (n 1) ) 3.2.10. (3 1)! = 1 2 = 2 1 (mod 3) (5 1)! = 1 2 3 4 = 24 1 (mod 5) (7 1)! = 1 2 6 = 720 1 (mod 7) (11 1)! = 1 2 10 = 3628800 1 (mod 11) 1 Fermat, 1607 1665,

3.2. 37 (4 1)! = 1 2 3 = 6 1 (mod 4) (6 1)! = 1 2 3 4 5 = 120 1 (mod 6) 3.2.11. n = 13, 15 3.2.12 ( ). p a p a p 1 1 (mod p) 3.2.13. p = 5, a = 3 3 5 1 = 81 1 (mod 5) p p = 4, a = 3 3 4 1 = 27 3 (mod 4) a = 1 p p n n n ϕ(n) 1 3.2.14 ( ). n a n a ϕ(n) 1 (mod n) p ϕ(p) = p 1 p p 3.2.14 3.2.12 3.2.15. ϕ(4), ϕ(6), ϕ(8), ϕ(9), ϕ(10) 3 ϕ(8) 1 (mod 8) p, q n = pq ( ) 3.2.16 ( ). m, n a, b x a (mod m), x b (mod n) x mn 1 Euler, 1707 1783,

38 CHAPTER 3. 3.2.17. 5 3 7 2 3.2.18. p, q ϕ(pq) = (p 1)(q 1). pq pq p q q p p q pq pq p + q 1 ϕ(pq) = pq p q + 1 = (p 1)(q 1) 3.2.19. p, q a m a m(p 1)(q 1)+1 a (mod pq).. a pq 3.2.14 3.2.18 a (p 1)(q 1) 1 (mod pq) a m(p 1)(q 1)+1 = (a (p 1)(q 1) ) m a a (mod pq) a pq (1) a p q (2) a q p (3) a p q 3 (3) a m(p 1)(q 1)+1 0 a (mod pq) (1) a q 1 1 (mod q) a m(p 1)(q 1)+1 = (a q 1 ) m(p 1) a a (mod q). a 0 (mod p) a m(p 1)(q 1)+1 0 (mod p) 3.2.16 pq a a m(p 1)(q 1)+1 a (mod pq) (2) 3.3 RSA RSA (Rivest, Shamir, Adleman, 1977) ( ) A A

3.3. RSA 39 (1) p, q. ( p, q 200 ) (2) N = pq. (3) L = (p 1)(q 1). (4) L e. (5) ed 1 (mod L) d. N e p, q, L, d M N M M e (mod N) e, N C = M e d C C d (mod N) C d M ed M (mod N) M 3.3.1. p = 7, q = 11 N = 7 11 = 77, L = (7 1)(11 1) = 60 e = 7 7d 1 (mod 60) d = 43 ( ) M = 50 M = 50 C = M e = 50 7 8 (mod 77) C d = 8 43 50 (mod 77) 3.3.2. p = 3, q = 11, e = 7 N, L, d M = 15 RSA C d M ed M (mod N) ed 1 (mod L), L = (p 1)(q 1) m ed = m(p 1)(q 1) + 1 3.2.19 a a ed a (mod pq) d d ed 1 (mod L) L = (p 1)(q 1)

40 CHAPTER 3. d L N = pq p, q pq p, q 200 ( ) RSA 3 RSA 3.3.3. 55973 223 251 RSA p, q 200 N, L, e, d 400 1. 200 2. p, q N, L e ed 1 (mod L) d 3. M 400 M e (mod N) (400 400 ) 3.4 (1) 1 3.4.1 ( ). a, b a = qb + r 0 q 0 r < b r 3.4.2 ( ). a, b r 0 = a, r 1 = b i > 1 r i 1 = q i 1 r i + r i+1 (0 r i+1 < r i ) 1 Euclid, BC365 BC275,

3.4. (1) 41 r i+1 0 r i+1 < r i {r i } r i > 0 n r n+1 = 0 gcd(a, b) = r n 3.4.3. gcd(200, 144). gcd(200, 144) = 8 3.4.4. gcd(240, 252) 200 = 1 144 + 56 144 = 2 56 + 32 56 = 1 32 + 24 32 = 1 24 + 8 24 = 3 8 + 0 3.4.5. a, b a = qb + r (0 b < r, q ) gcd(a, b) = gcd(b, r). d = gcd(a, b) d b r = a qb b r d gcd(b, r) d = gcd(b, r) d b a = qb + r a b d gcd(a, b) d = d. 3.4.5 gcd(a, b) = gcd(r 0, r 1 ) = gcd(r 1, r 2 ) = = gcd(r n 1, r n ) r n+1 = 0 r n 1 r n gcd(r n 1, r n ) = r n 1.3.5 3.4.6 ( 1.3.5). a, b d a b x, y ax + by = d

42 CHAPTER 3. x, y x, y ( ) 3.4.7 ( ). r 0 = a, r 1 = b, r i 1 = q i 1 r i + r i+1 (0 r i+1 < r i ), r n+1 = 0 r i = x i a + y i b x i, y i x n, y n s, t x i, y i r i+1 = r i 1 q i 1 r i = (x i 1 a + y i 1 b) q i 1 (x i a + y i b) = (x i 1 q i 1 x i )a + (y i 1 q i 1 y i )b x i+1 = x i 1 q i 1 x i, y i+1 = y i 1 q i 1 y i r 0 = a = 1 a + 0 b, r 1 = b = 0 a + 1 b x 0 = 1, y 0 = 0, x 1 = 0, y 1 = 1 x i, y i 3.4.8. 200s + 144t = gcd(200, 144) = 8 s, t. 3.4.3 x 0 = 1, y 0 = 0 x 1 = 0, y 1 = 1 x 2 = 1 1 0 = 1, y 2 = 0 1 1 = 1 x 3 = 0 2 1 = 2, y 3 = 1 2 ( 1) = 3 x 4 = 1 1 ( 2) = 3, y 4 = 1 1 3 = 4 x 5 = 2 1 3 = 5, y 5 = 3 1 ( 4) = 7 200 ( 5) + 144 7 = 8 3.4.9. gcd(220, 252) 220s + 252t = gcd(220, 252) s, t ax b (mod n) gcd(a, n) b ( 1.3.7) gcd(a, n) b b = b 0 gcd(a, n) x, q ax + nq = b ax 0 + nq 0 = gcd(a, n) x 0, q 0 x = b 0 x 0, q = b 0 q 0 ax + nq = b ( ) ( ) 3.4.10. 240x 36 (mod 252) 3.4.11. RSA p = 7, q = 11 e = 13 d (ed 1 (mod (p 1)(q 1)) )

3.5. (2) 43 3.5 (2) RSA (400 ) a, e, n a e (mod n) 102 100 (mod 123) 100 100 200 123 123 102 2 = 10404 72 102 3 72 102 = 7344 87 102 4 87 102 = 8874 18 100 ( ) 102 100 (mod 123) 100 2 1100100 100 = 2 6 + 2 5 + 2 2 102 100 = 102 (26 +2 5 +2 2) = 102 (26) 102 (25) 102 (22 ) 102 (2i) 102 (2i) = (102 (2i 1) ) 2 102 (20 ) 102 (21 ) 102 (22 ) 102 (23 ) 102 (24 ) 102 (25 ) 102 (26 ) 102 1 = 102 102 2 = 10404 72 72 2 = 5184 18 18 2 = 324 78 78 2 = 6084 57 57 2 = 3249 51 51 2 = 2601 18 102 100 18 51 18 42 (mod 123) a e (mod n) 2 log 2 e e 400 1300

44 CHAPTER 3. 3.5.1. 100 1200 100 mod 1234 3.5.2. 31 31 (mod 71), 3 100 (mod 127) a e (mod N) e 400 1300 a (2i) (mod N) ( ) 1300 (1) a, e, N (2) ans = 1 (3) e = 0 ans (4) e 1 (mod 2) ans ans a (mod N) (5) e e/2 (6) a a 2 (mod N) (7) (3) a, e, N, ans 4 e (5) (3) e = 0 102 100 (mod 123) [1] N = 123 ( ) e = 100, a = 102, ans = 1 ( ) [2] e 0 (mod 2) : ans = 1, e = 50, a = 102 2 (mod N) = 72 [3] e 0 (mod 2) : ans = 1, e = 25, a = 72 2 (mod N) = 18 [4] e 1 (mod 2) : ans = 1 18 (mod N) = 18, e = 12, a = 18 2 (mod N) = 78 [5] e 0 (mod 2) : ans = 18, e = 6, a = 78 2 (mod N) = 57 [6] e 0 (mod 2) : ans = 18, e = 3, a = 57 2 (mod N) = 51 [7] e 1 (mod 2) : ans = 18 51 (mod N) = 57, e = 1, a = 51 2 (mod N) = 18 [8] e 1 (mod 2) : ans = 57 18 (mod N) = 42, e = 0, a = 18 2 (mod N) = 78 [9] e = 0 ans = 42

3.6. 45 ans e a 1 100 102 1 50 72 1 25 18 1 18 = 18 12 78 18 6 57 18 3 51 18 51 = 57 1 18 57 18 = 42 0 3.5.3. RSA p = 13, q = 17 N = pq e = 11 (1) L = ϕ(pq) (2) d (d ed 1 (mod L) ) (3) m = 3 (4) (3) (m = 3) 3.6 A A B A A B M N B N A M N A B A A B C C B ( ) B C

Chapter 4 RSA RSA 200 200 4.1 4.1.1. N 2 N 1 2 4.1.2. N 2 N N N 3 N 1 N N = mn 2 m, n m, n N N 47

48 CHAPTER 4. 4.1.3. N 2 N N N 3 N N N 1 N N = mn, m m n 4.1.4. N 2 N N N 3 N N N 1 4.1.5 ( ). N (1) 1 N ( ) (2) 1 (3) (N N ) (4) N (3) (5) N N ( ) N N 200 4.1.6. 100 4.2 p p a a p 1 1 (mod p) p a a = 2, 3 a p 1 (mod p) 1 p a p p 1 Eratosthenes, BC275 BC194,

4.3. 49 4.3 p a p x x 2 a (mod p) a p ( ) a 1 p ( ) a = p 0 (a p ) 1 (a p ) 1 (a p ) ( ) 4.3.1. p = 7 1 2 1, 2 2 4, 3 2 2, 4 2 2, 5 2 4, 6 2 1 1, 2, 4 3, 5, 6 ( ) 1 = 7 ( ) 2 = 7 ( ) 4 = 1, 7 ( ) 3 = 7 ( ) 5 = 7 ( ) 6 = 1 7 4.3.2. ( a 11), a = 1, 2,, 10, 4.3.3. p a, b ( ) ( ) a b (1) a b (mod p) = p p (2) ( ) ab = p ( a p ) ( ) b p ( ) ab 2 (3) b p = p (4) ( ) 1 = 1, p ( ) 1 = ( 1) (p 1)/2, p 1 Legendre, 1752 1833, ( ) a p ( ) 2 = ( 1) (p2 1)/8 p

50 CHAPTER 4. ( p (5) [ ] q p ( ) ( ) q p q = ( 1) (p 1)(q 1)/4 q p ) ( ) q = ( 1) (p 1)(q 1)/4 p ( ) ( ) 1 2. p 1 (mod 4) 1 p 3 (mod 4) 1 p ( ) ( ) p p q p 1, 7 (mod 8) 1 p 3, 5 (mod 8) 1 p 3 q p (mod 4) q 3 (mod 4) 1 1 ( ) 24 4.3.4. 31. 4.3.3 (2) ( ) 24 = 31 ( ) 3 ( ) ( ) ( ) 2 3 2 3 = 31 31 31 31 (4) ( ) 2 = ( 1) (312 1)/8 = ( 1) 120 = 1 31 (5), (1) ( ) ( ) ( ) 3 31 1 = ( 1) (3 1)(31 1)/4 = ( 1) 15 = ( 1) 1 = 1 31 3 3 ( ) 24 = 1 31 ( ) 21 4.3.5. 31 4.3.3 n a n n = p e 1 1 p e 2 2 p er r ( ) e1 ( a a J(a, n) = p 1 p 2 ) e2 ( ) er a p r 1 n 4.3.3 1 Jacobi, 1804 1851,

4.3. 51 4.3.6. n a, b (1) a b (mod n) J(a, n) = J(b, n) (2) J(ab, n) = J(a, n)j(b, n) (3) gcd(a, n) > 1 J(a, n) = 0 (4) J(1, n) = 1, J( 1, n) = ( 1) (n 1)/2, J(2, n) = ( 1) (n2 1)/8 (5) a, b J(a, b)j(b, a) = ( 1) (a 1)(b 1)/4 J(a, b) = ( 1) (a 1)(b 1)/4 J(b, a) 4.3.7. J(26, 45). 4.3.6 (2) J(26, 45) = J(2, 45)J(13, 45) (4) J(2, 45) = 1 (5) J(2, 13) = 1 J(13, 45) = ( 1) (13 1)(45 1)/4 J(45, 13) = J(6, 13) = J(2, 13)J(3, 13) J(3, 13) = ( 1) (3 1)(13 1) J(13, 3) = J(1, 3) = 1 J(26, 45) = 1 J(a, b) a a = 2 e a 0 (a 0 ) J(a, b) = J(2, b) e J(a 0, b) (5) 2 4.3.8. J(28, 45) a, b J(a, b) 4.3.9. p a ( ) a a (p 1)/2 (mod p) p a p ( ) a 0 a = 1 p b a b 2 (mod p) a (p 1)/2 b p 1 1 (mod p) ( ) a a = 1 a (p 1)/2 p (mod p) 2 1 ±1 1

52 CHAPTER 4. 4.4 (Solovay Strassen ) Solovay Strassen 4.4.1 (Solovay Strassen ). p (1) 1 < a < p 1 (2) gcd(a, p) > 1 p (3) j a (p 1)/2 (mod p) ( ) (4) J(a, p) (5) j J(a, p) (mod p) p (6) j J(a, p) (mod p) p 1/2 ( ) a p = J(a, p) 4.3.9 j J(a, p) (mod p) p p 1/2 (200 p ) p Solovay Strassen a 25 2 7, 18 45 2 19, 26 49 4 18, 19, 30, 31 65 6 8, 14, 18, 47, 51, 57 85 6 13, 16, 38, 47, 69, 72 91 16 9, 10, 12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79, 81, 82 105 6 8, 13, 41, 64, 92, 97 117 2 53, 64 121 8 3, 9, 27, 40, 81, 94, 112, 118 125 2 57, 68 133 16 11, 12, 27, 30, 31, 39, 58, 64, 69, 75, 94, 102, 103, 106, 121, 122 145 6 12, 17, 59, 86, 128, 133 153 6 35, 55, 64, 89, 98, 118 165 2 34, 131 169 10 19, 22, 23, 70, 80, 89, 99, 146, 147, 150 175 4 24, 51, 124, 151 185 6 36, 43, 68, 117, 142, 149 a p 3 (p 3)/2 (9, 15, 21, 27, 33, 35, 39, 51, 55, 57, 63, 69, 75, 77, 81, 87, 93, 95,

4.4. (SOLOVAY STRASSEN ) 53 99, 111, 115, 119, 123, 129, 135, 141, 143, 147, 155, 159, 161, 171, 177, 183, 187, 189, 195) a Solovay Strassen 1/2 Solovay Strassen a ( Solovay Strassen ) 10 1/2 10 = 1/1024 ( ) 4.4.2. p Solovay Strassen a p a

[4] [3] [2] [1] ( ) 55

1.1.1. 4, 1, X. 1.2.1. 7, 4. 1.3.3. x 7 (mod 9). 1.3.9. (x, y) = (4, 3) 1.3.10. (x, y) = (2, 4) 1.3.11. 1 2 3 2.1.3. 4 5 4 3 3 1 ( ) 0 2.1.4. 0 2.4.3. s (1) (x, y, z) = (2, 1, 1) (2) (3) (x, y, z) = (0, 0, 3) (4) (x, y, z) = ( 2 + s, 3 2s, s) (5) (x, y, z, u) = ( 6 + s, 16 3s, s, 4) (6) (x, y, z) = (3s, 5s, 7s) 2.4.4. (1) (x, y, z) = (1, 1, 1) (2) 2.4.9. (1 2 3), (0 1 2). 2 2.4.10. (1 1 0), (0 1 1). 2 2.4.13. (1 0 1), (0 1 1). 2.4.14. (1 0 0 1), (0 1 0 1), (0 0 1 1). 2.5.3. 1 + 23 + 23 C 2 + 23 C 3 = 2048. 3.1.1. NAGANOKENMATSUMOTOSHI 3.1.2. 45 10 3.2.3. 101, 103, 107 3.2.6. 28. 3.2.15. ϕ(4) = 2, ϕ(6) = 2, ϕ(8) = 4, ϕ(9) = 6, ϕ(10) = 4. 3.2.17. 23. 3.3.2. N = 33, L = 30, d = 3 15 7 27 (mod 33), 27 3 15 (mod 33). 3.3.3. 55973 = 223 251, 223 251 = 55973. 3.4.4. 12 3.4.9. gcd(220, 252) = 4, (s, t) = (8, 7). 3.4.10. x = 249. 3.4.11. d = 37. 57

58 CHAPTER 4. 3.5.1. 1100100, 926. 3.5.2. 31 31 68 (mod 71), 3 100 79 (mod 127). 3.5.3. (1) L = 192 (2) d = 35 (3) 3 11 126 (mod 221) (4) 126 35 3 (mod 221). 4.3.2. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1. 4.3.5. 1. 4.3.8. 1.

[1] 1983. (ISBN4-254-11434-6) [2] 1958. (ISBN4-7853-1301-3) [3] 1997. (ISBN4-303-72330-4) [4] SGC 5, 2000. (ISSN0386-8257) 59