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

Метод квадратичного решета (Quadratic sieve algorithm, сокр. QS) — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше $\sqrt{n}$ (для чисел $n$, имеющих простые делители, много меньшие $\sqrt{n}$ более быстрым является метод факторизации на эллиптических кривых). Метод квадратичного решета представляет собой разновидность метода факторных баз (обобщение метода факторизации Ферма). Этот метод считается вторым по быстроте (после общего метода решета числового поля). И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.^[1]

Основные цели

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

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

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

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

$O(exp(\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 имеет только небольшие простые множители (такие числа называются гладкими числами). Их сложнее найти, но использование таких чисел позволяет избежать больших векторов и матриц.

Основная идея метода

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

Как метод квадратичного решета оптимизирует поиск равных квадратов

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

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

$y(x)=\left(\left\lceil\sqrt{n}\right\rceil+x\right)^2-n\hbox{ (where }x\hbox{ is a small integer)}$

$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 является квадратичным вычетом для этих простых чисел). Эти числа будут базисом для квадратичного решета.

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

$\begin{align}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{align}$

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

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

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

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

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

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

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

$\begin{align} 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{align}$

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

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

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

X + 124	Y	factors
124	29	20 • 170 • 230 • 291
127	782	21 • 171 • 231 • 290
195	22678	21 • 171 • 231 • 291

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

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

$\begin{align} 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{align}$

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

$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}$

Ее решение:

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

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

$29 \cdot 782 \cdot 22678 = 22678^2$

и

$124^2 \cdot 127^2 \cdot 195^2 = 3070860^2$

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

$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. — P. 180-182.
• Gerver J.L. Factoring large numbers with a quadratic sieve. — Math. Comp., 1983. — Vol. 41. — P. 287-294.

Примечания

1. ↑ Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.
2. ↑ Pomerance, Carl. A Tale of Two Sieves (December 1996), стр. 1473–1485.

• 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.

Ссылки

• Reference paper from University of Illinois at Urbana-Champaign