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

Інша назва алгоритму — SQUFOF (від англійської — SQUare FOrm Factorization), що означає факторизацію методом квадратичних форм. Даний підхід був досить успішним протягом багатьох років і, як наслідок, досить багато різних модифікацій і реалізацій можна знайти на цю тему в літературі.[3] Більшість методів є складними і заплутаними, особливо в тому випадку, коли необхідна реалізація методу на комп'ютері. В результаті чого, багато варіанти алгоритмів не придатні для реалізації. Однак в 1975 році Даніель Шенкс запропонував створити алгоритм, який можна реалізувати і використовувати не тільки на комп'ютері, але і на простому мобільному телефоні.

Хоча Шенкс описав інші алгоритми для факторизації цілих чисел, по SQUFOF він нічого не опублікував по інших алгоритмах. Він надав лекції з даної теми і пояснив основну суть свого методу досить невеликому колу людей. В деяких роботах, інші учені [4] [5] [6] [7] обговорювали алгоритм, але жодна з цих робіт не містить детальний аналіз. Також цікаво те, що в своєму методі Шенкс робить досить велику кількість припущень[8], які, на жаль, залишилися без доведення. В роботі [9] представлені результати деяких експериментів, які свідчать, що багато припущень мають бути доведені. У підсумку, ґрунтуючись на цих спростованих припущеннях, Шенксу вдалося створити 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}}.}$

В методі Шенкса використовуються тільки невизначені форми. Під ${\displaystyle \Delta }$ будем розуміти дискримінант квадратичної форми. Будем говорити, що квадратична форма ${\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}}$. У разі якщо дана рівність ${\displaystyle \gcd(x_{0},y_{0})=1}$, то її називають примітивною.

Для будь-якої невизначеною квадратичної форми ${\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}$, однозначно визначається умовами: [9]

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 n}$, яке треба розкласти, до квадратичної бінарної форми ${\displaystyle f}$ з дискримінантом ${\displaystyle D=4n}$, з якої потім виконується серія еквівалентних перетворень і перехід від форми ${\displaystyle f}$ до неоднозначної форми ${\displaystyle (a',b',c')}$. Тоді, ${\displaystyle \gcd(a',b')}$ буде дільником ${\displaystyle n}$.

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

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

Більш докладно алгоритм може бути записаний в наступному вигляді:[12]

Вхід: Непарне складене число ${\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={\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}$.

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 N=22117019}$[9]

Цикл №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}$

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

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

• Василенко О. Н. Теоретико-числові алгоритми в криптографії. — Москва : МЦНМО, 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. — С. ст 186 - 192. — ISBN 978-0-8176-8297-2. (англ.)
• Jason E. Gower and Samuel S. Wagstaff, JR. SQUARE FORM FACTORIZATION. — Москва : МЦНМО, 2003. — С. 1-16, 35-36. — ISBN 5-94057-103-4.
• Samuel S. Wagstaff Jr. (2003). Cryptanalysis of Number Theoretic Ciphers. CRC Press. с. 318. ISBN 978-1584881537. (англ.)
• Yike Guo,R.L. Grossman (1999). High Performance Data Mining: Scaling Algorithms, Applications and Systems. Kluwer Academic Publishers. с. 111. ISBN 0-7923-7745-1. (англ.)