Метод квадратичних форм Шенкса

Метод квадратичних форм Шенкса — метод факторизації цілих чисел із застосуванням квадратичних форм, розроблений Даніелем Шенксом (Шаблон:Lang-en) 1975 року на основі Шаблон:Нп.

На початку XX-го сторіччя програми для 32-розрядних комп'ютерів, засновані на цьому методі, були безумовними лідерами для факторизації чисел від $10^{10}$ до $10^{18}$ Шаблон:Sfn. Цей алгоритм може розкласти практично будь-яке складене 18-значне число швидше, ніж за мілісекунду. Методи, що базуються на цьому алгоритмі, застосовуються для розкладання на дільники великих чисел, типу чисел Ферма.

Історія

Хоча Шенкс описав інші алгоритми для факторизації цілих чисел, по SQUFOF він нічого не опублікував. Він прочитав лекції з цієї теми і пояснив основну суть свого методу досить невеликому колу людей. Після смерті Шенкса в його паперах знайшли незавершену чернетку з описом методу SQUFOF. Її оцифрували й опублікували 2003 рокуШаблон:Sfn. Інші дослідникиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn обговорювали алгоритм. У своєму методі Шенкс зробив деяку кількість припущень, які залишилися без доведення. Утім, результати експериментів свідчать, що більшість припущень справджуютьсяШаблон:Sfn. У підсумку, ґрунтуючись на цих спрощених припущеннях, Шенксу вдалося створити SQUFOF.

Ідея методу

Ідея методів Шенкса полягає в зіставленні числу $n$, яке треба розкласти, квадратичної форми від двох змінних $f$ із дискримінантом $D=4n$, із якою потім виконується серія еквівалентних перетворень і перехід від форми $f$ до неоднозначної форми $(a^{\prime },b^{\prime },c^{\prime })$. Тоді, $\gcd (a^{\prime },b^{\prime })$ буде дільником $n$.

Перший варіант працює з додатноозначеними квадратичними формами від двох змінних заданого негативного дискримінанту і в групі форм він знаходить неоднозначну (Шаблон:Lang-en) форму, яка дозволяє розкласти дискримінант на множники. Складність першого варіанту становить $O(n^{1/5+\epsilon })$ за умови істинності розширеної гіпотези РіманаШаблон:Sfn.

Другий варіант — це власне SQUFOF (від Шаблон:Lang-en), у якому застосовується група квадратичних форм від двох змінних із позитивним дискримінантом. У ньому також відбувається пошук неоднозначної форми й розкладання дискримінанту на множники. Складність SQUFOF становить $O(n^{1/4+\epsilon })$ арифметичних операцій. Особливістю алгоритму є те, що він працює з цілими числами, які не перевищують $2\sqrt{n}$. На початку XX-го сторіччя SQUFOF вважався одним із найефективніших серед алгоритмів факторизації з експоненційною складністюШаблон:Sfn.

Допоміжні визначення

Квадратичною формою двох змінних називають однорідний поліном від двох змінних $x$ і $y$:

$f(x,y)=a{x}^2+bxy+c{y}^2=\left(\begin{array}{cc}x& y\end{array}\right)\left(\begin{array}{cc}a& b\\ 0& c\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right).$

У методі SQUFOF застосовуються тільки невизначені форми. Під $\mathrm{\Delta }$ розуміється дискримінант квадратичної форми $b^2-4ac$. Квадратична форма $f$ представляє ціле число $m\in \mathbb{Z}$, якщо існують такі цілі числа $x_0,y_0$, що виконується рівність: $f(x_0,y_0)=a{x}_0^2+b{x}_0{y}_0+c{y}_0^2=m$. У разі, якщо в представленні $\gcd (x_0,y_0)=1$, то таке представлення називають примітивним.

Форму $f=(a,b,c)$ називають скороченою (редукованою), якщо $|\sqrt{\mathrm{\Delta }}-2|a||<b<\sqrt{\mathrm{\Delta }}$.

Для будь-якої невизначеної квадратичної форми $f=\left(\begin{array}{ccc}a,& b,& c\end{array}\right)$ можна визначити оператор редукції:

$\rho \left(\begin{array}{ccc}a,& b,& c\end{array}\right)=\left(\begin{array}{ccc}c,& r(-b,c),& \frac{r(-b,c{)}^2-\mathrm{\Delta }}{4c}\end{array}\right)$, де $r(-b,c)$ — ціле число $r$, яке однозначно визначається умовамиШаблон:Sfn:

1. $r+b\equiv 0mod(2c)$
2. $-|c|<r<|c|,if\sqrt{\mathrm{\Delta }}<|c|$
3. $\sqrt{\mathrm{\Delta }}-2|c|<r<\sqrt{\mathrm{\Delta }},if|c|<\sqrt{\mathrm{\Delta }}$

Результат застосування оператора $\rho$ до форми $f$ $n$ разів записується у вигляді ${\rho }^n(f)$. Також визначено оператор ${\rho }^{-1}$ як:

${\rho }^{-1}\left(\begin{array}{ccc}a,& b,& c\end{array}\right)=\left(\begin{array}{ccc}\frac{r(-b,c{)}^2-\mathrm{\Delta }}{4c},& r(-b,c),& c\end{array}\right)$, де $r(-b,c)$ визначений так само як і в попередньому випадку. У результаті застосування операторів ${\rho }^{-1}$ і $\rho$ до квадратичної форми $f=\left(\begin{array}{ccc}a,& b,& c\end{array}\right)$ з дискримінантом $\mathrm{\Delta }$, отримані квадратичні форми також матимуть дискримінант $\mathrm{\Delta }$.

Метод отримання скороченої форми, еквівалентної даній, знайшов ще Карл Гаусс і він полягає в послідовному застосуванні оператора редукції $g=\rho (f)$, поки $f$ не стане скороченою.

Теорема.

Для розуміння операцій з квадратичними формами потрібні поняття квадратних, суміжних і неоднозначних квадратичних форм.

Неоднозначними (Шаблон:Lang-en) називають форми вигляду $(k,kn,c)$. Така неоднозначна форма існує для кожного дільника k дискримінанту ∆Шаблон:Sfn.

Теоретичний опис

Алгоритм може бути записаний в наступному вигляді:Шаблон:Sfn

Вхід: Непарне складене число $n$, яке потрібно факторизувати. Якщо $nmod4=1,$ замінимо $n$ на $2n.$ Тепер $nmod4=2;3.$ Остання властивість потрібна, щоб визначник квадратичної форми був фундаментальним, що забезпечує збіжність методу.

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

1. Визначимо вихідну квадратичну форму $f=(1,2b,b^2-D)$, з дискримінантом $D=4n$, де $b=\lfloor \sqrt{n}\rfloor$.

2. Виконаємо цикл редукування $f=\rho (f)$, поки форма $f$ не стане квадратною.

3. Обчислимо квадратний корінь з $f:g=(a^{\prime },b^{\prime },c^{\prime })=f^{1/2}$

4. Виконаємо цикл редукування $p=\rho (g)$, поки значення другого коефіцієнта не стабілізується $b_{i^{\prime }+1}=b_{i^{\prime }}$. Кількість ітерацій $m$ цього циклу має становити приблизно половину від кількості ітерацій першого циклу. Останнє значення $a^{\prime }$ дасть дільник числа $n$ (можливо, тривіальний).

Реалізація алгоритму

Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина виконується на основі обчислення коефіцієнтів $P,Q,r$ Шаблон:Нп без звертання до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної формиШаблон:Sfn. За потреби можна відновити відповідні форми $f_k=(a_k,b_k,c_k)$ за формулами: $(a_k,b_k,c_k)=((-1{)}^{k-1}{Q}_{k-1},2P_k,(-1{)}^k{Q}_k)$

Вхід: Складене число $n$

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

• ініціалізація алгоритму.
  • Перевіримо, чи є $n$ повним квадратом. Якщо так, то обчислимо $d=\sqrt{n},$ і завершимо обчислення. Інакше, перейдемо до наступного пункту.
  • Якщо $n\equiv 1(mod4),$ тоді замінимо $n$ на $2n.$ Визначимо $D=4n,q_0=\lfloor \sqrt{D}\rfloor .$
  • Визначимо вихідні значення параметрів $P,Q,r:$

$P_0=0,Q_0=1,r_0=P_1=\lfloor \sqrt{n}\rfloor ,Q_1=n-r_0^2,r_1=\lfloor 2r_0/Q_1\rfloor .$

• Перший цикл
  • $P_k=r_{k-1}\cdot Q_{k-1}-P_{k-1},Q_k=Q_{k-2}+(P_{k-1}-P_k)\cdot r_{k-1},r_k=\lfloor \frac{P_k+\lfloor \sqrt{n}\rfloor }{Q_k}\rfloor ,k\ge 2.$
  • Продовжуємо обчислення коефіцієнтів $P_k,Q_k{r}_k$ доти, доки не знайдемо Q_k, що є повним квадратом. Це має статися за деякого $k.$ Нехай $Q_k=d^2$ для цілого $d>0.$ Перейдемо до наступного циклу.

• Другий цикл.
  • почнемо цикл обчислень нових параметрів $P_j^{\prime },Q_j^{\prime },r_j^{\prime }.$ Формули для реалізації другого циклу залишаться такими ж, як раніше. Зміняться лише початкові значення параметрів $P^{\prime },Q^{\prime },r^{\prime }:$
  • $P_0^{\prime }=-P_k,Q_0^{\prime }=d,r_0^{\prime }=\lfloor \frac{P_0^{\prime }+\lfloor \sqrt{n}\rfloor }{Q_0^{\prime }}\rfloor ,P_1^{\prime }=r_0^{\prime }\cdot Q_0^{\prime }-P_0^{\prime },Q_1^{\prime }=(N-P_1^{\prime 2})/Q_0^{\prime }.$
  • Обчислення слід продовжувати, поки два поспіль значення $P_j^{\prime },P_{j+1}^{\prime }$ не стануть рівними. Тоді, значення $Q_j$ дасть шуканий дільник числа $n.$

Оцінка збіжності

Згідно з розрахунками, виконаними самим Шенксом, кількість ітерацій першого й другого циклів алгоритму визначається кількістю множників $w$ числа $n$ і дорівнює приблизно:

$\frac{C}{2^w-2}\cdot n^{1/4},$

де $C$ — константа, що дорівнює приблизно 2,4 для першого циклу ітерацій.Шаблон:Sfn

Приклад факторизації числа

Застосуємо цей метод для факторизації числа $N=22117019$Шаблон:Sfn

Цикл №1 $F_i$ $i$ $(-1{)}^{i-1}{Q}_{i-1}$ $2\cdot P_i$ $(-1{)}^i{Q}_i$ $0$ $-8215$ $2\cdot 4702$ $1$ $1$ $1$ $2\cdot 4702$ $-8215$ $2$ $-8215$ $2\cdot 3513$ $1190$ $3$ $1190$ $2\cdot 3627$ $-7531$ $4$ $-7531$ $2\cdot 3904$ $913$ $5$ $913$ $2\cdot 4313$ $-3850$ $6$ $-3850$ $2\cdot 3387$ $2765$ $7$ $2765$ $2\cdot 2143$ $-6338$ $8$ $-6338$ $2\cdot 4195$ $713$ $9$ $713$ $2\cdot 4361$ $-4346$ $10$ $-4346$ $2\cdot 4331$ $773$ $11$ $773$ $2\cdot 4172$ $-6095$ $12$ $-6095$ $2\cdot 1923$ $3022$ $13$ $3022$ $2\cdot 4121$ $-1699$ $14$ $-1699$ $2\cdot 4374$ $1757$ $15$ $1757$ $2\cdot 4411$ $-1514$ $16$ $-1514$ $2\cdot 4673$ $185$ $17$ $185$ $2\cdot 4577$ $-6314$ $18$ $-6314$ $2\cdot 1737$ $3025(=55^2)$

Цикл №2 $G_i$ $i$ $(-1{)}^{i-1}{Q}_{i-1}^{\prime }$ $2\cdot P_i^{\prime }$ $(-1{)}^i{Q}_i^{\prime }$ $0$ $-55$ $2\cdot 4652$ $8653$ $1$ $8653$ $2\cdot 4001$ $-706$ $2$ $-706$ $2\cdot 4471$ $3013$ $3$ $3013$ $2\cdot 4568$ $-415$ $4$ $-415$ $2\cdot 4562$ $3145$ $5$ $3145$ $2\cdot 1728$ $-6083$ $6$ $-6083$ $2\cdot 4355$ $518$ $7$ $518$ $2\cdot 4451$ $-4451$ $8$ $-4451$ $2\cdot 4451$ $518$

У другому циклі $P_7^{\prime }=P_8^{\prime }.$ Отже, $4451$ є дільником числа $N=22117019$. Далі обчислюємо другий дільник: $22117019÷4451=4969$
$22117019=4451\cdot 4969.$

Застосування

Алгоритм застосовується в багатьох реалізаціях решета числового поля і квадратичного решета для факторизації невеликих чисел, що виникають під час факторизації великого цілого числа. У будь-якому випадку, SQUFOF застосовується в основному як допоміжний алгоритм у потужніших методах для факторизації чисел невеликого розміру, які не мають малих простих дільників. Як правило, такі числа є добутком кількох різних простих чиселШаблон:Sfn.

Література

• Шаблон:КнигаШаблон:Ref-ru
• Шаблон:КнигаШаблон:Ref-ru
• Шаблон:Книга Шаблон:Ref-en
• Шаблон:Публікація
• Шаблон:Книга Шаблон:Ref-en
• Шаблон:Книга Шаблон:Ref-en
• Шаблон:Cite web 2

Шаблон:Алгоритми теорії чисел