A( ) 1 1.1 12 3 15 3 9 3 12 x (x ) x 12 0 12 1.1.1 x x = 12q + r, 0 r < 12 q r 1 N > 0 x = Nq + r, 0 r < N q r 1 q x/n r r x mod N 1
15 mod 12 = 3, 3 mod 12 = 3, 9 mod 12 = 3 1.1.2 N N 0 x, y x y N x y (mod N) x y N mod N mod N 1.1.3 N, x, y N > 0 (1) x x (mod N) (2) x y (mod N) y x (mod N) (3) x y (mod N), y z (mod N) x z (mod N) (3) x y (mod N), y z (mod N) x y y z N x z = (x y)+(y z) x z N 1.1.4 N, x, y, m N > 0 (1) x y (mod N) x mod N = y mod N (2) x y (mod N) mx my (mod N) (3) m 0 x y (mod N) mx my (mod mn) (4) x y (mod mn) x y (mod N) (1) x y (mod N) x = q 1 N + r 1, y = q 2 N + r 2 r 1 r 2 x y = (q 1 q 2 )N +(r 1 r 2 ). x y N r 1 r 2 N 0 r 1 r 2 < N r 1 r 2 = 0 x mod N = r 1 = r 2 = y mod N (2) x y N mx my = m(x y) N 2
(3) ( ) x y (mod N) x y = qn (q: ) m(x y) = mqn mx my mn ( ) mx my (mod mn) mx my = qmn (q: ) m(x y) = mqn m 0 x y = qn x y N (4) mn N mod N 1.1.5 x x (mod N) y y (mod N) x + y x + y (mod N), xy x y (mod N) x x (mod N) y y (mod N) x x y y N (x + y) (x + y ) = (x x ) + (y y ) N x + y x + y (mod N). xy x y = xy x y + x y x y = (x x )y + x (y y ) N xy x y (mod N). 1.2 1.2.1 m, d m d d m d m d n d m n m n gcd(m, n) m n 3
1.2.2 m, n > 0 (1) r = 0 gcd(m, n) = n m = qn + r (2) r 0 gcd(m, n) = gcd(n, r) (1) n > 0 n n r = 0 n m gcd(m, n) = n (2) d d m n d n r m n n r m n (1) r := m mod n (0 r < n ) (2) r = 0 n (3) r > 0 n r 1.2.3 m := n; n := r (1) 2109 1653 2109 1653 = 456 1653 456 3 = 285 456 285 = 171 285 171 = 114 171 114 = 57 114 57 2 = 0 4
57 gcd(2109, 1653) = gcd(1653, 456) = gcd(456, 285) = gcd(285, 171) = gcd(171, 114) = gcd(114, 57) = 57 1.2.4 1. 2257 mod 1073 (2257 1073 ) 2. 2257 1073 1.2.3 2 456 1 1653 (2109 1653) 3 = 285 1653 4 2109 3 = 285 456 285 = 171 456 285 2109 1653 171 2109 1653 114 2109 1653 57 2109 1653 1.2.5 m, n 0 x, y mx + ny = gcd(m, n) 5
x, y 1 (1) 2109 1 +1653 0 = 2109 (2) 2109 0 +1653 1 = 1653 (3) 2109 1 +1653 ( 1) = 456 (1) (2) (4) 2109 ( 3) +1653 4 = 285 (2) (3) 3 (5) 2109 4 +1653 ( 5) = 171 (3) (4) (6) 2109 ( 7) +1653 9 = 114 (4) (5) (7) 2109 11 +1653 ( 14) = 57 (5) (6) gcd(m, n) = 1 1.2.6 m, n 0 gcd(m, n) = 1 m n 1.2.7 m, n > 0 (1) m n (2) mx + ny = 1 x, y (3) mx 1 (mod n) x (4) nx 1 (mod m) x (1) (2) 1.2.5 (2) (1) d = gcd(m, n) (2) d m, n mx + ny 1 d > 0 d = 1 (2) (3) mx + ny = 1 ny 0 (mod n) mx 1 (mod n) (3) (2) mx 1 (mod n) mx 1 = qn q mx + n( q) = 1 (2) (4) 6
1.2.8 N > 0 m mx 1 (mod N) x mod N m ( ) x mod N (x N 0 (x mod N) < N) m 1 mod N m mod N m N mod N ( ) 1.2.9 mod 97 23 23x 1 (mod 97) 97x 0 (mod 97) 2 x 2 x a (mod N) (1) 97x 0 (mod 97) (2) 23x 1 (mod 97) (3) 5x 4 (mod 97) (1) (2) 4 (4) 3x 17 (mod 97) (2) (3) 4 (5) 2x 21 (mod 97) (3) (4) (6) x 38 (mod 97) (4) (5) 23 38 = 874 = 97 9 + 1 1 (mod 97) (23 38 1)/97 = 9 23 38 + 97 ( 9) = 1 Nx 0 (mod N) mx 1 (mod N) x x a (mod N) a mod N m 7
m n mx + ny = 1 x, y 1.2.10 mod 97 22 97x + 22y = 1 x, y 1 96 mod 97 1.2.11 3 5 1 1600cc 1300cc 100cc 1.3 1 100 3, 5, 7 x x a (mod 3), x b (mod 5), x c (mod 7) x = (70a + 21b + 15c) mod 105 1.3.1 m n a, b mu+nv = 1 8
u, v { x a (mod m) x b (mod n) x nva + mub (mod mn). 1 mn (0 mn 1) 1 x a (mod m) x b (mod n) nx na (mod mn) mx mb (mod mn) nvx nva (mod mn) mux mub (mod mn) (nv + mu)x nva + mub (mod mn) nv + mu = 1 x nva + mub (mod mn) x nva + mub (mod mn) m mn x nva + mub (mod m) mu 0 (mod m) mu+nv = 1 nv 1 (mod m) mub 0 (mod m) nva + mub a (mod m) nva + mub b (mod n) 1.3.2 x a (mod 3), x b (mod 5) 3 2 5 = 1 x 6b 5a (mod 15) x c (mod 7), x d (mod 15) 9
7 ( 2) + 15 = 1 x 15c 14d (mod 105) d = 6b 5a x 15c 14(6b 5a) (mod 105) x 70a 84b + 15c (mod 105) 84 21 (mod 105) x 70a + 21b + 15c (mod 105) x a (mod 3), x b (mod 5), x c (mod 7) 10
1.4 1.4.1 N > 0 Z N = {a Z : 0 a < N, a N } Z N φ(n) φ(n) 1.4.2 Z 12 = {1, 5, 7, 11}, φ(12) = 4. Z 10 = {1, 3, 7, 9}, φ(10) = 4. Z 7 = {1, 2, 3, 4, 5, 6}, φ(7) = 6. 1.4.3 N > 0 (1) a N a mod N Z N. (2) a Z N a 1 mod N Z N. (3) a, b Z N ab mod N Z N. (1) a N 1.2.7 ab 1 (mod N) b a = a mod N 0 a < N a a (mod N) a b ab 1 (mod N) 1.2.7 a N a mod N = a Z N (2) a Z N a N b = a 1 mod N ab 1 (mod N) 0 b < N b Z N (3) a, b Z N aa 1 (mod N) bb 1 (mod N) a, b c = ab mod N 0 c < N c ab (mod N) c(a b ) ab(a b ) = (aa )(bb ) 1 (mod N) c Z N 1.4.4 N > 0 N 11
a a φ(n) 1 (mod N) a Z N Z N = {a 1,..., a m } m = φ(n) 1.4.3 i = 1,..., m a i = aa i mod N a i Z N {a 1, a 2,..., a m} = {a 1, a 2,..., a m } i j a i a j a i = a j aa i mod N = aa j mod N aa i aa j (mod N) b = a 1 mod N baa i baa j (mod N) ba 1 (mod N) 1 a i 1 a j (mod N) a i a j (mod N) 0 a i, a j < N a i = a j a i aa i (mod N) a 1a 2 a m = a 1 a 2 a m a m a 1 a 2 a m = (aa 1 )(aa 2 ) (aa m ) a 1 a 2 a m (mod N) a m a 1 a 2 a m a 1 a 2 a m (mod N) b i = a 1 i mod N b m b 2 b 1 a m (a 1 a 2 a m )(b m b 2 b 1 ) (a 1 a 2 a m )(b m b 2 b 1 ) (mod N) a i b i 1 (mod N) (a 1 a 2 a m )(b m b 2 b 1 ) 1 (mod N) a m 1 (mod N) 12
a N a = a mod N a φ(n) 1 (mod N) a a (mod N) a φ(n) a φ(n) 1 (mod N) Z 10 = {1, 3, 7, 9} 3 1 3 (mod 10) (1) 3 3 9 (mod 10) (2) 3 7 1 (mod 10) (3) 3 9 7 (mod 10) (4) (3 1)(3 3)(3 7)(3 9) 3 9 1 7 (mod 10) 3 4 (1 3 7 9) 1 3 7 9 (mod 10) 9 3 7 3 4 (3 7 9)(9 3 7) (3 7 9)(9 3 7) (mod 10) (3 7 9)(9 3 7) 1 (mod 10) 3 4 1 (mod 10) p Zp = {1, 2,..., p 1} 1.4.5 p ( ) a p a p 1 1 (mod p) a a p a (mod p) 13
p 1.4.6 p Z p 1 (mod p) a Z p Z p = {a i mod p : i = 1, 2,..., p 1} a 1.4.7 Z 7 3 5 1.4.8 Z p φ(p 1) a Z p l > 0 l p 1 al l p 1 lj 1 (mod p 1) j > 0 lj = 1 + m(p 1) (m 0) (a l ) j = a lj = a 1+m(p 1) = a(a p 1 ) m a 1 m = a (mod p). a l Z p Z p 1.5 RSA ( ) 0 1 (2 ) ( ) 2 2 2 14
1.5.1 2 11010110 2 1 2 7 + 1 2 6 + 0 2 5 + 1 2 4 + 0 2 3 + 1 2 2 + 1 2 1 + 0 2 0 2 10 10 RSA 1 1.5.2 RSA p, q 2 L p 1 q 1 ( ) e L e = 41, 257, 65537 2 N = pq : e N : x < N y = x e mod N : d = e 1 mod L x = y d mod N 1.5.3 RSA y = x e mod N ed 1 (mod L) ed = 1 + ml y d x ed (mod N). N = pq y d x ed (mod p), y d x ed (mod q) 15
L p 1 x ed = x 1+mL = x(x p 1 ) m x p x ed = x(x p 1 ) m x 1 m x (mod p) x p 0 x ed x (mod p) y d x (mod p) y d x (mod q) ( y d x p q ) y d x (mod pq) 0 < x < N = pq y d mod N = x. e, N d N = pq p q ( 1000 ) N p N 2 1000 d d 1000 y d mod N 2 1000 16
1.5.4 d 2 α x d mod N α mod N 2 α 0 α0 α 2 1 α1 α 2 + 1 x α mod N = a x α0 mod N = a 2 mod N, x α1 mod N = a 2 x mod N d 2 x d mod N 3 37 mod 100 37 = 100101 2 2 3 1 = 3, 3 10 = 3 2 = 9, 3 100 = (3 10 ) 2 = 81, 3 1001 = (3 100 ) 2 3 = 81 2 3 83 (mod 100) 3 10010 = (3 1001 ) 2 83 2 89 (mod 100) 3 100101 = (3 10010 ) 2 3 89 2 3 63 (mod 100) 1.6 ElGamal RSA ElGamal RSA ElGamal 1 ( ) 17
IC ElGamal Z n b b x x b b x = b x x b b Diffie-Hellman p Z p g ga mod p g b mod p g ab mod p ElGamal q Z q ( )q 1 q := ( ); (q ) 1 < g < q 1 g 1 (g ) g Z p 1 < a < q 1 (a ) h = g a mod q; (h ) x (0 < x < q): (g k mod q, xh k mod q) : (y, z) x = zy a mod q y = g k mod q y a g ka (mod q) y = (y a ) 1 mod q y g ka 1 (mod q) z = xh k xg ak (mod q), zy x (mod q) 18
2 ( ) 2 RSA 2 2 2 2 10 ( ) 1425 10 3 + 4 10 2 + 2 10 + 5 10 1 4 2 5 + 3 1 7 1 6 1 8 0 1 1 4 2 5 3 7 6 8 5 5 0 9 9 7 5 4 2 7 5 5 3 5 8 0 0 1 x 3 + 4x 2 + 2x + 5 3x 2 + 7x + 6 x 1 4 2 5 + 3 7 6 1 7 9 11 1 4 2 5 3 7 6 6 24 12 30 7 28 14 35 3 12 6 15 3 19 40 53 47 30 19
1 7 9 11 x 3 + 7x 2 + 9x + 11 3 19 40 53 47 30 3x 5 + 19x 4 + 40x 3 + 53x 2 + 47x + 30 x 1 Z[x] mod 10 1 4 2 5 + 3 7 6 1 7 9 1 1 4 2 5 3 7 6 6 4 2 0 7 8 4 5 3 2 6 5 3 9 0 3 7 0 10 Z 10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Z 10 x Z 10 [x] Z 10 [x] 2 2 (0 1) 1 2 Z 2 = F 2 = {0, 1} F 2 x F 2 [x] F 2 [x] 1011 x 3 + x + 1 x 2 10 x 2 = 10 2 = 100 x 3 = 10 3 = 1000... F 2 [x] 1011 + 111 1011 111 1 0 1 1 + 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 20
2.1 F 2 [x] 2.1.1 F 2 [x] ( ) 0 1011 = x 3 + x + 1 3 1 n F 2 [x] n 1 f F 2 [x] f deg f 0 0 0 0 f F 2 [x] x a F 2 = Z 2 ( mod 2 ) f(a) f = 1011 = x 3 + x + 1 f(0) = (0 3 + 0 + 1) mod 2 = 1 f(1) = (1 3 + 1 + 1) mod 2 = 3 mod 2 = 1 2.1.2 f F 2 [x] f 0 g F 2 [x] g = qf + r, 0 deg r < deg f q, r F 2 [x] 1 q g/f r r g mod f F 2 = Z 2 1 1 (mod 2) 1 1 1 1 1 ) 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 + 1 0 1 0 1 1 21
1011 = x 3 + x + 1 111 = x 2 + x + 1 F 2 [x] 0 1 F 2 [x] f = f(x) F 2 [x] x F 2 a F 2 f(a) F 2 = {0, 1} f(0) f(1) f(a) = 0 a f 2.1.3 f, g F 2 [x] f = gh h F 2 [x] g f ( ) g f f mod g = 0 2.1.4 a F 2 x a ( 2 1a) f F 2 [x] f(a) = 0 (a f ) f(x) = (x a)q + r r 0 0 F 2 f(a) = r r 0 f(a) = 0 2.1.5 F F 0 F 2 [x] f, g F 2 [x] f g F ( 0) f g (mod F ) f g F mod F mod F 2.1.6 F, f, g, h F 2 [x] F 0 (1) f f (mod F ) (2) f g (mod F ) g f (mod F ) 22
(3) f g (mod F ), g h (mod F ) f h (mod F ) 2.1.7 F, f, g, h F 2 [x] (1) f g (mod F ) f mod F = g mod F (2) f g (mod F ) hf hg (mod F ) (3) h 0 f g (mod F ) hf hg (mod hf ) (4) f g (mod hf ) f g (mod F ) 2.1.8 f f (mod F ) g g (mod F ) f + g f + g (mod F ), fg f g (mod F ) 2.2 2.2.1 F 2 1 f, g, h f = gh g(h ) f ( ) h f h g h f g f g gcd(f, g) f g 2.2.2 f, g F 2 1 g 0 f = qg + r (1) r = 0 gcd(f, g) = g (2) r 0 gcd(f, g) = gcd(g, r) F 2 f g 0 (1) r := f mod g (deg g > 0 0 deg r < deg g ) (2) r = 0 g 23
(3) r 0 g r f := g; g := r (1) (1) deg r = 0 r = 1 0 2.2.3 1111 (= x 3 + x 2 + x + 1) 1010 (= x 3 + x) 101 (= x 2 + 1) 1111 1010 = 101 1010 101 10 = 0 2.2.4 f, g 0, f, g F 2 [x] fu + gv = gcd(f, g) u, v F 2 [x] gcd(m, n) = 1 2.2.5 f, g 0, f, g F 2 [x] gcd(f, g) = 1 f g 2.2.6 f, g 0, f, g F 2 [x] (1) f g (2) fu + gv = 1 u, v F 2 [x] (3) fu 1 (mod g) u F 2 [x] (4) gv 1 (mod f) v F 2 [x] 2.2.7 f F 2 [x] deg f 1 deg g < deg f 24
g F 2 [x] g 0 g f f f f F 2 [x] 1 deg f p Z p = {1,..., p 1} mod p Z p Z p Z p 1 (mod p ) 2.3 F 2 [x] F 2 [x] F 2 [x] 1 ( ) 1 1 f = 101 f(1) = 1 2 + 1 = 0 101 m n (m + n) ( ) 7 4 4 3 3 1 10, 11 (1 ) 2 111 1 ( ) 1 1 1 2 1 111 3 1011, 1101 1 2 3 1 25
4 10011, 11001, 11111 1 10101 4 1 2 111 3 111 0 10101 = 111 2 2.3.1 F 2 [x] 8 110000111 F 2 [x] ( 8 4 ) 2.3.2 n 1 F 2 [x] n 1 2 1 1 n 1 n 2.4 2 n F 2 [x] 2 {0, 1, 10, 11} F 2 [x]( ) f, g 2 f g fg mod 111 ( 111 ) F 4 = {0, 1, 10, 11} F 4 F 2 [x] 0 10 11 = 110 1 (mod 111) a 0 ax = 1 x 0 ( ) F 4 4 26
4 q q 2.4.1 2 n F F 2 [x] n q = 2 n F q = F 2 [x] n 1 F 2 [x] f, g F q fg f g F F q F q q n 1 n 1 n 2... 1 0 n 0 1 2 2 n F 2 [x] 0 f F q F F 2 [x] F f 1 2.2.6 fu + F v = 1 u, v F 2 [x] g = u mod F g n 1 fg 1 (mod F ) F q fg = 1 3 F q q F q F q = F q {0} 1 27
2.4.2 q F q α F q F q = {α i : i = 1, 2,, q 1} α q 1 = 1 α F q x F q xq 1 = 1 F q [y](f q ) 2.4.3 F 2 [x] mod 1011 F 8 (8 = 2 3 ) 10 α = 10 α = 10, α 2 = 100, α 3 = 1000 11 (mod 1011), α 4 = 110, α 5 = 1100 111 (mod 1011), α 6 = 1110 101 (mod 1011), α 7 = 1010 1 (mod 1011). f mod f 10 = x f 2.4.4 F 2 [x] 10011, 11001 11111 mod 11111 1 (11 ) 28
2.5 F 2 n Z/pZ (p ) q q F q q 1 F q 1 GF (q) p F p = Z/pZ = {0, 1,..., p 1} + p p n 2 F p [x] n f F p [x]/(f) F p n 1 1 + ( ) F p f F p [x]/(f) (0 ) F p [x]/(f) n F p = {0, 1,..., p 1} p n F p n = F p [x]/(f) (f n 1 ) F q 1 F q [y] a 0 y 3 + a 1 y 2 + a 2 y + a 3 = (a 0, a 1, a 2, a 3 ) F q 2.5.1 F q m (a 0, a 1, a 2,..., a m 1 ) (a i F q ) ( ) F m q Fm q (m 1) 1 ( ) 29
2.5.2 f = (a 0, a 1,..., a m 2, a m 1 ) F m q F q y y f(y) = a 0 y m 1 + a 1 y m 2 + + a m 2 y + a m 1 f = (1, 2, 3) R 3 f(y) = y 2 + 2y + 3 f(1) = 6 f = (1, 0, 0, 0) f(y) = y 3 F q [y] F 2 [x] 2.5.3 K f K[y] deg f > 0 g K[y] g = qf + r, 0 deg r < deg f q, r K[y] 1 q g/f r r g mod f K = F 4 = F 2 [x]/(111) (111 x 2 + x + 1 ) F 4 = {0, 1, 10, 11} 10 2 = 11, 11 2 = 10, 10 11 = 1 f = (11, 1, 10) = 11y 2 + y + 10, g = (1, 11, 10, 1, 0, 1) = y 5 + 11y 4 + 10y 3 + y 2 + 1 30
10 10 1 1 11 1 10 ) 1 11 10 1 0 1 1 10 11 1 1 1 1 10 11 11 10 0 11 1 10 11 10 1 11 1 10 11 11 11 11 1 = 10 2.5.4 F 2 [x] f, g, F K[y] f g mod F = 0 f g (mod F ) 2.5.5 K K 1 f, g, h f = gh g h f (, factor, divisor) g f f 0 (mod g) h f h g h f g f g 1 gcd(f, g) f g 2.5.6 K a K y a f K[y] f(a) = 0 f(a) = 0 a f ( ) f(y) = (y a)q + r r 0 0 K f(a) = r r 0 f(a) = 0 31
2.5.7 K f(y) K[y] n f(y) K (f(y) = 0 ) n a 1 K f(a 1 ) = 0 f(y) = (y a 1 )f 2 (y) a 2 K f(a 1 ) = 0 a 2 a 1 f(a 2 ) = (a 2 a 1 )f 2 (a 2 ) = 0 (a 2 a 1 ) 1 = f 2 (a 2 ) = 0 f 2 (y) = (y a 2 )f 3 (y) f(y) = (y a 1 )(y a 2 )f 3 (y) a 3 K f(a 3 ) = 0 a 3 a 1, a 2 f(a 3 ) = (a 3 a 1 )(a 3 a 2 )f 3 (a 3 ) = 0 a 3 a 1 0 a 3 a 2 0 K f 3 (a 3 ) = 0 f 3 (y) = (y a 3 )f 4 (y) 1 n n 2.5.8 f, g K[y] g 0 f = qg + r, q, r K[y] (1) r = 0 gcd(f, g) = a 1 g (a g ) (2) r 0 gcd(f, g) = gcd(g, r) K f g 0 (1) r := f mod g (deg g > 0 0 deg r < deg g deg g = 0 g K g 1 K ) (2) r = 0 a 1 g a g (3) r 0 g r f := g; g := r (1) 32
(1) deg r = 0 r K 0 33