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

Візьмемо, наприклад, число ${\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)

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

Замість перевірки на гладкість перебором дільників застосовної на етапі 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)}$ перебором дільників.