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

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

Історія  

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

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

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

Другий варіант — це власне SQUFOF (від ), у якому застосовується група квадратичних форм від двох змінних із позитивним дискримінантом. У ньому також відбувається пошук неоднозначної форми й розкладання дискримінанту на множники. Складність SQUFOF становить  арифметичних операцій. Особливістю алгоритму є те, що він працює з цілими числами, які не перевищують . На початку XX-го сторіччя SQUFOF вважався одним із найефективніших серед алгоритмів факторизації з експоненційною складністю.

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

Квадратичною формою двох змінних називають однорідний поліном від двох змінних  і :

 

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

Форму  називають скороченою (редукованою), якщо .

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

 
 

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

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

Теорема.

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

Неоднозначними () називають форми вигляду . Така неоднозначна форма існує для кожного дільника k дискримінанту ∆.

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

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

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

 1. Визначимо вихідну квадратичну форму , з дискримінантом , де .

 2. Виконаємо цикл редукування , поки форма  не стане квадратною.

 3. Обчислимо квадратний корінь з 

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

Реалізація алгоритму 
Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм, практична частина виконується на основі обчислення коефіцієнтів   без звертання до форм. Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми. За потреби можна відновити відповідні форми  за формулами:

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

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

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

 Перший цикл
 
 Продовжуємо обчислення коефіцієнтів  доти, доки не знайдемо Qk, що є повним квадратом. Це має статися за деякого  Нехай  для цілого  Перейдемо до наступного циклу.

 Другий цикл.
 почнемо цикл обчислень нових параметрів  Формули для реалізації другого циклу залишаться такими ж, як раніше. Зміняться лише початкові значення параметрів 
 
 Обчислення слід продовжувати, поки два поспіль значення  не стануть рівними. Тоді, значення  дасть шуканий дільник числа

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

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

Приклад факторизації числа 
Застосуємо цей метод для факторизації числа 

У другому циклі  Отже,  є дільником числа . Далі обчислюємо другий дільник:

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

Примітки

Джерела

Література 
 
 
  
 
  
  
 

Алгоритми факторизації
Метод квадратичних форм Шенкса — метод факторизації цілих чисел із застосуванням квадратичних форм , розроблений Даніелем Шенксом ( ) року на основі \ . На початку XX-го сторіччя програми длярозрядних комп'ютерів , засновані на цьому методі , були безумовними лідерами для факторизації чисел від до \ . Цей алгоритм може розкласти практично будь-яке складенезначне число швидше , ніж за мілісекунду . Методи , що базуються на цьому алгоритмі , застосовуються для розкладання на дільники великих чисел , типу чисел Ферма . Історія Хоча Шенкс описав інші алгоритми для факторизації цілих чисел , по SQUFOF він нічого не опублікував . Він прочитав лекції з цієї теми і пояснив основну суть свого методу досить невеликому колу людей . Після смерті Шенкса в його паперах знайшли незавершену чернетку з описом методу SQUFOF . Її оцифрували й опублікувалироку . Інші дослідники обговорювали алгоритм . У своєму методі Шенкс зробив деяку кількість припущень , які залишилися без доведення . Утім , результати експериментів свідчать , що більшість припущень справджуються . У підсумку , ґрунтуючись на цих спрощених припущеннях , Шенксу вдалося створити SQUFOF . Ідея методу Ідея методів Шенкса полягає в зіставленні числу , яке треба розкласти , квадратичної форми від двох змінних із дискримінантом , із якою потім виконується серія еквівалентних перетворень і перехід від форми до неоднозначної форми \ . Тоді , буде дільником \ . Перший варіант працює з додатноозначеними квадратичними формами від двох змінних заданого негативного дискримінанту і в групі форм він знаходить неоднозначну ( ) форму , яка дозволяє розкласти дискримінант на множники . Складність першого варіанту становить за умови істинності розширеної гіпотези Рімана . Другий варіант — це власне SQUFOF ( від ) , у якому застосовується група квадратичних форм від двох змінних із позитивним дискримінантом . У ньому також відбувається пошук неоднозначної форми й розкладання дискримінанту на множники . Складність SQUFOF становить арифметичних операцій . Особливістю алгоритму є те , що він працює з цілими числами , які не перевищують \ . На початку XX-го сторіччя SQUFOF вважався одним із найефективніших серед алгоритмів факторизації з експоненційною складністю . Допоміжні визначення Квадратичною формою двох змінних називають однорідний поліном від двох змінних і \ : У методі SQUFOF застосовуються тільки невизначені форми . Під розуміється дискримінант квадратичної форми \ . Квадратична форма представляє ціле число , якщо існують такі цілі числа , що виконується рівність : \. У разі , якщо в представленні , то таке представлення називають примітивним . Форму називають скороченою ( редукованою ) , якщо \ . Для будь-якої невизначеної квадратичної форми можна визначити оператор редукції : , де — ціле число , яке однозначно визначається умовами : Результат застосування оператора до форми разів записується у вигляді \ . Також визначено оператор як : , де визначений так само як і в попередньому випадку . У результаті застосування операторів і до квадратичної форми з дискримінантом , отримані квадратичні форми також матимуть дискримінант \ . Метод отримання скороченої форми , еквівалентної даній , знайшов ще Карл Гаусс і він полягає в послідовному застосуванні оператора редукції , поки не стане скороченою . Теорема . Для розуміння операцій з квадратичними формами потрібні поняття квадратних , суміжних і неоднозначних квадратичних форм . Неоднозначними ( ) називають форми вигляду \ . Така неоднозначна форма існує для кожного дільника k дискримінанту ∆ . Теоретичний опис Алгоритм може бути записаний в наступному вигляді : Вхід : Непарне складене число , яке потрібно факторизувати . Якщо замінимо на Тепер Остання властивість потрібна , щоб визначник квадратичної форми був фундаментальним , що забезпечує збіжність методу . Вихід : Нетривіальній дільник \ . Визначимо вихідну квадратичну форму , з дискримінантом , де \ . Виконаємо цикл редукування , поки форма не стане квадратною . Обчислимо квадратний корінь з Виконаємо цикл редукування , поки значення другого коефіцієнта не стабілізується \ . Кількість ітерацій цього циклу має становити приблизно половину від кількості ітерацій першого циклу . Останнє значення дасть дільник числа ( можливо , тривіальний ) . Реалізація алгоритму Хоча теоретична частина алгоритму пов'язана з еквівалентними перетвореннями квадратичних форм , практична частина виконується на основі обчислення коефіцієнтів без звертання до форм . Кожна ітерація циклу відповідає одній операції застосування оператора редукції до відповідної форми . За потреби можна відновити відповідні форми за формулами : Вхід : Складене число Вихід : Нетривіальний дільник ініціалізація алгоритму . Перевіримо , чи є повним квадратом . Якщо так , то обчислимо і завершимо обчислення . Інакше , перейдемо до наступного пункту . Якщо тоді замінимо на Визначимо Визначимо вихідні значення параметрів Перший цикл Продовжуємо обчислення коефіцієнтів доти , доки не знайдемо Qk , що є повним квадратом . Це має статися за деякого Нехай для цілого Перейдемо до наступного циклу . Другий цикл . почнемо цикл обчислень нових параметрів Формули для реалізації другого циклу залишаться такими ж , як раніше . Зміняться лише початкові значення параметрів Обчислення слід продовжувати , поки два поспіль значення не стануть рівними . Тоді , значення дасть шуканий дільник числа Оцінка збіжності Згідно з розрахунками , виконаними самим Шенксом , кількість ітерацій першого й другого циклів алгоритму визначається кількістю множників числа і дорівнює приблизно : де — константа , що дорівнює приблизно4 для першого циклу ітерацій . Приклад факторизації числа Застосуємо цей метод для факторизації числа У другому циклі Отже , є дільником числа \ . Далі обчислюємо другий дільник : Застосування Алгоритм застосовується в багатьох реалізаціях решета числового поля і квадратичного решета для факторизації невеликих чисел , що виникають під час факторизації великого цілого числа . У будь-якому випадку , SQUFOF застосовується в основному як допоміжний алгоритм у потужніших методах для факторизації чисел невеликого розміру , які не мають малих простих дільників . Як правило , такі числа є добутком кількох різних простих чисел . Примітки Джерела Література Алгоритми факторизації