AOP_Tom2 (1021737), страница 119
Текст из файла (страница 119)
Воспользовавшись процедурой, предложенной в упр. 10, вычис- лим следующие значения, х~ ~~г шо6 п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 2 137 2 1973 3 2 5 2 7 2 (1) (1) (1) (1) (1) (1) (1) (1) 1 (17) 21О7 + 254 + 1 Поскольку Зьм шодпэ ф 1, известно, что пэ не является простым числом, и выполнение алгоритма В показывает, что пэ — — 843589 пэ, где пэ = 92343993140277293096491917. К сожалению, 3"' ' шобла ф 1, поэтому остается 27-разрядное непростое число. Повторное обращение к алгоритму В могло бы истощить наше терпение (но не бюджет- — мы чаще тратим свободное время в выходные дни, чем "рабочее время"). Пришло время ввести в действие метод решета. Алгоритм Р, реализующий этот метод, может разбить число пэ на два множителя: п~ — — 8 174 912 477 117.
23 528 569 104 401. (Здесь "(1)" означает результат, равный 1, который не требуется вычислять, так как он может быть выведен из предыдущих вычислений.) Таким образом, п4 — простое число, а число пз — 1 полностью разложено на простые множители. Аналогичные вычисления показывают, что и пз является простым числом; такое же полное разложение числа пэ — 1 на простые множители показывает наконец, после вычислений еще и значений из табл. (17), что пэ — простое число.
Последние три строки в табл. (17) представляют процесс поиска целого числа х, удовлетворяющего соотношению х~"4 07~ ~ х"' ' = 1 (по модулю пэ). Если п4 — -простое число, то шансы на успех равны только 50/50, так что случай, когда р = 2, является, как правило, наиболее трудным для проверки. Можно обойти эту часть вычислений, используя закон квадратичной взаимности (упр. 23), который гласит, например, что 5" 01~ = — 1 (по модулю е), когда о есть простое число * 1 (по модулю 5). Выбрав значение г = 5, нельзя убедиться в том, что число пэ простое. Это сразу показывает вычисление п4 шоб 5. Тем не менее из результата упр.
26 действительно следует, что при проверке, является ли число и простым, вовсе нет необходимости рассматривать случай, когда р = 2, несмотря на то что и — 1 делится на большие степени 2. Таким образом, три последние строки в табл. (17) необязательны. Следующая величина, подлежащая разложению на простые множители, -- другая часть соотношения (15), т. е. (Применение алгоритма В тоже привело бы к положительному результату, но после выполнения 6 432 966 итераций.) При помощи алгоритма А не удалось бм получить этот результат за приемлемое время.
Теперь вычисления завершены: разложение числа 2" 4 + 1 на простые множители имеет вид 5. 857 843589 8174912477117 23528569104401 пш где по представляет собой 29-разрядное простое число, приведенное в (16). В этих вычислениях нам сопутствовала определенная доля удачи, поскольку, если бы вычисления начались пе с известного разложения на простые множители по уравнению (15), вполне возможно, что мы сначала получили бы малые множители, сведя и к папа. А это 55-разрядное число намного сложнее разложить на простые множители — применять алгоритм !Л бесполезно, а алгоритм В должен был бы работать бесконечно долго из-за необходимости выполнять операции с высокой точностью.
Десятки дополнительных примеров разложения чисел на простые множители можно найти в статье Джона Бриллхарта (,!оЬп ВН11Ьаг!) и Дж. Л. Селфриджа (Л. Ь. Ве1(г!68е) в журнале МаГЛ. Сошр. 21 (1967), 87 — 96. Усовершенствованные методики проверки принадлежности чисел к простым.
Описанная выше процедура требует полного разложения числа п — 1 на простые множители, прежде чем можно будет доказать, что число и — простое. Поэтому при работе с большими числами можно просто увязнуть в вычислениях. В упр. 15 описана друтая процедура, использующая разложение на простые множители числа и + 1. Если окажется, что разложение числа п — 1 слишком затруднительно, то может статься, проще будет разложить на простые множители число и+ 1. При работе с большими числами можно добиться существенного усовершенствования способов проверки. Например, нетрудно доказать более строгое обратное утверждение теоремы Ферма, которое требует только частичного разложения числа и — 1.
Из упр. 26 следует, что можно избежать большей части вычислений в (17); для доказательства того, что число п4 является простым, достаточно выполнения трех условий: 2"» ~ шобп4 = Всб(20м Югз — 1, и ) = Всб(2! 4-г!Дэгз — ! и ) = 1. Бриллхарт, Лемер и Селфридж разработали метод, работающий с числами и — 1 и и + 1, которые имеют. только частичные разложения на простые множители (МагЬ. Сотр. 29 (1975), 620-647, Сото)!агу 11]. Предположим, что и — 1 = Л г и и + 1 = ~+г+, где известно полное разложение на простые множители чисел 7' и Л+: известно также, что все множители чисел г и г > Ь.
Если произведение (Ьзг ~~ шах(г, Л'+)) больше йп, то небольшого объема дополнительных вычислений, описанных в этой работе, достаточно для ответа на вопрос, является ли число п простым. Поэтому принадлежность чисел длиной вплоть до 35 разрядов может быть в доли секунды проверена путем выделения из п х 1 всех простых множителей ( 30 030 (см. Л. Ь. Вс!!г!68е, М. С. %пппег!!сЬ, Сопйгеззиз Хшпегапг!пш 12 (1974), 109— 120). Для дальнейшего усовершенствования этого метода может быть использовано частичное разложение на простые множители других величин вида и х и+1 и и'+ 1 [см.
Н. С. %'!!!!ашз, Л. В. ЛшЫ, Маг!ь Сошр. 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), так что х'е шо6 561 = 1 = хлво шоб 561, когда х есть взаимно простое с 561. При попытке показать, что такое число и простое, наша процедура будет терпеть неудачу всякий раз, когда мы будем сталкиваться с одним из делителей этого числа.
Метод можно усовершенствовать, если найти способ быстрого определения "непростоты" непростого числа и даже в таких патологических случаях. Гарантируется, что следующая удивительно простая процедура выполняет анализ с высокой вероятностью. Алгоритм Р (Веролтиостнвл проверка, лвллетсл ли число ироситмм), Этот алгоритм пытается определить, является ли данное целое нечетное число и простым.
Несколько повторных попыток выполнения алгоритма, как объяснено в примечаниях ниже, позволяют с весьма болыпой вероятностью считать число и простым, хотя строгим это доказательство не является. Пусть и = 1+ 2~9, где д — нечетное число. Р1. [Генерировать х.) Пусть х — случайное целое число в интервале 1 < х ( и. Р2. [Возвести в степень.] Присвоить у +- 0 и у +- хл пюс( и. (Как и в предыдущем примере проверки, будет ли число простым, хл пюб и должно быть вычислено за 0(1ок 9) шагов; см. раздел 4.6.3.) РЗ.
[Выполнено?] (Теперь у = хз'л шоб и.) Если у = 0 и у = 1 или если у = и — 1 то выполнение алгоритма завершается и выдается сообщение "и, вероятно, простое". Если у > 0 и у = 1, перейти к шагу Р5. Р4. [Увеличить 1.] Увеличить у на 1. Если у < й, то присвоить у < — уз шоби и возвратиться к шагу РЗ Рб. [Не простое.] Завершить выполнение алгоритма сообщением "и, определенно, не простое". $ Отличительным свойством алгоритма Р является то, что, если хл шоб и Зе 1 и и = 1 + 2~9 — простое число, последовательность значений хл шоДи, х'~ шоДи, хчо пюби, ..., х ° пюви лй будет заканчиваться 1 и значение, предшествующее первому появлению 1, будет равно и — 1.
(Единственными решениями уравнения ут = 1 (по модулю р) будут у = х1, когда р — простое, поскольку (у — 1)(у + 1) должно быть кратным р.) В упр. 22 доказывается основополагающее свойство алгоритма Р, состоящее в том, что для любого и он будет давать неправильный результат не более чем в одном случае из четырех.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
