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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Історія[ред. | ред. код]

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

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

Допоміжні визначення[ред. | ред. код]

Для того щоб зрозуміти, як реалізований цей алгоритм, необхідно дізнатись мінімальні відомості про математичні об'єкти, використані в даному методі, а саме про квадратичні форми. Бінарною квадратичною формою називається поліном від двох змінних і :


В методі Шенкса використовуються тільки невизначені форми. Під будем розуміти дискримінант квадратичної форми. Будем говорити, що квадратична форма представляє ціле число , якщо існують такі цілі числа , що виконується рівність: . У разі якщо дана рівність , то її називають примітивною.

Для будь-якої невизначеною квадратичної форми можна визначити оператор редукції так:

,де  — визначено, як ціле число , однозначно визначається умовами: [9]

Результат застосування оператора до форми раз записується в вигляді . Також визначено оператор як:

, де визначений так само як і в попередньому випадку. Зауважимо, що в результаті застосування операторів і до квадратичної форми з дискримінантом , отримані квадратичні форми так само матимуть дискримінант .

Метод отримання скороченої форми, еквівалентний даній, був знайдений ще Карлом Гаусом і складається в послідовному застосуванні оператора редукції , поки не стане скороченою.

Теорема.

Кожна форма еквівалентна деякій скороченій формі, і будь-яка скорочена форма для рівна для деякого додатного . Якщо - скорочена, то також скорочена.

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

Варіанти[ред. | ред. код]

Ідея методу Шенкса складається в зіставленні числа , яке треба розкласти, до квадратичної бінарної форми з дискримінантом , з якої потім виконується серія еквівалентних перетворень і перехід від форми до неоднозначної форми . Тоді, буде дільником .

Перший варіант працює з позитивно певними бінарними квадратичними формами заданого негативного дискримінанту і в групі класів форм він знаходить форму, яка дозволяє розкладати дискримінант на множники. Складність першого варіанту становить за умови істинності розширеної гіпотезою Рімана.[10]

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

Оцінка збіжності[ред. | ред. код]

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

де — константа, рівна приблизно 2,4 для першого циклу ітерацій.[11]

Опис алгоритму[ред. | ред. код]

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

Вхід: Непарне складене число , яке потрібно факторизувати. Якщо замінимо на Тепер Остання властивість потрібна, щоб визначник квадратичної форми був фундаментальним, що забезпечує збіжність методу.

Вихід: Нетривіальній дільник .

1. Визначимо вихідну квадратичну форму , з дискримінантом , де .
2. Виконаємо цикл редукування , поки форма не стане квадратною.
3. Обчислимо квадратний корінь з
4. Виконаємо цикл редукування , поки значення другого коефіцієнта не стабілізується . Число ітерацій цього циклу має бути приблизно дорівнює половині від числа ітерацій першого циклу. Останнє значення дасть дільник числа (ймовірно тривіальний).

Реалізація алгоритму[ред. | ред. код]

Тепер опишемо алгоритм для реалізації на комп'ютері.[12] Відзначимо, що хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина алгоритму виконується на основі обчислення коефіцієнтів методу безперервних дробів без звернення до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми. При необхідності можна відновити відповідні форми по формулах:


Вхід: Складене число

Вихід: Нетривіальний дільник

  • ініціалізація алгоритму.
    • Перевіримо, чи є повним квадратом. Якщо та, то вичислимо і завершимо обчислення. Інакше, перейдемо до наступного пункту.
    • Якщо тоді замінимо на Визначимо
    • Визначимо вихідні значення параметрів

  • Перший цикл
    • Продовжуємо обчислення коефіцієнтів до тих пір, поки не знайдемо Q_k, що є повним квадратом. Це повинно відбутися при деякому Нехай для цілого Перейдемо до наступного циклу.
  • Другий цикл.
    • почнемо цикл обчислень нових параметрів Формули для реалізації другого циклу залишаться такими ж, як раніше. Зміняться лише початкові значення параметрів
    • Обчислення слід продовжувати, поки два поспіль значення не опиняться рівними. Тоді, значення дасть шуканий дільник числа Опис алгоритму Шенкса закінчено.

Як уже було згадано, це не єдина реалізація цього алгоритму. Так само реалізації алгоритму можна знайти тут [9]

Приклад факторизації числа[ред. | ред. код]

Використаємо даний метод для факторизації числа [9]

Цикл №1
Цикл №2

Тепер можна побачити в другому циклі, що Отже число

Застосування[ред. | ред. код]

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

Примітки[ред. | ред. код]

  1. Детальніше про історію цього метода і про його зв'язки з методом неперервних дробів можна дізнатись зі статі Говера и Вагстаффа (J. Gover, S.S. Wagstaff).
  2. Yike Guo, 1999, High Performance Data Mining: Scaling Algorithms, Applications and Systems.
  3. Hans Riesel, 1994, Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition
  4. Henri Cohen, тисячі дев'ятсот дев'яносто шість, A Course in Computational Algebraic Number Theory.
  5. Hans Riesel, тисячі дев'ятсот дев'яносто чотири, Prime Numbers and Computer Methods for Factorization. Birkhauser, second edition
  6. D. A. Buell, +1989, Binary Quadratic Forms
  7. Samuel S. Wagstaff Jr., 2003, Cryptanalysis of Number Theoretic Ciphers
  8. Наприклад в роботі SQUARE FORM FACTORIZATION JASON E. GOWER AND SAMUEL S. WAGSTAFF, JR. Assumption 4.12. на сторінці 20, Assumption 4.5 на сторінці 16, так само при доведенні теорем про складність алгоритму і т. д.
  9. а б в г д SQUARE FORM FACTORIZATION, 2003, SQUARE FORM FACTORIZATION
  10. а б Василенко, 2003, Теоретико-числові алгоритми в криптографії
  11. Ішмухаметов, 2011, Методи факторизації натуральних чисел: Навчальний посібник
  12. а б Ішмухаметов, 2011, Методи факторизації натуральних чисел: Навчальний посібник стр. 79-80

Література[ред. | ред. код]

  • Василенко О. Н. Теоретико-числові алгоритми в криптографії. — Москва : МЦНМО, 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.  (англ.)