Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 8
Текст из файла (страница 8)
Следует избегать также значения с = -2, поскольку рекуррентное уравнение х +, — — х — 2 имеет 2 решение в виде х = гэ + г э . Похоже, что другие значения параметра с не приводят к возникновению простых связей по модулю р и все они должны быть удовлетворительными при подходящих начальных значениях. Ричард Бреят применил эту модификацию алгоритма В для нахождекия простого множителя 1 238926361552897 числа 2мв + 1, [См. Май.
Сошр. 36 (1981), 627-630; 38 (1982), 253-255.) Метод Ферма. Другой подход к решению проблемы разложения чисел на простые множители, который в 1643 году предложил Пьер де Ферма (Рктге де Регшас), более подходит для поиска больших множителей, нежели малых. [Описание метода, данное самим Ферма и переведенное на английский язык, можно найти в книге Л. Е. Диксона (1 . Е. Вьскяоп) Швгогу о/ йе ТБеогу о/Яишбегэ 1 (Сэгпе81е 1пэц о( %ээЬш81оп, 1919), 357.[ Допустим, что Х = ие, где и < е.
Для практических целей можно положиттн что 1у — нечетное число. Это означает, что и и е тоже нечетны. Можно такисе положить, что х = (и+ е)/2, у = (е — и)/2, (12) Х=х~ — уэ, О<у<я</У. (13) Суть метода Ферма заключается в том, что ищутся такие значения х и у, которые удовлетворяют уравнению (13). В следующем алгоритме показано, как таким путем можно разложить число на простые множители, нв выполняя операций деления. Алгоритм С (Разлохсепие на простые .иножигпели при полипци операций сложения и вмчишанил).
По данному нечетному числу 87 этот алгоритм определяет наибольший множитель числа Х, меньший или равный ~/Х. С1. [Начальная установка.[ Присвоить х <- 2(е'Ф) + 1, у <- 1, г <- [~/Ф)" — )У. (Во время выполнения этого алгоритма величины х, р„г отвечают соответственно величинам 2х+ 1, 2у+ 1, хэ — у~ — Ю в уравнении (13). Должно соблюдаться условие [г[ < х и р <х.) С2. [Выполнено?) Если г = О, то выполнение алгоритма завершается.
Имеем Х = [(х — у)/2) [(х + р — 2)/2), а (х — у)/2 — наибольший множитель для Х, меныпий нли равный ь/Х. СЗ. [Шаг по х.) Присвоить г +- г+ х и х е- х + 2. С4. [Шаг по р.] Присвоить г < — г — у и у в- у + 2. С5. [Проверить г.[ Если г > О, то возвратиться к шагу С4, иначе возвратиться к шагу С2. 1 Возможно, читатель сочтет небезынтересным поиск вручную простых множителей числа 377 при помощи этого «лгорнтма. Число шагов, необходимых для нахождения множителей и и е числа /у = ие, по существу, пропорционально (х + р — 2)/2 — [~/Ю) = е — [ь/Ж); зто, конечно, может оказаться очень большой величиной, хотя каждый шаг на большинстве компьютеров может выполняться очень быстро. Р.
Ш. Леман (К. Б. (еЬшап) (МасЬ. Сошр. 28 (1974), 63?-646) усовершенствовал алгоритм таким образом, что в худшем случае для его выполнения требуется только 0(Х'~э) операций. Называть алгоритм С методом Ферма не совсем правильно, поскольку Ферма использовал несколько более обтекаемый подход. В компьютерах основной цикл алгоритма С выполняется довольно быстро, но для вычислений вручную он мало пригоден.
На самом деле Ферма не сохранял текущие-значения р; он рассматривал величину хт — Х и, исходя из наименее значимых разрядов, делал вывод о том, является ли эта величина полным квадратом. (Последние два разряда полного квадрата должны быть ОО, е1, е4, 25, об или е9, где е — четная, а о — нечетная цифра,) По этой причине он избегал операций, которые выполнялись на шагах С4 и С5, заменяя их пря помощи специальных приемов операцией определения числа, не являющегося полным квадратом. Предложенный Ферма способ просмотра правых крайних разрядов можно, конечно, обобщить, используя другие модули.
Предположим для ясности, что Ю = 8616460 799 (историческое значение этого числа описывается ниже), и рассмотрим следующую таблицу. и (хт — Ю) шойш равно 1,2,2 1,2,0,0,2 5,6,2,0,0,2,6 1,2,5,2,1,2,5,2 10, О, 3, 8, 4, 2, 2, 4, 8, 3, О , то х шой т равно 0,1,1 0,1,4,4,1 О, 1, 4, 2, 2, 4, 1 0,1,4,1,0,1,4,1 0,1,4,9,5,3,3,5,9,4,1 Если х шоб т равно 0,1,2 0,1,2,3,4 0,1,2,3,4,5,6 0,1,2,3,4,5,6,7 О, 1, 2, 3, 4, 5, 6, 7, 8, О, 10 3 5 7 8 11 Если величина х~ — Ю есть полный квадрат ут, то она должна иметь остаток по модулю ти, соответствующий этому факту. Например~ если йГ = 8616460799 и х шоб 3 э~ О, то (хт — Ю) шо63 = 2, т.
е. величина хт — Х не может быть полным квадратом. Поэтому х должно быть кратным 3 для всех значений Х = х~ — рт. Из таблицы видно, что хшод3 =0; хшод5 = О, 2 или 3; х шоб 7 = 2, 3, 4 или 5; х шоб 8 = 0 либо 4 (отсюда х шоб 4 = 0); хшо611 = 1, 2, 4, 7, 9 или 10. (14) Это значительно сокращает процесс поиска х. Пусть, например, х должно быть кратно 12. Тогда должно быть х > (ь'Х1 = 92825 и наименьшим числом, кратным 12, является число 92832.
Это значение дает в остатке (2,5,3) по модулю (5, 7, 11) соответственно, поэтому оно не удовлетворяет уравнению (14) по отношению к модулю 11. Увеличив х на 12, можно заменить остаток по модулю 5 на 2, по модулю 7 на 5 н по модулю 11 на 1. Поэтому легко увидеть, что первое значение величины х > 92825, удовлетворяющее всем условиям в уравнении (14), есть х = 92880. Теперь 92880т — Х = 10233601, и, вычислив вручную квадратный корень, получаем, что 10 233 601 = 3 199~ действительно является полным квадратом.
Таким образом получено искомое решение х = 92880, р = 3 199, а разложение на простые множители имеет вид 8616460799= (х — у)(х+ у) = 89681 96079. Это значение Х интересно тем, что английским экономистом и логиком У. С. Дживонсом (ьу. Б. Зетопэ) в хорошо известной книге оно было введено следующим образом: "По данным двум числам можно найти их произведение простым и надежным способом, но совсем другое дело, когда для большого числа необходимо найти его множители.
Можно ли сказать, какие два числа были перемножецы, чтобы получилось число 8 616 460 7997 Я думаю, что вряд ли кто-либо, кроме меня, знает это". (ТЛе Рг!лс!р!вэ оГ бс1епсе (Маспп1!ап, 1874), Спар1ег 7.) Однако, как следует нз вышесказанного, Ферма смог разложить это число на простые множители на обратной стороне конверта меньше чем за десять минут! Основная мысль Дживонса о сложности разложения чисел на простые множители по сравнению с нх перемножением справедлива, но только в случае, когда мы имеем дело с произведением чисел, не настолько близких друг к другу.
Вместо модулей, рассматриваемых в уравнении (14), можно использовать любые степени разчичных простых чисел. Например, если взять 25 вместо 5, то возможные значения величины х шоб 25 будут равняться О, 5, 7, 10, 15, 18 и 20. Это дает больше информации, чем (14), В общем случае можно получить больше информации, выполняя операции по модулю рэ, чем по модулю р, при нечетных р, если хз — Ю вт 0 (по модулю р) имеет решение х. Рассмотренный модулярный метод называется методом решета (сита,! (гйете ргосебиге), так как можно представить, что все целые числа проходят через "решето'*, пропускающее только те значения, для которых х шод 3 = 0; затем эти числа просеиваются через другое сито, которое пропускает только числа, для которых хшо65 ж О, 2 или 3, и т.
д. Каждое сито в отдельности отсеивает примерно половину оставшихся значений (см. упр. 6). Когда же просеивание ведется при помощи попарно взаимно простых модулей, то на основании китайской теоремы об остатках (теорема 4.3,2С) каждое сито работает независимо от остальных. Поэтому, если выполнять просеивание относительно, скажем, 30 различных простых чисел, то для того, чтобы определить, будет ли величина хз — Х полным квадратом для уз, достато4но из каждых 2за величин проверить только одну. Алгоритм 13 (Резлохсеиие па простые множители мепшдом решета).
По данным нечетным числам Х этот алгоритм определяет наибольший множитель числа Х, меныпий или равный ~У. В процедуре используются попарно взаимно простые модули ты тм ..., т„которые также взаимно просты с Х. Предположим, что доступны г таблиц просеиаанил о(1,А, О < у < то 1 < ! < г, где з(в',А = '(уз — Хвзуэ (по модулю т,) имеет решение у~.
Ш. !Начальная установка.) Присвоить х +- (~/Х ) и й; е- ( — х) ппх1 т~ при 1 <1 < г. (Во время выполнения этого алгоритма индексные переменные йм аю ..., к, будут установлены таким образом, что Ц = (-х) шоб ть) 132. !Просеять.) Если з 11, Ц = 1 при 1 < 1 < г, то перейти к шагу Р4. 113. (Найти х.) Присвоить х +- х + 1 н й; ь- (й; — 1) шобт, при 1 < 1 < г. Возвратиться к шагу В2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
