AOP_Tom2 (1021737), страница 120
Текст из файла (страница 120)
На практике алгоритм Р очень редко выдает неправильный результат для большинства значений и. Однако критическим является тот факт, что вероятность отказа ограничена независимо от значений и. Допустим, что мы обращаемся к алгоритму Р несколько раз, выбирая х независимо и случайно, когда выполняется шаг Р1.
Если алгоритм сообщает, чта число и непростое, можно быть уверенным, что так оно и есть. Но если алгоритм сообщает 25 раз подряд, что и "возможно, простое", значит, и — "почти наверное простое", так как вероятность того, что процедура, выполняющаяся 25 раз подряд, дает неправильную информацию об исходном числе, меньше (1/4)~е. Эта величина меньше, чем один шанс на квадрильон; даже после проверки при помощи такой процедуры миллиарда различных чисел ожидаемое количество ошибок будет меньше, . Скорее всего, можно предположить, что компьютер потерял бит при 1 вычислениях из-за аппаратных неполадок или влияния космической радиации, чем та, что алгоритм Р непрерывно ошибается! Вероятностные алгоритмы, подобные описанному, приводят нас к традиционному вопросу о достоверности.
Нуждаемся ли мы в строгом доказательстве принадлежности числа к простым? Для тех, кто ие склонен игнорировать традиционные понятия доказательства, Гэри Л. Миллер (Сагу Ь. М!Пег) продемонстрировал (в немного ослабленном виде), что если определенное, хорошо известное предположение в теории чисел, называемое обобщенной гипотезой Римана, может быть доказано, то либо и — простое число, либо существует число х < 2(1п и)~, такое, что алгоритм Р обнаружит, что и — не простое число.
[Обзор различных обобщений гипотезы Римана приведен в Х Сотр. Яузсет Яс? 13 (1976), 300-317. Присутствующая в этой оценке постоянная 2 получена Эриком Бахом (ЕПс ВасЬ), МагЛ. Сотр, 55 (1990), 355-380; см. гл. В в А!лог!гЛт!с ХнтЬег ТЛеогу 1 Ьу Е, ВасЬ, 3, О. ВЬай!! (М1Т Ргеее, 1996).» Таким образом, можно найти строгий способ проверки, будет ли число простым, выполняемый за О(!ой и)з элементарных операций, в противовес вероятностному методу, время выполнения которого при условии, что доказаны обобщенные гипотезы Римана, равно О(!ой и)л. Вполне резонно задать вопрос: дают ли доказанные гипотезы такой же надежный результат, какой дает неоднократное применение к случайным числам алгоритма Р.
Вероятностная проверка принадлежности числа к простым была впервые предложена в 1974 году Р. Саловеем (К. Во!аллу) и В. Штрассеном (Ч. Всгаэееп), разработавшими интересный, но более сложный алгоритм проверки, описанный в упр. 23, (Ь). [См. 81СОМР 6 (1977), 84 — 85; 7 (1978), 118.» Алгоритм Р является упрощенным вариантом процедуры, разработанной М. О. Рабином (М. О. КаЬ|п), в основу которого частично положены идеи Гэри Л. Миллера [см. А!ВоПсЛтз алс! Сотр!ехйу, егП!ед Ьу 3.
Р. ТгаиЬ (Асабет!с Ргеэз, 1976), 35 — 36». Исследования, выполненные Б. Арази (В. Агаьб) [Сотр. Х 37 (1994), 219-222», показали, что можно существенно повысить скорость выполнения алгоритма Р для больших и за счет применения быстрого метода вычисления остатков Монтгомери (см. упр. 4.3.1-41). В 1980 году Леонард М. Эдлеман (Ьеопагд М.
АгПетап) предложил совершенно другой подход к решению этой задачи. Его очень интересный метод основан на теории алгебраических целых чисел, но это выходит за рамки данной книги. Метод Эдлемана приводит к невераятностной процедуре, которая определяет, будет ли любое число длиной, скажем, 250 знаков простым не более чем за несколько часов. [В общем случае время, необходимое для решения задачи па этому методу, равно (!ойи)о!мама "а"!; см, 1,.
М. Аг!!етап, С. Ротегапсе, И. 8. Вите!у, Аппа!з оу ЛХасЬ, 117 (1983), 173 — 206.) Х. В. Ленстра (мл.) (Н. %. 1епвтга, Лг.) усовершенствовал этот метод, благодаря чему он стал выполняться еще быстрее, чта подтвердила практика применения метода Г. Кохеном (Н. СоЬеп) и А. К. Ленстрай (А. К. ! епэ1га) (Май. Сотр. 42 (1984), 297 — 330; 48 (1987), 103-12Ц. Позже Эдлеман и Минг-Дех А. Хуанг (ь!1пй-РеЬ А. Нпапк) предложили способ строгого доказательства принадлежности числа к простому для всех простых и.
С высокой вероятностью время выполнения этого алгоритма пропорционально !об п (1 ессиге Хо1ез т Май. 1512 (1992)). Однако их метод, кажется, представляет только чисто теоретический интерес. Разложение иа простые множители при помощи цепных дробей. Камнем преткновения для методов разложения на простые множители, рассмотренных выше, является разложение чисел, содержащих 30 и более разрядов, поэтому' для их разложения нужна другая идея, которая позволила бы идти дальше в этом направлении. К счастью, такая идея существует; точнее, есть две такие идеи, предложенные А. М. Лежандром (А.
М. 1 ебепйге) и М. Крайчикам (М. Кга11сЬЙ). Основываясь на них, Д. Г. Лемер и Р. Е. Пауэрс (В. Е. Роиегв) много лет назад разработали новый подход к решению этой задачи (Ви!!. Атег. Май. Яос. 37 (1931), 770-776]. Однако некоторое время данный метод не применялся из-за трудностей, связанных с его реализацией на настольных арифмометрах. Негативное мнение об этом методе было преодолено к концу 60-х годов, когда Джон Бриллхарт (ЛоЬп ВП11Ьаг1) обнаружил, чта приближение Лемера-Пауэрса можно "воскресить" благодаря тому, что метод очень хорошо подходит для компьютерного программирования. Действительно, чуть позже он вместе с Майклом А.
Моррисоном (МгсЬае1 А. Могтьзап) разработал алгоритм, ставший в 70-е годы непревзойденным средством разложения на простые множители с использованием формата многократной точности. Их программа обрабатывала на компьютере 1ВМ 360/91 произвольные 25-разрядные числа за 30 с, а 40-разрядные числа — за 50 мин [см.
Май. Согпр, 29 (1975), 183 — 205). Первый триумфальный успех был достигнут в 1970 году, когда был продемонстрирован результат: 2'эв + 1 = 59649589127497217 5 704689200685129054721. Основная идея заключается в том, чтобы найти числа х и у, такие, что х эз у~ (по модулю !у), 0 ( х,у ( Х, х Ф у, х+у 1с )у.
(18) Метод Ферма накладывает более строгое условие хз — уз = 1г', но в действительности соответствия (18) достаточно для того, чтобы разложить число Х на множители. Из (18) следует, что число !У есть делитель числа х — у~ = (х — у)(х + у), но число !У пе делит нн х — у, нн х + у; следовательно, Всс1(Л~, х — у) и Вс(1(!У, х, + у) являются делителями числа М, которые могут быть найдены при помощи эффективных алгоритмов, рассмотренных в разделе 4.5.2. Один из способов нахождения решения уравнения (18) — найти такие значения х, при которых хз = а (по модулю !т') для малых значений ~о~. В дальнейшем будет показано, что зачастую, чтобы получить решения (18), достаточно просто объединить решения приведенного выше уравнения.
Далее, если х = а+ !с!т'и' для некоторых Ь и 4 при малом значении ~а~, дробь х/4 является хорошим приближением к т%Х; и обратно, если х/4- — очень хоропгее приближение к ъ%У, то 1х — !с!У4~~ будет малб. Сказанное наводит на мысль о необходимости рассмотреть разложение в цепную дробь числа т>'а>у', поскольку, как видно из соотношения 4.5.3 (12) и упр. 4.5.3 — 42, цепные дроби дают хорошие рациональные приближения. Для квадратичных иррациональностей цепные дроби обладают многими приятными свойствами, как было доказано в упр.
4.5.3- 12. В приводимом ниже алгоритме эти свойства используются для получения решений уравнения х' = ( — 1)"р",р"...р'" (по модулю >У). (19) Здесь используется фиксированное множество простых чисел р> — — 2, рз —— 3, ... вплоть до р . Из этого множества выбираются только такие простые числа р, для которых либо р = 2, либо (е>>>)>о >Уз п>о>(р < 1, поскольку другие простые числа никогда не будут множителями чисел, порождаемых этим алгоритмом (упр. 14).
Если (х>,ео>,е>>,...,е„,>), ..., (х, ео„,е>„...,е,„„)- решения (19), такие, что в векторной сумме (ео>,е>>,, е,„>) +. + (ео,,е„,...,е„,„) = (2ео,2е>>,...,2е',„) (20) каждый компонент че>пнмй, то х = (х>... х„) шо>(Х, у = (( — 1)'2р (.,.р ) пю>(А> (21) дает решение уравнения (13) за исключением случая, когда х = ~р. Условие, (20) равнозначно утверждению, что рассматриваемые векторы линейно зависимы по модулю 2, поэтому, если найдено по меньшей мере >и + 2 решений (19), должно существовать хотя бы одно решение, соответствующее (20). Алгоритм Е (Рааложение на прас>пь>е множители при помощи цепных дробей).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
