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

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

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

Історія

Інша назва алгоритму — SQUFOF (акроним від англійського — SQUare FOrm Factorization), що означає факторизація методомквадратичних форм. Даний підхід був досить успішним протягом багатьох років і, як наслідок, досить багато різних модифікацій і реалізацій можна знайти на цю тему в літературі. Більшість методів є складними і заплутаними, особливо в тому випадку, коли необхідна реалізація методу на комп'ютері. В результаті чого, багато варіанти алгоритмів не придатні для реалізації. Однак в 1975 році Даніель Шенкс запропонував створити алгоритм, який можна реалізувати і використовувати не тільки на комп'ютері, але і на простому мобільному телефоні. Хоча Шенкс описав інші алгоритми для факторизації цілих чисел, по SQUFOF він нічого не опублікував. Він надав лекції з даної теми і пояснив основну суть свого методу досить невеликому колу людей. Деякі роботи інших учених обговорювали алгоритм, але жодна з них не містить детальний аналіз. Також цікаво те, що в своєму методі Шенкс робить досить велику кількість припущень <ref> Наприклад в роботі SQUARE FORM FACTORIZATION JASON E. GOWER AND SAMUEL S. WAGSTAFF, JR. Assumption 4.12. на сторінці 20, Assumption 4.5 на сторінці 16, так само при доведенні теорем про складність алгоритму і т. д. </ ref>, які, на жаль, залишилися без доведення. В роботі Представлені результати деяких експериментів, які свідчать, що багато припущень мають бути. У підсумку, грунтуючись на цих спрощених припущеннях, Шенксу вдалося створити SQUFOF.

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

Для того щоб зрозуміти, як реалізований цей алгоритм, необхідно дізнатися мінімальні відомості про математичні об'єкти, що використовуються в даному методі, а саме про квадратичних формах. Бінарної квадратичною формою називається поліном від двох змінних Неможливо розібрати вираз (синтаксична помилка): {\displaystyle x </ math> і <math> y </ math>: : <Math> 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}. </ math> <br /> У методі Шенкса використовуються тільки [[Квадратична форма | невизначені форми]]. Під <math> \ Delta </ ​​math> будемо розуміти дискримінант квадратичної форми. Будемо говорити, що квадратична форма <math> f </ math> представляє ціле число <math> m \ in \ Z </ math>, якщо існують такі цілі числа <math> x_0, y_0 </ math>, що виконано рівність: <math> f (x_0, y_0) = ax_0 ^ 2 + bx_0y_0 + cy_0 ^ 2 </ math>. У разі якщо виконано рівність <math> \ gcd (x_0, y_0) = 1 </ math>, то уявлення називається '' примітивним ''. Для будь-якої невизначеною квадратичної форми <math> f = \ begin {pmatrix} a, & b, & c \ end {pmatrix} </ math> можна визначити '' оператор редукції '' як: : <Math> \ rho \ begin {pmatrix} a, & b, & c \ end {pmatrix} = \ begin {pmatrix} c, & r (-b, c), & \ frac {r (-b, c) ^ 2 - \ Delta} {4c} \ end {pmatrix} </ math>, де <math> r (-b, c) </ math> - визначено, як ціле число <math> r </ math>, однозначно визначається умовами : {{sfn | SQUARE FORM FACTORIZATION | 2003 | loc = SQUARE FORM FACTORIZATION | name = Jason E. Gower and Samuel S. Wagstaff, JR.}} :: # <math> r + b \ equiv 0 \ mod (2c) </ math> :: # <math> - | c | <R <| c |, \ quad if \ quad \ sqrt {\ Delta} <| c | </ Math> :: # <math> \ sqrt {\ Delta} - 2 | c | <R <\ sqrt {\ Delta}, \ quad if \ quad | c | <\ Sqrt {\ Delta} </ math> Результат застосування оператора <math> \ rho </ math> до форми <math> f </ math> <math> n </ math> раз записується у вигляді <math> \ rho ^ n (f) </ math>. Також визначено оператор <math> \ rho ^ {- 1} </ math> як: : <Math> \ rho ^ {- 1} \ begin {pmatrix} a, & b, & c \ end {pmatrix} = \ begin {pmatrix} \ frac {r (-b, c) ^ 2 - \ Delta} {4c }, & r (-b, c), & c \ end {pmatrix} </ math>, де <math> r (-b, c) </ math> визначено так само як і в попередньому випадку. Зауважимо, що в результаті застосування операторів <math> \ rho ^ {- 1} </ math> і <math> \ rho </ math> до квадратичної формі <math> f = \ begin {pmatrix} a, & b, & c \ end {pmatrix} </ math> з дискримінантом <math> \ Delta </ ​​math>, отримані квадратичні форми так само матимуть дискриминант <math> \ Delta </ ​​math>. Метод отримання скороченої форми, еквівалентної даної, був знайдений ще [[Карл Гаусс | Карлом Гауссом]] і складається в послідовному застосуванні оператора редукції <math> g = \ rho (f) </ math>, поки <math> f </ math > не стане скороченим. '' 'Теорема.' '' {{Теорема | Кожна форма <math> f </ math> еквівалентна деякій скороченій формі, і будь-яка скорочена форма для <math> f </ math> дорівнює <math> \ rho ^ {k} (f) </ math> для деякого позитивного <math> k </ math>. Якщо <math> f </ math> - скорочена, то <math> \ rho (f) </ math> також скорочена.}} Так само для ясності розуміння всіх операцій з квадратичними формами нам знадобиться поняття [[Квадратична форма | квадратних, суміжних і неоднозначних квадратичних форм]] == Варіанти == Ідея методу Шенкса складається в зіставленні числа <math> n </ math>, яке треба розкласти, квадратичної бінарної форми <math> f </ math> з дискримінантом <math> D = 4n </ math>, з якої потім виконується серія еквівалентних перетворень і перехід від форми <math> f </ math> до неоднозначного формі <math> (a ', b', c ') </ math>. Тоді, <math> \ gcd (a ', b') </ math> буде дільником <math> n </ math>. Перший варіант працює з позитивно певними бінарними квадратичними формами заданого негативного дискримінанту і в групі класів форм він знаходить [[Амбігова форма | амбігову форму]], яка дає розкладати дискримінант на множники. Складність першого варіанту становить <math> O (n ^ {1/5 + \ varepsilon}) </ math> за умови істинності розширеної [[Гіпотеза Рімана | гіпотези Рімана]]. {{Sfn | Василенко | 2003 | loc = Теоретико- числові алгоритми в криптографії | name = Василенко О. Н.}} Другий варіант це SQUFOF, він використовує групу класів бінарних квадратичних форм з позитивним дискримінантом. У ньому також відбувається знаходження амбігової форми і розкладання дискримінанту на множники. Складність SQUFOF становить <math> O (n ^ {1/4 + \ varepsilon}) </ math> арифметичних операцій; при цьому алгоритм працює з цілими числами, що не перевершують <math> 2 \ sqrt {n} </ math>. Серед алгоритмів факторизації з експоненційної складністю SQUFOF вважається одним з найефективніших. {{Sfn | Василенко | 2003 | loc = Теоретико-числові алгоритми в криптографії | name = Василенко О. Н.}} === Оцінка збіжності === Згідно з розрахунками, виконаними самим Шенксом, число ітерацій першого і другого циклів алгоритму визначається числом <math> w </ math> співмножниками числа <math> n </ math> і дорівнює приблизно: <Math> \ frac {C} {2 ^ w-2} \ cdot n ^ {1/4}, </ math> де <math> C </ math> - константа, рівна приблизно 2,4 для першого циклу ітерацій. {{sfn | Ишмухаметов | 2011 | loc = Методи факторизації натуральних чисел: Навчальний посібник | name = Ишмухаметов Ш. Т. 1}} == Опис алгоритму == Більш докладно алгоритм може бути записаний в наступному вигляді: {{sfn | Ишмухаметов | 2011 | loc = Методи факторизації натуральних чисел: Навчальний посібник стор. 79-80 | name = Ишмухаметов Ш. Т.}} '' 'Вхід:' '' Непарне складене число <math> n </ math>, яке потрібно факторизувати. Якщо <math> n \! \! \! \ Mod 4 = 1, </ math> замінимо <math> n </ math> на <math> 2n. </ Math> Тепер <math> n \! \! \ ! \ mod 4 = 2; 3. </ math> Остання властивість потрібна, щоб визначник квадратичної форми був фундаментальним, що забезпечує збіжність методу. '' 'Вихід:' '' Нетривіальний дільник <math> n </ math>. : 1. Визначимо вихідну квадратичну форму <math> f = (1,2b, b ^ 2-D) </ math>, з дискримінантом <math> D = 4n </ math>, де <math> b = \ mathcal { b} \ sqrt {n} \ mathcal {c} </ math>. : 2. Виконаємо цикл редукування <math> f = \ rho (f) </ math>, поки форма <math> f </ math> не стане квадратної. : 3. Обчислимо квадратний корінь з <math> f: ~ g = (a ^ \ prime, b ^ \ prime, c ^ \ prime) = f ^ {1/2} </ math> : 4. Виконаємо цикл редукування <math> p = \ rho (g) </ math>, поки значення другого коефіцієнта не стабілізується <math> b_ {i + 1} '= b_ {i}' </ math>. Число ітерацій <math> m </ math> цього циклу має бути приблизно дорівнює половині від числа ітерацій першого циклу. Останнє значення <math> a ^ \ prime </ math> дасть дільник числа <math> n </ math> (можливо тривіальний). === Реалізація алгоритму === Тепер опишемо алгоритм для реалізації на комп'ютері. {{Sfn | Ишмухаметов | 2011 | loc = Методи факторизації натуральних чисел: Навчальний посібник стор. 79-80 | name = Ишмухаметов Ш. Т.}} Відзначимо, що хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина алгоритму виконується на основі обчислення коефіцієнтів <math> P, Q, r </ math> методу неперервних дробів без звернення до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми. При необхідності можна відновити відповідні форми <math> f_k = (a_k, b_k, c_k) </ math> за формулами: <Math> (a_k, b_k, c_k) = ((- 1) ^ {k-1} Q_ {k-1}, 2P_k, (-1) ^ kQ_k) </ math> '' 'Вхід:' '' Складене число <math> n </ math> '' 'Вихід:' '' Нетривіальний дільник <math> n </ math> * '' Ініціалізація алгоритму. '' ** Перевіримо, чи є <math> n </ math> повним квадратом. Якщо так, то обчислимо <math> d = \ sqrt {n}, </ math> і завершимо обчислення. Інакше, перейдемо до наступного пункту. ** Якщо <math> n \ equiv 1 (mod 4), </ math> тоді замінимо <math> n </ math> на <math> 2n. </ Math> Визначимо <math> D = 4n, ~ q_0 = \ mathcal {b} \ sqrt {D} \ mathcal {c}. </ math> ** Визначимо вихідні значення параметрів <math> P, Q, r: </ math> <Math> P_0 = 0, ~ Q_0 = 1, ~ r_0 = P_1 = \ mathcal {b} \ sqrt {n} \ mathcal {c}, ~ Q_1 = n-r_0 ^ 2, r_1 = \ mathcal {b} 2r_0 / Q_1 \ mathcal {c}. </ math> * '' Перший цикл '' ** <math> 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 = \ mathcal {b} \ frac {P_k + \ mathcal {b} \ sqrt {n} \ mathcal {c}} {Q_k} \ mathcal {c}, ~ k \ ge 2. </ math> ** Продовжуємо обчислення коефіцієнтів <math> P_k, ~ Q_k ~ r_k </ math> до тих пір, поки не знайдемо Q_k, що є повним квадратом. Це повинно відбутися при деякому <math> k. </ Math> Нехай <math> Q_k = d ^ 2 </ math> для цілого <math> d> 0. </ Math> Перейдемо до наступного циклу. * '' Другий цикл. '' ** почнемо цикл обчислень нових параметрів <math> P_j ^ \ prime, ~ Q_j ^ \ prime, ~ r_j ^ \ prime. </ Math> Формули для реалізації другого циклу залишаться такими ж, як і раніше. Зміняться лише початкові значення параметрів <math> P ^ \ prime, ~ Q ^ \ prime, ~ r ^ \ prime: </ math> ** <math> P_0 ^ \ prime = -P_k, ~ Q_0 ^ \ prime = d, ~ r_0 ^ \ prime = \ mathcal {b} \ frac {P_0 ^ \ prime + \ mathcal {b} \ sqrt {n} \ mathcal {c}} {Q_0 ^ \ prime} \ mathcal {c}, ~ P_1 ^ \ prime = r_0 ^ \ prime \ cdot Q_0 ^ \ prime-P_0 ^ \ prime, ~ Q_1 ^ \ prime = (N-P_1 ^ {\ prime 2}) / Q_0 ^ \ prime. </ math> ** Обчислення слід продовжувати, поки два поспіль значення <math> P_j ^ \ prime, ~ P_ {j + 1} ^ \ prime </ math> не опиняться рівними. Тоді, значення <math> Q_j </ math> дасть шуканий дільник числа <math> n. </ Math> Опис алгоритму Шенкса закінчено. Як уже було згадано, це не єдина реалізація цього алгоритму. Так само реалізації алгоритму можна знайти тут {{sfn | SQUARE FORM FACTORIZATION | 2003 | loc = SQUARE FORM FACTORIZATION | name = Jason E. Gower and Samuel S. Wagstaff, JR.}} === Приклад факторизації числа === Застосуємо даний метод для факторизації числа <math> N = 22117019 </ math> {{sfn | SQUARE FORM FACTORIZATION | 2003 | loc = SQUARE FORM FACTORIZATION | name = Jason E. Gower and Samuel S. Wagstaff, JR.}} {| | {| border="1" class="wikitable" style="text-align:center; " !colspan="4" | Цикл №1 |- !colspan="4" |<math>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$
|}

 | || 
 | valign=top|

Цикл №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 }.$ Отже число $N=22117019=4451\cdot 4969.$

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

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

Література

• Василенко О. Н. {{{Заголовок}}}. — ISBN 5-94057-103-4.
• Ишмухаметов Ш. Т. {{{Заголовок}}}.
• D. A. Buell. ISBN 0-387-97037-1. {{cite book}}: Пропущений або порожній |title= (довідка); Проігноровано невідомий параметр |год= (довідка); Проігноровано невідомий параметр |заглавие= (довідка); Проігноровано невідомий параметр |издательство= (довідка); Проігноровано невідомий параметр |место= (довідка); Проігноровано невідомий параметр |ссылка= (довідка); Проігноровано невідомий параметр |страниц= (довідка); Проігноровано невідомий параметр |страницы= (довідка)
• Hans Riesel. {{{Заголовок}}}. — ISBN 978-0-8176-8297-2.
• Henri Cohen. ISBN 3-540-55640-0. {{cite book}}: Пропущений або порожній |title= (довідка); Проігноровано невідомий параметр |год= (довідка); Проігноровано невідомий параметр |заглавие= (довідка); Проігноровано невідомий параметр |издательство= (довідка); Проігноровано невідомий параметр |страниц= (довідка); Проігноровано невідомий параметр |страницы= (довідка)
• Jason E. Gower and Samuel S. Wagstaff, JR. {{{Заголовок}}}. — ISBN 5-94057-103-4.
• Samuel S. Wagstaff Jr. ISBN 978-1584881537. {{cite book}}: Пропущений або порожній |title= (довідка); Проігноровано невідомий параметр |год= (довідка); Проігноровано невідомий параметр |заглавие= (довідка); Проігноровано невідомий параметр |издательство= (довідка); Проігноровано невідомий параметр |страниц= (довідка)
• Yike Guo,R.L. Grossman. ISBN 0-7923-7745-1. {{cite book}}: Пропущений або порожній |title= (довідка); Проігноровано невідомий параметр |<ref>= (довідка); Проігноровано невідомий параметр |год= (довідка); Проігноровано невідомий параметр |заглавие= (довідка); Проігноровано невідомий параметр |издательство= (довідка); Проігноровано невідомий параметр |страницы= (довідка)