III. Арифметические алгоритмы

§ 11. Проверка простоты

11.1. Решето Эратосфена

Под этим названием понимают следующий метод построения всех простых чисел, не превосходящих некоторого заданного числа N. Берем число 2 и выбрасываем все числа кратные 2. Из оставшихся чисел оставляем наименьшее (в данном случае это число 3) и выбрасываем все числа кратные 3, и так далее. Если первое оставшееся число превышает [a VJ, то работу прекращаем, поскольку все отобранные и оставшиеся числа являются простыми. При этом ни одно простое число в заданном интервале не будет упущено.

Данный метод позволяет строить множество простых чисел, но он неудобен для проверки простоты заданного числа. Тем не менее, идея решета и ее обобщения в настоящее время часто используются для «просеивания» множеств чисел, обладающих тем или иным условием. Более того, разрабатываются специальные микропроцессоры, на которых операции «просеивания» выполняются очень эффективно.

11.2. Критерий Вильсона

В 1770 г. Э.Варинг опубликовал следующую теорему, приписываемую Д. Вильсону.

(б) (и - 1)! = -1 (mod и).

ли и=p> 2 - простое, то кажщм элемент таичный от -1 имеет обратный a- ртчем a = a-1. Поэтому

(и - 1)! = (-1) II aa

a=1,-1

= -1 (mod и).

Если и = aCTaBHoe, 1 < a < ио a (и - 11)! и, следовательно, (и - 1) элементом кольца Zn. Поэтому (и - 1)! = -1 (mod и) □

Данный критерий иногда бывает удобен в доказательствах, но применять его для проверки простоты невозможно ввиду большой трудоемкости.

11.3. Тест на основе малой теоремы Ферма

няется условие:

при всех a &{2,3,... ,и - 1} имеет место сравнение

an-1 = 1 (mod и). (1)

Обратное утверждение неверно.

Из этой теоремы следует, что если сравнение (1) не выполнено хотя a {1, 2, . . . , и - 1} и

Поэтому можно предложить следующий вероятностный тест простаты:

{1, 2, . . . , и - 1}

(a, и) = 1

3) проверяем выполнимость сравнения (1);

5) если сравнение выполнено, то ответ неизвестен, но можно повторить тест еще раз.

(a, и) и

по основанию шер, при (a,и) = (2,341 чаем 2340 = = (2io)i4 = 1 (mod и)штя 431 = 11-31. Приведем наименьшие примеры минимальных псевдопростых чисел для оснований a = 2, 3,5, 7.

a > 1

a (2, и)

(2, 2n-1)

2n - 2 = 2(2n-1 - 1) = 2tn t

22П-2 - 1 = 22*n - 1 = (2n - 1)(2(2*-1)n + + 1) = О (mod n) n 2n - 1

а> 2

предлагается доказать в качестве упражнения, для любого нечетного простого числа р и любого а такого, что (а2 - = 1, число "зГ/

В то же время псевдопростых чисел относительно мало. Например,

21853

нию ди 1 091 98740 ет меньших, чем 25 000 000 000. Приведем свойства псевдопростых чисел.

(а) ж по основанию а в том и только в том случае, когда (а, n) = алемента в т чиело n - 1;

(б) если n ж по основаниям и 6 € Z" то n псевдо-

а6 а6-1

(в) множество Fn = {а € Zn: an-1 = 1 (mod n)} образует подгруппу мультипликативной группы Z";

(г) если n щостым по основанию а хотя бы одного числа а, то Р„ < \ \п\-

□

стым, то имеется по крайней мере (n -1)/2 чисел, по которым данное число также не является псевдопростым.

Особый случай составляют составные числа, для которых условие (1) выполняется при всех основаниях. Они называются псевдопростыми числами, или числами Кармайкла.

Таким образом, при применении описанного выше теста может возникнуть три ситуации: n n

1/2 n

гда дает ответ «не известно».

Наличие третьей ситуации является очень неудобным свойством данного теста. Для практики нужны такие тесты, в которых третья ситуация не возникает. Для построения таких тестов изучим сначала свойства чисел Кармайкла.

11.4. Свойства чисел Кармайкла

Нам потребуется следующая

m> 1 шная групп а кольца Zpm является циклической. Доказательство. Имеем

Zpm = (Zpm )= pm-1(p - 1)

а pk

ordk(а) = min{t 1: а* = 1 (mod pk)}

Заметим, что функция ordk ( ) имеет обычные свойства порядка. В частности, если порядки двух элементов взаимно просты, то порядок произведения равен произведению их порядков. Кроме того, при 1 < k < тся равенство ordk (а) ordk+1(a), так как отображение а а mod мрфизмом кольца Zpm в кольцо Zpk, а порядок образа делит порядок прообраза.

При k = отьцо жи, поэтому в Zpm найдется элемент ш по модулю щдок p - 1.

Покажем, что один из элементов гаи g = (p + 1)go имеет порядок p(p - 1 тодулю элемент go не такой, то он имеет p - 1 p2 g

p+ 1, p

(p + 1)p Н1 + pp +

= 1 (mod p2),

go p - 1 p2

p( p - 1)

mg ord2(g)= p(p - 1o ordm(g)= pm-1(p - 1 любом mpи m = 2 это верно. Предположим, что для m - но, т.е. ordm-1(g) =

(p- 1)

(p-1)

= 1 (mod pm-1)

g(p-1)pm 3 = 1 (mod p

Для простоты записи положим h=g(p 1)p . Тогда данные сравнения примут вид

hp = 1 (mod pm-1) и h = 1 (mod pm-1). Следовательно,

h = (1 + kpm-2) (mod pm-1), (k,p) = 1,

откуда

hp = (1 + kpm-2)p =

1 + pkpm-2 +

k2p2(m-2) +,

= 1 + kpm-1 = 1 (mod pm

С другой стороны, hp = (1 + kpm 1)p = 1 (mod pm). Таким образом,

pm-2 (p - 1)= ordm-i(g) = ordm(g),

ho ordm(g) Ipm-1 (p - стедует, что ordm(g) = pm-1(p - 1). □

Докажите в качестве упражнения следующую теорему о существовании примитивного элемента в кольце вычетов.

Теорема (Гаусс, 1801). Мультипликативная группа кольца Zn яви

чисел 2, 4, и 2pmde m 1, p - нечетное простое.

p2 и p > 1 и

(б) если и = p1p2.. .p pi = то и - число Кармайкла в том

(pi - 1) I (и - 1);

(в) если и = pip2.. .p pi = майкла, то k 3.

Доказательство, (а) Пусть u=pt m, t2, (m, 2)=1. Пусть для a ord2(a) = p(p- 1) и

ляется псевдопростым по основанию гак если an-1 = 1 (mod и),

то и an-1 = 1 (mod p2 должно быть p(p - 1) (и - 1), что p и

(б) Достаточность. Пусть и = pip2 ...p pi = pj, и при всех i ( pi - 1) ( и - 1) и - 1 = ( pi - 1) mi

-n-1 -

-,n-1 -

= (aPi-1)mi = 1 (mod pi), и по китайской теореме об остатках = 1 (mod и)

i=1, . . . , k ai

такой, что ordi(ai) = pi - го условия an-1 = 1 (mod и) следует, что (pi - 1) I (и - 1).

(в) Если k=2 u=p p<o и-1=p(q-1 + 1)-1=p-1 (mod q-!). Это противоречит условию (q - 1) (и - как 0 <p - 1 <q - 1. □

Числа Кармайкла являются достаточно редкими. Так, имеется 2163 25 000 000 000

561 1105 1729 2465 2821 6601 8911 10585 15841 29341 41041 46657 52633 62745 63973 75361

ное число числом Кармайкла, согласно доказанной теореме требует нахождения разложения числа на простые сомножители, т. е. факторизации числа. Поскольку задача факторизации чисел является более сложной, чем задача проверки простоты, то предварительная отбраковка чисел Кармайкла не представляется возможной. Поэтому в приведенном выше тесте простые числа и числа Кармайкла полностью неразличимы.

11.5. Тест Соловея-Штрассена

(б) для любого a £ Zn выполняется сравнение

а 2 =

(mod и).

видно выполнено в силу свойств символа Лежандра. Пусть теперь

а"-1 = I =

= 1 (mod и).

ния 2 оно должно иметь вид и=pip2 ... pi = p m эле мент Ъ, не являющийся квадратичным вычетом по модулю pi. По китайской