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

Скорее всего, можно предположить, что компъютер потерял бнт прн 1 вычислениях из-за аппаратных неполадок илн влиянии космической радиации, чем то, что алгоритм Р непрерывно ошибается! Вероятностные алгоритмы, подобные описанному, приводят нас к традиционному вопросу о достоверности. Нуэсдаеисл ли мы в строгом доказательстве принадлежности числа к простым? Для тех, кто не склонен игнорировать традиционные понятия доказательства, Гэри Л, Миллер (Сагу 1. Мй!ег) продемонстрировал (в немного ослабленном виде), что если определенное, хорошо известное предположение в теории чисел, называемое обобщенной гипотезой Римана, может быть доказана, то либо и — простое число, либо существует число х < 2(1п п)з, такое, что алгоритм Р обнаружит, что и — не простое число.

[Обзор различных обобщений гипотезы Римана приведен в,7. Сошр. Яуэсеш Яс? 13 (1976), 300-317. Присутствующая в этой оценке постоянная 2 получена Эриком Бахом (ЕПс ВасЬ), Ма!Ь. Сошр. 66 (1990), 355-380; см. гл. 8 в А)яог!гЬиис ХпшЬег ТЬеогу 1 Ьу Е. ВасЬ, 3.

О. 8Ьа!!!с (М1Т Ргевэ, 1996).] Таким образом, можно найти строгий способ проверки, будет лн число простым, выполняемый за 0(!ойп)э элементарных операций, в противовес вероятностному методу, время выполнения которого при условии, что доказаны обобщенные гипотезы Римана, равно 0(!ойп)з. Вполне резонно задать вопрос дают ли доказанные гипотезы такой же надежный результат, какой дает неоднократное применение к случайным числам алгоритма Р, Вероятностная проверка принадлежности числа к простым была впервые предложена в 1974 году Р.

Соловеем (К. 8о!отау) и В. Штрассеном (Ч. Бтгаээеп), разработавшими интересный, но более сложный алгоритм проверки, описанный в упр. 23, (Ь). [См. ЯХСОМР 6 (1977), 84-85; 7 (1978), 118.] Алгоритм Р является упрощенным вариантом процедуры, разработанной М. О. Рабином (М. О. КаЬ!и), в основу которого частично положены идеи Гэри Л, Миллера [см. А!яог!гЬшэ апс~ Сошр!ех!гу„ей!гео Ьу Я. Р. ТгацЬ (Аса4еппс Ргеш, 1976), 35-36].

Исследования, выполненные Б, Арази (В. Агах!) [Сошр. Х 37 (1994), 219-222], показали, что можно существенно повысить скорость выполнения алгоритма Р для больших и за счет применения быстрого метода вычисления остатков Монтгомери (см. упр. 4.3.1-41), В 1980 году Леонард М. Эдлеман (Ьеопагб М. Аб!ешап) предложил совершенно другой подход к решению этой задачи. Его очень интересный метод основан на теории алгебраических целых чисел, но это выходит за рамки данной книги. Метод Эдлемана приводит к невероятностной процедуре, которая определяет, будет ли любое число длиной, скажем, 250 знаков простым не более чем за несколько часов. [В общем случае время, необходимое для решения задачи по этому методу, равно (1ойп)ойьэмэ мэ"!; см.

1.. М. А<Пешап, С. Ротегэпсе, К. 8. Кшпе!у, Аппп)э о! Маей. 117 (1983), 173 — 2061 Х, В. Ленстра (мл.) (Н. Ж. Ьепэгга, Эг.) усовершенствовал этот метод, благодаря чему он стал выполняться еще быстрее, что подтвердила практика применения метода Г. Кохеном (Н. СоЬеп) и А. К. Ленстрой (А. К. 1.епэгга) (Масй. Сотр. 42 (1984), 297-330; 48 (1987), 103-121), Позже Эдлеман и Минг-Дех А. Хуанг (М!п8-ПеЬ А.

Нцапй) предложили способ строгого доказательства принадлежности числа к простому для всех простых и. С высокой вероятностью время выполнения этого алгоритма пропорционально )ой и [Ъес!пге косее !и МаНь 1512 (1992)). Однако их метод, кажется, представляет только чисто теоретический интерес. Разложение на простые множители при помощи цепных дробей. Камнем преткновения для методов разложения на простые множители, рассмотренных выше, является разложение чисел, содержащих 30 и более разрядов, поэтому для их разложения нужна другая идея, которая позволила бы идти дальше в этом направлении. К счастью, такая идея существует; точнее, есть две такие идеи, предложенные А.

М. Лежандром (А. М.?,ейепбге) и М. Крайчиком (М. Кга)ссай), Основываясь на них, Д. Г. Лемер и Р. Е. Пауэрс (Н. Е. Роиегэ) много лет назад разработали новый подход к решению этой задачи (Ви!). Атег. МагЬ. Вос. 37 (1931), 770-776]. Однако некоторое время данный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах. Негативное мнение об этом методе было преодолено к концу 60-х годов, когда Джон Бриллхарт (ЗоЬп ВН!!Ьагт) обнаружил, что приближение Лемера-Пауэрса можно "воскресить" благодаря тому, что метод очень хорошо подходит для компьютерного программирования, Действительно, чуть позже он вместе с Майклом А.

Моррисоном (М!сЬае! А. Магг!эоп) разработал алгоритм, ставший в 70-е годы непревзойденным средством разложения на простые множители с использованием формата многократной точности. Их программа обрабатывала на компьютере 1ВМ 360/91 произвольные 25-разрядные числа за 30 с, а 40-разрядные числа — за 50 мин (см.

Ма!5. Сотр. 29 (1975), 183-205). Первый триумфальный успех был достигнут в 1970 году, когда был продемонстрирован результат: 2'ээ+1 = 59649589127497217 5704689200685129054721, Основная идея заключается в том, чтобы найти числа х и у, такие, что х аз уз (по модулю Х), Ос х,у ()У, х ~у, я+у ~)У. (18) Метод Ферма накладывает более строгое условие х~ — уэ = !э', но в действительности соответствия (18) достаточно для того, чтобы разложить число )У на множители. Из (18) следует, что число !У есть делитель числа хэ — уэ = (х — у)(х + у), но число !у не делит ни х — у, ни х+ у; следовательно, 8сб(А1, х — у) и 80!(А', х + у) являются делителями числа )т', которые могут быть найдены при помощи эффективных алгоритмов, рассмотренных в разделе 4.5.2.

Один из способов нахождения решения уравнения (18) — найти такие значения х, при которых хэ = а (по модулю Ю) для малых значений (а(. В дальнейшем будет показано, что зачастую, чтобы получить решения (18), достаточно просто объединить решения приведенного выше уравнения. Далее, если хэ = а+ кап~ для некоторых Й и г( при малом значении !а(, дробь х/а является хорошим приближением к ~ЙЮ; и обратно, если х/4 — очень хорошее приближение к ~ЙЮ, то (хэ — Й)Уа"! будет малб. Сказанное наводит на мысль о необходимости рассмотреть разложение в цепную дробь числа ~АЖ, поскольку, как видно из соотношения 4.5.3-(12) и упр.

4.5.3-42, цепные дроби дают хорошие рациональные приближения, Для квадратичных иррациональностей цепные дроби обладают многими приятными свойствами, как было доказано в упр. 4.5.3-12. В приводимом ниже алгоритме зти свойства используются для получения решений уравнения хт— : ( — 1) "р"'р"...

р' (по модулю Х). (19) Здесь используется фиксированное множество простых чисел р| — — 2, рз — — 3, ... вплоть до р . Из этого множества выбираются только такие простые числа р, для которых либо р = 2, либо (йХ)~о '1~э шоб р < 1, поскольку другие простые числа никогда не будут множителями чисел, порождаемых этим алгоритмом (упр. 14). Если (хыеоыем,...,е е), ..., (х„ео„,еы,, ..,е„„) — решения (19), такие, что в векторной сумме (еомеы,...,е е)+ +(ео„,е1„,...,е е) =(2ео,2е'„...,2е' ) (20) каждый компонент четный, то х = (х|... х„) шое) Х, у = (( — 1)е1р" ...р"") шое1 Ф (21) дает решение уравнения (18) за исключением случая, когда х га ху.

Условие,(20) равнозначно утверждению, что рассматриваемые векторы линейно зависимы по модулю 2, поэтому, если найдено по меньшей мере т + 2 решений (19), должно существовать хотя бы одно решение, соответствующее (20). Алгоритм Е (Разложение на простые мнолсители при помощи цепных дробей). По данным положительному целому числу Х и положительному целому числу 1, такому, что число йХ не является точным квадратом,' этот алгоритм предпринимает попытку найти решения уравнения (19) для данной последовательности простых чисел рм ..., р„,„исследуя сходимость цепной дроби для .ДМ. (Другой алгоритм, использующий для поиска множителей числа Х выходные данные (алгоритма Е,— Прим.

перев.), является предметом рассмотрения в упр. 12.) Е1. (Начальная установка.] Присвоить Ю с- йХ, В +- (иЪ], В' +- 2В, П <- Г ~- В', 1' <- 1, $" ~- .0 — Вт, Р ~- В, Р' < — 1, А +- О, Я <- О. (Следуя основной процедуре упр. 4.5.3-12, алгоритм находит разложение в цепную дробь числа ~%Я.