, . , , , .
. = nan -1 a 1 a 0, rA = k s... k 1.
, , ( ) .( ), , , . . : r (mod p), r (mod p); r (mod p); . r .(mod p).
. , , :
r r + (mod p), (4.6)
r = 2 r .
n k s, .
n - , an n +1 [ n +1 (n + 1)- ].
k s= 1, 2s. . (4.6)
r (r + an n +1+ ak s) mod (2s1), (4.7)
, 2s, :
s =3 nn -1 n -2 n -3 a 3 a 2 a 1
2221 20 22 222120
:
n.......... 0 1 0 1
k s........ 0 0 1 1
......... 0 -1 +1 0
. an ( n +1-1); n +1=1, 0. , (4.7)
r . r + ak s mod (2s-1), (4.8)
. = 1,01011010, , p =7 (s =3).
. 7: r = 101 011 010 = 011(mod7)
= 0,10110100 r =110.
(4.7) an = 1, ak s= 0 :
r =1101+000= 101(mod 7).
: A .=0,10110101, r .= 110 + 000 = 110(mod 7).
|
|
: r =101, r .=110.
. 2,
=( q 1)/2; r A =(rA ak s)/2.
. ,
rA = r A +(mod 2s-1). (4.9)
:
1. 0 0 1 1
k 1........0 1 0 1
:
=3............ 00 10 01 00
=7............ 000 100 011 000
,
= 1, n -1 an -2 a 2 a 1; .= 1,1 n -1 a 3 a 2,
. (4.9) , :
1. 0 0 1 1
k 1..... 0 1 0 1
:
=3............ 10 01 00 10
=7............ 100 001 000 100
. = 1,01110111101, , p =7.
. 7: r A= 101 110 111 101 (mod 7).
=0,10111011110 r =001.
(4.9) 1= 1, k 1= 0, = 011 :
rA 001+011 l00(mod 7).
.=1,10111011110, = 000:
rA . 001 + 000 001(mod 7).
: rA = 010, rA = 100, rA .=001.
2. 2 , : = + 2( ).
,
= + +.
, , :
(4.10)
r + ; .
. =010000111 =101110011 7.
. : rA =010, r = 000, rA + =010.
:
= 000000011,; =000000110, r 1=110.
= 001.
(4.10) :
r = 010+001 011(mod 7).
: r =011.
. :
= 2-1( + )2-1( ).
2-1 , , .
, ; , .
|
|
.
. 3:
= 10011001, rA = 00, = 0,001111, rB = 01.
. :
+ = 11101000, rA + B =01.
(4.9) += 10.
A B =11010110, r =01, =10, =01.
, =10+10=00(mod 3).
: = 00.