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

• Published on
08-Dec-2016

• 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) n 1.

, n > m 0, sn sm - . , s0 = 3, a = 2. -, 22 1

n

ns = + . ( n- , ).

6. a = bq + r, , a > b > 0, q 1. b a/2, , ,

• 12

r < a/2. b > a/2, , r a/2. , i 0 r i+2 < ri /2, ri > 0? ( r0 = a, r1 = b). , , r3 < r1/2, r5 < r3/2, . . . , r2n+1 = 0, n 2n b. - .

7. a b , . S = {ax + by: x y }. h S, . a = qh + r, 0 r < h, , r S -, h|b. , a b h , h = (a, b). , - 3.8, s t as + bt = (a, b).

8. 3 3.10, , , (a, b) = 1, (Ra, Rb) = 1, Ra (10 1)/9, a . , (Ra, Rb) = R(a, b).

9. m n u, v nv mu = 1. , x = a(am + bm)u, y = = b(am + bm)u, z = (am + bm)v xm + ym = zn. [- m = n 3 , - ].

10. p q n > 1. - np 1 nq 1 npq 1? 3 - 3.1 6 2.2, ,

( 1)( 1)( 1)( 1)

pq

p qn nNn n

= .

3.11. : ax + by = d, (1)

a, b, x y , , a, b . - x, y (1). (a, b) = h, a = a1h, b = = b1h, (a1, b1) = 1.

1. , h d, (1) - [h | (1)].

2. , h | d, d = d1h; ,

a1x + b1y = d1. (2) s, t , a1s + b1t = 1, x = sd1, y = td1 -

. , X, Y ,

• 13

a1(X x ) = b1(Y y) , X = x + kb, Y = y kb k.

3. 7x + 5y = 17; 6x + 9y = 33; 6x + 12y = 36.

4. a b , a b, b a. , x y ,

ax + by = (a , b), 1 x b 1 1 y 1. 5. 4 -

1 , a a 1 - ( 2) (b 2) b 1 . , a b b a, , - (a, b)/ab ().

6. ax + by + cz = d, (3)

, (a, b, c) | d, - . , (a, b, c) = (a, (b, c)) (. 8 - 2.1), , x0 u0, - ax0 + (b, c)u0 = d. , y0 z0, - by0 + cz0 = (b, c). by + + cz = k(b, c) k , , - (3) s t:

x = x0 + ( , )

( , , )b c s

a b c,

y = uy0 ( , , )as

a b c y0 + c t,

(b, c)

z = uz0 ( , , )as

a b c z0 b t.

(b,c)

7. : 2x + 6y 8z = 0; 2x + 6y 8z = 2; 7x y + 3z = 2.

2x + 5y + 10z = 100; 2, 5 10, , . (, , (), ()!).

, -, s t, as + bt = (a, b). .

3.12. . si ti i = 0, 1, 2, . . .

: s0 = 1, s1 = 0, t0 = 0, t1 = 1 i 2, si = si-2 qi1si1, ti = ti2 qi1ti1 .

• 14

r0 = a, r1 = b. ri = asi + bti i 0, , (a, b) = asn + btn. (, rn - a b).

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

s, t, , as + bt = 1, . ., as 1 b. s - , () b. b > 0. b s: a(s + mb) + b( t am) = 1, -, 0 s = s + mb < b. s s b[s/b]. - s. , s2 -, INT ,

q1 := INT(s2/b); IF (q1 > s2/b) THEN q1:= q1 1; s2:= s2 b*q1. ,

, , 271 104 (mod 2807); 191 104 (mod 1652).

2. ax + by = d, ax + + by+cz = d. , .

3.14. : ax + by x y . a > 0, b > 0

(a, b) = 1. = {ax + by: x 0 y 0}. , m A, ab a m A. ; , . (a, b) = 1, - x, y , ax + by = m ; k Z, a(x + kb) + + b(x ka) = m; , x , 0 x b 1? ( ), m ab a b m : x, y, u, v , ax + by = m , 0 x b 1, y < 0 ( m A), au + bv = ab a b m , 0 u b 1, v < 0. , a( x + u + 1) + b( y + v + 1) = ab - (a, b) = 1, y + v + 1 = la, x + u + 1 = (1 l )b - l. !

, m > ab a b - m 0 m ab a b . ( a b), m .

• 15

3.15*. . ( -) . 3.14, , a b (>0) (a, b) = 1, m > ab a b ax + by x 0 y 0. , a b, a b (, ), m n, m n > ab a b. , m n a b. , ab | mn. , ab | mn, . , , a b , ab | mn : a | m b | n, a b m. , ( )! , - w, x, y, z ( 0), , aw + bx = m ay + bz = n. -, , , - m n: , ab | mn? , a b ?

3.16. : : a, b

a (12 ln 2/2)ln b . , a b.

3.17. ( . . ). , a b

, s t , as + bt = 1. , s t; , a(s + rb) + b( t ra) = 1 r. f (r) = (s + rb)2 + ( t ra)2. , , r = 0: . - f (r) = r2(a2+ b2 ) + r(2 sb 2ta) + ( s2 + t2 ) r. , , r, - r.

1. , f (r) r = 0, , f(1) f(0) f(1) f(0)?

2. , . 1 , |2sb 2ta| a2 + b2. , - s t, a |2t | b |2s |. .

3. ( b > 1), a = bq + 1, s = 1, t = q. .

• 16

4. , a = bq + r ; (b, r) = 1 , bs1 + rt1 = 1, b |2t1| r |2s1|. -, s = t1 t = s1 qt1. , b |2s | a |2t |.

4. [x]

4.1. . x [x] -

x. , - , :

4.2. [x] , -

x 1 < [x] x. [x] , - x = [x] + y 0 y < 1.

4.3. 1. , n , [x + n] = [x] + n. 2. , n , [x] n x n. 3. , x y ,

[x] < [y] c n Z x < n y. ( , n [y]). 4. , [x + y]= [x]+ [y] + , 0 1. 5. , x y [x] + [y] [x + y].

(, ). 6. x y 0. , [xy] [x][y].

, x y < 0 ?

7. , x [x] + [x + 12

] = [2x].

, , , ,

n x < n + 12

n + 12 x < n + 1 n.

, x n > 0,

[ ] [ ]1 nx xn = .

8. x R P Q , Q > 0. -, k, [x] + P < Qk x + P. ( 3 4.3). , [ ]x P x P

Q Q + +=

.

, , a b , b > 0,

• 17

aab

b bb

= .

9.* 8 4.3. , f , , , x f, f(x) - , x . ( f {y: [x ] y x}) [f([x])] = [f(x)]. (. n = [x] , n < x. , [f([n])] [f(x)], , [f([n])] + 1 [f(x)]. , f(n) < < [f(x)] f(x) , , y , n < y x f(y) = [f(x)]. y ( - f), ).

10. r i , i > 0. 2

r ixi+= . -

[x] x, , 2[x] 1 < ri+ 1 ,

x 1 < [x], , r 1 2[x] + 1. ,

ir 1+

2[x] + 1 2[x] 1 < i

r 1+,

ir 1+

2

+iir

2 + 1.

1?

11. x > 0. , 1 x [(x + 1)/2].

12. k 2. 3k 2k : 3k = = q 2k + r,

0 r < 2k, q = [3k/2k]. s = q 2k 1, < 3k. , s k- ( ) - . k- 1 2? s = (q 1) 2k + (2k 1) 1k, , s (q 2 + 2k) k- . , , [3k/2k] 2 + 2k k- . k = 2, 3, 4? [ - ; . ].

• 18

13. , n 25

n + 2 < n(n + 1) < 1

2n +

2 , 710

n + 2 < n(n + 2) < (n + 1)2

710

n...