Эти вычисления проводятся до тех пор. пока не будет построено s + 2 вектора показателей. В получившейся матрице показателей, очевидно, можно подобрать вектора-строки так. что их сумма будет вектором с чётными координатами 2(Ьо. Ь\,.. .bs). Если А - множество номеров векторов, вошедших в эту сумму, то. как легко проверить с помошью (19). имеет место сравнение

Если с помошью этого сравнения не удаётся разложить N на множители, разложение в непрерывную дробь продолжается, продолжается набор векторов показателей и т. д.

можно раскладывать в непрерывную дробь число \/kN. где маленький множитель к подбирается так. чтобы в базу множителей вошли все малые простые; была предложена так называемая стратегия раннего обрыва и т. д. Сложность этого алгоритма была оценена в 1982 г. величиной 0(ехр(д/1.5 • In N lnln А)). При выводе этой оценки использовался ряд правдоподобных, но не доказанных гипотез о распределении простых чисел. Получившаяся в опенке функция растет медленнее любой степенной функции. Алгоритмы, сложность которых оценивается подобным образом, получили название субэкспоненциальных (в зависимости от In А).

В 1982 г. Померанном был предложен ешё один субэкспоненпиаль-ный алгоритм - алгоритм квадратичного решета. Его сложность оценивается такой же функцией, как и в методе непрерывных дробей, но

Q(x) = (х + то)2 - N и выберем ту же базу множителей, что и в методе непрерывных дробей. При малых целых значениях х величина Q(x) будет сравнительно невелика. Следующий шаг объясняет название алгоритма - квадратичное решето. Вместо того, чтобы перебирать числа х и раскладывать соответствующие значения Q(x) на множители, алгоритм сразу отсеивает негодные значения х, оставляя лишь те. для которых Q(x) имеет делители среди элементов базы множителей.

Задав некоторую границу В, для каждого простого числа р. входящего в базу множителей, и каждого показателя степени а. с условием ра В находим решения х квадратичного сравнения Q(x) = 0 (mod ра). Множество решений обозначим буквой А. Итак, для каждого х 6 А найдётся элемент базы множителей, а может быть и не один, входяший в некоторой степени в разложение на простые сомножители числа Q(x). Те числа

В этот алгоритм был внесен ряд усовершенствований: вместо

вместо константы

х. при которых значения Q(x) оказываются полностью разложенными, дают нам вектор показателей, как и в алгоритме непрерывных дробей. Если таких векторов окажется достаточно много, с ними можно проделать те же операции, что и в алгоритме непрерывных дробей.

Мы кратко описали здесь лишь основную идею алгоритма. Помимо этого, используется много других дополнительных соображений и различных технических приемов. Например, аналог соотношения (20) имеет вид

В нем допускается наличие двух дополнительных больших простых множителей В\ < qi < Е?2- Эти множители впоследствии при перемножении значений Q(x) исключаются.

Некоторые детали реализации алгоритма можно найти в работе [6]. Отметим здесь только, что на множители раскладывалось число 5N. база множителей состояла из -1 и 524338 простых чисел, меньших, чем В\ = 16333609. При этом было использовано В2 = 230. В результате просеивания получилось 112011 соотношений вида (21) без множителей qi. 1431337 соотношений с одним таким множителем и 6881138 соотношений с двумя множителями. Именно на поиск всех этих соотношений понадобились 220 дней и большое количество работавших параллельно компьютеров. На втором шаге алгоритма, когда из соотношений (21) комбинировались чётные векторы показателей степеней, приходилось работать с матрицами, размеры которых измерялись сотнями тысяч битов. Этот второй шаг потребовал 45 часов работы. Уже четвёртый вектор с чётными показателями привёл к искомому разложению на множители.

Мы затронули в этой статье лишь небольшую часть вопросов, связанных с теоретико-числовыми алгоритмами и опенками их сложности. За рамками остались даже чрезвычайно важные для криптографии вопросы дискретного логарифмирования, т. е. поиска чисел х. удовлетворяюших сравнению а = Ьх (mod р) при заданных целых а. Ь. р. см. например. [20. 21]. Мы не описывали перспективные исследования, связанные с распространением алгоритмов решета на поля алгебраических чисел (решето числового поля), и использование их для разложения целых чисел на множители или решения задачи дискретного логарифмирования, см. [22. 20. 25]. Именно с помошью этих алгоритмов достигнуты теоретические

Заключение

опенки сложности разложения на множители exp(c(ln A)1/,3(lnln TV)2/3). Не были затронуты эллиптические кривые, т. е. определённые с точностью до обратимого множителя пропорциональности множества точек

Еа,ь = {(ж. у, z) £ (Z/mZ)3y22 = ж3 + axz2 + bz3}.

обладающие групповой структурой. С их помощью удалось построить весьма эффективные алгоритмы разложения чисел на множители и проверки целых чисел на простоту. В отличие от мультипликативной группы (Z/mZ)*. порядок группы Еа.ь при одном и том же m меняется в зависимости от целых параметров а, Ь. Это оказывается весьма существенным, например, при разложении чисел m на множители. Мы отсылаем читателей за подробностями использования эллиптических кривых к статье [23].

[5: [6:

[т: [§:

СПИСОК ЛИТЕРАТУРЫ

Ященко В. В. Основные понятия криптографии Математическое просвещение. Сер. 3. №2. 1998. С. 53-70.

Rivest R. L.. Shamir A.. Adleman L. A method for obtaining digital signatures and public key cryptosystems Commun. ACM. V.21. No 2. 1978. P. 120-126.

Gardner M. A new kind of cipher that would take millions of years to break Sci. Amer. 1977. P. 120-124.

Виноградов И. M. Основы теории чисел. М.: Наука. 1972.

Карацуба А. А. Основы аналитической теории чисел. М.: Наука. 1983 г.

Atkins D.. Graff М.. Lenstra А. К. and Leyland Р. С. The magic words are squeamish ossifrage ASIACRYPT-94. Lect. Notes in Comput. Sci. V. 917. Springer. 1995.

Кнут Д. Искусство программирования на ЭВМ. Т.2: Получисленные алгоритмы. М.: Мир. 1977.

Ахо А., Хопкрофт Дж.. Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. 1979.

Варновский Н. П. Криптография и теория сложности Математическое просвещение. Сер. 3. №2. 1998. С. 71-86.

Williams Н. С. Primality testing on a computer Ars Combin.. 5. 1978. P. 127-185. (Русский перевод: Кибернетический сборник, вып. 23. 1986. С. 51-99.)