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

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

Ідея

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

• У методі Ферма шукають числа, які задовольняють порівнянню $x^2-N=y^2$, але досить часто виникають пари $x_i^2-N=y_i$, в яких $y_i$ не є квадратом. Формально ці пари можна розглядати як порівняння $x_i^2\equiv y_i(\mathrm{mod}N)$.
• Крайчик відзначив, що такі пари можна множити між собою і в результаті отримати пару, яка задовольнятиме порівнянню $x^2\equiv y^2(\mathrm{mod}N)$Шаблон:Sfn.
• Якщо в такій парі $x\equiv ̸\pm y(\mathrm{mod}N)$, то найбільший спільний дільник чисел $(x-y)$ та $N$ буде нетривіальним дільником $N$.

Метод

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

Метод передбачає, що вхідне число $n$ є складеним. Цю умову можна досить швидко перевірити за допомогою ймовірнісних тестів простоти. Крім того, передбачається, що $n$ не являє собою степінь простого числа.
Також слід перевірити, що $n$ не ділиться на невеликі прості числаШаблон:Sfn.

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

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

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

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

У базовому варіанті, який запропонував Діксон, визначення гладкості числа $y_{i}modn=b_i$ здійснюється шляхом послідовного ділення на прості з факторної бази. Для кожного розкладеного $b_i=\prod _{p_k\in P}{p}_k^{a_{ik}}$ зберігають вектор показників степенів у його розкладі $a_i:=\{a_{i_1},a_{i_2},\dots ,a_{i_k}\}$Шаблон:Sfn.

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

На другому кроці зі знайдених розкладів $a_i$ потрібно скласти добуток, який буде повним квадратом.

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

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

Для чисел X та Y перевіряють умову: 1 < gcd(X ± Y, N) < N Шаблон:Sfn:

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

Імовірність успіху чи невдачі на цьому кроці оцінюється величиною 1/2Шаблон:Sfn, тому на практиці на першому кроці зазвичай шукають дещо більшу кількість гладких чисел — k+2, k+3, k+4…Шаблон:Sfn

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

Псевдокод

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

// Ініціалізація
Обрати межу просіювання $B$.
Укласти факторну базу з простих чисел до обраної межі: $P:=\{p_1,p_2,\dots ,p_k\}$, $p_k\le B$.

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

    У множині векторів $a_i$ знайти таку підмножину $T\subseteq \{1,2,\dots ,k+1\}$, що добуток $a_i(i\in T)$ являє собою повний квадрат (усі степені в добутку — парні): 
    $\sum _{i\in T}{a}_i\equiv \overrightarrow{0}(\mathrm{mod}2)$
    Обчислити: 
               $x:=\left(\prod _{i\in T}{z}_i\right)(\mathrm{mod}N)$
               $y:=\left(\prod _{p_j\in P}{p}_j^{\frac{\sum _{i\in T}{a}_{ij}}{2}}\right)(\mathrm{mod}N)$
while $x\equiv \pm y(\mathrm{mod}N)$ 

return $\gcd (x+y,N)$

Складність

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

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

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

  або $L_n[\frac{1}{2},2\sqrt{2}]$ в L-нотації

• $L_n[\frac{1}{2},2]$Шаблон:Sfn

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

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

Фактично, за схемою Діксона побудовано метод ланцюгових дробів (опублікований 1975 року), а також набагато потужніше квадратичне решето (1982). Однак, в обох згаданих методах замість випадкового вибору $x_i$ та послідовного ділення $(y_{i}modn)$ на елементи факторної бази застосовують інші шляхи побудови пар $(x_i,y_i)$ та пошуку в них гладких чисел $b_i$Шаблон:Sfn.

Посилання

• Шаблон:Cite article
• Шаблон:КнигаШаблон:Ref-ru
• Шаблон:КнигаШаблон:Ref-ru