в случае, когда г = 2[log N/(2 logpm)J, поэтому время выполнения алгоритма можно оценить почти так же, как в (22), но при этом величина 2yfN должна быть заменена величиной N. На этот раз выбираем

г = V21niV/lnlniV + e,

где й < 1 и г - четное число. Теперь значение m выбираем так, чтобы

r = \nNI \прт + 0(1/ log log N);

это означает, что

lnPm = y-2---InlnN+ 0{\),

Inm = 1п7г(р„г) =lnpm - 1п 1пр„г + 0(1/logp)

InTVlnlnA/ й + 1, , , , ----- In In iV + о (log log log iV),

exp(-\/2 IniVln 1пЛ + 0(r log log log N)).

Выберем M таким, что Mm/{r\N) > 4m. Следовательно, ожидаемое количество выходных значений MP{m,N) будет не меньше 4т. Время выполнения алгоритма- порядка MmlogN плюс О(т) шагов, что следует из результатов упр. 12; отсюда получаем, что О(т) оказывается меньше MmlogN, что равно

exp(8(lniV)(lnlniV) + 0((logiV)i/2(loglogiV)-i/2(logloglogiV))).

Вероятность того, что с помощью данного метода не удастся получить множитель, ничтожно мала, так как вероятность того, что вычислено меньше, чем 2т выходных значений (упр. 31), не превышает е""/, в то время как вероятность того, что из числа первых 2т выходных значений не будет найдено ни одного множителя, не превышает 2~" и m » In TV. Доказана следующая несколько усиленная теорема Диксона.

Теорема D. Существует алгоритм, время выполнения которого равно 0(Л), где e{N) = c/kilnN/lnN и с - произвольная константа, большая, чем \/8, и который находит нетривиальный множитель числа N с вероятностью 1 - 0{1/N) в случае, когда для числа N существует по меньшей мере два простых делителя.

Другие подходы. Джон М. Поллард (John М. Pollard) предложил другой способ разложения на простые множители [Proc. Cambridge Phil. Soc. 76 (1974), 521-528], в котором дается практический способ нахождения простых множителей р числа N для случая, когда число р- 1 не имеет больших простых множителей. Этот алгоритм (см. упр. 19) был, вероятно, первой попыткой решения поставленной задачи после того, как выяснилось, что алгоритмы А и В для больших чисел Л выполняются слишком долго.

В обзорной работе, написанной Р. К. Ги (R. К. Guy) в соавторстве с Дж. X, Кон-веем (J. Н. Conway) и опубликованной в Congressus Numerantium 16 (1976), 49-89, проведен анализ состояния проблемы на то время и перспектив разработки новых методов ее решения. Ги утверждал: "Я буду удивлен, если кто-либо в этом веке разложит на простые множители числа длиной 10*°, не оговаривая специальных

случаев"; ему действительно пришлось много раз удивляться в течение следующих 20-ти лет.

Значительные успехи в разработке способов разложения на простые множители были достигнуты в 80-е годы, начиная с метода квадратичного просеивания Карла Померанса (Carl Pomerance), разработанного им в 1981 году [см. Lecture Notes in Сотр. Sci. 209 (1985), 169-182]. Затем Хендрик Ленстра (Hendrik Lenstra) разработал метод эллиптических кривых [AnnaJs of Math. 126 (1987), 649-673]. Он эвристически предположил, что для нахождения простого множителя р необходимо выполнить около ехр(-(2 -Ь е)(Inр)(In Inр)) операций умножения. Эта величина - не что иное, как асимптотический квадратный корень из оценки времени вьшолне-ния алгоритма Е, когда р « VN, и она становится даже лучше, если число N имеет относительно малые простые множители. Прекрасное описание этого метода дано Джозефом X. Силверманом (Joseph Н. Silverman) и Джоном Тейтом (John Tate) в RationaJ Points on Elliptic Curves (New York: Springer, 1992), Chapter 4.

В 1988 году к решению этой задачи вернулся Джон Поллард. Он предложил новый подход, который стал позже известен как решето числового поля. С рядом работ, посвященных этому методу, который является в настоящее время чемпионом по разложению на простые множители чрезвычайно больших чисел, можно ознакомиться в Lecture Notes in Math. 1554 (1993). При использовании этого метода прогнозируемый порядок времени вьшолнения равен

ехр ((64/9 + еу/ (In Nf/ (In In ЛО/) (25)

при N -+ оо. Согласно анализу, выполненному А. К. Ленстрой (А. К. Lenstra), порогом, после которого хорошо настроенный метод решета числового поля начинает превосходить хорошо настроенный метод квадратичного просеивания, является число N « 10".

Подробности этих методов выходят за рамки данной книги, но представление об их эффективности можно получить, обратив внимание на некоторые уже известные случаи неудачных попыток разложения на простые множители чисел Ферма вида 22 + 1. Например, разложение 2512 2424833-

745 560 282 564 788 4208 337 395 736 200 454 918 783 366 342 657 - рээ

было получено при помощи метода решета числового поля после вычислений в течение четырех месяцев, что заняло все свободное время почти 700 рабочих станций [Lenstra, Manasse, Pollard, Math. Сотр. 61 (1993), 319-349; 64 (1995), 1357]; здесь pgg обозначает 99-разрядное простое число. Следующее число Ферма было в два раза длиннее предыдущего, но при помощи метода эллиптических кривых 20 октября 1995 года был получен результат:

2 °* + 1 = 45 592 577 - 6487 031 809 -

4 659 775 785 220018 543 264 560 743 076 778192 897 - pasa -

[Richard Brent, Math. Сотр. 68 (1999), 429-451.] На самом деле Брент уже применял метод эллиптических кривых в 1988 году для решения следующей задачи: 22 048 319489-974849-

167 988 556 341760 475.137 3 560 841906 445 833 920 513 - р5б4-

Все простые множители, кроме одного, оказались, хотя и с некоторой долей везения, меньшими < Ю. так что метод эллиптических кривых стал победителем.

А как насчет числа 2*°® + 1? К настояш;ему моменту эта задача кажется слишком сложной для решения. Данное число содержит пять множителей < 10®, но остаток, который не удается разложить на множители, содержит 1187 десятичных разрядов. Еще один случай: число 2* + j содержит четыре известных множителя < 10 и очень большой неразложенный остаток. [Crandall, Fagin, Math. Сотр. 62 (1994), 321; Brent, Crandall, Dilcher, van Halewyn, 68 (1999), 429-451.]

Секретные множители. Всеобщий интерес к проблеме разложения на простые множители резко возрос в 1977 году, когда Р. Л. Ривест (R. L. Rivest), А. Шамир (А. Shamir) и Л. Эдлеман (L. Adleman) нашли способ кодирования сообщений, которые могут быть декодированы в явном виде только по известным множителям, на которые разлагается большое число N, даже в том случае, когда метод кодирования известен всем и каждому. Так как большинство величайших математиков мира не могут до сих пор найти эффективный метод разложения чисел на простые множители, этот метод [САСМ 21 (1978), 120-126] позволяет почти гарантированно защитить засекреченные данные и сообщения в компьютерной сети.

Представим себе маленькое электронное устройство (назовем его RSA-блоком), в памяти которого хранятся два больших простых числа ряд. Будем считать, что числа р-1ид - 1не делятся на 3. RSA-блок, подсоединенный каким-то образом к компьютеру, передал последнему произведение N = pq, поэтому ни один человек не может обнаружить значения чисел р и q, не разложив число N на простые множители. При попытке взлома RSA-блок запрограммирован на самоуничтожение. Другими словами, блок сотрет информацию в своей памяти, если будет предпринята попытка доступа к нему или он подвергнется воздействию внешнего излучения, которое может изменить или считать данные, хранящиеся в памяти. Кроме того, RSA-блок достаточно надежен с точки зрения эксплуатации; в случае его выхода из строя вследствие неполадок в системе питания или износа нужно выбросить имеющееся устройство и купить новое. Простые множители р ч q генерируются самим RSA-блоком с помощью схемы, основанной на явлениях, которые случайны по самой своей природе (например, космические лучи). Важным является тот факт, что никто не знает простых чисел ри q, даже то лицо (или организация), которому принадлежит устройство или которое имеет доступ к нему. Не может быть и речи о подкупе, шантаже или. захвате заложников с целью получения информации о простых числах числа N.

Чтобы отослать секретное сообщение владельцу RSA-блока, для которого произведение двух чисел равно N, нужно преобразовать сообщение в последовательность чисел (xi,... ,Xk), в которой каждое из чисел xi принимает значения в интервале между О и iV, а затем передать числа

{xf mod N, xl mod N).

RSA-блок, зная ри q, может декодировать сообщение, поскольку в нем уже имеется вычисленное заранее число d < N, такое, что 3d = 1 (по модулю (р - l){q - 1)). Теперь RSA-блок может, используя рассмотренный в разделе 4.6.3 метод, за приемлемое время вычислить (хУ mod N = х. Естественно, RSA-блок хранит это