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

Метод квадратичних форм Шенкса — метод факторизації цілих чисел із застосуванням квадратичних форм, розроблений Даніелем Шенксом (англ. Daniel Shanks) 1975 року на основі методу ланцюгових дробів.

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

Історія

1975 року Даніель Шенкс створив алгоритм, який нині можна реалізувати й застосовувати не тільки на комп'ютері, а й на простому мобільному телефоні^{[джерело?]}

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

Ідея методу

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

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

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

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

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

$f(x,y)=ax^{2}+bxy+cy^{2}={\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}a&b\\0&c\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}.$

У методі SQUFOF застосовуються тільки невизначені форми. Під $\Delta$ розуміється дискримінант квадратичної форми $b^{2}-4ac$. Квадратична форма $f$ представляє ціле число $m\in \mathbb {Z}$, якщо існують такі цілі числа $x_{0},y_{0}$, що виконується рівність: $f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2}=m$. У разі, якщо в представленні $\gcd(x_{0},y_{0})=1$, то таке представлення називають примітивним.

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

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

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

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

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

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

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

Теорема.

Кожна форма $f$ еквівалентна деякій скороченій формі, і будь-яка скорочена форма для $f$ рівна $\rho ^{k}(f)$ для деякого додатного $k$. Якщо $f$ - скорочена, то $\rho (f)$ також скорочена.

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

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

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

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

Вхід: Непарне складене число $n$, яке потрібно факторизувати. Якщо $n\!\!\!\mod 4=1,$ замінимо $n$ на $2n.$ Тепер $n\!\!\!\mod 4=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+1}'=b_{i}'$. Кількість ітерацій $m$ цього циклу має становити приблизно половину від кількості ітерацій першого циклу. Останнє значення $a^{\prime }$ дасть дільник числа $n$ (можливо, тривіальний).

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

Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина виконується на основі обчислення коефіцієнтів $P,Q,r$ методу ланцюгових дробів без звертання до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми. За потреби можна відновити відповідні форми $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\geq 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 для першого циклу ітерацій.

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

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

Цикл №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\div 4451=4969$
$22117019=4451\cdot 4969.$

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

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

Література

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 2003. — С. 75 - 76. — ISBN 5-94057-103-4.(рос.)
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казанский университет, 2011. — С. 74 - 82.(рос.)
• Hans Riesel. Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition. — Sweden : Birkhauser, 1994. — ISBN 978-0-8176-8297-2. (англ.)
• Gower, Jason E. ; Wagstaff, Samuel S., Jr. Square form factorization // Mathematics of Computation. — 2008. — Т. 77. — С. 551—588. — DOI:10.1090/S0025-5718-07-02010-8.
• Samuel S. Wagstaff Jr. Cryptanalysis of Number Theoretic Ciphers. — CRC Press, 2003. — P. 318. — ISBN 978-1584881537. (англ.)
• Yike Guo, R.L. Grossman. High Performance Data Mining: Scaling Algorithms, Applications and Systems. — Kluwer Academic Publishers, 1999. — С. 111. — ISBN 0-7923-7745-1. (англ.)
• SQUFOF : an unfinished manuscript : written about 1982 / Daniel Shanks ; typed in LaTeX by Wagstaf. — 2003. — 06. — Дата звернення: 02.06.2023.