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

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

Вступ

Візьмемо, наприклад, число ${\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=\lfloor {\sqrt {n}}\rfloor }$. Розглянемо многочлен ${\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}$ також включаємо до фактор-бази.

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

Замість перевірки на гладкість перебором дільників застосовується ефективніша техніка відома як просіювання (англ. 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}$ (для цього існують дієві алгоритми, наприклад алгоритм Тоннелі—Шенкса^[en]), отримуємо одну або дві (залежно від кількості квадратичних лишків) послідовності значень ${\displaystyle y}$, для яких ${\displaystyle p}$ ділить ${\displaystyle q(y)}$.

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

Перебіг просіювання такий. Створюється масив ${\displaystyle Q[x]}$, де ${\displaystyle x,-M\leq x\leq M,}$ і кожний елемент ініціалізується значенням ${\displaystyle \log |q(x)|}$. Нехай ${\displaystyle x_{1},x_{2}}$ будуть розв'язками для ${\displaystyle q(x)\equiv 0{\pmod {p}},}$ де ${\displaystyle p}$ є непарним простим числом з фактор-бази. Тоді значення ${\displaystyle \log 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 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 q(x)=(x+m)^{2}-n}$ й обчислити значення ${\displaystyle \log |q(x)|}$ для x ${\displaystyle -M\leq x\leq M}$. Просіяти побудований масив елементами факторної бази p_i (та їх невеликими степенями).
4. Серед близьких до нуля залишків у просіяному масиві знайти ${\displaystyle t+1}$ гладких чисел ${\displaystyle b_{i}}$:

   Встановити ${\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.}$
5. Серед векторів v_i над полем Z₂ знайти нетривіальну лінійну комбінацію, яка дорівнює нульовому вектору, тобто, непорожню підмножину ${\displaystyle T\subseteq {1,2,\dots ,t+1}}$ таку, що ${\displaystyle \sum _{i\in T}v_{i}=0}$. Коефіцієнти такої лінійної комбінації можна знайти шляхом розв'язання системи лінійних рівнянь.
6. Обчислити ${\displaystyle x=\prod _{i\in T}{a_{i}\mod n}.}$
7. Для кожного ${\displaystyle j,1\leq j\leq t,}$ обчислити ${\displaystyle l_{j}=(\sum _{i\in T}e_{ij})/2}$.
8. Обчислити ${\displaystyle y=\prod _{j=1}^{t}p_{j}^{l_{j}}\mod n.}$
9. Якщо ${\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.
10. Обчислити ${\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)

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