стоять не только 1, но и -1 (при а = - 1 имеем а" = -1, так как и нечётно), а также, возможно, и другие числа.

Рассмотрим наибольшее значение j £ {0,1,... ,t}, для которого существует такой элемент v £ Z*, что v2Vu = - 1 (mod га). (При j = 0, как мы видели, такой элемент v найдётся.) Пусть v £ Z* - один из твких элементов, то есть vVu = - 1 (mod га). (Этот элемент пригодится нам чуть позже.)

Положим

В = {х £ Z* : xVu = ±1 (mod га)}.

Поскольку В замкнуто относительно умножения по модулю га, оно является подгруппой группы Z*.

Покажем, что любой плохой элемент а принадлежит В. Посмотрим на последовательность а, порождённую плохим элементом, и двигаясь справа налево. На её последнем месте стоит единица. Перед единицей может стоять либо ещё одна единица, либо число - 1 (иначе был бы обнаружен нетривиальный корень из единицы и элемент а не был бы плохим). При этом число -1 может появиться лишь в позиции j или левее (так как j было выбрано максимальным). Значит, в j-ой позиции находится либо 1, либо -1, то есть

а е в.

Теперь мы воспользуемся существованием элемента v, чтобы показать, что В является собственной подгруппой, построив w £ Z* \ В. По следствию 33.29 из vVu = -1 (mod га) следует, что v2Ju = -1 (mod щ). По следствию 33.28 найдётся элемент ги, для которого одновременно выполнены условия

w = v (mod щ), w = 1 (mod 112).

Тогда

w2Ju = 1 (mod rai), w2Ju (mod П2),

откуда видно (следствие 33.29), что

wVu-l±1 (moci га)5(33.46)

Из двух последних сравнений по модулям щ и 112 видно, что w взаимно просто с щ и с 112 и тем самым взаимно просто с га. Следовательно, w принадлежит Z* \ В, что завершает доказательство теоремы - мы установили, что все плохие элементы принадлежат собственной подгруппе, и потому их число не превосходит (га-1)/2. Теорема 33.39

Для нечётного га > 2 нечётно и для любого целого положительного s вероятность ошибки процедуры Miller-Rabin (га, s) не превосходит 2~s.

Доказательство

Для простого га вообще не может быть ошибки. Если же га составное, то по теореме 33.38 при каждом случайном выборе а в строке 2 мы с вероятностью 1/2 или более обнаружим свидетеля того, что га составное. Поэтому вероятность того, что этого не произойдёт при s (независимых) попытках, не превосходит 2~s.

Взяв, например, s = 50, мы получим вероятность ошибки 2-50. Такими малыми вероятностями на практике обычно пренебрегают. Если применять тест к случайно выбранному числу, то вероятность ошибки будет ещё меньше. Дело в том, что наша оценка (свидетелей не меньше половины) для большинства га верна с большим запасом. Для большинства га количество плохих значений а обычно значительно меньше (га - 1)/2, и на практике можно ограничиться, скажем, тремя попытками (s = 3) с достаточно малой вероятностью ошибиться. Однако если га не выбирается случайным образом, а даётся нам извне, то значительно улучшить оценку (га - 1)/2 для числа плохих элементов нельзя (хотя немного можно: число плохих элементов, как можно доказать, не превосходит (га - 1)/4 - и эта оценка уже неулучшаема).

Упражнения

33.8-1

Докажите, что если целое число га не является простым и не является степенью простого числа, то в Ъп существует нетривиальный корень из 1.

33.8-2*

Можно несколько усилить теорему Эйлера, показав, что

аМп) = i (moci ra);

для всех а, если А (га) определить формулой

\(п)=\ст(фе1),...,фе/).(33.47)

(при га = рех .. .регг). Докажите, что А(га) <~р(п). Докажите, что составное число га является числом Кармайкла тогда и только тогда, когда А(га) га - 1. Например, для числа 561 = 3-11-17 (наименьшее число Кармайкла) им имеем А(га) = 1ст(2,10,16) = 80 560. Докажите, что всякое число Кармайкла «свободно от квадратов» (не делится на квадрат никакого простого числа) и имеет по меньшей мере 3 простых делителя. (Это одна из причин, почему числа Кармайкла редки.) 33.8-3

Пусть ж является нетривиальным корнем из 1 по модулю га. Докажите, что gcd (ж - 1, га) и gcd (ж + 1, га) являются нетривиальными (отличными от 1 и от га) делителями числа га.

*33.9 Разложение чисел на множители.

Пусть нам дано число га, которое надо разложить на множители (to factor it), то есть представить в виде произведения простых чисел. Тест из предыдущего раздела позволяет установить, что га составное, но ничего не говорит об его множителях. Это не случайно - насколько мы можем судить сегодня, разложение на множители значительно сложнее проверки простоты. Даже наиболее мощные современные суперкомпьютеры, использующие наиболее совершенные (из известных на сегодняшний день) алгоритмы, не способны за разумное время разложить на множители наугад взятое 200-значное число.

р-эвристика Полларда.

Перебирая все числа от 1 до В в качестве возможных делителей заданного числа га, мы сможем разложить на множители любое число вплоть до В2. Сейчас мы опишем алгоритм, который делает примерно столько же действий и позволяет раскладывать на множители числа порядка В4 (в большинстве случаев). К сожалению, нельзя гарантировать, что он выдаст ответ достаточно быстро; нельзя гарантировать даже того, что вообще разложение будет найдено. Однако на практике этот алгоритм зарекомендовал себя неплохо.

Pollard-Rho(n)

1i \gets 1

2x i \gets Random (0,n-l)

3у \gets x i

4k \gets 2

5while true

6do i \gets i+1

7x i \gets (x {i-l}~2 - 1) \bmod n

8d \gets \Н0Д(у-х 1,п)

9if d \ne 1 и d \ne n

10then print d

11if i=k

12then у \gets x i

13k \gets 2k

Эта процедува основана на рекуррентном соотношении

Xi = (ж2 1 - 1) mod га(33.48)

и вычисляет один за другим члены соответствующей последовательности

xi, ж2, ж3, ж4,... .(33.49)

(строка 7); переменная г указывает номер члена, начиная с 1ж первый член х\ выбирается случайно (строки 1-2). (На самом деле в каждый момент хранится только один член последовательности,