(Применение алгоритма В тоже привело бы к положительному результату, но после выполнения б 432 966 итераций.) При помощи алгоритма А не удалось бы получить этот результат за приемлемое время.

Теперь вычисления завершены: разложение числа 2* + 1 на простые множители имеет вид

5 • 857 • 843 589 • 8174 912477117 • 23 528 569104 401 • по,

где По представляет собой 29-разрядное простое число, приведенное в (16). В этих вычислениях нам сопутствовала определенная доля удачи, поскольку, если бы вычисления начались не с известного разложения на простые множители по уравнению (15), вполне возможно, что мы сначала получили бы малые множители, сведя л к пеПо- А это 55-разрядное число намного сложнее разложить на простые множители- применять алгоритм D бесполезно, а алгоритм В должен был бы работать бесконечно долго из-за необходимости вьшолнять операции с высокой точностью.

Десятки дополнительных примеров разложения чисел на простые множители можно найти в статье Джона Бриллхарта (John Brillhart) и Дж. Л. Селфриджа (J. L. Selfridge) в журнале Math. Сотр. 21 (1967), 87-96.

Усовершенствованные методики проверки принадлежности чисел к простым. Описанная выше процедура требует полного разложения числа п - 1 на простые множители, прежде чем можно будет доказать, что число п - простое. Поэтому при работе с большими числами можно просто увязнуть в вычислениях. В упр. 15 описана другая процедура, использующая разложение на простые множители числа п -I- 1. Если окажется, что разложение числа п - 1 слишком затруднительно, то может статься, проще будет разложить на простые множители число п -I-1.

При работе с большими числами можно добиться существенного усовершенствования способов проверки. Например, нетрудно Доказать более строгое обратное утверждение теоремы Ферма, которое требует только частичного разложения числа п - 1. Из упр. 26 следует, что можно избежать большей части вычислений в (17); для доказательства того, что число является простым, достаточно выполнения трех условий:

2"-1 modn4 = gcd(2("-i)/23 1, т) = gcd(2("-i)/i83 - 1, П4) = 1.

Бриллхарт, Лемер и Селфридж разработали метод, работающий с числами п - 1 и п -I- 1 , которые имеют, только частичные разложения на простые множители [Math. Сотр. 29 (1975), 620-647, Corollary 11]. Предположим, что п - 1 = fr-и п -I-1 = /Г+, где известно полное разложение на простые множители чисел /" и /+; известно также, что все множители чисел г~ и г+ > Ь. Если произведение тах(/~,/+)) больше 2п, то небольшого объема дополнительных вычислений, описанных в этой работе, достаточно для ответа на вопрос, является ли число п простым. Поэтому принадлежность чисел длиной вплоть до 35 разрядов может быть в доли секунды проверена путем выделения из п ± 1 всех простых множителей < 30030 [см. J. L. Selfridge, М. С. Wunderhch, CongressusNumerantium 12 (1974), 109-120]. Для дальнейшего усовершенствования этого метода может быть использовано частичное разложение на простые множители других величин вида п±п--1ип-И [см. Н. С. Wilhams, J. S. Judd, Math. Сотр. 30 (1976), 157-172, 867-886].

На практике, когда п не содержит малых простых множителей и 3"" mod п = I, последующие вычисления почти всегда показывают, что п -простое число. (Одним из редких исключений в практике автора является число п = (2* - 9) = 2 341-16381.) С другой стороны, некоторые значения числа п, не являющиеся простыми, представляют собой весьма тяжелый случай для рассмотренных способов проверки, так как может случиться, что х"" mod п = 1 для всех х, взаимно простых с п (упр. 9). Наименьшим таким числом является п = 3 - И - 17 = 561; здесь А(п) = 1ст(2,10,16) = 80 в обозначениях уравнения 3.2.1.2-(9), так что х° mod 561 = 1 = х° mod 561, когда х есть взаимно простое с 561. При попытке показать, что такое число п простое, наша процедура будет терпеть неудачу всякий раз, когда мы будем сталкиваться с одним из делителей этого числа. Метод можно усовершенствовать, если найти способ быстрого определения "непростоты" непростого числа п даже в таких патологических случаях.

Гарантируется, что следующая удивительно простая процедура выполняет анализ с высокой вероятностью.

Алгоритм Р (Вероятностная проверка, является ли число простым). Этот алгоритм пытается определить, является ли данное целое нечетное число п простым. Несколько повторных попыток выполнения алгоритма, как объяснено в примечаниях ниже, позволяют с весьма большой вероятностью считать число п простым, хотя строгим это доказательство не является. Пусть п = 1 -I- 2*д, где q - нечетное число.

Р1. [Генерировать х.] Пусть х - случайное целое число в интервале 1 < х < п.

Р2. [Возвести в степень.] Присвоить j О и j/ modn. (Как и в предыдущем примере проверки, будет ли число простым, х mod п должно быть вычислено за O(logg) шагов; см. раздел 4.6.3.)

РЗ. [Выполнено?] (Теперь у = хч modn.) Если j = О и j/ = 1 или если у = п-1, то выполнение алгоритма завершается и выдается сообщение "п, вероятно, простое". Если j > О и 2/ = 1, перейти к шагу Р5.

Р4. [Увеличить j.] Увеличить j на 1. Если j < к, то присвоить у у modn и возвратиться к шагу РЗ.

Р5. [Не простое.] Завершить выполнение алгоритма сообщением "п, определенно, не простое".

Отличительным свойством алгоритма Р является то, что, если х mod п ф 1 и п = 1 -I- 2*9 - простое число, последовательность значений

xmodn, xmodn, xmodn, xmodn

будет заканчиваться 1 и значение, предшествующее первому появлению 1, будет равно п - 1. (Единственными решениями уравнения у" = 1 (по модулю р) будут у = ±1, когда р - простое, поскольку (у - 1){у + 1) должно быть кратным р.)

В упр. 22 доказывается основополагающее свойство алгоритма Р, состоящее в том, что для любого п он будет давать неправильный результат не более чем в одном случае из четырех. На практике алгоритм Р очень редко выдает неправильный результат для большинства значений п. Однако критическим является тот факт, что вероятность отказа ограничена независимо от значений п.

Допустим, что мы обращаемся к алгоритму Р несколько раз, выбирая х независимо и случайно, когда выполняется шаг Р1. Если алгоритм сообщает, что число п непростое, можно быть уверенным, что так оно и есть. Но если алгоритм сообщает 25 раз подряд, что п "возможно, простое", значит, п-"почти наверное простое", так как вероятность того, что процедура, выполняющаяся 25 раз подряд, дает неправильную информацию об исходном числе, меньше (1/4). Эта величина меньше, чем один шанс на квадрильон; даже после проверки при помощи такой процедуры миллиарда различных чисел ожидаемое количество ошибок будет меньше 1000000- Скорее всего, можно предположить, что компьютер потерял бит при вычислениях из-за аппаратных неполадок или влияния космической радиации, чем то, что алгоритм Р непрерывно ошибается!

Вероятностные алгоритмы, подобные описанному, приводят нас к традиционному вопросу о достоверности. Нуждаемся ли мы в строгом доказательстве принадлежности числа к простым? Для тех, кто не склонен игнорировать традиционные понятия доказательства, Гэри Л. Миллер (Gary L. Miller) продемонстрировал (в немного ослабленном виде), что если определенное, хорошо известное предположение в теории чисел, называемое обобщенной гипотезой Римана, может быть доказано, то либо п - простое число, либо существует число х < 2(1пп), такое, что алгоритм Р обнаружит, что п - не простое число. [Обзор различных обобщений гипотезы Римана приведен в J. Сотр. System Sd. 13 (1976), 300-317. Присутствующая в этой оценке постоянная 2 получена Эриком Бахом (Eric Bach), Math. Сотр. 55 (1990), 355-380; см. гл. 8 в Algorithmic Number Theory 1 by E. Bach, J. 0. Shallit (MIT Press, 1996).]

Таким образом, можно найти строгий способ проверки, будет ли число простым, выполняемый за O(logn) элементарных операций, в противовес вероятностному методу, время выполнения которого при условии, что доказаны обобщенные гипотезы Римана, равно O(logn). Вполне резонно задать вопрос: дают ли доказанные гипотезы такой же надежный результат, какой дает неоднократное применение к случайным числам алгоритма Р.

Вероятностная проверка принадлежности числа к простым была впервые предложена в 1974 году Р. Соловеем (R. Solovay) и В. Штрассеном (V. Strassen), разработавшими интересный, но более сложный алгоритм проверки, описанный в упр. 23, (Ь). [См. SICOMP 6 (1977), 84-85; 7 (1978), 118.] Алгоритм Р является упрощенным вариантом процедуры, разработанной М. О. Рабином (М. О. Rabin), в основу которого частично положены идеи Гэри Л. Миллера [см. Algorithms and Complexity, edited by J. F. Traub (Academic Press, .1976), 35-36]. Исследования, выполненные Б. Арази (В. Arazi) [Сотр. J. 37 (1994), 219-222], показали, что можно существенно повысить скорость выполнения алгоритма Р для больших п за счет применения быстрого метода вычисления остатков Монтгомери (см. упр. 4.3.1-41).

В 1980 году Леонард М. Эдлеман (Leonard М. Adleman) предложил совершенно другой подход к решению этой задачи. Его очень интересный метод основан на теории алгебраических целых чисел, но это выходит за рамки данной книги. Метод Эдлемана приводит к невероятностной процедуре, которая определяет, будет ли любое число длиной, скажем, 250 знаков простым не более чем за несколько часов. [В общем случае время, необходимое для решения задачи по этому методу, равно (logn)°(°8l°s°s"); см. L. М. Adleman, С. Pomerance, R. S. Rumely, Annals of