, : , . . , .
, . , . .
, . , , . , .
: n .
, n , , 2n .
(
) . , () .
, , RSA, . n , d.
1994 -, . . .
- N O((logN)3), O(logN).
RSA.
.
RSA.
( ), N O((logN)3), O(logN) .
, , RSA.
RSA N, RSA N. N , . , , . , , . ѐ , .
|
|
, : ѐ . . , ( ) , , , , .
14. -
, g p(, ), . , , : a, b. A= gamod p , B= gbmod p ѐ .
, , ( ). a B Bamodp= gabmod p, b A Abmod p= gabmod p. , : K=gabmod p. , ( ) gabmodp gamodpgbmod p, p,a,b .
- , :
a ѐ p g( pg ), p g p A, A = gamod p ѐ K, B aK = Bamod p
, :Bamodp = (gbmodp)amodp = gabmodp = (gamodp)bmodp = Abmod p
, ab 10100 p 10300. g .
- , . , , , "-".
15. - .
|
|
- (Elgamal) , 1984
. -
:
1 ,
2 .
3 .
, - .
16. . .
Y^2+axy+by=x^3+cx^2+dx+e
1. ( O)
+0=
2. ={x;y},-A={x,y}
A-A=O
3. P Q 1 2, , . P Q. , , P Q, (Q), P Q -Q.
4. Q+Q. Q, S , S:
Q+Q=2Q= - S
p
Ep(a,b)
p a b(
4a^3+27b^2modp<>0)
,
1) O
2) y x;
3) :
0<=x<=p-1
0<=y<=p-1
(y^2)modp=(x^3 + ax+ b)mod p
17. . BB84.
, , .
( , , , ) . , . , , , . , , , . .
(StephenWeisner) 1970 . 10 , , .
1984 . , 84.
84 , 0, 45, 90, 135 . , : , , , , ; 45 135 . , 45?, .
18. . . . . . .