( 9 1 )

1 2 1.1................................... 2 1.2................................................. 3 1.3............................................... 4 1.4........................................... 6 1.5.................................... 7 2 10 2.1..................................... 10 2.2........................................... 11 3 RSA 13 3.1 RSA......................................... 13 3.2 RSA............................. 14 3.3.............................................. 15 3.4............................................ 15 4 16 4.1............................................... 16 4.2................................... 18 4.3......................................... 18 5 23 5.1 Fiat-Shamir......................................... 23 5.2 RSA...................... 24 5.3...................................... 25 5.4.............................. 26 6 28 6.1........................... 28 6.2 Solovay-Strassen................................. 29 6.3 Miller-Rabin.................................... 30 7 32 7.1............................................... 32 7.2 Pollard p 1........................................ 32 7.3 2........................................... 32 8 35 8.1............................................ 35 8.2 F p............................................. 35 8.3 F p n............................................ 36 8.4 ( F p version ).................... 38 8.5....................................... 39 1

Information Analysis by Ken-ichi Shiota 2 1 1.1 Z 1.1.1 a, b Z (a, b) 1.1.2 a, b Z (a, b) 1 1.1.3 b 0 a b r (a, b) = (b, r) 1.1.4 (a, b) = d d = ax + by x, y d, x, y ( ) 1.1.5 (1) b = 0 d := a, 1 ( a 0 ) x :=, 1 ( a < 0 ) y := 0 (2) b 0 a) { r n }, { x n }, { y n } r 0 := a, r 1 := b, x 0 := 1, x 1 := 0, y 0 := 0, y 1 := 1, q := r n 2 r n 1 r n := r n 2 q r n 1 = r n 2 r n 1 (n = 2, 3, ). x n := x n 2 q x n 1 y n := y n 2 q y n 1 b) r n = 0 n d := r n 1, x := x n 1, y := y n 1 ( r n 1 > 0 ) d := r n 1, x := x n 1, y := y n 1 ( r n 1 < 0 )

Information Analysis by Ken-ichi Shiota 3 1.1.6 r n r n = 0 (a, b) = (r 0, r 1 ) = (r 1, r 2 ) = = (r n 1, r n ) = r n 1 r n = ax n + by n 1.1.7 a n ax + ny = 1 x, y 1.2 1.2.1 G (1) G ( ) (2) : (ab) c = a (bc) for a, b, c G. (3) e : ae = ea = a for a G. (4) a G a 1 : a G, a 1 G s.t. aa 1 = a 1 a = e. 1.2.2 G ( ) : ab = ba for a, b G. 1.2.3 G G G G 1.2.4 G a, b, c G ab = ac ba = ca = b = c. 1.2.5 G N a N = e for a G. 1.2.6 G a a n = e a 1.2.7 G a 0 m, n a m = a n = e m, n d = (m, n) a d = e.

Information Analysis by Ken-ichi Shiota 4 1.2.8 1.1.4 d = mx + ny x, y a d = a (mx+ny) = (a m ) x (a n ) y = e. 1.2.9 (1) G a m a m = e m a (2) G 1.2.10 G G = {, a 2, a 1, e, a, a 2, } a G = a G a a G 1.3 1.3.1 2 n ( ) 1.3.2 a, b a b n a b n a b ( mod n) a b n ( mod n ) 1.3.3 n Z/nZ a Z ā a mod n Z/nZ = { 0, 1,, n 1} 1.3.4 Z/nZ : ā + b := a + b, ā b := ab 1.3.5 Z/nZ 0 n 1.3.6 Z/nZ n a Z (Z/nZ) ( ) (Z/nZ) ( ) 1.3.7 (Z/nZ) 1

Information Analysis by Ken-ichi Shiota 5 1.3.8 ax + ny = 1 x, y x ā 1 = ax + ny ax ( mod n ) 1.3.9 (Z/nZ) 0 n 1 n ϕ(n) 1.3.10 a n a ϕ(n) 1 ( mod n ) 1.3.11 p (Z/pZ) = { 1, 2,, p 1 }, ϕ(p) = p 1. 1.3.12 p e (Z/p e Z) = { x 0 x < p e, x p }, ϕ(p e ) = p e p e 1. 1.3.13 p a Z p a p 1 1 ( mod p ). a Z a p a ( mod p ). 1.3.14 (1) p (Z/pZ) p 1 g (Z/pZ) (Z/pZ) = g = { 1 = g 0, g = g 1, g 2,, g p 2 } g ( ) mod p (2) mod p ( mod p ) ϕ(p 1) g mod p g j ( 1 j p 2, (j, p 1) = 1 )

Information Analysis by Ken-ichi Shiota 6 1.3.15 (Z/3Z) = { 2 0 = 1, 2 } (Z/5Z) = { 2 0 = 1, 2, 2 2 = 4, 2 3 = 3 } (Z/7Z) = { 3 0 = 1, 3, 3 2 = 2, 3 3 = 6, 3 4 = 4, 3 5 = 5 } (Z/11Z) = { 2 0 = 1, 2, 2 2 = 4, 2 3 = 8, 2 4 = 5, 2 5 = 10, 2 6 = 9, 2 7 = 7, 2 8 = 3, 2 9 = 6 } { } (Z/13Z) 2 0 = 1, 2, 2 2 = 4, 2 3 = 8, 2 4 = 3, 2 5 = 6, 2 6 = 12, 2 7 = 11, 2 8 = 9, 2 9 = 5, = 2 10 = 10, 2 11 = 7 1.3.16 p e (Z/p e Z) p e 1 (p 1) mod p e 1.4 1.4.1 ( ) m, n a, b x a ( mod m ), x b ( mod n ) mn x 1.4.2 m n u, v mu + nv = 1 x := bmu + anv 1.4.3 m n x anv = a(1 mu) a ( mod m ). 1.4.4 m, n x a ( mod mn ) x a ( mod m ), x a ( mod n )

Information Analysis by Ken-ichi Shiota 7 1.4.5 m, n ϕ(mn) = ϕ(m) ϕ(n) 1.4.6 n n = p e q f r g ϕ(n) = (p e p e 1 )(q f q f 1 ) (r g r g 1 ) = n ( 1 1 ) ( 1 1 ) ( 1 1 ) p q r 1.4.7 ( ) s m 1, m 2,, m s 2 s a 1, a 2,, a s x a 1 ( mod m 1 ), x a 2 ( mod m 2 ),, x a s ( mod m s ) m 1 m 2 m s x 1.4.8 ( ) x (1) m 1 M 1 = m 2 m s m 1 u 1 + M 1 v 1 = 1 u 1, v 1 w 1 := M 1 v 1 (2) j w 1 1 ( mod m 1 ), w 1 0 ( mod m 2 ),, w 1 0 ( mod m s ) w j 1 ( mod m j ), w j 0 ( mod m k ) ( k j ) w j (3) x := a 1 w 1 + a 2 w 2 + + a s w s 1.5 1.5.1 p p a x 2 a ( mod p ) p

Information Analysis by Ken-ichi Shiota 8 1.5.2 p a 1 a p ( ) a := p 1 a p 0 a p 1.5.3 ( ) 2 2 9 = 3 2 ( mod 7 ) = 1. 7 ( ) 3 x 2 3 ( mod 7 ) x = 1. 7 1.5.4 ( ) ( ) a a Z a p 1 2 ( mod p ) p 1.5.5 ( ) ( ) 2 2 7 1 2 2 = 2 3 = 8 1 ( mod 7 ) = 1. 7 7 ( ) ( ) 3 3 7 1 3 2 = 3 3 = 27 1 ( mod 7 ) = 1. 7 7 1.5.6 q q = p e1 1 per r q a (a ) q ( a := p 1 ) e1 ( ) er a p r ( q ) 1.5.7 a, b q, r ( ) ( ) a b (1) a b ( mod q ) =. q q ( ) ( ) a 2 1 (2) a q = 1. = 1. q q (3) (4) ( ) ab = q ( a q ( ) { 1 = q )( ) b. q 1 q 1 ( mod 4 ) 1 1 q 3 ( mod 4 )

Information Analysis by Ken-ichi Shiota 9 (5) (6) ( ) { 2 = q ( ) r = q 1 q 1, 7 ( mod 8 ) 2 1 q 3, 5 ( mod 8 ) ( q r ) ( q ) r q 1 ( mod 4 ) r 1 ( mod 4 ) q r 3 ( mod 4 ) 1.5.8 (1 6) (2) 1 2 ( ) ( ) ( ) ( ) ( ) 7 19 5 7 2 = = = = = ( 1) = 1 19 7 7 5 5 1.5.9 Pascal function jacobi_symbol(a,b:integer):integer; var c,j:integer; begin j:=1; if a<0 then begin a:=-a; if (b mod 4)=3 then j:=-j end; a:=a mod b; while a>1 do begin while (a mod 2)=0 do begin a:=a div 2; if ((b mod 8)=3) or ((b mod 8)=5) then j:=-j end; if a<>1 then begin if ((a mod 4)=3) and ((b mod 4)=3) then j:=-j; c:=b; b:=a; a:=c mod b end end; if a=0 then j:=0; jacobi_symbol:=j end;

Information Analysis by Ken-ichi Shiota 10 2 2.1 2.1.1 P = ( plain text ) C = ( cipher text ) E : P C D = E 1 : C P P E C D P E E ( encryption ) D ( decryption ) K = A K P E A C D A P { } P E A C D A P A K 2.1.2 P = C = {, A, B,, Z } = 27 Z/27Z = { 0, 1, 2,, 26 } K = Z/27Z { 0 } n K E n (x) = x + n ( in Z/27Z ) E n : P C E n n INFORMATION E 3 LQIRUPDWLRQ D n (y) = y n n 2.1.3

Information Analysis by Ken-ichi Shiota 11 2.1.4 (1) A K : A = (A p, A s ) A p :, A s : (2) E A A p (3) D A A p A s 2.1.5 A K 2.1.6 (1) A = (A p, A s ) A p ( A s ) (2) A p x y = E A (x) (3) A s y x = D A (y) 2.1.7 (1) N(N 1) (2) N 2 N 2.2 2.2.1 ( ) P = C, P E A C D A P E A D A = id C ( ) ( RSA ) 2.2.2 x, A = (A p, A s ) Step 1 : Step 2 : Step 3 : A s y = D A (x) x y (x, y) E A (y) x = E A (y)

Information Analysis by Ken-ichi Shiota 12 2.2.3 A s x = E A (y) y 2.2.4 name D A (name) (x, D A (name)) D A (name)

Information Analysis by Ken-ichi Shiota 13 3 RSA 3.1 RSA 3.1.1 x Z (x, mod n) n x 0 (x, mod n) < n 3.1.2 p, q : n = pq m = ϕ(n) = (p 1) (q 1) e : m d : ed 1 ( mod m ) p, q, e n, m, d ( d ) : P = C = { x Z 0 x < n } : A p = (n, e) : A s = (p, q, m, d) 3.1.3 n, e x y = E A (x) := (x e, mod n) 3.1.4 d y w = D A (y) := (y d, mod n) x = w x 3.1.5 x p w x ed 0 x ( mod p ). x p ed 1 ( mod p 1 ) w x ed x ( mod p ). q w x ed x ( mod n ). w x 0 x, w < n n w = x.

Information Analysis by Ken-ichi Shiota 14 3.2 RSA 3.2.1 RSA (1) n, e y y = (x e, mod n) x ( ) (2) d d n p, q 3.2.2 (1) p, q (2) m (3) d 3.2.3 a 2 b 2 ( mod n ) a ±b ( mod n ) 2 a, b p, q 3.2.4 (a + b)(a b) 0 ( mod n ), a ± b 0 ( mod n ) n p, q a + b a b (a + b, n) n 3.2.5 a 2 1 ( mod n ) a ±1 ( mod n ) 2 a, b p, q 3.2.6 3.2.2 (3) (1) ( ) ed 1 = 2 s t ( t ) n w w 2st 1 ( mod n ) w t, w 2t,, w 2s t 1 ( mod n ) w 2rt r = 0 w 2r 1t 1 ( mod n ) 50% ( ) w w 2r 1t 1 ( mod n ), w 2rt 1 ( mod n ) w 3.2.5 a a = w 2r 1t

Information Analysis by Ken-ichi Shiota 15 3.3 3.3.1 p q x = p + q 2, y = p q 2 x n, y 0, x 2 y 2 = n b = 1, 2, b 2 + n ( = a 2 ) b y 3.2.3 a, b y 3.3.2 p 1 q 1 p 1 q 1 l ed 1 ( mod l ) d ( 3.1.5 ) p 1 q 1 l d 3.3.3 ϕ(n) K =( ) ϕ(n) K ϕ(n) ed 1 ( mod K ) d d 3.4 3.4.1 n 512 ( 10 155 ) 3.4.2 93) 10 120 RSA RSA-120 2 825MIPSYear 94) 10 129 RSA RSA-129 2 5000MIPSYear 95) 10 130 RSA RSA-130

Information Analysis by Ken-ichi Shiota 16 4 4.1 4.1.1 34567 (1) 34567 2 3 45 67 (2) a 2 3 a ( = 1 ) (a) a (b) 3 a 2 ( = 1 ) ( = 2 ) 2 ( = 45 ) (c) a ( = 1 ) 2 ( = 2 ) 1 1 3 45 67 1 1 2 2 45 (3) 2 (a) (20 + b) b 245 b ( = 8 ) (b) b (c) 245 (20 + b) b ( = 224 ) ( = 21 ) 2 ( = 67 ) (d) 20 + b ( = 28 ) b ( = 8 ) 2 ( = 36 ) 1 8 1 3 45 67 1 1 28 2 45 8 2 24 36 21 67 (4) 1 8 5. 1 3 45 67 1 1 28 2 45 8 2 24 365 21 67 5 18 25 370 3 42 00

Information Analysis by Ken-ichi Shiota 17. 1 8 5. 9 2 2 0 2 1 3 45 67 1 1 28 2 45 8 2 24 365 21 67 5 18 25 3709 3 42 00 9 3 33 81 37182 8 19 00 2 7 43 64 371842 75 36 00 2 74 36 84 3718440 99 16 00 0 0 37184402 99 16 00 00 2 74 36 88 04 37184404 24 79 11 96 4.1.2 1 (100a) 2 34567 a 2 3 a = 1 2 (100 + 10b) 2 34567 (10 + b) 2 345 10 2 + 20b + b 2 345 (20 + b) b 345 10 2 = 245 b = 8 3 (180 + c) 2 34567 180 2 + 360c + c 2 34567 (360 + c) c 34567 100 2 (200 + 80) 80 = 2167 c = 5

Information Analysis by Ken-ichi Shiota 18 4 (185 + d/10) 2 34567 1850 2 + 3700d + d 2 3456700 (3700 + d) d 3456700 1000 2 (2000 + 800) 800 (3600 + 50) 50 = 34200 d = 9 4.1.3 1 3 ( ) 1 4.2 a 4.2.1 { x n } n=0,1,2, (1) x 0 := ( ) (2) x n+1 := 1 ( x n + a ) ( n = 0, 1, 2, ) 2 x n x n a ( n ) 4.2.2 a a 4.2.3 4.3 4.3.1 p 1 p (Z/pZ) 2 2 4.3.2 g mod p { x (Z/pZ) x } = { g 0, g 2, g 4, } ( ) a (Z/pZ) { ±1 } ; a p { x (Z/pZ) x }

Information Analysis by Ken-ichi Shiota 19 4.3.3 p a 2 b 2 ( mod p ) = a b ( mod p ) a b ( mod p ). a 2 1 ( mod p ) = a 1 ( mod p ) a 1 ( mod p ). 4.3.4 ( ) p x 2 a ( mod p ) x (1) a (2) p = 2u + 1 ( u ) x := ±a u+1 2. (3) p = 4u + 1 ( u ) (3a) a u 1 ( mod p ) x := ±a u+1 2. (3b) a u 1 ( mod p ) x := ±a u+1 2 2 u. (4) p = 8u + 1 ( u ) ( ) b (4a) b = 3, 5, 7, 11, = 1 b p (4b) a 2u 1 ( mod p ) (4b-1) a u 1 ( mod p ) x := ±a u+1 2. (4b-2) a u 1 ( mod p ) x := ±a u+1 2 b 2u. (4c) a 2u 1 ( mod p ) (4c-1) a u b 2u 1 ( mod p ) x := ±a u+1 2 b u. (4c-2) a u b 2u 1 ( mod p ) x := ±a u+1 2 b 3u. (5) p = 2 k u + 1 ( k 3, u ) ( ) b (5a) b = 3, 5, 7, 11, = 1 b p (5b) i = 1, 2,, k 1 e i = 0 1 : (5b-1) a 2k i 1u b (2k i e 1 + +2 k 2 e i 1 )u 1 ( mod p ) e i := 0, (5b-2) a 2k i 1u b (2k i e 1+ +2 k 2 e i 1)u 1 ( mod p ) e i := 1. (5c) x := ±a u+1 2 b (e 1+2e 2 + +2 k 2 e k 1 )u 4.3.5 (2) p = 23 = 2 11 + 1 ( u = 11 ), a = 2 x = ±2 u+1 2 = ±2 6 5. ( ( 5) 2 = 25 2. ) (3a) p = 29 = 4 7 + 1 ( u = 7 ), a = 7 7 u = 7 7 1 x = ±7 u+1 2 = ±7 4 6. ( ( 6) 2 = 36 7. ) (3b) p = 29 = 4 7 + 1 ( u = 7 ), a = 5 5 u = 5 7 1 x = ±5 u+1 2 2 7 11. ( ( 11) 2 = 121 5. )

Information Analysis by Ken-ichi Shiota 20 4.3.6 p (2) 1.5.4 ( ) a u = a p 1 a 2 = 1. p ) 2 a a u+1 = (a u+1 2. (3) 4.3.3 a 2u = a p 1 2 a u 1 ( ) a = 1. p a u 1 (3a) a u 1 a a u+1 = ) 2 (a u+1 2. (3b) a u 1 ( ) 2 2u = 2 p 1 2 2 = 1. p (4) 4.3.3 a u 2 2u 1 a a u+1 2 2u = (a u+1 2 2 u) 2. a 4u = a p 1 2 a 2u 1 ( ) a = 1. p a 2u 1 (4a) a 2u 1 4.3.3 a u 1 a u 1 (4a-1) a u 1 a a u+1 = ) 2 (a u+1 2. (4a-2) a u 1 ( ) b 4u = b p 1 2 2 = 1. p a u b 4u 1 a a u+1 b 4u = (a u+1 2 b 2u) 2. (4b) a 2u 1 a 2u b 4u 1. 4.3.3 a u b 2u 1 a u b 2u 1 (4b-1) a u b 2u 1 a a u+1 b 2u = (a u+1 2 b u ) 2.

Information Analysis by Ken-ichi Shiota 21 (4b-2) a u b 2u 1 a u b 2u b 4u 1. a a u+1 b 6u = (a u+1 2 b 3u ) 2. (5) (4) 4.3.7 ( ) p e x 2 a ( mod p e ) x ( ) a (1) = 1 p (2) (x 1 ) 2 a ( mod p ) x 1 4.3.4 (3) (x e ) 2 a ( mod p e ) x e ( e = 2, 3, ) x e := x e 1 + (2x e 1 ) 1 (a (x e 1 ) 2 ). (2x e 1 ) 1 mod p 2x e 1 ( ) 4.3.8 a (x e 1 ) 2 0 ( mod p e 1 ) (a (x e 1 ) 2 ) 2 0 ( mod p 2e 2 ). 2e 2 = e + (e 2) e (a (x e 1 ) 2 ) 2 0 ( mod p e ). (x e 1 + (2x e 1 ) 1 (a (x e 1 ) 2 )) 2 = (x e 1 ) 2 + (a (x e 1 ) 2 ) + ((2x e 1 ) 1 ) 2 (a (x e 1 ) 2 ) 2 (x e 1 ) 2 + (a (x e 1 ) 2 ) = a ( mod p e ) 4.3.9 ( ) n x 2 a ( mod n ) x (1) n = p e 1 1 pe m ( ) a (2) p j = 1 p j (3) (x j ) 2 a ( mod p ej j ) x j 4.3.7 (4) x x j ( mod p e j j ) ( j = 1, 2,, m )

Information Analysis by Ken-ichi Shiota 22 4.3.10 n (1) n (2) 2 x 2 a ( mod n ) 4.3.11 (1) (2) (2) (1) n p n = p e m ( (p, m) = 1 ) x 2 a ( mod n ) x 1 x 2 ( mod p e ), x 1 x 2 ( mod m ) 2 x 1, x 2 3.2.3 p e = (x 1 + x 2, n)

Information Analysis by Ken-ichi Shiota 23 5 5.1 Fiat-Shamir 5.1.1 : A, ( ) P, ( ) V : : p, q : A, n = pq :, t : P ( ), a = (t 2, mod n) : P ID ( ) P t t V 5.1.2 4.3.10 A P t 5.1.3 A Step 1 : Step 2 : Step 3 : Step 4 : P r x := (r 2, mod n) V V b = 0 1 b P b P { r y := tr V b = 0 b = 1 V : { x y 2 ( mod n ) b = 0 ax y 2 ( mod n ) b = 1 5.1.4 A (1) V b = 0 P t (2) V b = 1 P y Step 1 x := y 2 /a V ( t ) ax y 2 ( mod n ) (3) P V { b = 0 r b = 1 y

Information Analysis by Ken-ichi Shiota 24 (4) b m P V ) m 0 ( m ) ( 1 2 5.2 RSA 5.2.1 : ( RSA ) P, V : : p, q : P RSA, n = pq : P p, q V 5.2.2 4.3.10 P mod n a t 2 a ( mod n ) t t 5.2.3 1 Step 1 : Step 2 : Step 3 : V s a := (s 2, mod n) P P t 2 a ( mod n ) t t V V a t 2 ( mod n ) 5.2.4 1 V s t s t ( mod p ), s t ( mod q ) 1/2 p = (s t, n) p V 5.2.5 2 Step 1 : Step 2 : Step 3 : V s a := (s 2, mod n) P P t 2 a ( mod n ) t P A t V

Information Analysis by Ken-ichi Shiota 25 5.2.6 2 V a P P ( ) 5.2.7 B Step 1 : Step 2 : Step 3 : Step 4 : V s a := (s 2, mod n) P V A s P P t 2 a ( mod n ) t P A t V 5.3 5.3.1 A B 5.3.2 p, q p q 3 ( mod 4 ) n = pq Blum 5.3.3 n = pq Blum a n mod n (1) x 2 a mod n x mod n 4 ±x 1, ±x 2 ( ) ( ) ±x1 ±x2 = 1, = 1 n n (2) (1) n 5.3.4 C Step 1 : Step 2 : Step 3 : Step 4 : Step 5 : Step 6 : A p q 3 ( mod 4 ) p, q n = pq B B x a := (x 2, mod n) A A e = 1 1 e B B x A A x 2 a ( mod n ) ( x = e A B n)

Information Analysis by Ken-ichi Shiota 26 5.3.5 C ( x (1) A x 2 a ( mod n ) 5.3.3 (1) n) (2) 5.3.3 (2) B x 2 a ( mod n ) ( ) x ( x = n n) ( ) x A e = e x n 5.3.6 (1) C n mod 4 3 Blum ( x (2) n mod 4 1 2 x 2 a ( mod n ) n) A B a x e = B ( x n) 5.3.7 C A n Blum B p q B 5.3.8 D Step 1 : Step 2 : Step 3 : Step 4 : A x a := (x 2, mod n) B B e = 1 1 e A ( ) x A (x ) 2 a ( mod n ) = e x x B n ( ) x B (x ) 2 a ( mod n ) = e n 5.4 5.4.1 : P V : : G, H : ( ), σ : G H : ( P ) P σ σ V

Information Analysis by Ken-ichi Shiota 27 5.4.2 G ( = H ) n G, H A = (a ij ), B = (b ij ) σ n a ij = b σ(i)σ(j) for i, j 5.4.3 E Step 1 : Step 2 : Step 3 : Step 4 : P n φ F = φ(h) C = (c ij ) = (b φ 1 (i)φ 1 (j)) V V e = 1 2 e P e P { φ τ := φ σ V e = 1 e = 2 V : { F = τ(h) c τ(i)τ(j) = b ij for i, j e = 1 F = τ(g) c τ(i)τ(j) = a ij for i, j e = 2 5.4.4 E (1) V e = 1 P σ (2) V e = 2 P τ Step 1 τ(g) V ( σ ) F = τ(g) (3) P V { e = 1 φ e = 2 τ (4) e m P V ( 1 2) m 0 ( m )

Information Analysis by Ken-ichi Shiota 28 6 6.1 RSA n n 6.1.1 n ( ) ( ) a n 1 1 ( mod n ) for a Z s.t. (a, n) = 1 6.1.2 a n 1 1 ( mod n ) a n ( ) n 6.1.3 n = 561 = 3 11 17 (a, n) = 1 6.1.1 a 2 1 ( mod 3 ) a 10 1 ( mod 11 ) a 16 1 ( mod 17 ) 560 2, 10, 16 a 560 1 ( mod 3 11 17 ) 6.1.4 ( ) n ( Carmichael ) 6.1.5 n (1) n (2) n = p 1 p 2 p r n (a) p j (b) r 3 (c) j p j 1 n 1 6.1.6 ( Alford, Graville and Pomerance (1992) ) n 1 ( )

Information Analysis by Ken-ichi Shiota 29 6.1.7 n 1 = p e 1 1 pe 2 2 per r j a n 1 j 1 ( mod n ) a (n 1)/p j j 1 ( mod n ) a j n 6.1.8 (Z/nZ) a j m j m j p ej (Z/nZ) ϕ(n) m j ϕ(n) ( m 1, m 2,, m r ) = p e 1 1 pe 2 2 per r = n 1 ϕ(n) = n 1 n n 1 j 6.1.9 n 1 = p e 1 1 pe 2 2 pe r r m ( p j m < n ) j a n 1 j 1 ( mod n ) (a (n 1)/p j j 1, n) = 1 a j n 6.1.10 n q n q a n 1 j 1 ( mod q ) a (n 1)/p j j 1 ( mod q ) a j (Z/qZ) p ej ϕ(q) = q 1 p e1 1 pe2 2 pe r r = (n 1)/m n 1 m > n 1 = n 1 > n 1 q 1 n n j 6.2 Solovay-Strassen 6.2.1 n a Z ( ) ( ( ) a n 1 a 2 ( mod n ) n) 6.2.2 n 50% a (Z/nZ) ( )

Information Analysis by Ken-ichi Shiota 30 6.2.3 (1) ( ) a (a) n n p n = pm mod p a Z a 1 ( mod m ) ( ( ) a a ( a ) = = 1, a n) n 1 2 1 ( mod m ). p m (b) n p 2 n n = p e m ( e 2, (p, m) = 1 ) a = 1 + n p = 1 + pe 1 m n q ( p ) a 1 ( mod q ) ( a = 1 n) a n 1 2 1 + n 1 p e 1 m 1 ( mod p e ). 2 (2) (1) a x (Z/nZ) ( ) ax ( ) ( ) (Z/nZ) ( ) 6.2.4 Step 1 : Step 2 : Step 3 : Step 4 : a ( 1 < a < n ) (a, n) > 1 (a, n) n ( ) ( ) Step 1 ( ) n ( ) m ) m ( 1 2 6.3 Miller-Rabin n 1 2 n 1 = 2 s t 6.3.1 n a ( (a, n) = 1 ) : (i) a t 1 ( mod n ) ( ) (ii) r ( 0 r < s ) s.t. a 2rt 1 ( mod n ) 6.3.2 n a 2st = a n 1 1 ( mod n ) 1 mod n ±1 a 2s 1t 1 ( mod n ) a 2s 1t ±1 ( mod n ) a 2s 2t ±1 ( mod n ) (ii) (i)

Information Analysis by Ken-ichi Shiota 31 6.3.3 n 75% a (Z/nZ) ( ) 6.3.4 ( ) a 6.3.5 6.2.4 ( ) ( ) ) m n ( ) m 6.2.4 ( 1 4 6.3.6 Solovay-Strassen Miller-Rabin 0 Adleman-Rumery

Information Analysis by Ken-ichi Shiota 32 7 7.1 ( ) n 7.1.1 1 < (a, n) < n a 1 < (a, n) < n (a, n) n (a, n) (a, n) 7.2 Pollard p 1 n p 1 p n 7.2.1 p n p 1 p 1 = p e1 1 pe2 2 pe r r M ( M = 10 5 ) j p ej j M 7.2.2 (1) M q k f k := log qk M K := ( q f k k M < qf k+1 k ) (2) a (3) (a, n) 1 < (a, n) < n q k M (4) (a, n) = 1 d := (a K 1, n) (5) d = n (2) d < n d p ( ) q f k k 7.2.3 d p K j p e j K p 1 j a K 1 ( mod p ) 7.3 2

Information Analysis by Ken-ichi Shiota 33 7.3.1 x n x 2 n x 2 n = ( ) x 2 ( ) ( mod n ) X 2 Y 2 ( mod n ) (X + Y ) (X Y ) 0 ( mod n ) (X ± Y, n) n 7.3.2 R, B 1 x n R x n + R x 2 n B 1 7.3.3 n = 101687401 R = 1000, B 1 = 50 9459 2 n = 12214720 = 2 6 5 7 2 19 41 9541 2 n = 10656720 = 2 4 3 2 5 19 2 41 9581 2 n = 9891840 = 2 12 3 5 7 23 9811 2 n = 5431680 = 2 7 3 2 5 23 41 9861 2 n = 4448080 = 2 4 5 7 13 2 47 9926 2 n = 3161925 = 3 2 5 2 13 23 47 9949 2 n = 2704800 = 2 5 3 5 2 7 2 23 9951 2 n = 2665000 = 2 3 5 4 13 41 9973 2 n = 2226672 = 2 4 3 2 7 47 2 9991 2 n = 1867320 = 2 3 3 3 5 7 13 19 10016 2 n = 1367145 = 3 3 5 13 19 41 10029 2 n = 1106560 = 2 7 5 7 13 19 10043 2 n = 825552 = 2 4 3 4 7 2 13 10049 2 n = 705000 = 2 3 3 5 4 47 10061 2 n = 463680 = 2 6 3 2 5 7 23 10067 2 n = 342912 = 2 7 3 19 47 10081 2 n = 60840 = 2 3 3 2 5 13 2 10084 2 n = 345 = 3 5 23 10096 2 n = 241815 = 3 5 7 3 47 10099 2 n = 302400 = 2 6 3 3 5 2 7 10124 2 n = 807975 = 3 5 5 2 7 19 10133 2 n = 990288 = 2 4 3 2 13 23 2 10141 2 n = 1152480 = 2 5 3 5 7 4 10199 2 n = 2332200 = 2 3 3 5 2 13 2 23

Information Analysis by Ken-ichi Shiota 34 10225 2 n = 2863224 = 2 3 3 2 7 13 19 23 10349 2 n = 5414400 = 2 9 3 2 5 2 47 10484 2 n = 8226855 = 3 2 5 7 3 13 41 10537 2 n = 9340968 = 2 3 3 7 2 13 2 47 10549 2 n = 9594000 = 2 4 3 2 5 3 13 41 10631 2 n = 11330760 = 2 3 3 5 7 2 41 47 10754 2 n = 13961115 = 3 2 5 7 23 41 47 10757 2 n = 14025648 = 2 4 3 7 13 3 19 10771 2 n = 14327040 = 2 8 3 5 7 13 41 11017 2 n = 19686888 = 2 3 3 5 13 19 41 11027 2 n = 19907328 = 2 8 3 7 2 23 2 1, 2, 20, 21 a := 9459 9541 10099 10124, b := 2 8 3 5 5 3 7 2 19 2 41 (a + b, n) = (9232833075958044, 101687401) = 14533, (a b, n) = (9221554003510044, 101687401) = 6997 6997 = p 900, 14533 = p 1701 900 1701 n = 6997 14533 7.3.4 x p x p x log p log n ( ) 7.3.5 ( 1) F 2 7.3.6 x 2 n 2 2 X 2 Y 2 ( mod n ) (d, n) > 1 d

Information Analysis by Ken-ichi Shiota 35 8 8.1 8.1.1 0 1 8.1.2 0 ( ) 8.1.3 R R := { x R y R s.t. xy = 1 } ( R ) R R 8.1.4 F F = F { 0 } 8.1.5 8.2 F p 8.2.1 F p p Z/pZ = { 0, 1, 2,, p 1 } 1.3.11 F p p 8.2.2 F p F p : F p a + b := (a + b, mod p), (x, mod p) x p 0 (x, mod p) p 1 F p a b := (a b, mod p) a F p ( a 0 ) b ax + ny = 1 x a b F p = bx a

Information Analysis by Ken-ichi Shiota 36 8.2.3 F 2 + 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 8.2.4 F 3 + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 8.2.5 F 5 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 ( 2 1 = 2, 2 2 = 4, 2 3 = 3, 2 4 = 1. ) 8.2.6 F 7 + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 ( 3 1 = 3, 3 2 = 2, 3 3 = 6, 3 4 = 4, 3 5 = 5, 3 6 = 1. ) 8.3 F p n 8.3.1 p F p = { 0, 1, 2,, p 1 } p G(t) F p n F F := { F p n 1 } G(t) F F p n F p n F a(t) + b(t) := ( a(t) + b(t) F p ) F a(t) b(t) := ( a(t) b(t) G(t) ) ( 0 )

Information Analysis by Ken-ichi Shiota 37 8.3.2 F 4 p = 2, G(t) = t 2 + t + 1 4 F 4 α F 2 α 2 + α + 1 = 0 + 0 1 α α+1 0 0 1 α α+1 1 1 0 α+1 α α α α+1 0 1 α+1 α+1 α 1 0 0 1 α α+1 0 0 0 0 0 1 0 1 α α+1 α 0 α α+1 1 α+1 0 α+1 1 α ( α 1 = α, α 2 = α + 1, α 3 = 1. ) 8.3.3 F 8 p = 2, G(t) = t 3 + t + 1 8 F 8 β F 2 β 3 + β + 1 = 0 + 0 1 β β+1 β 2 β 2 +1 β 2 +β β 2 +β+1 0 0 1 β β+1 β 2 β 2 +1 β 2 +β β 2 +β+1 1 0 β+1 β β 2 +1 β 2 β 2 +β+1 β 2 +β β 0 1 β 2 +β β 2 +β+1 β 2 β 2 +1 β+1 0 β 2 +β+1 β 2 +β β 2 +1 β 2 β 2 0 1 β β+1 β 2 +1 0 β+1 β β 2 +β 0 1 β 2 +β+1 0 0 1 β β+1 β 2 β 2 +1 β 2 +β β 2 +β+1 0 0 0 0 0 0 0 0 0 1 1 β β+1 β 2 β 2 +1 β 2 +β β 2 +β+1 β β 2 β 2 +β β+1 1 β 2 +β+1 β 2 +1 β+1 β 2 +1 β 2 +β+1 β 2 1 β β 2 β 2 +β β β 2 +1 1 β 2 +1 β 2 +β+1 β+1 β 2 +β β 2 +β β β 2 β 2 +β+1 β + 1 ( β 1 = β, β 2 = β 2, β 3 = β + 1, β 4 = β 2 + β + 1, β 5 = β 2 + β, β 6 = β 2 + 1, β 7 = 1. ) 8.3.4 F 16 p = 2, G(t) = t 4 + t + 1 16 F 16 p = 2, G(t) = t 4 + t 3 + 1 16 F 16 γ F 2 γ 4 + γ + 1 = 0 δ F 2 δ 4 + δ 3 + 1 = 0 δ = γ 3 + 1 F 16 F 16

Information Analysis by Ken-ichi Shiota 38 8.3.5 F 9 p = 3, G(t) = t 2 + t + 2 9 F 9 α F 3 α 2 + α + 2 = 0 + 0 1 2 α α+1 α+2 2α 2α+1 2α+2 0 0 1 2 α α+1 α+2 2α 2α+1 2α+2 1 2 0 α+1 α+2 α 2α+1 2α+2 2α 2 1 α+2 α α+1 2α+2 2α 2α+1 α 2α 2α+1 2α+2 0 1 2 α+1 2α+2 2α 1 2 0 α+2 2α+1 2 0 1 2α α α+1 α+2 2α+1 α+2 α 2α+2 α+1 0 1 2 α α+1 α+2 2α 2α+1 2α+2 0 0 0 0 0 0 0 0 0 0 1 1 2 α α+1 α+2 2α 2α+1 2α+2 2 1 2α 2α+2 2α+1 α α+2 α+1 α 2α + 1 1 α+1 α+2 2α+2 2 α+1 α+2 2α 2 α 2α+1 α+2 2 2α+2 1 α 2α 2α+1 α+1 1 2α+1 2 2α 2α+2 α+2 ( α 1 = α, α 2 = 2α + 1, α 3 = 2α + 2, α 4 = 2, α 5 = 2α, α 6 = α + 2, α 7 = α + 1, α 8 = 1. ) 8.4 ( F p version ) 8.4.1 ( F p version ) F p a(t), b(t), a(t), b(t) d(t), u(t), v(t) a(t)u(t) + b(t)v(t) = d(t) (1) b(t) = 0 d(t) := a(t), u(t) := 1 (2) b(t) 0 a) { r n (t) }, { u n (t) }, { v n (t) } r 0 (t) := a(t), r 1 (t) := b(t), u 0 (t) := 1, u 1 (t) := 0, v 0 (t) := 0, v 1 (t) := 1, q (t) := r n 2 (t) r n 1 (t) r n (t) := r n 2 (t) q(t) r n 1 (t) = r n 2 (t) r n 1 (t) (n = 2, 3, ). u n (t) := u n 2 (t) q(t) u n 1 (t) v n (t) := v n 2 (t) q(t) v n 1 (t)

Information Analysis by Ken-ichi Shiota 39 b) r n (t) = 0 n d(t) := r n 1 (t), u(t) := u n 1 (t), v := v n 1 (t) (3) c := (d(t) ), f := (c F p ) d(t) := f d(t), u(t) := f u(t), v(t) := f v(t) 8.4.2 ( ) ( F 2 ) ( ) = 1 (3) 8.4.3 F p n G(t) F p n F = { F p n 1 } G(t) a(t) F ( a(t) 0 ) ( version ) a(t), G(t) u(t) 8.5 8.5.1 8.2 8.3 8.5.2 ( 8.3 G(t) F p n ) 8.5.3 p n p n F p n F p - n 8.5.4 F p n p n 1 g F F = { g, g 2,, g pn 1 = 1 } g F p n

Information Analysis by Ken-ichi Shiota 40 1. : (1995) 2. : = 4 ( 1996 ) 3. : = 5 ( 1980 ) 4. : ( 1987 ) 5. D. M. Bressoud: Factorization and Primality Testing = Undergraduate Texts in Mathematics, Springer-Verlag ( 1989 ) 6. H. Cohen: A Course in Computational Algebraic Number Theory = Graduate Texts in Mathematics, 138, Springer-Verlag ( 1993 ) 7. N. Koblitz: A Course in Number Theory and Cryptography, 2nd Edition = Graduate Texts in Mathematics, 114, Springer-Verlag ( 1994 ) 8. A. K. Lenstra, H. W. Lenstra Jr. (Eds.): The developement of the number field sieve = Lecture Notes in Mathematics, 1554, Springer-Verlag ( 1993 ) 9. A. Salomaa: Public-Key Cryptgraphy = EATCS Monographs on Theoretical Computer Science, 23, Springer-Verlag ( 1990 ) ( )