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

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

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

Історія

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

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

Ідея методу

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема.

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

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

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

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

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

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

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

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

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

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

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

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

Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина виконується на основі обчислення коефіцієнтів ${\displaystyle P,Q,r}$ ^[en] без звертання до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми. За потреби можна відновити відповідні форми ${\displaystyle f_{k}=(a_{k},b_{k},c_{k})}$ за формулами: ${\displaystyle (a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k}Q_{k})}$

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

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

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

${\displaystyle 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 .}$

• Перший цикл
  • ${\displaystyle 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.}$
  • Продовжуємо обчислення коефіцієнтів ${\displaystyle P_{k},~Q_{k}~r_{k}}$ доти, доки не знайдемо Q_k, що є повним квадратом. Це має статися за деякого ${\displaystyle k.}$ Нехай ${\displaystyle Q_{k}=d^{2}}$ для цілого ${\displaystyle d>0.}$ Перейдемо до наступного циклу.

• Другий цикл.
  • почнемо цикл обчислень нових параметрів ${\displaystyle P_{j}^{\prime },~Q_{j}^{\prime },~r_{j}^{\prime }.}$ Формули для реалізації другого циклу залишаться такими ж, як раніше. Зміняться лише початкові значення параметрів ${\displaystyle P^{\prime },~Q^{\prime },~r^{\prime }:}$
  • ${\displaystyle 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 }.}$
  • Обчислення слід продовжувати, поки два поспіль значення ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime }}$ не стануть рівними. Тоді, значення ${\displaystyle Q_{j}}$ дасть шуканий дільник числа ${\displaystyle n.}$

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

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

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

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

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

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

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

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

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

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

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

Примітки

1. Наприклад, Припущення 4.5, що розклад вхідного числа N у добуток простих чисел не містить їх квадратів (SQUARE FORM FACTORIZATION, 2008, стор 556 (16 у pdf)), також у доведенні теорем про складність алгоритму та ін.

Джерела

1. Yike Guo, 1999.
2. Shanks, 2003.
3. Henri Cohen, 1996, A Course in Computational Algebraic Number Theory..
4. Hans Riesel, 1994, стор. 186—192.
5. D. A. Buell, 1989, Binary Quadratic Forms.
6. Samuel S. Wagstaff Jr., 2003.
7. SQUARE FORM FACTORIZATION, 2008, стор. 559.
8. Василенко, 2003, 75—76.
9. SQUARE FORM FACTORIZATION, 2008, с. 553.
10. Ішмухаметов, 2011, 79—80.
11. Ішмухаметов, 2011, 82.
12. SQUARE FORM FACTORIZATION, 2008, стор. ??.

Література

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 2003. — С. 75 - 76. — .(рос.)
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казанский университет, 2011. — С. 74 - 82.(рос.)
• Hans Riesel. Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition. — Sweden : Birkhauser, 1994. — . (англ.)
• 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. — . (англ.)
• Yike Guo, R.L. Grossman. High Performance Data Mining: Scaling Algorithms, Applications and Systems. — Kluwer Academic Publishers, 1999. — С. 111. — . (англ.)
• SQUFOF : an unfinished manuscript : written about 1982 / Daniel Shanks ; typed in LaTeX by Wagstaf. — 2003. — 06. — Дата звернення: 02.06.2023.