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

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

Ідея

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

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

Приклад

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

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

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

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

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

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

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

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

випливає

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

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

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

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

Метод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

Вхід: натуральне число ${\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-гладкими):
        $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)}$ являє собою повний квадрат (усі степені в добутку — парні): 
    $\sum _{i\in T}{}a_{i}\equiv {\vec {0}}{\pmod {2}}$
    Обчислити: 
               $x:=\left(\prod _{i\in T}{}z_{i}\right){\pmod {N}}$
               $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)}$

Складність

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

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

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

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

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

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

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

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

Посилання

• 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 с.(рос.)