|
����������: ������ �����: ���������� �� ���������.
��������� ������������ �������� (������ �����-�����)
�� ���������� 2 ������ ������� ������ ������������,
������������ ���������. ��� ����� ������ � ���������
������ ������� �� ���������� ����� ��� ��� ��������� ������� ��������.
����� �����-����� 1
����� ������ ����� ������ ������� ������ ���������� �� ������������
�������� �����, �������� m. �� ���� � ������ ������, ����� m ����
������������ ���� ������� ����� �������� ������ �������, ����� m
�������������� ���� ������� �� ��������� �� ����� ������
��������� ������� �� m. �������� ����� �����, ��� ������ �������
������, ��� ����������, ������ �� ��������. ����� "�����-�����"
������������ � ��� �������� ������, ��� ������ ��������� �������
�� ���������� ������ ���������� �����.
���������� ����������� f ������ Zm � Zm:
f: Zm --> Zm
f(x) = x^2 + 1 (mod m)
������� ��������� ������� ������� b_0 ������ Zm.
���������� ����������� ������������������ ��������� ������ Zm:
b_0, b_1 = f(b_0), b_2 = f(b_1), b_3 = f(b_2), ... (2)
������������������ ������������ ����� ������ �������� b_0 ��� ����������� f.
��������� ��� �������� ������������������ ����������� ��������� ���������,
������������������ ����������� -- ������, ��� �������� ���������
�������������� ������� � ����� ���������� ������������� ������.
����� p -- �������� ����� m. ���������� �������� ������������������
(2) �� ������ p (�.�. ������ ��������� b_i ��� ������������ �����������
Zm --> Zp):
c_0 == b_0 (mod p), c_1 == b_1 (mod p), c_2 == b_2 (mod p), ... (3)
��� ��� � Zp ������ ���������, ��� � Zm, �� � ������� ������������
������ ������������������ (3) ������, ��� ������ ������������������ (2).
�������������, �������� ���� �������� i, j �����, ���
c_i = c_j, b_i != b_j.
��� ��������, ���
b_i == b_j (mod p), b_i != b_j (mod m).
������ ��������, ��� (b_i - b_j) ������� �� p, �� �� �������
�� m. �������������, ���(b_i - b_j, m) �����������, � ��� �������
��������� m �� ���������.
����, �������� �������� 1 �������� � ������ ����� � �����������
����������� ������������������, ��������� �� ��������� ���������
���������. ��� ���� ������ ����, ����� ���������� ����� �����
��� ��������, �� ��������� ���������� ����� �������� �� �������� � ����� m.
�������� �����������, ����� ���������� ����� �������� �����������.
����� ���������� 2 ������� ������� ������ ������ ����� � ������������������.
������ ������ �������� �������. ������ ����-���� �������, �� ���� �����
�������.
������ 1
--------
����������� ��������� ������������������ ���������:
b0 <---> b1
b1 <---> b3
b2 <---> b5
b3 <---> b7
b4 <---> b9
. . .
b_i <---> b_{2*i+1}
. . .
���� ��� ������ �� ������ �� ��������� ���� ���������,
��������� ���������� ����� ������������� ���������� �� ������
���� ������������� ����� �� �������; ����� ����, ����� �������
���������� ������, ��� ��� �� ���� ��� ������ ������ � �������������
������� ������������������.
������� �������� ���������� ��������.
�������� ������������1(����: ����� ����� m, �����: ����� ����� d): �����
| ����: ����� ����� m
| ����: �������� ������������� �������� d ����� m
| ������������ ��������: true, ���� ������� ���������,
| false � ��������� ������
������
| maxSteps := 1000000 // ������������ ����� �����
| step := 0
|
| b0 := ��������� ����� � ��������� 0..m
| b1 := mod(b0 * b0 + 1, m)
| d := gcd(b1 - b0, m)
|
| ���� ���� step < maxSteps && d == 1 ��������� // ���� ��� ���������
| | b0 = mod(b0 * b0 + 1, m) // ��������� ����������� f
| | b1 = mod(b1 * b1 + 1, m); // ���� ��� � b0 � ������
| | b1 = mod(b1 * b1 + 1, m) // � b1
| | d := gcd(b1 - b0, m)
| | step := step + 1
| �����_�����
|
| ������� (d != 1) // ����� := d �����������
�����_���������
�� ������ ���� ����� �� ������ ��������� �������� ����������� f.
��������� ����������� ��������� ��������� ������ ��� ������ ���� ���.
������ 2
--------
����������� ��������� ����������� ������������������ ���������
b0 <---> b1
b1 <---> b2
b1 <---> b3
b2 <---> b4
b2 <---> b5
b2 <---> b6
b2 <---> b7
b4 <---> b8
b4 <---> b9
b4 <---> b10
. . .
b4 <---> b15
b8 <---> b16
b8 <---> b17
. . .
b8 <---> b31
. . .
��� ������������������ ��������� ����������� �� �����. � ��������� �����
�� ���������� ������� b_s, ��� s -- ������� ������, ���������������
� ���������� b_{2s}, b_{2s+1}, b_{2s+2}, ..., b_{4s-1}.
����� �������� 2s ���������.
������� ��������.
�������� ������������2(����: ����� ����� m, �����: ����� ����� d): �����
| ����: ����� ����� m
| ����: �������� ������������� �������� d ����� m
| ������������ ��������: true, ���� ������� ���������,
| false � ��������� ������
������
| maxSteps := 19 // ������������ ����� ����� 2^19
| step := 0
|
| b0 := ��������� ����� � ��������� 0..m
| b1 := mod(b0 * b0 + 1, m)
| a := b1 // ������ ������� �����
| seriesLength := 1 // ����� �����
|
| ���� ���� step < maxSteps && d == 1 ��������� // ���� ��� ���������
| | ���������: b0 -- ������� ������������������ � ��������,
| | ������ ���� ��� ������� ������
| | a -- �������, ������ �������� ����� ���������� �������
| | �������� b0 (��� 1, ���� ������ b0 ����� 0)
| | seriesLength == ���������� ������� �������� a
| | d := gcd(b1 - b0, m)
| | len := 0
| |
| | ���� ���� d == 1 � len < seriesLength ���������
| | | b1 = mod(b1 * b1 + 1, m);
| | | d := gcd(b1 - b0, m)
| | | len := len + 1
| | �����_�����
| |
| | b0 := a
| | a := b1
| | seriesLength := seriesLength * 2
| �����_�����
|
| ������� (d != 1) // ����� := d �����������
�����_���������
����� �����-����� 2
����� m --- ����� �����, ������� �� ������������ �� ���������.
��� ����������� � ���� ������������ �������� ������� �����
m = p1^e1 p2^e2 ... pk^ek
�����������, ��� p1 - 1 ����������� � ���� ������������ ��������
������� �����, ������ ������ �� ���� �������� �� ����� ������.
����� �����, ���������� N �����, ���
p1 - 1 = q1^a1 q1^a2 ... qr^ar
q1^a1 < N, q2^a2 < N, ..., qr^ar < N.
���������� ������������ ������������ ������� ������� �����, ��
������������� N. ��������, ����� N = 20, ����� ���������������
������� ������� 16, 9, 5, 7, 11, 13, 17, 19. ��������� ��� �������
������� ����� t1, t2, ..., ts.
������� ������������ ����� ����� b. ���������� ������������������
b0 = b,
b1 = b0^t1 (mod m),
b2 = b1^t2 (mod m),
...
bs = b_{s-1}^ts (mod m)
������ ���, �������� bi, ��������� ������������
���(bi - 1, m).
������������, ��� � ������� ������������ �� �����-�� ����
���� ��� ����� ������������� ��������� N. �������������,
�������, ���
p | ���(bs - 1, m).
�������������,
bs = b^(t1 t2 ... ts),
�, ��������� �� �������������, p1 - 1 | t1 t2 ... t3, �� ����
t1 t2 ... ts = (p1 - 1)g, ��
bs = b^(t1 t2 ... ts) = b^((p1 - 1) g) =
(b^(p1 - 1))^g = 1 (mod p1)
�� ����� ������� �����. ������, bs - 1 ������� �� p1, ����� m �����
������� �� p1, �������������, ���(bs - 1, m) ������� �� p1.
��������������� �������� �� ������� �������. ������� N = 20.
������� ��� ������� �������, �� ������������� 20:
t1 = 16, t2 = 9, t3 = 5, t4 = 7,
t5 = 11, t6 = 13, t7 = 17, t8 = 19.
���������� ��������� �� ��������� ����� m = 41779 = 41 * 1019.
������� b = 2. ��������������� ���������
2 ^ 16 (mod 41779) = 23757, gcd(23757 - 1, 41779) = 1,
23757 ^ 9 (mod 41779) = 7970, gcd(7970 - 1, 41779) = 1,
7970 ^ 5 (mod 41779) = 33580, gcd(33580 - 1, 41779) = 41.
�� �������� ������������� �������� �� ������� ����, ���������
41 - 1 = 8 * 5 ����� (t1 * t2 * t3) = 16 * 9 * 5.
�������� ��������� ������� �� ����� N --- ��� ������ ���,
��� ������� ����� ����� ��������� � ������� ����� ���������.
������ ��������� ����������� �� 2 ����. ������� �� ���������� ���
������������ ������� ������� �����, �� ������������� N. ���� ���
����������� ������ ���� ��� � �� ������� �� �������� ����� m,
������� ��������������� ������� �����, � �������, �������� � ����
� � ���������� ������������ �����������. ����� �� �������� ���������
������� ����� b � ��������� ��������� ���� ������������������
�������� b. ��� ������ ������� bi ����������� ���(bi - 1, m).
�������� ����������� �������, ���� ����������� ��� �����������.
�������� ����� ���������, ���� ��������� ��� �� �� ������ ����,
�, ������, �� ������ ����� ����. ��� ���� �� ������������� �����
��������������� ����������� ������������
(b_i - 1) (b_{i+1} - 1) (b_{i+2} - 1) ... (b_{i+99} - 1) = n (mod m)
� ����� ����������� ���(n, m).
| |