|
|||||
����������: ������ �����.������������� ���� �������� ������.© ���������, ���-��� ���. �������� ����������� ��� ���������� �� ������������ ������ ����� � �������.����� ������� �����. ����� p -- ������� �����. ����� ��� ������� ������ ����� b, ��������� �� ����, ����������� ��������� bp-1 == 1 (mod p). ����� ������� ����� �������� ���������������� ���������� ������� �������� (������� ������ �������� ������ ����� ������� ������) � ���� �����, ��� ������ Zp � ������ �������� p �������� �����, �.�. ��� ��� ��������� �������� ����������� ������ ��������� ���������. ������� ������ ��������� ��������� ������ Zp ����� p-1. ���������� ���� �������� �������� ����� m ������� � �������� ����� ������� �����. ������� ������������ ����� ����� b (��������, b = 2), � �������� ��� � ������� m - 1 �� ������ m. ���� �� ������� �� �������, �� �� ����� ������� ����� ����� m ���������. ���� ������� � ���, ��� ���� bm-1 == 1 (mod m),
�� ������ ������ ������� �� m. ������� ����� �������� ��������, ��� ��� ����� m, ��������������� ��������� ����� ������� ����� ��� ��������� 2, �������: ���� 2m-1 == 1 (mod m),
�� m -- ������� �����. ����������� ����������� � ����� ����������� ��� ������ ������ � XVII ����: 2340 == 1 (mod 341),
�� ����� 341 -- �� �������, 341 = 11 * 31. (�������������, 2340 = (2^10)34 = 102434, �� 1024 = 3 * 341 + 1 == 1 (mod 341), ������� 102434 == 1 (mod 341).)��, ��� 341 �� ������������� ����� ������� �����, ����� ���� �������� � ������� ������ ���������: 3340 == 56 (mod 341)
��� �� ����� ���������� �����, ������� �� �������� ��������, �� ������� ����� ���� ��� ������� � ����� ������� �����. ����� ����� ���������� �������������. �����������. ����� m ���������� ������������, ���� ��� �� ������� � ��� ������� b, ������� �������� � m, ����������� ����������� ����� ������� �����: bm-1 == 1 (mod m).
����������� ����������� ����� -- ��� 561, 1105, 1729, ... �� ��� ��� ����������, ���������� �� ��������� ������������ �����.
�������� �������� ��������� �����������.
����������� 5. ����� m = p1e1 * p2e2 * ... * pkek --
������������� ������ ����� m � ���� ������������ �������� �������. ����� m �������� ������������ ����� � ������ �����, ����� 1) ��� ������� i ���������� ������� ei = 1; 2) k >= 3; 3) ��� ������� i ����� pi - 1 ����� m - 1. ��������������. ������� ������ ��������, �������� ���������� ����������. ����� ����� m ������������� �������� 1-3. ���������� ������������ b, ������� ������� � m. �� ��������� ������� �� ��������, ������ Zm �������������� � ���� ������ ����� Zm == Zp1 + Zp2 + ... + Zpk.
��� ���� ����������� ������ b �������������� � ���� ������ b == (b1, b2, ..., bk)
����� bm-1 == (b1m-1, b2m-1, ..., bkm-1.
�� ����� ������� �����, ��� ������� i bim-1 == 1 (mod pi),
��������� (m - 1) ������� �� (pi - 1). ������� bm-1 == (1, 1, ..., 1)
�.�. bm-1 == 1 (mod m). ������. �������, ��� ����� 561 �������� ������������. �������������, 561 = 3 * 11 * 17. ����� (3 - 1) | 560, (11 - 1) | 560, (17 - 1) | 560.
�������������, ����� 561 ������������� �������� ����������� 5. ����, ��� ������������ ����� ���� ��������, ���������� �� ������� �����, �� ��������. ��� �� ����� ��� �����������, ������������ �������, ��������� � ����� ����� ������. ���� ������ �������� �������������. ��� ��������, ��� �� ���������� ������ ��������� ����� �, ����� �������, �������� �� ����������������. ��� �������� ������ ����� m ���� ������ ����� ������ ���� �� ��������� ���� �������. 1. ����� m �������� ���������. 2. �� ����. � ������ ������� ������ ����� m ������������� �������� ���������, ���� ������ ����������� �������������� ����� �����. ������ ����� ����� ���� ����� ��� ��� ��������, ��� � ��� ���������� ����� m. ������ ��� ������ ���������� ����� m ����������� ������� ������ �� ��������� 1/4. �������� ����� ������ ������� ������ � �����������, �������������� ������ ����������� ������� ������ ��� ������������� ���������� ����� m. ����� �������, ���� �� �������� 100 ��� ���� ������ � ����� m � ������� 100 ������� "�� ����", �� ����� � ������� ������������ ����������, ��� ����� m �������. ����� �����, ����������� ��������� ��� ������� "�� ����" ��� ���������� ����� m �� ��������� (1/4)100, �.�. ����������� ����� ����. ��� �� ����� ���� ������ �� ����������� �������������� ����, ��� ����� m �������. �������� ��������������� � ��������� ����� ������. �� ��������� �������� �������� ����� m. �������� �����, ��� ����� m ��������. (���������� ������ ���� ������ ������� ����� -- 2.) ����� ����� m - 1 ������. ���������� ��� � ���� m - 1 = 2t * s
��� s -- �������� �����. ������� ��������� ����� b �����, ���
b =/= 0, b =/= 1 (mod m), 1 < b < m
��� ������ b ������������ ������ ��������� �����.
��������� �������� �������� ���������� � ������� �� ������ m, �������� ��������� ������������������ ��������� ������ Zm: x0 == bs (mod m), (1) x1 == x0 * x0 (mod m), x2 == x1 * x1 (mod m), ... xt == xt-1 * xt-1 == bm - 1 (mod m)(�� ������ ���� �� �������� � ������� �����, ���������� �� ���������� ����.) ���� ������ ������ ����� 'm -- ��������� �����' � ������, ���� 1) xt =/= 1 (mod m), ��� 2) � ������������������ x0, x1, x2, ..., xt ������� �������� ���� ..., *, 1, ... ��� ���������� ���������� �����, �������� �� ������� ��� ����� ������� �� ������ m. � ��������� ������ ���� ������ ������ ����� "�� ����". ������������������ x0, x1, ..., xt � ���� "������" ������ ���� ���������� � �������, ���� �������� (-1) ���-������ �� � �����. C��������� ��������, ������������ ��������, �� ��������� O(ln3n), �������� �������� ���������� �������� ���� ������ �� ����� ������� 2 <= b < 70ln2m, � ����� ���������, �� �������� �� m �������� �������� �����. ������ ��� ������������ ������� �� ������������ � ��������� ����� �������� ������.
���� ��������, �������� �� ������������ ����, � �������� ����� '�������' � ��������� �������������� ��������, ���� ���� ���� ������ �������, ��� ����� ���������, ������ ��� ��� � ����. �� �������� �� �������� ����� ���� �������. ������� (���������� ����� ������).1. ���� ���� ������ ������ ����� 'm -- ��������� �����', �� m ������������� �������� ���������. 2. ����������� ������ '�� ����' ��� ���������� ����� m �� ����������� 1/4. ��������������. ������� ������ ������ �����������. ���� xt =/= 1 (mod m), �� m �� ������������� ����� ������� ����� �, �������������, �� �������� �������. ���� �� ������������������ (1) �������� �������� ..., a, 1, ..., ��� a =/= +-1 (mod m), �� ����� a2 == 1 (mod m), a =/= 1, a =/= -1 (mod m)
���� �� m ���� �������, �� ������ Zm �������� �� �����. �� � ����� ���� ���� ������ ��� ���������� ����� �� �������: ��� ������� � ����� �������. (�� ������� ����, ����� ������ ���������� �� ����������� ��� �������, ���������� ����� �� ������� -- ��� ����� ���������� x2 - 1.) �������������, ����� m �� �������� �������. |