Введение в криптографию
[an error occurred while processing this directive]

Как раскладывают составные числа на множители - часть 3


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

Задав некоторую границу , для каждого простого числа , входящего в базу множителей, и каждого показателя степени , с условием находим решения квадратичного сравнения

. Множество решений обозначим буквой . Итак, для каждого найдется элемент базы множителей, а может быть и не один, входящий в некоторой степени в разложение на простые сомножители числа . Те числа , при которых значения оказываются полностью разложенными, дают нам вектор показателей, как и в алгоритме непрерывных дробей. Если таких векторов окажется достаточно много, с ними можно проделать те же операции, что и в алгоритме непрерывных дробей.

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

(21)

В нем допускается наличие двух дополнительных больших простых множителей исключаются.

Некоторые детали реализации алгоритма можно найти в работе []. Отметим здесь только, что на множители раскладывалось число , база множителей состояла из и 524338 простых чисел, меньших, чем . При этом было использовано . В результате просеивания получилось 112011 соотношений вида () без множителей , 1431337 соотношений с одним таким множителем и 6881138 соотношений с двумя множителями. Именно на поиск всех этих соотношений понадобились 220 дней и большое количество работавших параллельно компьютеров. На втором шаге алгоритма, когда из соотношений () комбинировались четные векторы показателей степеней, приходилось работать с матрицами, размеры которых измерялись сотнями тысяч битов. Этот второй шаг потребовал 45 часов работы. Уже четвертый вектор с четными показателями привел к искомому разложению на множители.

Next: 4.8. Дискретное логарифмирование

Up: 4. Алгоритмические проблемы теории

Previous: 4.6. Как проверить большое

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]