����� �� �����.


������ ���������.

����������: ������ �����.

������������� ���� �������� ������.

© ���������, ���-��� ���.

�������� ����������� ��� ���������� �� ������������ ������ ����� � �������.

���� ������� �����. ����� 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 �� �������� �������.




����� �� ��������, � ���������� � ���������.

SpyLOG