1. , .
2. ( ). .
3. ( , ); . .( ).
4. RSA ( , ; ). .( ; m).
(+2 )
5 RSA.
: , t, t = [N/ 13] N ( ).
1 6
. | . 2 | . 3 | . 4 | |||||||
x | y | mod n | p | a | b | p | q | e | m | |
5,11 | ||||||||||
7, 15 | ||||||||||
8,17 | ||||||||||
23,9 | ||||||||||
17,8 | ||||||||||
4,21 | ||||||||||
6,14 | ||||||||||
9,22 | ||||||||||
15,8 | ||||||||||
13,6 | ||||||||||
7,17 | ||||||||||
9,23 | ||||||||||
7,12 |
1 ( ).
2 .
3 .
4 RSA, ; .
5 ?
|
|
, ( ). .
x, n> 0 x (mod n) r x n ( x= k n + r, k ).
( )
x, y n > 0 , (y, n) = 1 ( ; (y, n) = 1, y n ).
1. (x + y) mod n = [(x) mod n + (y) mod n] (mod n).
2. ( x) mod n = (n x) mod n = n (x mod n).
3. (x x y) mod n = [(x) mod n x (y) mod n] (mod n).
4. y-1 mod n , y n. [1,n 1], (y-1 x y)mod n = 1.
, ( ). y, (y, n) = 1, (x x y-1) mod n (x / y) mod n.
x mod n k . x mod n = y mod n x y , n. x ≡ y mod n y ≡ x mod n. , x y .
, . :
) ( );
) ( ).
x y (mod n) x, y > 0 (. = x x x x (y ) (mod n)).
2 (y ÷ 2):
y÷ 2 = | y /2, y | |
(y 1)/2, y |
:
x y= | (x 2) (y ÷ 2), y | |
x (x 2) (y ÷ 2), y |
: x, y, n: x> 0, y≥ 0 n > 1
: x, y (mod n).
(x, y, n)
1. if y = 0 return (1);
2. if y (mod 2) = 0 return (E (x2(mod n)), (y ÷ 2), n);
3. return (x ∙E (x2(mod n)), (y ÷ 2), n) (mod n).
return () (.. 2, 3 ).
1 221(mod 23).
221(mod 23) = (2, 21, 23) = 2∙ (4, 10, 23) = 2∙ (16, 5, 23) = 2∙ 16∙ (162, 2, 23) =
= (2∙ 16)(mod 23) ∙ (162(mod 23), 2, 23) = 9∙ (3, 2, 23) = 9∙ (9, 1, 23) = 81∙ (9, 0, 23) =
=81 (mod 23) = 12.
: 221(mod 23) ≡ 12.