Квадратичне решето

Квадратичне решето (англ. quadratic sieve, QS) — алгоритм факторизації цілих чисел, на практиці найшвидший для чисел до 10¹⁰⁰. Асипмтотично є другим за швидкістю після загального решета цифрового поля, і значно простіший за нього. Це метод факторизації загального призначення, тобто, час його виконання залежить лише від розміру цілого числа на вході, і не залежить від його вигляду (на відміну від ^[en]). Метод винайшов математик ^[en] 1981 року як поліпшення .

Вступ

Візьмемо, наприклад, число ${\displaystyle 2419.}$ Це число складене і не ділиться на жодне з малих простих чисел. Але можна побачити, що це ${\displaystyle 2500-81,}$ тобто ${\displaystyle 2419=50^{2}-9^{2}.}$ Отже ми можемо розкласти ${\displaystyle 2419}$ як різницю квадратів. Це є ${\displaystyle (50-9)(50+9)}$ або ${\displaystyle 41\times 59.}$ Кожне непарне складене число можна розкласти як різницю квадратів:

${\displaystyle n=pq=\left({\frac {p+q}{2}}\right)^{2}-\left({\frac {p-q}{2}}\right)^{2}.}$

Спробуймо знов з числом 1649. Воно також складене і не має малих простих дільників, менших ніж його логарифм. З 2419 ми взяли перший квадрат більший від нього, а саме ${\displaystyle 50^{2}}$ і тоді зауважили, що ${\displaystyle 50^{2}-2419=81,}$ що є квадратом. Можна подумати, що в пошуці квадратів можна пройти послідовність ${\displaystyle x^{2}-n}$ з ${\displaystyle x=\lceil n^{1/2}\rceil ,\lceil n^{1/2}\rceil +1,\dots .}$ Для ${\displaystyle n=1649}$ маємо:

${\displaystyle 41^{2}-n=32,}$

${\displaystyle 42^{2}-n=115,}$

${\displaystyle 43^{2}-n=200,}$

(1)

${\displaystyle \vdots }$

і не бачимо квадратів поміж перших результатів.

Попри цю невдачу, попередні три рівняння вже можна використати для розкладення ${\displaystyle n.}$ Хоча ані 32, ані 200 не є квадратами, однак їхній добуток — квадрат, а саме ${\displaystyle 80^{2}.}$ отже з того, що

${\displaystyle 41^{2}\equiv 32{\pmod {n}},}$

${\displaystyle 43^{2}\equiv 200{\pmod {n}},}$

маємо ${\displaystyle 41^{2}\times 43^{2}\equiv 80^{2}{\pmod {n}},}$ що рівнозначно

${\displaystyle (41\times 43)^{2}\equiv 80^{2}{\pmod {n}}.}$

(2)

Ми знайшли розв'язок для ${\displaystyle a^{2}\equiv b^{2}{\pmod {n}}.}$ Наскільки це цікаво? Звісно існує багато нецікавих пар ${\displaystyle a^{2}\equiv b^{2}{\pmod {n}}.}$ А саме, якщо взяти будь-яке значення ${\displaystyle a}$ і покласти ${\displaystyle b=\pm a.}$ Але цей перелік не вичерпує всі розв'язки для цього рівняння, бо розкладення ${\displaystyle n}$ як різницю квадратів дало б пару ${\displaystyle a,b}$ з ${\displaystyle b\not =\pm a.}$ Далі, будь-яка пара ${\displaystyle a,b}$ з

${\displaystyle a^{2}\equiv b^{2}{\pmod {n}},b\not \equiv \pm a{\pmod {n}}}$

(3)

має вести до нетривіального розкладу ${\displaystyle n,}$ через ${\displaystyle \gcd(a-b,n).}$ Справді, з 3 випливає, що ${\displaystyle n}$ ділить ${\displaystyle (a-b)(a+b),}$ але не ділить жоден з множників, отже ${\displaystyle \gcd(a-b,n),\gcd(a+b,n)}$ мають бути нетривіальними дільниками ${\displaystyle n.}$ НСД можна знайти через алгоритм Евкліда. Зрештою, якщо ${\displaystyle n}$ має щонайменше два простих множники, тоді не менше половини розв'язків ${\displaystyle a^{2}\equiv b^{2}{\pmod {n}}}$ з ${\displaystyle ab}$ взаємно простим з ${\displaystyle n}$ також задовольняють ${\displaystyle b\not \equiv \pm a{\pmod {n}},}$ що і є 3.

Доведення

Для степені непарного простого ${\displaystyle p^{u},}$ конгруентність ${\displaystyle y^{2}\equiv 1{\pmod {p^{u}}}}$ має рівно 2 розв'язки, отже з того, що ${\displaystyle n}$ ділимо не менш як двома різними непарними простими, конгруенція ${\displaystyle y^{2}\equiv 1{\pmod {n}}}$ має щонайменше 4 розв'язки. Позначимо ці значення як ${\displaystyle y_{1},y_{2},y_{3},\dots ,y_{s},}$ де ${\displaystyle y_{1}=1,}$ ${\displaystyle y_{2}=-1.}$ Тоді повний перелік пар квадратичних залишків ${\displaystyle a,b}$ за модулем ${\displaystyle n}$ взаємно простих з ${\displaystyle n}$ і з ${\displaystyle a^{2}\equiv b^{2}{\pmod {n}}}$ збігається з усіма парами ${\displaystyle a,y_{i}a,}$ де ${\displaystyle a}$ пробігає всі залишки, взаємно прості з ${\displaystyle n,}$ a ${\displaystyle i=1,\dots ,s.}$ Пари з ${\displaystyle i=1,2}$ не задовольняють 3, тоді як інші так. З того, що ${\displaystyle s\geq 4,}$ доведення завершене.

Ідея

В основі методу лежить така ідея. Припустимо ${\displaystyle x}$ і ${\displaystyle y}$ є цілими такими, що ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}},}$ але ${\displaystyle x\not \equiv \pm y{\pmod {n}}}$. Тоді ${\displaystyle n}$ ділить ${\displaystyle x^{2}-y^{2}=(x-y)(x+y),}$ але не ділить ані ${\displaystyle (x-y),}$ ані ${\displaystyle (x+y).}$ Звідси ${\displaystyle \gcd(x-y,n)}$ має бути нетривіальним дільником ${\displaystyle n.}$

Припустимо, що маємо розкласти ціле ${\displaystyle n}$. Нехай ${\displaystyle m={\sqrt {n}},}$ розглянемо многочлен ${\displaystyle q(x)=(x+m)^{2}-n.}$ Зауважимо, що

${\displaystyle q(x)=x^{2}+2mx+m^{2}-n\approx x^{2}+2mx}$

є малим порівняно з ${\displaystyle n}$, якщо абсолютне значення ${\displaystyle x}$ мале. Алгоритм квадратичного решета обирає ${\displaystyle a_{i}=(x+m)}$ і перевіряє чи є ${\displaystyle b_{i}=(x+m)^{2}\ \ p_{t}}$-гладким. Зауважимо, що ${\displaystyle a_{i}=(x+m)^{2}\equiv b_{i}{\pmod {n}},}$ звідси ${\displaystyle n}$ є квадратичним залишком за модулем ${\displaystyle p.}$ Отже фактор-база повинна складатись з простих чисел ${\displaystyle p}$, для яких символ Лежандра ${\displaystyle \left({\frac {n}{p}}\right)=1.}$ Окрім цього, тому що ${\displaystyle b_{i}}$ може бути від'ємним, ${\displaystyle -1}$ також включаємо до фактор-бази.

Алгоритм

Вхід: ціле складене число ${\displaystyle n}$, яке не є степенем простого.

Вихід: нетривіальний дільник ${\displaystyle d}$ для ${\displaystyle n}$.

1. Обираємо базу дільників ${\displaystyle S=\{p_{1},p_{2},...,p_{t}\},}$ де ${\displaystyle p_{1}=-1}$ і ${\displaystyle p_{j}(j\geq 2)}$ є ${\displaystyle (j-1)}$-е просте ${\displaystyle p}$ для якого ${\displaystyle n}$ є квадратичним залишком за модулем ${\displaystyle p}$.
2. Обчислити ${\displaystyle m=\lfloor {\sqrt {n}}\rfloor .}$
3. (Зібрати ${\displaystyle t+1}$ двійок ${\displaystyle (a_{i},b_{i}).}$ Значення ${\displaystyle x}$ обираємо в порядку ${\displaystyle 0,\pm 1,\pm 2,\dots }$)

   Встановити ${\displaystyle i\gets 1}$. Поки ${\displaystyle i\leq t+1}$ робити наступне:

   1. Обчислити ${\displaystyle b=q(x)=(x+m)^{2}-n,}$ і перевірити послідовним діленням на елементи з ${\displaystyle S}$ чи є ${\displaystyle b\ p_{t}}$-гладким. Якщо ні, обираємо новий ${\displaystyle x}$ і повторюємо.
   2. Якщо ${\displaystyle b}$ є ${\displaystyle p_{t}}$-гладким, скажімо ${\displaystyle b=\prod _{j=1}^{t}p_{i}^{e_{ij}},}$ тоді покласти ${\displaystyle a_{i}\gets (x+m),b_{i}\gets b,v_{i}=(v_{i1},v_{i2},\dots ,v_{it})}$, де ${\displaystyle v_{ij}=e_{ij}\mod 2}$ для ${\displaystyle 1\leq j\leq t.}$
   3. ${\displaystyle i\gets i+1.}$
4. Використати лінійну алгебру над ${\displaystyle \mathrm {Z} _{2}}$ для знаходження непустої підмножини ${\displaystyle T\subseteq {1,2,\dots ,t+1}}$ такої, що ${\displaystyle \sum _{i\in T}v_{i}=0.}$
5. Обчислити ${\displaystyle x=\prod _{i\in T}{a_{i}\mod n}.}$
6. Для кожного ${\displaystyle j,1\leq j\leq t,}$ обчислити ${\displaystyle l_{j}=(\sum _{i\in T}e_{ij})/2}$.
7. Обчислити ${\displaystyle y=\prod _{j=1}^{t}p_{j}^{l_{j}}\mod n.}$
8. Якщо ${\displaystyle x\equiv \pm y{\pmod {n}},}$ тоді знайти іншу непорожню підмножину ${\displaystyle T\subseteq \{1,2,\dots ,t+1\}}$ таких, що ${\displaystyle \sum _{i\in T}v_{i}=0,}$ і перейти до етапу 5. (У малоймовірному випадку, якщо підмножина ${\displaystyle T}$ не існує, замінити декілька з двійок ${\displaystyle (a_{i},b_{i})}$ новими парами (етап 3), і перейти на етап 4.
9. Обчислити ${\displaystyle d=\gcd(x-y,n)}$ і повернути ${\displaystyle d}$.

Приклад роботи

Алгоритм квадратичного решета для находження нетривіального дільника для ${\displaystyle n=24961.}$

1. Обираємо фактор-базу ${\displaystyle S=\{-1,2,3,5,13,23\}}$ розміру ${\displaystyle t=6.}$ ${\displaystyle (7,11,17}$ і ${\displaystyle 19}$ опущені з ${\displaystyle S,}$ бо для цих простих ${\displaystyle ({\frac {n}{p}})=-1.}$)
2. Обчислити ${\displaystyle m=\lfloor {\sqrt {2}}4961\rfloor =157}$.
3. Далі йдуть дані зібрані для перших ${\displaystyle t+1}$ значень ${\displaystyle x,}$ для яких ${\displaystyle q(x)}$ є 23-гладких.

${\displaystyle i}$	${\displaystyle x}$	${\displaystyle q(x)}$	факторизація ${\displaystyle q(x)}$	${\displaystyle a_{i}}$	${\displaystyle b_{i}}$
1	0	−312	${\displaystyle -2^{3}\times 3\times 13}$	157	(1, 1, 1, 0, 1, 0)
2	1	3	${\displaystyle 3}$	158	(0, 0, 1, 0, 0, 0)
3	−1	−625	${\displaystyle -5^{4}}$	156	(1, 0, 0, 0, 0, 0)
4	2	320	${\displaystyle 2^{6}\times 5}$	159	(0, 0, 0, 1, 0, 0)
5	−2	−936	${\displaystyle -2^{3}\times 3^{2}\times 13}$	155	(1, 1, 0, 0, 1, 0)
6	4	960	${\displaystyle 2^{6}\times 3\times 5}$	161	(0, 0, 1, 1, 0, 0)
7	−6	−2160	${\displaystyle -2^{4}\times 3^{3}\times 5}$	151	(1, 0, 1, 1, 0, 0)

1. Обчислимо ${\displaystyle x=(a_{1}a_{2}a_{5}\mod n)=936.}$
2. Обчислимо ${\displaystyle l_{1}=1,l_{2}=3,l_{3}=2,l_{4}=0,l_{5}=1,l_{6}=0.}$
3. Обчислимо ${\displaystyle y=-23\times 32\times 13\mod n=24025.}$
4. Через те, що ${\displaystyle 936\equiv -24025{\pmod {n}},}$ потрібно взяти наступну лінійну залежність.
5. У випадку ${\displaystyle T=\{2,4,6\},}$ отримуємо такий самий вислід.
6. Наступна ${\displaystyle T=\{3,6,7\},v_{3}+v_{6}+v_{7}=0.}$
7. Обчислимо ${\displaystyle x=(a_{3}a_{6}a_{7}\mod n)=23405.}$
8. Обчислимо ${\displaystyle l_{1}=1,l_{2}=5,l_{3}=2,l_{4}=3,l_{5}=0,l_{6}=0.}$
9. Обчислимо ${\displaystyle y=(-25\times 32\times 53\mod n)=13922.}$
10. Тепер, ${\displaystyle 23405\not \equiv \pm 13922{\pmod {n}},}$ отже обчислимо ${\displaystyle \gcd(x-y,n)=\gcd(9483,24961)=109.}$ Звідки, маємо два нетривіальних дільники для ${\displaystyle 24961}$ — ${\displaystyle 109}$ і ${\displaystyle 229.}$

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

Замість перевірки на гладкість перебором дільників застосовної на етапі 3.1, використовується ефективніша техніка відома як просіювання (англ. sieving). Спочатку звернемо увагу на те, що якщо ${\displaystyle p}$ є непарним простим у фактор-базі і ${\displaystyle p}$ ділить ${\displaystyle q(x),}$ тоді ${\displaystyle p}$ також ділить ${\displaystyle q(x+lp)}$ для кожного цілого ${\displaystyle l.}$

${\displaystyle y(x)=x^{2}-n}$

${\displaystyle y(x+kp)=(x+kp)^{2}-n}$

${\displaystyle y(x+kp)=x^{2}+2xkp+(kp)^{2}-n}$

${\displaystyle y(x+kp)=y(x)+2xkp+(kp)^{2}\equiv y(x){\pmod {p}}}$

Отже через розв'язання рівняння ${\displaystyle q(x)\equiv 0{\pmod {p}}}$ для ${\displaystyle x}$ (для цього існує багато дієвих алгоритмів), отримуємо одну або дві (залежно від кількості розв’язків у квадратного рівняння) послідовностей інших значень ${\displaystyle y}$ для яких ${\displaystyle p}$ ділить ${\displaystyle q(y).}$

Також просіювання використовує властивість логарифма ${\displaystyle \log(\prod _{1}^{n}p_{i})=\sum _{1}^{n}\log(p_{i}).\,}$

Перебіг просіювання такий. Створюється масив ${\displaystyle Q[\ ]}$ проіндексований по ${\displaystyle x,-M\leq x\leq M,}$ і кожний запис ініціалізується ${\displaystyle \lg |q(x)|.}$ Нехай ${\displaystyle x_{1},x_{2}}$ будуть розв'язками для ${\displaystyle q(x)\equiv 0{\pmod {p}},}$ де ${\displaystyle p}$ є непарним простим числом з фактор-бази. Тоді значення ${\displaystyle \lg p}$ віднімають від тих записів в ${\displaystyle Q[x]}$ для яких ${\displaystyle x\equiv x_{1}}$ або ${\displaystyle x_{2}{\pmod {p}},}$ і ${\displaystyle -M\leq x\leq M.}$ Дія повторюється для кожного простого ${\displaystyle p}$ у фактор-базі. (Випадки з ${\displaystyle p=2}$ і степенями простих чисел можна обробити подібним чином.) Після просіювання, записи в масиві ${\displaystyle Q[x]}$ зі значеннями близькими до ${\displaystyle 0}$ швидше за все є ${\displaystyle p_{t}}$-гладкі (треба брати до уваги помилки округлення), і це можна перевірити через факторизацію ${\displaystyle q(x)}$ перебором дільників.

Примітки

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. Повний перелік лінійно залежних підмножин векторів такий: 125, 264, 763, 1456, 2347, 13457, 1234567.