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

Квадратичне решето (Шаблон:Lang-en) — алгоритм факторизації цілих чисел, на практиці найшвидший для чисел до 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,$

$⋮$

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

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

$41^2\equiv 32(\mathrm{mod}n),$

$43^2\equiv 200(\mathrm{mod}n),$

маємо $41^2\times 43^2\equiv 80^2(\mathrm{mod}n),$ що рівнозначно Шаблон:NumBlk Ми знайшли розв'язок для $a^2\equiv b^2(\mathrm{mod}n).$ Наскільки це цікаво? Звісно існує багато нецікавих пар $a^2\equiv b^2(\mathrm{mod}n).$ А саме, якщо взяти будь-яке значення $a$ і покласти $b=\pm a.$ Але цей перелік не вичерпує всі розв'язки для цього рівняння, бо розкладення $n$ як різницю квадратів дало б пару $a,b$ з $b=\pm a.$ Далі, будь-яка пара $a,b$ з Шаблон:NumBlk має вести до нетривіального розкладу $n,$ через $\gcd (a-b,n).$ Справді, з Шаблон:EquationNote випливає, що $n$ ділить $(a-b)(a+b),$ але не ділить жоден з множників, отже $\gcd (a-b,n),\gcd (a+b,n)$ мають бути нетривіальними дільниками $n.$ НСД можна знайти через алгоритм Евкліда. Зрештою, якщо $n$ має щонайменше два простих множники, тоді не менше половини розв'язків $a^2\equiv b^2(\mathrm{mod}n)$ з $ab$ взаємно простим з $n$ також задовольняють $b\equiv ̸\pm a(\mathrm{mod}n),$ що і є Шаблон:EquationNote.

Доведення

Для степені непарного простого $p^u,$ конгруентність $y^2\equiv 1(\mathrm{mod}{p}^u)$ має рівно 2 розв'язки, отже з того, що $n$ ділимо не менш як двома різними непарними простими, конгруенція $y^2\equiv 1(\mathrm{mod}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(\mathrm{mod}n)$ збігається з усіма парами $a,y_{i}a,$ де $a$ пробігає всі залишки, взаємно прості з $n,$ a $i=1,\dots ,s.$ Пари з $i=1,2$ не задовольняють Шаблон:EquationNote, тоді як інші так. З того, що $s\ge 4,$ доведення завершене.

Ідея

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

Припустимо, що маємо розкласти ціле $n$. Нехай $m=\lfloor \sqrt{n}\rfloor$. Розглянемо многочлен $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(\mathrm{mod}n),$ звідси $n$ є квадратичним залишком за модулем $p.$ Отже фактор-база має складатися з простих чисел $p$, для яких символ Лежандра $\left(\frac{n}{p}\right)=1.$ Окрім цього, тому що $b_i$ може бути від'ємним, $-1$ також включаємо до фактор-бази.

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

Замість перевірки на гладкість перебором дільників застосовується ефективніша техніка відома як просіювання (Шаблон:Lang-en). Спочатку звернемо увагу на те, що якщо $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)(\mathrm{mod}p)$

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

Для просіювання застосовується властивість логарифма: $\log (\prod _1^n{p}_i)=\sum _1^n\log (p_i).$

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

Алгоритм

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

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

1. Обираємо базу дільників $S=\{p_1,p_2,...,p_t\},$ де $p_1=-1$ і $p_j(j\ge 2)$ є $(j-1)$-е просте $p$ для якого $n$ є квадратичним залишком за модулем $p$.
2. Обчислити $m=\lfloor \sqrt{n}\rfloor$.
3. Побудувати многочлен $q(x)=(x+m{)}^2-n$ й обчислити значення $\log |q(x)|$ для x $-M\le x\le M$. Просіяти побудований масив елементами факторної бази p_i (та їх невеликими степенями).
4. Серед близьких до нуля залишків у просіяному масиві знайти $t+1$ гладких чисел $b_i$:

   Встановити $i\leftarrow 1$. Поки $i\le 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\leftarrow (x+m),b_i\leftarrow b,v_i=(v_{i1},v_{i2},\dots ,v_{it})$, де $v_{ij}=e_{ij}mod2$ для $1\le j\le t.$
   3. $i\leftarrow i+1.$
5. Серед векторів v_i над полем Z₂ знайти нетривіальну лінійну комбінацію, яка дорівнює нульовому вектору, тобто, непорожню підмножину $T\subseteq 1,2,\dots ,t+1$ таку, що $\sum _{i\in T}{v}_i=0$. Коефіцієнти такої лінійної комбінації можна знайти шляхом розв'язання системи лінійних рівнянь.
6. Обчислити $x=\prod _{i\in T}{a}_{i}modn.$
7. Для кожного $j,1\le j\le t,$ обчислити $l_j=(\sum _{i\in T}{e}_{ij})/2$.
8. Обчислити $y=\prod _{j=1}^t{p}_j^{l_j}modn.$
9. Якщо $x\equiv \pm y(\mathrm{mod}n),$ тоді знайти іншу непорожню підмножину $T\subseteq \{1,2,\dots ,t+1\}$ таких, що $\sum _{i\in T}{v}_i=0,$ і перейти до етапу 5. (У малоймовірному випадку, якщо підмножина $T$ не існує, замінити декілька з двійок $(a_i,b_i)$ новими парами (етап 3), і перейти на етап 4.
10. Обчислити $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}modn)=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 13modn=24025.$
8. Через те, що $936\equiv -24025(\mathrm{mod}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}modn)=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 53modn)=13922.$
14. Тепер, $23405\equiv ̸\pm 13922(\mathrm{mod}n),$ отже обчислимо $\gcd (x-y,n)=\gcd (9483,24961)=109.$ Звідки, маємо два нетривіальних дільники для $24961$ — $109$ і $229.$