- .
- ( 1976 .). , , . -.
, .
1. N (N ) g ,
(1 < g < N 1), , .. . , N . .
N g . , . N , 512 , N 1 . N .
2. ( , ).
3. , .
4. .
5. , :
: ;
: .
K = K', .
K ( ) .
, , ( RSA):
.
,
.
. , N = 47, g = 23. , : .
K, :
,
.
, , :
.
, , : ,
, = 16, .
.
, 1985 ., , . .
|
|
( ), G, G < . G .
X, < . X .
. Y .
, K, 1< K < 1, , K ( 1) .
;
.
(, b) . , .
(, b),
.
, , .
. = 11, G = 2, X = 8. . , Y = 3. = 5.
K = 9. , (K, 1) = 1. , (9, 10) = 1. b:
;
.
(a, b) = (6, 9).
. , X:
.
= 9/68 mod 11 . , = 5.
, 512...1024 .