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

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

Вступ

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

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

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

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

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

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

(1)

$\vdots$

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

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

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

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

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

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

(2)

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

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

(3)

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

Доведення

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

Ідея

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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