P={0, 1, 2,... q - 1}, P. (. 3.1.6). .
. F , q . F k.
, , .. , =1 , . , , - .
: F= , , k n.
. F2={0,1}.
, n=3, q=2. : . x. n=3 k=1, , . . .
14. ρ- , . 1978 .
p a b x, :
:
:
: .
i, . i
,
15. . ( ρ -1) .
. ,
, (
). . .
: . , (ρ − 1)- . .
(ρ -1) :
|
|
n , 1 < p < n . , a, 1 ≤ a < p, ap−1 ≡ 1(mod p), .
n = p*q, p,q =>
<p: ap-1 mod p = 1, aq-1 mod q = 1 =>
ap-1 = k*p, (p-1) .
(ap-1-1,n) = p.
: p-1 = 2r^1 * 3r^2 **Br^t. B < B1 (p-1).
M(B1) = ∏ pir^i, pir^i < B1.
a, 2, aM mod n.
(n, aM−1) = d, 1<d<n, .
(ρ -1) .
,
q p − 1, B1.
B2 ~ B12.
b aM(B1) mod n, .
q0 < q1 <... < qs [B1; B2]. p−1 qi , n, c = bq mod n, d=(n, − 1). d = 1, ci. ci+1 bqi+1 mod n = bqi+δi mod n = bqi bδi mod n = ci bδi mod n, δi = qi+1 − qi.