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

  • Published on
    08-Dec-2016

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

Recommended

View more >