Введение

Алгоритм целочисленной факторизации
Алгоритм квадратного сита (QS) — это алгоритм целочисленной факторизации и, на практике, второй по скорости известный метод (после общего сита числового поля). Он по-прежнему является самым быстрым для целых чисел, содержащих менее 100 десятичных цифр, и значительно проще, чем сито числового поля. Это алгоритм факторизации общего назначения, то есть время его работы зависит исключительно от размера целого числа, подлежащего факторизации, а не от его специальной структуры или свойств. Он был изобретен Карлом Померансом в 1981 году как усовершенствование линейного сита Шроеппеля.

Основная цель

Алгоритм пытается установить конгруэнтность квадратов по модулю n (целое число, подлежащее разложению на множители), что часто приводит к факторизации n. Алгоритм работает в две фазы: фаза сбора данных, на которой собирается информация, которая может привести к конгруэнтности квадратов; и фаза обработки данных, на которой все собранные данные помещаются в матрицу и решаются для получения конгруэнтности квадратов. Фаза сбора данных может быть легко распараллелена на множество процессоров, но фаза обработки данных требует большого объема памяти и ее сложно эффективно распараллелить на множество узлов или если узлы обработки не имеют достаточного объема памяти для хранения всей матрицы. Алгоритм блочного Видемана может быть использован в случае нескольких систем, каждая из которых способна хранить матрицу. Наивный подход к поиску конгруэнтности квадратов заключается в выборе случайного числа, возведении его в квадрат, делении на n и надежде, что наименьший неотрицательный остаток является полным квадратом. Например, этот подход редко находит конгруэнтность квадратов для больших n, но когда находит, конгруэнтность чаще всего нетривиальна и факторизация завершена. Это примерно лежит в основе метода факторизации Ферма. Квадратичное решето является модификацией метода факторизации Диксона. Общее время работы, необходимое для квадратичного решета (для факторизации целого числа n), выражается в L-нотации. Константа e – основание натурального логарифма.

Как QS оптимизирует поиск совпадений

Квадратное сито пытается найти пары целых чисел x и y(x) (где y(x) – функция от x), удовлетворяющие гораздо более слабому условию, чем x² ≡ y² (mod n). Оно выбирает множество простых чисел, называемое основой делителей, и пытается найти x таким образом, чтобы наименьший абсолютный остаток y(x) = x² mod n полностью разлагался на простые множители из основы делителей. Такие значения y говорят, что они гладкие относительно основы делителей. Разложение на множители значения y(x), которое разлагается на простые множители из основы делителей, вместе со значением x, называется отношением. Квадратное сито ускоряет процесс поиска отношений, выбирая x близким к квадратному корню из n. Это гарантирует, что y(x) будет меньше, и, следовательно, имеет больше шансов быть гладким. Это означает, что y имеет порядок 2x[]. Однако это также подразумевает, что y растет линейно с x, умноженным на квадратный корень из n. Другой способ увеличить вероятность гладкости – просто увеличить размер основы делителей. Однако необходимо найти как минимум одно гладкое отношение больше, чем количество простых чисел в основе делителей, чтобы обеспечить существование линейной зависимости.

Проверка гладкости путем просеивания

Есть несколько способов проверить гладкость чисел y. Наиболее очевидный – пробное деление, хотя это увеличивает время работы фазы сбора данных. Другим методом, получившим определенное признание, является метод эллиптических кривых (ECM). На практике обычно используется процесс, называемый просеиванием. Если f(x) – это полином, то у нас есть

Таким образом, решение уравнения f(x) ≡ 0 (mod p) для x генерирует целую последовательность чисел y, для которых y = f(x), и все они делятся на p. Это эквивалентно нахождению квадратного корня по модулю простого числа, для чего существуют эффективные алгоритмы, такие как алгоритм Шенкса — Тоннелли. (Отсюда и название «квадратичное сито»: y является квадратичным полиномом от x, а процесс просеивания работает аналогично решету Эратосфена.) Просеивание начинается с установки каждой ячейки в большом массиве байтов A[] в ноль. Для каждого p решаем квадратное уравнение по модулю p, чтобы получить два корня α и β, а затем добавляем приближение к log(p) к каждой ячейке, для которой y(x) ≡ 0 (mod p), то есть к A[kp + α] и A[kp + β]. Также необходимо решать квадратное уравнение по модулю малых степеней p, чтобы распознавать числа, делящиеся на малые степени простых чисел из фактор-базы. В конце работы с фактор-базой любое A[], содержащее значение выше порога, приблизительно равного log(x² − n), будет соответствовать значению y(x), которое раскладывается на множители из фактор-базы. Информация о том, какие именно простые числа делят y(x), теряется, но оно имеет только малые множители, и существует множество хороших алгоритмов для факторизации числа, известных только малыми множителями, таких как пробное деление на малые простые числа, SQUFOF, Pollard rho и ECM, которые обычно используются в некоторой комбинации. Существует множество значений y(x), которые подходят, поэтому процесс факторизации в конце не обязательно должен быть полностью надежным; часто процессы дают сбой, скажем, на 5% входных данных, требуя небольшого дополнительного просеивания.

Пример базового сита

Этот пример продемонстрирует стандартное квадратное сито без оптимизаций по логарифмам или степеням простых чисел. Пусть число, которое необходимо разложить на множители, N = 15347, следовательно, целая часть от квадратного корня из N равна 124. Поскольку N невелико, достаточно базового многочлена: y(x) = (x + 124)² − 15347.

Многочленные полиномы

На практике для y используется множество различных многочленов, поскольку обычно один многочлен не обеспечивает достаточное количество пар (x, y), гладких относительно факторного базиса. Используемые многочлены должны иметь специальную форму, так как они должны быть полными квадратами по модулю n. Все многочлены должны иметь форму, аналогичную исходному y(x) = x² − n:

Предполагая, что является кратным A, многочлен y(x) можно записать как. Если A является полным квадратом, то необходимо учитывать только фактор. Этот подход (называемый MPQS, Multiple Polynomial Quadratic Sieve – метод решета многочленных квадратичных форм) идеально подходит для параллелизации, поскольку каждому процессору, участвующему в факторизации, можно предоставить n, факторный базис и набор многочленов, и ему не потребуется общаться с центральным процессором до завершения работы с этими многочленами.

Один большой простый

Если после деления на все факторы, меньшие A, оставшаяся часть числа (кофактор) меньше A², то этот кофактор должен быть простым. Фактически, его можно добавить в факторную базу, сортируя список соотношений по возрастанию кофактора. Если y(a) = 7*11*23*137 и y(b) = 3*5*7*137, то y(a)y(b) = 3*5*11*23 * 7² * 137². Это работает за счет снижения порога элементов в решете, выше которого выполняется полная факторизация.

Более крупные простые числа

Еще больше снижая порог и используя эффективный метод разложения значений y(x) на произведения, состоящие даже из относительно больших простых чисел, ECM для этого прекрасно подходит. Он может находить соотношения, в которых большинство множителей содержатся в фактор-базе, но при этом присутствуют два или даже три больших простых числа. Затем поиск циклов позволяет объединить набор соотношений, имеющих несколько общих простых множителей, в одно соотношение.

Записи факторинга

До открытия сита числового поля (NFS), QS был асимптотически самым быстрым известным универсальным алгоритмом факторизации. В настоящее время, факторизация эллиптическими кривыми Ленстры имеет такое же асимптотическое время работы, как QS (в случае, когда n имеет ровно два простых множителя одинакового размера), но на практике QS оказывается быстрее, поскольку использует операции одинарной точности вместо операций произвольной точности, применяемых в методе эллиптических кривых. 2 апреля 1994 года факторизация RSA-129 была завершена с использованием QS. Это было 129-значное число, являющееся произведением двух больших простых чисел: одного из 64 цифр и другого из 65 цифр. Фактор-база для этой факторизации содержала 524 339 простых чисел. Фаза сбора данных заняла 5000 MIPS-лет и выполнялась распределённо через Интернет. Общий объём собранных данных составил 2 ГБ. Фаза обработки данных заняла 45 часов на суперкомпьютере MasPar (массивно-параллельном) компании Bellcore (ныне Telcordia Technologies). Это была самая крупная опубликованная факторизация, выполненная универсальным алгоритмом, до тех пор, пока NFS не был использован для факторизации RSA-130, завершённой 10 апреля 1996 года. Все числа RSA, факторизованные после этого, были факторизованы с использованием NFS. Текущий рекорд факторизации QS – это 140-значное (463-битное) RSA-140, которое было факторизовано Патриком Консором в июне 2020 года, потребовав около 6000 процессорных часов в течение 6 дней.