Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 10

Н. Ецзз, Соггезролс(алое Мазб. ес РБуэзйие 1 (1843), 145). Задача заключается в исследовании каждого из 33-разрядных множителей в соотношении (15). Компьютерная программа легко обнаруживает„что 2'ог — 2зз + 1 = 5. 857. по, где (16) по = 378668090616600о7264219253397 есть 29-разрядное чясло, не имеющее ни одного простого множителя, меньшего 1 000. Вычисления с многократной точностью, выполняемые при помощи алгоритма 4.6.3А, показывают, что 3'" ' шодпо = 1, так что есть основание предполагать, что по — простое число. Конечно.

не может быть и речи о том, чтобы для проверки, является ли по простым числом, проанализировать 10 миллионов миллионов или около того возможных делителей, но рассмотренный выше метод вполне пригоден для такой проверки. Следующая задача--разложение на простые множители числа по — 1. Преодолев некоторые трудности, компьютер сообщит, что по — 1 = 2 2 ° 19 ° 107 ° 353 пз, пз = 13191270754108226049301. Здесь 3"' ' шод пз Зз 1, поэтому пз — не простое число. Продолжая выполнение алгоритма А или В, можно подучить следующие множители: пз = 91813 пз, пз = 143675413657196977.

Теперь 3"' ' шод пз = 1,.поэтому можно попытаться доказать, что пз — простое число. Приняв во внимание, что множители < 1000, получаем пз — 1=2 2 2 ° 2 3 ° 3 547 ° пз~ где пз = 1824032 775457. Так квк 3"' л шод пз ф 1, приходим к заключению, что пз — составное число, а при помощи алгоритма А находим, что пз = 1103 ° пм где пз = 1 653 701 519. Число п4 ведет себя, как простое (т. е. 3"' ~ шоб пз = 1), поэтому пэ — 1 = 2 ° 7 19 23 ° 137 1973. Итак, выполнено первое полное разложение на простые множители.

Теперь мы готовы вернуться к предыдущей подзадаче, а именно — к доказательству того, что пз есть простое число. Воспользовавшись процедурой, предложенной в упр. 10, вычис- лим следующие значения. х("4-' Уг шоб и4 1 766 408 626 332 952 683 1 154 237 810 373 782 186 490 790 919 1 1 1 653 701 518 х"' ' шоб и4 х р 2 2 2 7 2 19 2 23 137 2 1973 3 2 5 2 7 2 (1) (1) (1) (1) (1) (1) (1) (1) 1 иь — 2~с" + 2ы + 1 Поскольку 3™ 1 п1одиэ ф 1, известно, что ие не является простым числом, и выполнение алгоритма В покаэывает, что иэ —— 843589 ив, где ие = 92343993140277293096491917. К сожалению, 3"" 1 пюб ие ф 1, поэтому остается 27-разрядное непростое число. Повторное обращение к алгоритму В могло бы истощить наше терпение (но не бюджет — мы чаще тратим свободное время в выходные дни, чем "рабочее время" ). Пришло время ввести в действие метод решета.

Алгоритм П, реализующий этот метод, может разбить число ие на два множителя: ив = 8174912477117 23528569104401. (Здесь "(1)" означает результат, равный 1, который не требуется вычислять, так как он может быть выведен из предыдущих вычислений.) Таким образом, па — простое число, а число из — 1 полностью разложено на простые множители.

Аналогичные вычисления показывают, что и и является простым числом; такое же полное разложение числа ио — 1 на простые множители показывает наконец, после вычислений еще и значений из табл. (17), что ие — простое число Последние три строки в табл. (17) представляют процесс поиска целого числа х, удовлетворяющего соотношению хйм 07з ф х"' ' ьз 1 (по модулю иэ). Если и4 — простое число, то шансы на успех равны только 50/50, так что случай, когда р = 2, является, как правило, наиболее трудным для проверки.

Можно обойти эту часть вычислений, используя закон квадратичной взаимности (упр. 23), который гласит, например, что 5~э 0~э = 1 (по модулю д), когда д есть простое число х 1 (по модулю 5). Выбрав значение х = 5, нельзя убедиться в том, что число и4 простое. Это сразу показывает вычисление и4 шос(5. Тем не менее из результата упр. 26 действительно следует, что при проверке, является ли число и простым, вовсе нет необходимости рассматривать случай, когда р = 2, несмотря ив то что и-1 делится на болыпие степени 2.

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

Теперь вычисления завершены: разложение числа 2ыэ + 1 на простые множятели имеет вид 5 857 843589 8174912477117 23528569104401 ° пэ где пэ представляет собой 29-разрядное простое число, приведенное в (16). В этих вычислениях нам сопутствовала определенная доля удачи, поскольку, если бы вычисления начались не с известного разложения на простые множители по уравнению (1э), вполне возможно, что мы сначала получили бы малые множители, сведя и к пэпе. А это 55-рэзрядное число намного сложнее разложить на простые множители — применять алгоритм П бесполезно, а алгоритм В должен был бы работать бесконечно долго из-за необходимости выполнять операции с высокой точностью. Десятки дополнительных примеров разложения чисел на простые множители можно найти в статье Джона Бриллхарта (аппп ВНПЬагг) и Дж.

Л. Селфриджа (3. 1. Бейг168е) в журнале МаГй. Сошр. 21 (1967), 87 — 96. 'Усовершенствованные методики проверки принадлежности чисел к простым. Описанная выше процедура требует полного разложения числа и — 1 на простые множители, прежде чем можно будет доказать, что число п — простое. Поэтому при работе с большими числами можно просто увязнуть в вычислениях. В упр. 15 описана другая процедура, использующая разложение на простые множители числа ц + 1. Если окажется, что разложение числа и — 1 слишком затруднительно, то может статься, проще будет разложить на простые множители число и+ 1. При работе с большими числами можно добиться существенного усовершенствования способов проверки.

Например, нетрудно доказать более строгое обратное утверждение теоремы Ферма, которое требует только частичного разложения числа и — 1. Из упр. 26 следует, что можно избежать большей части вычислений в (17); для доказательства того, что число п4 является простым, достаточно выполнения трех условий: 2"' 1 щог) п4 = йебра -~Уээ 1 и ) = 8сб(2("' ндэ"з — 1 и ) = 1 Брнллхарт, Лемер и Селфридж разработали метод, работающий с числами и — 1 и и + 1, которые имеют.

только частичные разложения на простые множители (Масй. Сотар. 29 (1975), 620-647, Согойагу 1Ц. Предположим, что и — 1 = ~ г и и + 1 = 7"г', где известно полное разложение на простые множители чисел 7' и 7+; известно также, что все множители чисел г н г+ > 5.

Если произведение (5~7 ~~ шах(У, ~+)) больше 2п, то небольшого объема дополнительных вычислений, описанных в этой работе, достаточно для ответа на вопрос, является ли число и простым. Поэтому принадлежность чисел длиной вплоть до 35 разрядов может быть в доли секунды проверена путем выделения из и к 1 всех простых множителей < 30 030 (см. 3. 1.. 8е!Ег168е, М. С, Ъцпбегйсй, Соп8геээнэ Хцшегапгшш 12 (1974), 109- 120). Для дальнейшего усовершенствования этого метода может быть использовано частичное разложение на простые множители других величин вида и~~и+1 н и~+1 (см.

Н. С. )т'101ашэ, 3. 8. Зцбб, Магй. Сошр. 30 (1976)„157-172, 867-886). На практике, когда и не содержит малых простых множителей и 3" ' пки1 и = 1, последующие вычисления почти всегда показывают, что и — простое число. (Одним из редких исключений в практике автора является число и = -'(2ее — 9) = 2341 ° 16381.) С другой стороны, некоторые значения числа и, не являющиеся простыми, представляют собой весьма тижелый случай для рассмотренных способов проверки, так как может случиться, что х" ' шоб и = 1 для всех х, взаимно простых с и (упр, 9).

Наименьшим таким числом является и = 3 ° 11 ° 17 = 561; здесь Л(и) ж !сш(2, 10, 16) = 80 в обозначениях уравнения 3.2.1,2-(9), так что хее пюй 561 = 1 = х~~~ шоб 561, когда х есть взаимно простое с 561. При попытке показать, что такое число и простое, наша процедура будет терпеть неудачу всякий раз, когда мы будем сталкиваться с одним из делителей этого числа. Метод можно усовершенствовать, если найти способ быстрого определения "непростоты" непростого числа и даже в таких патологических случаях.

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

)Генерировать х.) Пусть х — случайное целое число в интервале 1 < х < и. Р2. )Возвести в степень.] Присвоить у е- 0 и р е- хе шод и. (Как и в предыдущем примере проверки, будет ли число простым, хе шоб и должно быть вычислено за О(1о8 9) шагов; см. раздел 4.6.3.) РЗ. )Выполненоу] (Теперь у = хэ е шод и.) Если у = 0 и 9 = 1 или если у = и — 1 то выполнение алгоритма завершается и выдается сообщение "и, вероятно, простое". Если у' > 0 и р = 1, перейти к шагу. Р5.

Р4. )Увеличить Д Увеличить у на 1. Если у < й, то присвоить у +- уз тоби и возвратиться к шагу РЗ. Рб. [Не простое.) Завершить выполнение алгоритма сообщением "и, определенно, ие простое". Отличительным свойством алгоритма Р является то, что, если хе тоби ф 1 и и = 1+ 2ед — простое число, последовательность значений хе тоби, хте тоби, хмпкк1и, ..., хз ешоби будет заканчиваться 1 и значение, предшествующее первому появлению 1, будет равно и — 1.

(Единственными решениями уравнения уэ ьз 1 (по модулю р) будут Н ев х1, когда р — простое, поскольку (у — Ц(у + 1) должно быть кратным р.) В упр. 22 доказывается основополагающее свойство алгоритма Р, состоящее в том, что для любого и он будет давать неправильный результат ие более чем в одном случае из четырех. На практике алгоритм Р очень редко выдает неправильный результат для большинства значений и. Однако критическим является тот факт, что вероятность отказа ограничена кееавпсимо от значений и. Допустим, что мы обращаемся к алгоритму Р несколько рэз, выбирая х независимо и случайно, когда выполняется шаг Р1. Если алгоритм сообщает, что число п непростое, можно быть уверенным, что так оно и есть.

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