# Элементы теории чисел и криптозащита: Учебное пособие для вузов. Часть 2

• View
229

11

Embed Size (px)

Transcript

• 2

: . . ,

. .

-

2008

• 2

- -, 11 2008 ., 1

..

- , - .

4- 4- - .

010501

• 3

C ...............................................................................................4

1. ........................................................................................4

2. ...........5

3. . ................................................................................8

4. [] ................................................................................. 16

5. .......................................................................................... 22

6. .................................................................. 28

7. (x) ........................................................... 33

8. ............................................................................. 34

9. ............................................................................................ 36

10. mod m ..... 39

11. .................................................... 44

12. .............................................................................................. 48

13. mod m............................................. 53

14. ....................................................................... 54

15. ............................................................................. 58

16. ..................................................................................... 59

17. ..................................... 63

18. ................................................................................ 65

19. ................................................ 70

20. ............................................................................. 75

21. RSA (Rivest R., Shamir A., Adleman L.) ............... 79

22. ......................................................... 82

23. ......................................................................... 83

.......................................................................................... 95

• 4

- . - , , - , - .

, , -, . - , - - .

- , , .

[1, 2, 4, 7, 914]. - , - , , , - [6, 7].

, , .

1.

1.1. 1. , 24n+2 + 1= (22n+1 2n+1 + 1)( 22n+1 + 2n+1 + 1).

n = 4, , . - , , x4 + 4 y4 = (x2 2 xy + 2 y2)(x2 + 2 xy + 2 y2)? , , x4 + 4 - x > 1.

2. , 23n 1 = (2n 1)(22n 2n + 1). - - 1?

3. , 2mn 1= (2m 1)(2m(n-1) + 2m(n-2) + ... + 1), an 1 = (a 1)( an1 + an2 + ... + 1). , n 2, a 2 an 1 . , a = 2. , n (, a = 2m). 2n 1, n , .

• 5

4. -, . , , a10 + 1 = (a2 + 1)((a4 + + a3 + 7a2 + 5a + 1)2 10a (a3 + 2a2 + 2a + 1)2). - , , 10a , - . . , a = 103.

5. , k 2 k 1 k! + 1, k! + 3, . . . , k! + k, . -, . , k = 8, 40 322, . . . , 40 328 . . 100. 13 , - 114.

6. n . , (2n + + 1)/3 .

7. n . , (10n 1)/9 . , 10n-1+10n-2 + ... + + 101 + 1, . . ! -, n , . , n > 8. , n ; n = 3 5, , .

8. , , . -, (2ab 1) = (2a 1)(2c 1) . : n ( - 1 n), 2n 1 . [, 2n 1 ; . 1.1 (3)]. , n = ck c 2, k 3, - 2n 1 . n, 2n 1 ?

9. p , k 1, , p + 1 = 2t s, s . , 2t 2, - pk + 1. [ : ].

2.

2.1. 1. , (a, b) = 1 (a, ) = 1, (a, b) = 1.

• 6

, a | n, b | n (a, ) = 1, ab | n. [ ra = sb = n (a, b) = 1, , a | s ].

, a | b (b, ) = 1, (a, ) = 1. 2. , a | b , (a, b) = | a | . 3. , (a, b) = 2 a | k , b | k, ab | 2k.

, , ab k . 4. , 1 r p1, p , (r!, p) = 1.

, ! ( 1)...( 1)

!( )! !p p p p p rr r p r r

+= =

p . , n , , n = k ps,

p , p k, k > 1 s > 1, np

-

n, . . , , - , n.

5. , a, b, x, y x/a = y/b ( !). h = (a, b) a = a1h, b = b1 h a1, b1. , x = ka1, y = kb1 k. ( ), a | b (a, b) = 1, a | . [, (a, b) = 1 b. = 4, b = 2, = 6].

6. a, b, c, d , (a, b) = 1 (c, d) = 1, a

b c

d . , a

b + c

d -

. , b = d. 7. 4 -

a b (a, b ), ab , , . -, x = = ka1, y = kb1 k = 0,h . , a + + b (a, b) .

8. a, b . , - , ((a, b), c) = ((c, a), b). , (a, b, c), a, b c. , ((a, b), (a, c)) = (a, b, c).

9.* a, b, c, x, y, z . -, x/a = y/b = z/c. h = (a, b, c), a = a1 h, b = b1 h, c = c1 h. -, (a1, b1, c1) = 1. , ((a1, b1), (a1, c1)) = 1 , 1, , x = ka1, y = kb1, z = kc1 k.

• 7

10.* a b c, abc , - , , . 9*, , - (a, b, c) +1 . - 5, , , - , a + b + c ((a, b) + ( b, c) + (, a)) + (a, b, c). [ n- - , ].

11. pi i- (p1 = 2, p2 = 3 . .) pk < n < pk+12 ( k 1). m - k m = qn + r, 0 r < n ( r m n). (, 7 < 101 < 112 (k = 4) m = 210 = 2 101 + 8). , r 0. , n , - (n, r) =1. [ , , (n, r) = 1, n , . , n p1, p2, . . ,pk, n , - n , n].

12. , 2184 2200 - , >1, , . , , . [- !].

2.2. 1. , h = (a, b) l = [a, b], h | l. ,

h | l , a b ( , a = h b = l), h = (a, b) l = [a, b]. a b, (a, b) = 12 [a, b] = 72. - ? ?

2. r s . , - r = ux, s = vy, (u, v) = (x, y) = 1 uv = (r, s), xy = (r, s), - x y . r = p1r1 p2r2 . . . pkrk, s = p1s1 p2s2 . . . pksk , x = p11 p22 . . . pkk , y = p1y1 p2y2 . . . pkyk,

=

ii

iiii sr

srsy

,0,,.

, ri = si, - pi x, y, . - u, v, x y, , r = 100 s = 60 r = 700 s = 300.

• 8

3. , [[a, b], c] = = [[b, c], a] = [[, a], b]. [a, b, c] a, b c. [a1, a2, . . . , an].

4. q1 < q2 < . . . < q8 r qj,, qi 1 i < j 8. = {5, 7, 8, 9}. -, . (, q/7 0, 1, . . . , 6, q/8 1, 3, 5, 7, q ). , m A, - , qi , m, , , m. ( , qi, ). , r 5, 7, 8 9 , , 5 7 8 9 = 2520? , - 11, 17, 23, 29, 41, 53, 59 r = 5040.

5. , max(i, j, k) = i + j + k min(j, k) min(k, i) min (i, j) + min(i, j, k) i, j k. [, i j k]. , a, b ,

[ ] ( , , ), , .( , )( , )( , )

abc a b ca b cb c c a a b

= 6. , (a, b) = 1 d | ab. ,

d d, d = d d, d |a, d |b. - , (d, d) = 1. : - d | a d | b, d d | ab, ab - a b.

3.

3.1. . k :

(a, b) = (a + kb, b). .

, a + kb b a b, . . d | a d | b d | (a + kb) d | b. . , a b a + kb b.

3.2. 1. . 3.1, , (6n + 1, 6n 3) = 1 -

n. [ k = 1]. , (5n + 3, 3n + 2) = 1, , , (5n + 3, 3n + 2) = (2n + 1, 3n + 2).

• 9

2. p p | n, p n p < n. a = (n + 1, p + 1), b = (n 1, p 1). , (a, b) = 2, (a, p) = 1, (b, p) = 1. , 3 2.1, abp | 2(n p) , , ab < 2n/p.

3. , . a b - b 0. q r ( ),

a = bq + r, 0 r < |b|.

, .

S = {a bq : q Z}.

, S (?).

r S, . , r 0 r < |b| ( , b > 0). , q r , , a = bq + r= bq1+ r1, 0 r< |b| 0 r1 10. ( 100 , , RANDOMIZE - , -

• 10

, . - RANDSEED (i*i).

3.5. : : a = bq1 + r2, . ., r2 = a bq1, b = r2 q2 + r3,

. ., r3 = b r2 q2. a a bq1 = a b[a/b], b b a q2 = b a[b/a] (, a 0!), a b r2 r3, . , r4 r5, . . , . 3.4 , . - ?

3.6. : , -

, . - , . , a h 1/h , 1, . . . , n h, 2h, 3h, . . . , [n/h|h] h, [n/h]/n - 1/h. ph , = h. , (a, b) = h a/h, b/h , (a/h, b/h) = 1. , , = h, ph = (1/h)(1/h)p1. 1, -

=1k

p k = 1, . ., p1h=

1

h 2 = 1.

( / )1 h 2, [8], 2 /6. -, p1 6/2 = 0.6079. , - , = 1 2? > 10? , - 1000 , -, 2 > 10. - . 2500 a b, 1 a 50 1 b 50 .

3.7. , (330, 140), -

, : 10 = 50 40 = 50

• 11

(140 50 2) = 50 3 140 = (330 140 2) 3 140 = 330 3 140 7. - = 10, as + bt, s = 3, t = 7. , .

3.8. . (a, b) = h. s t,

, as + bt = h. 3.9. . (a, b) = 1, s

t, , as + bt = 1. 3.10. 1. , a | bc (a, b) = 1, a | c, -

as + bt = 1 . 2. , (a, b) = 1 | (a + b). , (c, a) =

= (c, b) = 1. 3. a = bq + r, 0 r < b, .

, n > 1 > 0, na 1 = (nb 1)(nb(q1)+r + nb(q-2)+r + . . . + nb+r + nr) + nr 1.

A = BQ + R. 0 R < B ? , (, ) = (na 1)(nb 1) - (a, b) c ri nri 1. , , (na 1, nb 1) = n (a, b) 1.

4. (an bn)/(a b) = an + an-1b + an 2b2 + . . . + bn a b ,

1, ( , )n n

na b a b a b nba b

= .

: , , (a b, n(a, b)n1). , nbn1 - nak bnk k = 1,2, , n. h = (a, b), sa + tb = h , a b nbn1 nhn1.

5. s0 > a > 0 , (s0, a) = 1 sn n = 1, 2, 3, . . . sn = a + s n1(sn-1 a). , sn a = s0 s1 s2 . . . s n1(s0 a)