Перегляд вихідного коду сторінки Метод факторизації Діксона

'''Метод факторизації Діксона''' (або '''алгоритм Діксона''') — імовірнісний [[алгоритм]] [[факторизація цілих чисел|факторизації цілих чисел]] субекспоненційної [[Обчислювальна складність|складності]].
Алгоритм розробив [[Джон Діксон]], математик [[Карлтонський університет|Карлтонського університету]] (1979).

== Ідея ==
Метод заснований на ідеї Моріса Крайчика (Maurice Kraitchik), що узагальнює [[метод факторизації Ферма]]:
* У методі Ферма шукають числа, які задовольняють порівнянню <math>x^2 - N = y^2</math>, але досить часто виникають пари <math>x_i^2 - N = y_i</math>, в яких <math>y_i</math> не є [[Квадрат (алгебра)|квадратом]]. Формально ці пари можна розглядати як порівняння <math>x_i^2 \equiv y_i \pmod{N}</math>.
* Крайчик відзначив, що такі пари можна множити між собою і в результаті отримати пару, яка задовольнятиме порівнянню <math>x^2 \equiv y^2 \pmod{N}</math>{{sfn|Ишмухаметов|2011|loc=4.1. Идея Мориса Крейтчика и алгоритм Диксона (115—117)}}. 
* Якщо в такій парі <math display="inline">x \not\equiv \pm y \pmod{N}</math>, то [[найбільший спільний дільник]] чисел <math>(x - y)</math> та <math>N</math> буде нетривіальним дільником <math>N</math>.
{{Hidden
|header= Приклад
|titlestyle = border:1px solid black;color:blue
|content=
Якщо спробувати розкласти методом Ферма число <math>n = 1649</math>, то на перших кроках отримаємо такі рівності:
:<math>41^2 - 1649 = 32,</math>
:<math>42^2 - 1649 = 115,</math>
:<math>43^2 - 1649 = 200,</math>
Поміж перших різниць немає квадратів, втім, ці рівняння можна застосувати для розкладання <math>n</math>. Хоча ні 32, ані 200 не є квадратами, однак '''квадратом є їх добуток''': <math>32 \times 200 = 6400 = 80^2</math>. 

Отже з того, що: 
:<math>41^2 \equiv 32 \pmod n</math>,
:<math>43^2 \equiv 200 \pmod n</math>,
випливає 
:<math>(41\times 43)^2 \equiv 80^2 \pmod n</math>.

А оскільки <math>41\times 43 \pmod{1649} = 1763 \pmod{1649}= 114</math>
<br/>і <math>114 \ne \pm 80 \pmod{1649}</math>, то число 
:<math>\gcd (41\times 43 - 80, 1649) = \gcd (1683, 1649) = 17</math>
має бути нетривіальним дільником <math>1649</math>, у чому просто переконатися: <math>1649 / 17 = 97</math>.
}}
== Метод ==
'''Підготовчий крок'''

Метод передбачає, що вхідне число <math>n</math> є [[Складене число|складеним]]. Цю умову можна досить швидко перевірити за допомогою [[тест простоти#Імовірнісні тести|ймовірнісних тестів простоти]]. Крім того, передбачається, що <math>n</math> не являє собою степінь простого числа<ref name="Степінь простого" group="Прим.">Метод Діксона (як і інші методи із застосуванням факторних баз) неефективний для факторизації чисел, що являють собою степінь простого числа <math>n = p^m</math>. Такі числа вельми рідкісні.</ref>.<br/>Також слід перевірити, що <math>n</math> не ділиться на невеликі прості числа{{sfn|Василенко|2003|с=77}}.

'''Перший крок''' методу Діксона полягає в пошуку таких пар чисел <math>x_i^2 \equiv y_i \pmod n</math>, у яких <math>y_i \mod n</math> розкладається в добуток невеликих простих<ref group="Прим.">Спосіб побудови пар <math>x_i^2 \equiv y_i \pmod{N}</math> метод не визначає — їх значення вважаються випадковими. Наприклад, можна брати послідовні <math>x_i</math>,  починаючи з <math>\lceil \sqrt{n} \rceil</math>, як у [[Метод факторизації Ферма|методі Ферма]].</ref> (такі числа називають [[Гладке число|гладкими]]). 

Межу гладкості <math>B</math> (найбільше просте в розкладі) визначають величиною <math>L^\alpha</math>{{sfn|Василенко|2003|loc=§ 3.2. Метод Диксона (78—79)}}, де: 
*<math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}</math>
* <math>\alpha</math> — параметр методу, що визначається з міркувань оптимізації <math>(0< \alpha <1)</math>. У базовому варіанті цей параметр дорівнює 1/2.
Множину простих чисел, які лежать у проміжку <math>\left [ 2 \le p_k \le L^\alpha \right ]</math>, називають ''факторною базою''. Кількість простих у факторній базі (<math>k</math>) — її розмір.

У базовому варіанті, який запропонував Діксон, визначення гладкості числа <math>y_i \mod n = b_i</math> здійснюється шляхом послідовного ділення на прості з факторної бази.  Для кожного розкладеного <math>b_i = \prod_{p_k \in P}{} p_k^{a_{ik}}</math> зберігають вектор показників [[Степінь|степенів]] у його розкладі <math display="inline">a_i := \{a_{i_1}, a_{i_2}, \ldots, a_{i_k}\}</math>{{sfn|Василенко|2003|с=80}}.

Після того, як знайдено щонайменше k+1 гладких чисел (на одне більше, ніж розмір факторної бази), переходять до другого кроку.

'''На другому кроці''' зі знайдених розкладів <math display="inline">a_i</math> потрібно скласти добуток, який буде повним квадратом.

Для повного квадрата всі показники степенів мають бути парними, отже, [[Модульна арифметика|по модулю два]] вони будуть нульовими. Тож замість показників степенів розглядають їх залишки по модулю два. Оскільки вектори розміру k над [[поле Галуа#Поле з двох елементів|полем F<sub>2</sub>]] утворюють [[векторний простір]], то множина з к+1 векторів буде лінійно залежною, і в ній існує [[Лінійна комбінація|нетривіальна комбінація]], яка дорівнює нульовому вектору. Коефіцієнти такої лінійної комбінації шукають як розв'язання [[Система лінійних алгебраїчних рівнянь|системи лінійних рівнянь]], наприклад, [[Метод Гауса|методом Гаусса]]. Усі знайдені коефіцієнти дорівнюватимуть одиниці або нулю, тобто, відповідний вектор або входить у склад добутку, або ні{{sfn|Ишмухаметов|2011|loc=4.1. Идея Мориса Крейтчика и алгоритм Диксона (115—117)}}.

'''На третьому кроці''' зі знайдених пар будують добутки X та Y, такі, що <math>X^2 \equiv Y^2 \pmod{N}</math>. 

Для чисел X та Y перевіряють умову: ''1 < [[Найбільший спільний дільник|gcd]](X ± Y, N) < N'' {{sfn|Василенко|2003|с=79}}: 
* Якщо умова виконана, то числа <math>\gcd (X + Y, N)</math> та <math>\gcd (X - Y, N)</math> являють собою нетривіальні дільники числа N.
* Якщо ж умова не виконується, слід продовжити пошук нових гладких чисел (повернутися на перший крок).

Імовірність успіху чи невдачі на цьому кроці оцінюється величиною 1/2<ref name="Степінь простого" group="Прим."></ref>{{sfn|Василенко|2003|с=77}}, тому на практиці на першому кроці зазвичай шукають дещо більшу кількість гладких чисел — k+2, k+3, k+4…{{sfn|Ишмухаметов|2011|с=118}}

== Базовий алгоритм ==

=== Псевдокод ===
 '''Вхід:''' натуральне число <math display="inline">N</math>
 '''Вихід:''' нетривіальний дільник <math display="inline">N</math>
 
 // Ініціалізація
 Обрати межу просіювання <math display="inline">B</math>.
 Укласти ''факторну базу'' з [[просте число|простих чисел]] до обраної межі: <math display="inline">P := \{p_1, p_2, \ldots, p_k\}</math>, <math display="inline">p_k \leq B</math>.
 
 '''repeat'''
     '''for''' <math display="inline">i=1</math> '''to''' <math display="inline">k+1</math> '''do'''
         Серед чисел <math display="inline">0<z_i<N</math> знайти таке, квадрат якого по модулю <math display="inline">N</math> повністю розкладається на множники факторної бази (такі числа називають [[Гладке число|B-гладкими]]):
         <math>z_i^2 \pmod{N} = \prod_{p_j \in P}{} p_j^{a_{ij}}</math>
         Запам'ятати <math display="inline">z_i</math> та відповідний вектор <math display="inline">a_i := \{a_{i1}, a_{i2}, \ldots, a_{ik}\}</math> степенів <math display="inline">p_k</math> у розкладі: 
         
     '''end for'''
 
     У множині векторів <math display="inline">a_i</math> знайти таку підмножину <math display="inline">T \subseteq \{1, 2, \ldots, k+1\}</math>, що добуток <math display="inline">a_i (i \in T)</math> являє собою повний квадрат (усі степені в добутку — парні): 
     <math>\sum_{i \in T}{} a_i \equiv \vec{0} \pmod{2}</math>
     Обчислити: 
                <math>x := \left(\prod_{i \in T}{} z_i\right) \pmod{N}</math>
                <math>y := \left(\prod_{p_j \in P} p_j^{\frac{\sum_{i \in T}{} a_{ij}}{2}} \right) \pmod{N}</math>
 '''while''' <math display="inline">x \equiv \pm y \pmod{N}</math> 
 
 '''return''' <math display="inline">\gcd(x+y, N)</math>


=== Приклад ===
{{Розширити розділ}}

=== Складність ===
Сам Діксон оцінив [[обчислювальна складність|асимптотичну складність]] методу величиною <math>O\left(\exp\left(2 \sqrt 3 \sqrt{\log n \log \log n}\right)\right)</math>{{sfn|Dixon|1981|p=257}}.

У подальших дослідженнях його оцінку дещо поліпшили, зокрема, за рахунок того, що матриця, яка виникає на другому кроці, є [[Розріджена матриця|розрідженою]] й для розв'язку [[Система лінійних алгебраїчних рівнянь|СЛАУ]] можна застосувати методи, швидші за стандартний метод Гаусса<ref>{{cite web |url= http://www.cse.iitk.ac.in/users/manindra/CS681/Lecture23.pdf |title= CS 681: Computational Number Theory and Algebra |chapter= Lecture 23. Time Complexity of Dixon’s Algorithm |author= Manindra Agrawal |editor= Notes by: Ashwini Aroskar |date= 30 вересня 2005 |publisher= Indian Institute of Technology Kanpur|accessdate= 2019-07-13 |archive-date= 2007-09-27 |archive-url= https://web.archive.org/web/20070927184419/http://www.cse.iitk.ac.in/users/manindra/CS681/Lecture23.pdf }}</ref>:
* <math>O\left(\exp\left(2 \sqrt 2 \sqrt{\log n \log \log n}\right)\right)</math> у [[Нотація Ландау|нотації Ландау]] 
*: або <math>L_n \left [ \frac{1}{2}, 2 \sqrt 2 \right ]</math> в [[L-нотація|L-нотації]]
* <math>L_n \left [ \frac{1}{2}, 2 \right ]</math>{{sfn|Василенко|2003|с=83}}

== Застосування ==
Метод Діксона являє собою доволі зручну модель для отримання теоретичних оцінок складності без застосування недоведених гіпотез чи [[Евристичний алгоритм|евристик]]. Втім, на практиці він майже не застосовується{{sfn|Василенко|2003|с=83}}.
Хоча метод потужніший за більшість раніше відомих, однак послідовне ділення на елементи факторної бази (для пошуку [[Гладке число|гладких чисел]]) триває довго, а оскільки ця частина є найбільш витратною, то алгоритм виявляється надто повільним{{sfn|Ишмухаметов|2011|с=117}}.

Фактично, за схемою Діксона побудовано [[метод ланцюгових дробів]] (опублікований 1975 року), а також набагато потужніше [[квадратичне решето]] (1982). Однак, в обох згаданих методах замість випадкового вибору <math>x_i</math> та послідовного ділення <math>(y_i \mod n)</math> на елементи факторної бази застосовують інші шляхи побудови пар <math>( x_i , y_i )</math> та пошуку в них гладких чисел <math>b_i</math>{{sfn|Василенко|2003|с=83}}.

== Варіанти оптимізації ==
{{Розширити розділ}}

== Примітки ==
{{reflist|group=Прим.}}

== Джерела ==
{{reflist|refs=}}

== Посилання ==
* {{cite article|first= John D. |last=Dixon |title= Asymptotically fast factorization of integers |journal= Mathematics of Computation |volume= 36 |year= 1981 |pages= 255—260
|url=https://www.ams.org/mcom/1981-36-153/S0025-5718-1981-0595059-1/S0025-5718-1981-0595059-1.pdf |відомості = Received September 5, 1979
|ref=Dixon
}}
* {{книга
 |автор         = Василенко О. Н.
 |назва         = Теоретико-числовые алгоритмы в криптографии
 |посилання     = http://www.ict.edu.ru/ft/002416/book.pdf
 |місто         = Москва
 |видавництво   = [[Московський центр неперервної математичної освіти|МЦНМО]]
 |рік           = 2003
 |сторінок      = 326
 |сторінки      = 78—79
 |наклад        = 1000
 |ref           = Василенко
 |isbn          = 5-94057-103-4
}}{{ref-ru}}
* {{книга
 |автор         = Ишмухаметов Ш. Т.
 |заголовок     = Методы факторизации натуральных чисел: учебное пособие
 |посилання     = http://window.edu.ru/resource/980/73980/files/Monograph_ishm.pdf
 |місто         = Казань
 |видавництво   = [[Казанський федеральний університет|Казанский университет]]
 |рік           = 2011
 |сторінок      = 190
 |ref           = Ишмухаметов
}}{{ref-ru}}

{{Алгоритми теорії чисел}}

[[Категорія:Алгоритми факторизації]]
[[Категорія:Квадрати в теорії чисел]]