Метод квадратичних форм Шенкса
Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. (листопад 2018) |
Метод квадратичних форм Шенкса — метод факторизації цілих чисел із застосуванням квадратичних форм, розроблений Даніелем Шенксом (англ. Daniel Shanks) 1975 року на основі методу ланцюгових дробів[en].
На початку XX-го сторіччя програми для 32-розрядних комп'ютерів, засновані на цьому методі, були безумовними лідерами для факторизації чисел від до [1]. Цей алгоритм може розкласти практично будь-яке складене 18-значне число швидше, ніж за мілісекунду. Методи, що базуються на цьому алгоритмі, застосовуються для розкладання на дільники великих чисел, типу чисел Ферма.
Історія[ред. | ред. код]
1975 року Даніель Шенкс створив алгоритм, який нині можна реалізувати й застосовувати не тільки на комп'ютері, а й на простому мобільному телефоні[джерело?]
Хоча Шенкс описав інші алгоритми для факторизації цілих чисел, по SQUFOF він нічого не опублікував. Він прочитав лекції з цієї теми і пояснив основну суть свого методу досить невеликому колу людей. Після смерті Шенкса в його паперах знайшли незавершену чернетку з описом методу SQUFOF. Її оцифрували й опублікували 2003 року[2]. Інші дослідники[3][4][5][6] обговорювали алгоритм. У своєму методі Шенкс зробив деяку кількість припущень[Прим. 1], які залишилися без доведення. Утім, результати експериментів свідчать, що більшість припущень справджуються[7]. У підсумку, ґрунтуючись на цих спрощених припущеннях, Шенксу вдалося створити SQUFOF.
Ідея методу[ред. | ред. код]
Ідея методів Шенкса полягає в зіставленні числу , яке треба розкласти, квадратичної форми від двох змінних із дискримінантом , із якою потім виконується серія еквівалентних перетворень і перехід від форми до неоднозначної форми . Тоді, буде дільником .
Перший варіант працює з додатноозначеними квадратичними формами від двох змінних заданого негативного дискримінанту і в групі форм він знаходить неоднозначну (англ. ambiguous) форму, яка дозволяє розкласти дискримінант на множники. Складність першого варіанту становить за умови істинності розширеної гіпотези Рімана[8].
Другий варіант — це власне SQUFOF (від англ. SQUare FOrm Factorization), у якому застосовується група квадратичних форм від двох змінних із позитивним дискримінантом. У ньому також відбувається пошук неоднозначної форми й розкладання дискримінанту на множники. Складність SQUFOF становить арифметичних операцій. Особливістю алгоритму є те, що він працює з цілими числами, які не перевищують . На початку XX-го сторіччя SQUFOF вважався одним із найефективніших серед алгоритмів факторизації з експоненційною складністю[8].
Допоміжні визначення[ред. | ред. код]
Квадратичною формою двох змінних називають однорідний поліном від двох змінних і :
У методі SQUFOF застосовуються тільки невизначені форми. Під розуміється дискримінант квадратичної форми . Квадратична форма представляє ціле число , якщо існують такі цілі числа , що виконується рівність: . У разі, якщо в представленні , то таке представлення називають примітивним.
Форму називають скороченою (редукованою), якщо .
Для будь-якої невизначеної квадратичної форми можна визначити оператор редукції:
- , де — ціле число , яке однозначно визначається умовами[9]:
Результат застосування оператора до форми разів записується у вигляді . Також визначено оператор як:
- , де визначений так само як і в попередньому випадку. У результаті застосування операторів і до квадратичної форми з дискримінантом , отримані квадратичні форми також матимуть дискримінант .
Метод отримання скороченої форми, еквівалентної даній, знайшов ще Карл Гаусс і він полягає в послідовному застосуванні оператора редукції , поки не стане скороченою.
Теорема.
|
Для розуміння операцій з квадратичними формами потрібні поняття квадратних, суміжних і неоднозначних квадратичних форм.
Неоднозначними (англ. ambiguous) називають форми вигляду . Така неоднозначна форма існує для кожного дільника k дискримінанту ∆[9].
Теоретичний опис[ред. | ред. код]
Алгоритм може бути записаний в наступному вигляді:[10]
Вхід: Непарне складене число , яке потрібно факторизувати. Якщо замінимо на Тепер Остання властивість потрібна, щоб визначник квадратичної форми був фундаментальним, що забезпечує збіжність методу.
Вихід: Нетривіальній дільник .
- 1. Визначимо вихідну квадратичну форму , з дискримінантом , де .
- 2. Виконаємо цикл редукування , поки форма не стане квадратною.
- 3. Обчислимо квадратний корінь з
- 4. Виконаємо цикл редукування , поки значення другого коефіцієнта не стабілізується . Кількість ітерацій цього циклу має становити приблизно половину від кількості ітерацій першого циклу. Останнє значення дасть дільник числа (можливо, тривіальний).
Реалізація алгоритму[ред. | ред. код]
Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина виконується на основі обчислення коефіцієнтів методу ланцюгових дробів[en] без звертання до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми[10]. За потреби можна відновити відповідні форми за формулами:
Вхід: Складене число
Вихід: Нетривіальний дільник
- ініціалізація алгоритму.
- Перевіримо, чи є повним квадратом. Якщо так, то обчислимо і завершимо обчислення. Інакше, перейдемо до наступного пункту.
- Якщо тоді замінимо на Визначимо
- Визначимо вихідні значення параметрів
- Перший цикл
- Продовжуємо обчислення коефіцієнтів доти, доки не знайдемо Qk, що є повним квадратом. Це має статися за деякого Нехай для цілого Перейдемо до наступного циклу.
- Другий цикл.
- почнемо цикл обчислень нових параметрів Формули для реалізації другого циклу залишаться такими ж, як раніше. Зміняться лише початкові значення параметрів
- Обчислення слід продовжувати, поки два поспіль значення не стануть рівними. Тоді, значення дасть шуканий дільник числа
Оцінка збіжності[ред. | ред. код]
Згідно з розрахунками, виконаними самим Шенксом, кількість ітерацій першого й другого циклів алгоритму визначається кількістю множників числа і дорівнює приблизно:
де — константа, що дорівнює приблизно 2,4 для першого циклу ітерацій.[11]
Приклад факторизації числа[ред. | ред. код]
Застосуємо цей метод для факторизації числа [12]
|
|
У другому циклі Отже, є дільником числа . Далі обчислюємо другий дільник:
Застосування[ред. | ред. код]
Алгоритм застосовується в багатьох реалізаціях решета числового поля і квадратичного решета для факторизації невеликих чисел, що виникають під час факторизації великого цілого числа. У будь-якому випадку, SQUFOF застосовується в основному як допоміжний алгоритм у потужніших методах для факторизації чисел невеликого розміру, які не мають малих простих дільників. Як правило, такі числа є добутком кількох різних простих чисел[12].
Примітки[ред. | ред. код]
- ↑ Наприклад, Припущення 4.5, що розклад вхідного числа N у добуток простих чисел не містить їх квадратів (SQUARE FORM FACTORIZATION, 2008, стор 556 (16 у pdf)), також у доведенні теорем про складність алгоритму та ін.
Джерела[ред. | ред. код]
- ↑ Yike Guo, 1999.
- ↑ Shanks, 2003.
- ↑ Henri Cohen, 1996, A Course in Computational Algebraic Number Theory..
- ↑ Hans Riesel, 1994, стор. 186—192.
- ↑ D. A. Buell, 1989, Binary Quadratic Forms.
- ↑ Samuel S. Wagstaff Jr., 2003.
- ↑ SQUARE FORM FACTORIZATION, 2008, стор. 559.
- ↑ а б Василенко, 2003, 75—76.
- ↑ а б SQUARE FORM FACTORIZATION, 2008, с. 553.
- ↑ а б Ішмухаметов, 2011, 79—80.
- ↑ Ішмухаметов, 2011, 82.
- ↑ а б SQUARE FORM FACTORIZATION, 2008, стор. ??.
Література[ред. | ред. код]
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 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.
|