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

  • View
    229

  • Download
    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)