AOP_Tom2 (1021737), страница 122
Текст из файла (страница 122)
12 обнаружить множитель для числа Х. При исследовании этого алгоритма нужно найти границы для (а) вероятности того, что случайное значение Х приводит к выводу результата, и (Ь) вероятности того, что для нахождения множителя потребуется большое количество выходных данных. Пусть Р(т, Х)---вероятность (а), т. е.
вероятность того, что Т = 1, если величина Х выбирается случайной. После опробования М значений величины Х получим в среднем МР(т, Х) выходных значений, и число выходных значений имеет бииомиальное распределение, для которого среднеквадратичное отклонение меньше, чем квадратный корень из среднего значения. Вероятность (Ь) легко найти, воспользовавшись результатом упр. 13: при нахождении одного множителя алгоритму потребуется более гп + Л выходных значений с вероятностью < 2 ". В упр.
ЗО доказывается, что Р(тп, Х) ) ш"/(г! Х) в случае, когда т = 2(1ой Ж/(2 1ойр Ц, поэтому время выполнения алгоритма можно оценить почти так же, как в (22), но при этом величина 2з/Х должна быть заменена величиной 7з'. На этот раз выбираем , =,чьчььэ к где ф~ < 1 и г — четное числа Теперь значение гп выбираем так, чтобы г = 1п У/1пр,„+ 0(1/1ой!ой%); это означает, что ! и Х 1и 1и Л д 2 2 1пп(р ) =1пр — 1п1пр +0(1/1одр ) 1пю1п1пй 6+1 2 — — 1и 1п 1э' + 0 (1ой 1ой 1ой М), 2 р~-льэьБР+о[.~~ и кю)). 1п р„, 1и гп с г1 Х Выберем М таким, что Мгп'/(г!М) > 4гп.
Следовательно, ожидаемое количество выходных значений МР(гп, Ж) будет не меньше 4т. Время выполнения алгоритма — порядка Мт1о81т' плюс 0(шз) шагои, что следует из результатов упр. 12; отсюда получаем, что 0(тз) оказывается меньше Мт1ойЮ, что равно ~( /3(Ь ЕХИДН ~С + 0((! ГХ)'~Ч Ц1 ЬШ) '~'(1 Д1 К1 КЖ))). Вероятность того, что с помощью данного метода не удастся получить множитель, ничтожно мала, так как вероятность того, что вычислено меныпе, чем 2т выходных значений (упр. 31), не превышает е 7з, в то время как вероятность того, что из числа первых 2т выходных значений не будет найдено ни одного множителя, не превышает 2 "' и т» 1пХ. Доказана следующая несколько усиленная теорема Диксона.
Теорема П. Существует алгоритм, время выполнения которого равно 0(ХЦм1), где ,сс -с,~~;ээ.~~' ..—.~. находит петрпвпальный множитель числа Х с вероятностью 1 — 0(1/У) в случае, когда для числа й' существует по меньшей мере два простых делители. 3 Другие подходы. Джон М..Поллард (йоЬп М. РоПагб) предложил другой способ разложения на простые множители (Ргос. СашЬгЫйе РЫ1. Яос. 76 (1974), 521-528], в котором дается практический способ нахождения простых множителей р числа Х для случая, когда число р — 1 не имеет больших простых множителей.
Этот алгоритм (см. упр. 19) был, вероятно, первой попыткой решения поставленной задачи после того, как выяснилось, что алгоритмы А и В для больших чисел Х выполняются слишком долго. В обзорной работе, написанной Р. К. Ги (Н. К. Сну) в соавторстве с Дж. Х. Конвеем (д. Н. Сопзгау) и опубликованной в Сопйтеввив Житегапбит 16 (1976), 49-89, проведен анализ состояния проблемы на то время и перспектив разработки новых методов ее решения. Ги утверждал: "Я буду удивлен, если кто-либо в этом веке разложит на простые множители числа длиной 10"е, не оговаривая специальных случаев"; ему действительно пришлось много раз удивляться в течение следующих 20-ти лет.
Значительные успехи в разработке способов разложения на простые множители были достигнуты в 80-е годы, начиная с мешода квадратичного просеиванил Карла Померанса (Саг1 Рошегапсе), разработанного им в 1981 году (см. Бес!иге к!осев ш Согпр. Ясй 209 (1985), 169-182(. Затем Хендрик Лснстра (Непдг!!с Бепзгга) разработал метод эллиптических кривых (Аппа!в ог'МасЛ. 126 (1987), 649 — 673(.
Он эвристически предположил, что для нахождения простого множителя р необходимо выполнить около ехр( (2+ е)(!пр)(!и !п р) ) операций умножения. Эта величина— не что иное„как асимитотический квадратный корень из оценки времени выполнения алгоритма Е, когда р ге 4Х, и она становится даже лучше, если число Аг имеет относительно малые простые множители. Прекрасное описание этого метода дано Джозефом Х.
Силверманом (догерЬ Н. 8!!хегшап) и Джоном Тейтом (доган Тасе) в Яабопа! Ро!п1з оп Е!!!рбс Сиггев ( чем Уогйм брПпйег, 1992), СЬарсег 4. В 1988 году к решению этой задачи вернулся Джон Поллард. Он предложил новый подход, который стал позже известен как решето числового полл. С рядом работ, посвященных этому методу, который является в настоящее время чемпионом по разложению на простые множители чрезвычайно больших чисел, можно ознакомиться в Е,ее!иге эосев ш ЛдаНь 1554 (1993). При испсвчьзовании этого метода прогнозируемый порядок времени выполнения равен ехр((64~9+ е)г/э(!и А)г~э(!и!пХ)г/э) (25) при А' -+ со.
Согласно анализу, выполненному А. К. Ленстрой (А. К. Бепггга), порогом, пгкше которого хорошо настроенный метод решета числового поля начинает превосходить хорошо настроенный метод квадратичного просеивания, является Л" - 10ыг, Подробности этих методов выходят за рамки данной книги, но представление об их эФфективности можно полу'чить, обратии внимание на некоторые уже известные случаи неудачных попыток разложения на простые множители чисел Ферма вида 2г + 1. Например, разложение 2ыг+ 1 2424833 745 560 282 564 788 4208 337 395 736 200 454 918 783 366 342 657 рээ было получено при помощи метода решета числового поля после вычислений в течение четырех месяцев, что заняло все свободное время почти 700 рабочих станций (Ьепэсга, Мапазэе, Ро!!агс(, Л|аСЛ.
Сошр. 61 (1993), 319-349; 64 (1995), 1357]; здесь рог обозначает 99-разрядное простое число. С.чедуюшее чисво Ферма было в два раза длиннее предыдущего. но при помощи метода эллиптических кривых 20 октября 1995 года был получен результат: 2' огг + 1 = 45 592577 6487031809.
4 659 775 785 220 018 543 264 560 743 076 778 192 897 ргэг. [Бйсйагд Вгепц МагЛ. Сотр. 68 (1999), 429 — 45Ц На самом деле Брент уже применял метод эллиптических кривых в 1988 году для решения следующей задачи: 2 о4г+1 319489 974849 167988556341760475137 3560841906445833920513 ры4. Все простые множители, кроме одного, оказались, хотя и с некоторой долей везения, ьз меныпими < 10, так что метод эллиптических кривых стал победителем. А как насчет числа 24ээе + 17 К настоящему моменту зта задача кажется слишком сложной для решения.
Данное число содержит пять множителей < 10'", но остаток, который не удается разложить на множители, содержит 1187 десятичных разрядов. Еще один случай: число 2э 'э~ + 1 содержит четыре известных множителя < 10~~ и очень большой неразложенный остаток. [Сгапс1а11, Га81п, Л1агб. Сошр. 62 (1994), 321; ВгепС, Сгапда)1, П11сбег, зап На)ежуп, 68 (1999), 429-451.[ Секретные множители.
Всеобщий интерес к проблеме разложения на простые множители резко возрос в 1977 году, когда Р. Л. Ривест (В. ?.. Й1хеег), А. Шамир (А. БЬапнг) и Л. Эдлеман (1.. Абйешап) нашли способ кодирования сообщений, которые могут быть декодированы в явном виде только по известным множителям, на которые разлагается большое число Х, даже в том случае, когда метод кодирования известен всем н каждому. Так как большинство величайших математиков мира не могут до сих пар найти эффективный метод разложения чисел на простые множители, этот метод [САСМ 21 (1978), 120 — 126[ позволяет почти гарантированно защитить засекреченные данные и сообщения в компьютерной сети.
Представим себе маленькое электронное устройство (назовем его ЯЯА-блоком), в памяти которого хранятся два больших простых числа р и д. Будем считать, что числа р — 1 и д — 1 не делятся на 3. ВБА-блок, подсоединенный каким-то образом к компьютеру, передал последнему произведение Х = рд, поэтому ни один человек яе может обнаружить значения чисел р и д, не разложив число 67 на простые множители. При попытке взлома ВБА-блок запрограммирован на самоуничтожение.
Другими словами, блок сотрет информацию в своей памяти, если будет предпринята попытка доступа к нему или он подвергнется воздействию внешнего излучения, которое может изменить или считать данные, хранящиеся в памяти. Кроме того, ВБА-блок достаточно надежен с точки зрения эксплуатации; в случае его выхода из строя вследствие неполадок в системе питания или износа нужно выбросить имеющееся устройство и купить новое. Простые множители р н 4 генерируются самим ВБА-блоком с помощью схемы, основанной на явлениях, которые случайны по самой своей природе (например, космические лучи).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
