Метод квадратичного решета

Алгоритм пытается найти такие квадраты чисел, которые равны по модулю ${\displaystyle n}$ (факторизуемое число), что часто приводит к факторизации ${\displaystyle n}$ . Алгоритм работает в два этапа: этап сбора данных, где он собирает информацию, которая может привести к равенству квадратов; и этап обработки данных, где он помещает всю собранную информацию в матрицу и обрабатывает её для получения равенства квадратов. Первый этап может быть легко распараллелен на много процессов, но второй этап требует большие объемы памяти и его трудно распараллелить.

Один из простых методов отыскания равных квадратов заключается в том, чтобы выбрать случайное число, возвести его в квадрат и надеяться, что остаток от деления на ${\displaystyle n}$ является квадратом какого-либо другого числа. Например, ${\displaystyle 80^{2}{\pmod {5959}}=441=21^{2}}$ . Этот способ находит равные квадраты лишь в редких случаях для больших ${\displaystyle n}$ , но если он действительно найдет эти числа, то можно считать, что факторизация завершена. Этот метод похож на метод факторизации Ферма.

Метод квадратичного решета является модификацией метода разложения на множители Диксона.

Продолжительность расчёта для квадратичного решета (${\displaystyle n}$ - факторизуемое число):

${\displaystyle O(exp((1+o(1)){\sqrt {\log n\log \log n}}))}$ .^[2]

Пусть x mod y обозначает остаток от деления x на y. В методе факторизации Ферма в отдельностиподбираем число a, чтобы a² mod n являлось квадратом. Но такое число подобратьтяжело. В квадратичном решете мы вычисляем a² mod n для некоторых a, и затемнаходим такое подмножество, произведение элементов которого является квадратом. Этоприведёт к сравнению квадратов.

Например, 41² mod 1649 = 32, 42² mod 1649 = 115, и 43² mod 1649 = 200. Ни один изполученных результатов не является квадратом, но результат произведения (32)(200) = 6400 = 80². С другой стороны, рассмотрев предыдущее произведение по mod 1649, мыполучим, что (32)(200) = (41²)(43²) = ((41)(43))². Так как (41)∙(43) mod 1649 = 114, мыимеем сравнение квадратов: 114² ≡ 80² (mod 1649).

Но как мы решаем проблему, фиксируя множество чисел и, находя подмножество,произведение элементов, которого является квадратом?Начнём с понятия вектор показателей степеней. Например, у нас есть число 504. Егоразложение на простые множители имеет следующий вид 504 = 2³3²5⁰7¹. Мы могли быпредставить это разложение в виде вектора показателей степеней (3,2,0,1), которыйфиксирует степени простых чисел 2, 3, 5 и 7, участвующих в разложении. Число 490 поаналогии имело бы вектор (1,0,1,2). Умножение чисел - это то же самое, что ипоэлементное сложение их векторов показателей степеней, то есть произведение 504 ∙490 имеет вектор (4,2,1,3).

Теперь, обратите внимание, что число является квадратом, если каждый элемент вего векторе показателей степеней чётный. К примеру, при сложении векторов (3,0,0,1) и(1,2,0,1) получаем (4,2,0,2). Это говорит нам о том, что произведение чисел 56 ∙ 126является квадратом. На самом деле, мы не заботимся о точных значениях, получаемых ввекторе, до тех пор, пока каждый элемент в результирующем векторе чётный. По этойпричине мы берём каждый элемент по mod 2 и выполняем сложение элементов по mod 2:(1,0,0,1) + (1,0,0,1) = (0,0,0,0).

Таким образом, наша задача приняла следующий вид: задано множество векторов (0,1),найти такое подмножество, которое дополняется до нулевого вектора, при использованиисложения по mod 2. Это задача линейной алгебры, то есть необходимо найти линейнозависимые вектора. Из теоремы линейной алгебры следует, что, до тех пор, покаколичество векторов больше, чем количество элементов в каждом векторе, такаязависимость должна существовать. Мы можем эффективно находить линейно зависимыевекторы, например, поместив исходные векторы, в качестве столбцов матрицы и затем,использовать метод Гаусса, который легко приспособить для работы с целыми числами поmod 2. Как только мы найдём линейно зависимые векторы, мы просто перемножаемчисла, соответствующие этим векторам и получаем квадрат, который ищем.

Однако, возведение в квадрат множества случайныхчисел по mod n приводит к большому числу различных простых множителей,длиннымвекторам и большой матрице. Чтобы избавиться от этой проблемы, мы специальноищем числа, такие, что a² mod n имеет только небольшие простые множители (такиечисла называются гладкими числами). Их сложнее найти, но использование такихчисел позволяет избежать больших векторов и матриц.

В качестве факторной базы ${\displaystyle B}$ берется множество простых чисел, состоящее из ${\displaystyle p=2}$ и всех таких нечетных простых чисел ${\displaystyle p}$ , не превосходящих заданной границы ${\displaystyle P}$ (которая выбирается из соображений оптимальности), что ${\displaystyle n}$  — квадратичный вычет по модулю ${\displaystyle p}$ .

Множество ${\displaystyle S}$ целых чисел, в котором ищутся ${\displaystyle B}$ -числа (${\displaystyle B}$ -число — целое число, делящееся только на простые числа из ${\displaystyle B}$ ) выглядит следующим образом:

${\displaystyle S=\left\{t^{2}-n|[{\sqrt {n}}]+1\leq t\leq [{\sqrt {n}}]+A\right\}}$

Далее, вместо того, чтобы брать одно за другим ${\displaystyle s\in S}$ , и делить его на простые числа из ${\displaystyle B}$ , берутся одно за другим каждое ${\displaystyle p\in B}$ и проверяется делимость на ${\displaystyle p}$ (и его степени) одновременно для всех ${\displaystyle s\in S}$ . Для построения списка всех простых ${\displaystyle p}$ , не превосходящих ${\displaystyle A}$ , можно использовать решето Эратосфена.

1. Выбираются границы ${\displaystyle P}$ и ${\displaystyle A}$ порядка величины ${\displaystyle e^{\sqrt {\log {n}\log {\log {n}}}}}$ (далее обозначается как ${\displaystyle L(n)}$ ), такие что ${\displaystyle P<A<P^{2}}$ .

2. Для ${\displaystyle t=[{\sqrt {n}}]+1}$ , ${\displaystyle \left[{\sqrt {n}}\right]+2}$ ,…, ${\displaystyle \left[{\sqrt {n}}\right]+A}$ по порядку в столбец выписываются целые числа ${\displaystyle t^{2}-n}$ .

3. Для каждого нечетного простого числа ${\displaystyle p\leq P}$ вычисляется символ Лежандра - проверяется условие ${\displaystyle \left({n \over p}\right)=1}$ . Если оно не выполняется, ${\displaystyle p}$ удаляется из факторной базы.

4. Предполагая, что ${\displaystyle p}$  — такое нечетное простое число, что ${\displaystyle n}$  — квадратичный вычет по модулю ${\displaystyle p}$ , решается уравнение ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta }}}}$ для ${\displaystyle \beta =}$ 1,2,… . Значения ${\displaystyle \beta }$ берутся в порядке возрастания пока не окажется, что уравнение не имеет решений ${\displaystyle t}$ , сравнимых по модулю ${\displaystyle p^{\beta }}$ с каким-либо из чисел в области ${\displaystyle \left[{\sqrt {n}}\right]+1\leq t\leq \left[{\sqrt {n}}\right]+A}$ .

Пусть ${\displaystyle \beta }$  — наибольшее из таких чисел, для которых в указанной области найдется число ${\displaystyle t}$ со свойством ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta }}}}$ .

Пусть ${\displaystyle t_{1}}$ и ${\displaystyle t_{2}}$ решения ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta }}}}$ и ${\displaystyle t_{2}\equiv -t_{1}{\pmod {p^{\beta }}}}$ .

5. При том же значении ${\displaystyle p}$ просматривается список значений ${\displaystyle t^{2}-n}$ , полученный в п.2. В столбце, соответствующем ${\displaystyle p}$ , ставится 1 против всех значений ${\displaystyle t^{2}-n}$ , для которых ${\displaystyle t}$ отличается от ${\displaystyle t_{1}}$ на некоторое кратное ${\displaystyle p}$ . После этого 1 заменяется на 2 для всех таких значений ${\displaystyle t^{2}-n}$ , что ${\displaystyle t}$ отличается от ${\displaystyle t_{1}}$ на кратное ${\displaystyle p^{2}}$ и т. д. до ${\displaystyle \beta }$ . Затем то же самое проделывается с ${\displaystyle t_{2}}$ вместо ${\displaystyle t_{1}}$ . Наибольшее возможное число в столбце — ${\displaystyle \beta }$ .

6. При добавлении очередной единицы к числу в столбце в п.5, соответствующее число ${\displaystyle t^{2}-n}$ делится на ${\displaystyle p}$ и полученный результат сохраняется.

7. В столбце под ${\displaystyle p=2}$ при ${\displaystyle n\neq 1{\pmod {8}}}$ просто ставится 1 против ${\displaystyle t^{2}-n}$ с нечетным ${\displaystyle t}$ и соответствующее ${\displaystyle t^{2}-n}$ делится на 2. При ${\displaystyle n\equiv 1{\pmod {8}}}$ решается уравнение ${\displaystyle t^{2}=n{\pmod {2^{\beta }}}}$ и решение продолжается в том же ключе, как при нечетном ${\displaystyle p}$ .

8. Когда все указанные действия будут проведены для всех простых чисел, не превосходящих ${\displaystyle P}$ , следует отбросить все числа ${\displaystyle t^{2}-n}$ , кроме обратившихся в 1 после деления на все степени ${\displaystyle p}$ , не превосходящих ${\displaystyle P}$ . В итоге получится таблица, в которой в ${\displaystyle b_{i}}$ столбце будут содержаться все такие значения ${\displaystyle t}$ из интервала ${\displaystyle \left[{\left[{\sqrt {n}}\right]+1,\left[{\sqrt {n}}\right]+A}\right]}$ , что ${\displaystyle t^{2}-n}$ есть ${\displaystyle B}$ -число, а остальные столбцы будут соответствовать тем значениям ${\displaystyle p\leq P}$ , для которых ${\displaystyle n}$  — квадратичный вычет.

9. Далее используется обобщенный метод факторизации Ферма (метод факторных баз).

Метод квадратичного решета пытается найти пары целых чисел x и y(x) (где y(x) - функция от x) удовлетворяющих гораздо более слабым условием чем x² ≡ y² (mod n). Он выбирает множество простых чисел называемых факторной базой, и пытается найти x такой, что самый маленький остаток y(x) = x² mod n раскладывается на множители факторной базы. Такие y называются гладкими по отношению к факторной базе.

Факторизацией значения y(x) над факторной базой вместе со значением x называется зависимостью. Квадратическое решето ускоряет процесс поиска зависимостей путём выбора x близко к квадратному корню из n. Это гарантирует что число y(x) будет меньше, и поэтому имеет больше шансов быть гладким.

${\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (где }}x{\hbox{ --- небольшое целое)}}}$

${\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }$

Другой способ увеличения вероятности быть гладким числом заключается в увеличении размера факторной базы. Однако, тогда необходимо найти по крайней мере на одну гладкую связь больше чем количество простых чисел в базе, чтобы гарантировать существование линейной зависимости.

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

Сбор данных

Так как N мало, то необходимо только 4 простых числа. Первые 4 простых числа p для которых у 15347 есть квадратный корень по модулю p, равны 2, 17, 23, и 29 (Другими словами, 15347 является квадратичным вычетом для этих простых чисел). Эти числа будут базисом для квадратичного решета.

Сейчас мы строим наше решето ${\displaystyle V_{X}}$ из ${\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}$ и начнем с просеивания процесса для каждого простого числа в базисе, выбирая для просеивания первые Y(X) 0 ≤ X < 100 :

${\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}$

Следующим шагом является выполнение просеивания. Для каждого р в нашей факторной базе ${\displaystyle \lbrace 2,17,23,29\rbrace }$ решаем уравнение

${\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}$

чтобы найти записи в массиве V которые делятся на p.

Для ${\displaystyle p=2}$ решаем ${\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}$ чтобы получить решение ${\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}$ .

Таким образом, начиная с X=1 с шагом 2, каждая запись будет делиться на 2. Деление каждой из записей на 2 дает

${\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}$

Аналогично для оставшихся простых чисел p в ${\displaystyle \lbrace 17,23,29\rbrace }$ равенство${\displaystyle X\equiv {\sqrt {15347}}-124{\pmod {p}}}$ решено. Обратите внимание, что для каждого p > 2 будет 2 результирующих линейных уравнения, из-за наличия двух квадратных корней по модулю.

${\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}$

Каждое равенство ${\displaystyle X\equiv a{\pmod {p}}}$ приводит к тому, что ${\displaystyle V_{x}}$ делится на p при x=a, a+p, a+2p, и т.д.. Делением V на p в a, a+p, a+2p, a+3p, и т.д., для каждого простого числа в базисе находим гладкие числа.

${\displaystyle V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}$

Элемент из V который равен 1 соответствует гладкому числу. Так как ${\displaystyle V_{0}}$ , ${\displaystyle V_{3}}$ , и ${\displaystyle V_{71}}$ раняются 1, то:

Обработка матрицы

Рассмотрим равенства:

${\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}$

и выпишем показатели простых чисел в виде матрицы и решим систему ${\displaystyle {\pmod {2}}}$ :

${\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}$

Её решение:

${\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}$

Таким образом, произведение всех 3-х уравнений есть квадрат (mod N).

${\displaystyle 29\cdot 782\cdot 22678=22678^{2}}$

и

${\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}$

алгоритм находит

${\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}$

Теперь вычисляем GCD(3070860 - 22678, 15347) = 103, нетривиальный делитель 15347, другим является 149.

До открытия общего метода решета числового поля (NFS) QS был известен как самый быстрый алгоритм факторизации общего назначения. Сейчас у алгоритма факторизации с помощью эллиптических кривых такое же время выполнения, как и в QS (в случае, когда n есть произведение только двух простых чисел), но на практике QS быстрее, т.к. он использует операции одинарной точности вместо операций длинной арифметики, которые используются в методе эллиптических кривых.

2 апреля 1994 года была произведена факторизация RSA-129 методом QS. Это было число длины 129, результат произведения двух простых чисел, одного длиной 64 и другого длиной 65. При этом факторная база состояла из 524339 простых чисел. Этап сбора данных произвел 5000 MIPS. Собранная информация занимала 2GB. Этап обработки матрицы занял 45 часов на Bellcore^[англ.]-овском (сейчас Telcordia Technologies^[англ.]) суперкомпьютере MasPar. Это было самое большое число, которое в то время могли факторизовать алгоритмом общего назначения. Только 10 апреля 1996 года смогли факторизовать число длины 130 RSA методом NFS.

• Koblitz N.A. Course in number theory and cryptography (неопр.). — Springer-Verlag, 1987. — С. 180—182.
• Gerver J.L. Factoring large numbers with a quadratic sieve (англ.). — Math. Comp., 1983. — Vol. 41. — P. 287—294.

• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (англ.). — 1st. — Springer, 2001. — ISBN 0-387-94777-9. Section 6.1: The quadratic sieve factorization method, pp. 227–244.