Метод факторизації Діксона

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

Ідея

Метод заснований на ідеї Моріса Крайчика (Maurice Kraitchik), що узагальнює метод факторизації Ферма:

• У методі Ферма шукають числа, які задовольняють порівнянню ${\displaystyle x^{2}-N=y^{2}}$, але досить часто виникають пари ${\displaystyle x_{i}^{2}-N=y_{i}}$, в яких ${\displaystyle y_{i}}$ не є квадратом. Формально ці пари можна розглядати як порівняння ${\displaystyle x_{i}^{2}\equiv y_{i}{\pmod {N}}}$.
• Крайчик відзначив, що такі пари можна множити між собою і в результаті отримати пару, яка задовольнятиме порівнянню ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$^[1].
• Якщо в такій парі ${\textstyle x\not \equiv \pm y{\pmod {N}}}$, то найбільший спільний дільник чисел ${\displaystyle (x-y)}$ та ${\displaystyle N}$ буде нетривіальним дільником ${\displaystyle N}$.

Приклад

Якщо спробувати розкласти методом Ферма число ${\displaystyle n=1649}$, то на перших кроках отримаємо такі рівності:

${\displaystyle 41^{2}-1649=32,}$

${\displaystyle 42^{2}-1649=115,}$

${\displaystyle 43^{2}-1649=200,}$

Поміж перших різниць немає квадратів, втім, ці рівняння можна застосувати для розкладання ${\displaystyle n}$. Хоча ні 32, ані 200 не є квадратами, однак квадратом є їх добуток: ${\displaystyle 32\times 200=6400=80^{2}}$.

Отже з того, що:

${\displaystyle 41^{2}\equiv 32{\pmod {n}}}$,

${\displaystyle 43^{2}\equiv 200{\pmod {n}}}$,

випливає

${\displaystyle (41\times 43)^{2}\equiv 80^{2}{\pmod {n}}}$.

А оскільки ${\displaystyle 41\times 43{\pmod {1649}}=1763{\pmod {1649}}=114}$
і ${\displaystyle 114\neq \pm 80{\pmod {1649}}}$, то число

${\displaystyle \gcd(41\times 43-80,1649)=\gcd(1683,1649)=17}$

має бути нетривіальним дільником ${\displaystyle 1649}$, у чому просто переконатися: ${\displaystyle 1649/17=97}$.

Метод

Підготовчий крок

Метод передбачає, що вхідне число ${\displaystyle n}$ є складеним. Цю умову можна досить швидко перевірити за допомогою ймовірнісних тестів простоти. Крім того, передбачається, що ${\displaystyle n}$ не являє собою степінь простого числа^{[Прим. 1]}.
Також слід перевірити, що ${\displaystyle n}$ не ділиться на невеликі прості числа^[2].

Перший крок методу Діксона полягає в пошуку таких пар чисел ${\displaystyle x_{i}^{2}\equiv y_{i}{\pmod {n}}}$, у яких ${\displaystyle y_{i}\mod n}$ розкладається в добуток невеликих простих^{[Прим. 2]} (такі числа називають гладкими).

Межу гладкості ${\displaystyle B}$ (найбільше просте в розкладі) визначають величиною ${\displaystyle L^{\alpha }}$^[3], де:

• ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$
• ${\displaystyle \alpha }$ — параметр методу, що визначається з міркувань оптимізації ${\displaystyle (0<\alpha <1)}$. У базовому варіанті цей параметр дорівнює 1/2.

Множину простих чисел, які лежать у проміжку ${\displaystyle \left[2\leq p_{k}\leq L^{\alpha }\right]}$, називають факторною базою. Кількість простих у факторній базі (${\displaystyle k}$) — її розмір.

У базовому варіанті, який запропонував Діксон, визначення гладкості числа ${\displaystyle y_{i}\mod n=b_{i}}$ здійснюється шляхом послідовного ділення на прості з факторної бази. Для кожного розкладеного ${\displaystyle b_{i}=\prod _{p_{k}\in P}{}p_{k}^{a_{ik}}}$ зберігають вектор показників степенів у його розкладі ${\textstyle a_{i}:=\{a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{k}}\}}$^[4].

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

На другому кроці зі знайдених розкладів ${\textstyle a_{i}}$ потрібно скласти добуток, який буде повним квадратом.

Для повного квадрата всі показники степенів мають бути парними, отже, по модулю два вони будуть нульовими. Тож замість показників степенів розглядають їх залишки по модулю два. Оскільки вектори розміру k над полем F₂ утворюють векторний простір, то множина з к+1 векторів буде лінійно залежною, і в ній існує нетривіальна комбінація, яка дорівнює нульовому вектору. Коефіцієнти такої лінійної комбінації шукають як розв'язання системи лінійних рівнянь, наприклад, методом Гаусса. Усі знайдені коефіцієнти дорівнюватимуть одиниці або нулю, тобто, відповідний вектор або входить у склад добутку, або ні^[1].

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

Для чисел X та Y перевіряють умову: 1 < gcd(X ± Y, N) < N ^[5]:

• Якщо умова виконана, то числа ${\displaystyle \gcd(X+Y,N)}$ та ${\displaystyle \gcd(X-Y,N)}$ являють собою нетривіальні дільники числа N.
• Якщо ж умова не виконується, слід продовжити пошук нових гладких чисел (повернутися на перший крок).

Імовірність успіху чи невдачі на цьому кроці оцінюється величиною 1/2^{[Прим. 1][2]}, тому на практиці на першому кроці зазвичай шукають дещо більшу кількість гладких чисел — k+2, k+3, k+4…^[6]

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

Псевдокод

Вхід: натуральне число ${\textstyle N}$
Вихід: нетривіальний дільник ${\textstyle N}$

// Ініціалізація
Обрати межу просіювання ${\textstyle B}$.
Укласти факторну базу з простих чисел до обраної межі: ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$, ${\textstyle p_{k}\leq B}$.

repeat
    for ${\textstyle i=1}$ to ${\textstyle k+1}$ do
        Серед чисел ${\textstyle 0<z_{i}<N}$ знайти таке, квадрат якого по модулю ${\textstyle N}$ повністю розкладається на множники факторної бази (такі числа називають B-гладкими):
        ${\displaystyle z_{i}^{2}{\pmod {N}}=\prod _{p_{j}\in P}{}p_{j}^{a_{ij}}}$
        Запам'ятати ${\textstyle z_{i}}$ та відповідний вектор ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ степенів ${\textstyle p_{k}}$ у розкладі: 
        
    end for

    У множині векторів ${\textstyle a_{i}}$ знайти таку підмножину ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$, що добуток ${\textstyle a_{i}(i\in T)}$ являє собою повний квадрат (усі степені в добутку — парні): 
    ${\displaystyle \sum _{i\in T}{}a_{i}\equiv {\vec {0}}{\pmod {2}}}$
    Обчислити: 
               ${\displaystyle x:=\left(\prod _{i\in T}{}z_{i}\right){\pmod {N}}}$
               ${\displaystyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\frac {\sum _{i\in T}{}a_{ij}}{2}}\right){\pmod {N}}}$
while ${\textstyle x\equiv \pm y{\pmod {N}}}$ 

return ${\textstyle \gcd(x+y,N)}$

Приклад

Складність

Сам Діксон оцінив асимптотичну складність методу величиною ${\displaystyle O\left(\exp \left(2{\sqrt {3}}{\sqrt {\log n\log \log n}}\right)\right)}$^[7].

У подальших дослідженнях його оцінку дещо поліпшили, зокрема, за рахунок того, що матриця, яка виникає на другому кроці, є розрідженою й для розв'язку СЛАУ можна застосувати методи, швидші за стандартний метод Гаусса^[8]:

• ${\displaystyle O\left(\exp \left(2{\sqrt {2}}{\sqrt {\log n\log \log n}}\right)\right)}$ у нотації Ландау

  або ${\displaystyle L_{n}\left[{\frac {1}{2}},2{\sqrt {2}}\right]}$ в L-нотації

• ${\displaystyle L_{n}\left[{\frac {1}{2}},2\right]}$^[9]

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

Метод Діксона являє собою доволі зручну модель для отримання теоретичних оцінок складності без застосування недоведених гіпотез чи евристик. Втім, на практиці він майже не застосовується^[9]. Хоча метод потужніший за більшість раніше відомих, однак послідовне ділення на елементи факторної бази (для пошуку гладких чисел) триває довго, а оскільки ця частина є найбільш витратною, то алгоритм виявляється надто повільним^[10].

Фактично, за схемою Діксона побудовано метод ланцюгових дробів (опублікований 1975 року), а також набагато потужніше квадратичне решето (1982). Однак, в обох згаданих методах замість випадкового вибору ${\displaystyle x_{i}}$ та послідовного ділення ${\displaystyle (y_{i}\mod n)}$ на елементи факторної бази застосовують інші шляхи побудови пар ${\displaystyle (x_{i},y_{i})}$ та пошуку в них гладких чисел ${\displaystyle b_{i}}$^[9].

Варіанти оптимізації

Примітки

1. Метод Діксона (як і інші методи із застосуванням факторних баз) неефективний для факторизації чисел, що являють собою степінь простого числа ${\displaystyle n=p^{m}}$. Такі числа вельми рідкісні.
2. Спосіб побудови пар ${\displaystyle x_{i}^{2}\equiv y_{i}{\pmod {N}}}$ метод не визначає — їх значення вважаються випадковими. Наприклад, можна брати послідовні ${\displaystyle x_{i}}$, починаючи з ${\displaystyle \lceil {\sqrt {n}}\rceil }$, як у методі Ферма.

Джерела

1. Ишмухаметов, 2011, 4.1. Идея Мориса Крейтчика и алгоритм Диксона (115—117).
2. Василенко, 2003, с. 77.
3. Василенко, 2003, § 3.2. Метод Диксона (78—79).
4. Василенко, 2003, с. 80.
5. Василенко, 2003, с. 79.
6. Ишмухаметов, 2011, с. 118.
7. Dixon, 1981, с. 257.
8. Manindra Agrawal (30 вересня 2005). Notes by: Ashwini Aroskar (ред.). CS 681: Computational Number Theory and Algebra (PDF). Indian Institute of Technology Kanpur. Архів оригіналу (PDF) за 27 вересня 2007. Процитовано 13 липня 2019. {{cite web}}: Проігноровано |chapter= (довідка)
9. Василенко, 2003, с. 83.
10. Ишмухаметов, 2011, с. 117.

Посилання

• Dixon John D. Asymptotically fast factorization of integers : Received September 5, 1979 // Mathematics of Computation. — 1981. — Т. 36. — С. 255—260.
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 2003. — С. 78—79. — 1000 прим. — ISBN 5-94057-103-4.(рос.)
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казанский университет, 2011. — 190 с.(рос.)