Метод факторизації Діксона
Метод факторизації Діксона (або алгоритм Діксона) — імовірнісний алгоритм факторизації цілих чисел субекспоненційної складності. Алгоритм розробив Джон Діксон, математик Карлтонського університету (1979).
Метод заснований на ідеї Моріса Крайчика (Maurice Kraitchik), що узагальнює метод факторизації Ферма:
- У методі Ферма шукають числа, які задовольняють порівнянню , але досить часто виникають пари , в яких не є квадратом. Формально ці пари можна розглядати як порівняння .
- Крайчик відзначив, що такі пари можна множити між собою і в результаті отримати пару, яка задовольнятиме порівнянню [1].
- Якщо в такій парі , то найбільший спільний дільник чисел та буде нетривіальним дільником .
Якщо спробувати розкласти методом Ферма число , то на перших кроках отримаємо такі рівності:
Поміж перших різниць немає квадратів, втім, ці рівняння можна застосувати для розкладання . Хоча ні 32, ані 200 не є квадратами, однак квадратом є їх добуток: .
Отже з того, що:
- ,
- ,
випливає
- .
А оскільки
і , то число
Підготовчий крок
Метод передбачає, що вхідне число є складеним. Цю умову можна досить швидко перевірити за допомогою ймовірнісних тестів простоти. Крім того, передбачається, що не являє собою степінь простого числа[Прим. 1].
Також слід перевірити, що не ділиться на невеликі прості числа[2].
Перший крок методу Діксона полягає в пошуку таких пар чисел , у яких розкладається в добуток невеликих простих[Прим. 2] (такі числа називають гладкими).
Межу гладкості (найбільше просте в розкладі) визначають величиною [3], де:
- — параметр методу, що визначається з міркувань оптимізації . У базовому варіанті цей параметр дорівнює 1/2.
Множину простих чисел, які лежать у проміжку , називають факторною базою. Кількість простих у факторній базі () — її розмір.
У базовому варіанті, який запропонував Діксон, визначення гладкості числа здійснюється шляхом послідовного ділення на прості з факторної бази. Для кожного розкладеного зберігають вектор показників степенів у його розкладі [4].
Після того, як знайдено щонайменше k+1 гладких чисел (на одне більше, ніж розмір факторної бази), переходять до другого кроку.
На другому кроці зі знайдених розкладів потрібно скласти добуток, який буде повним квадратом.
Для повного квадрата всі показники степенів мають бути парними, отже, по модулю два вони будуть нульовими. Тож замість показників степенів розглядають їх залишки по модулю два. Оскільки вектори розміру k над полем F2 утворюють векторний простір, то множина з к+1 векторів буде лінійно залежною, і в ній існує нетривіальна комбінація, яка дорівнює нульовому вектору. Коефіцієнти такої лінійної комбінації шукають як розв'язання системи лінійних рівнянь, наприклад, методом Гаусса. Усі знайдені коефіцієнти дорівнюватимуть одиниці або нулю, тобто, відповідний вектор або входить у склад добутку, або ні[1].
На третьому кроці зі знайдених пар будують добутки X та Y, такі, що .
Для чисел X та Y перевіряють умову: 1 < gcd(X ± Y, N) < N [5]:
- Якщо умова виконана, то числа та являють собою нетривіальні дільники числа N.
- Якщо ж умова не виконується, слід продовжити пошук нових гладких чисел (повернутися на перший крок).
Імовірність успіху чи невдачі на цьому кроці оцінюється величиною 1/2[Прим. 1][2], тому на практиці на першому кроці зазвичай шукають дещо більшу кількість гладких чисел — k+2, k+3, k+4…[6]
Вхід: натуральне число Вихід: нетривіальний дільник // Ініціалізація Обрати межу просіювання . Укласти факторну базу з простих чисел до обраної межі: , . repeat for to do Серед чисел знайти таке, квадрат якого по модулю повністю розкладається на множники факторної бази (такі числа називають B-гладкими): Запам'ятати та відповідний вектор степенів у розкладі: end for У множині векторів знайти таку підмножину , що добуток являє собою повний квадрат (усі степені в добутку — парні): Обчислити: while return
Цей розділ потребує доповнення. |
Сам Діксон оцінив асимптотичну складність методу величиною [7].
У подальших дослідженнях його оцінку дещо поліпшили, зокрема, за рахунок того, що матриця, яка виникає на другому кроці, є розрідженою й для розв'язку СЛАУ можна застосувати методи, швидші за стандартний метод Гаусса[8]:
- у нотації Ландау
- або в L-нотації
- [9]
Метод Діксона являє собою доволі зручну модель для отримання теоретичних оцінок складності без застосування недоведених гіпотез чи евристик. Втім, на практиці він майже не застосовується[9]. Хоча метод потужніший за більшість раніше відомих, однак послідовне ділення на елементи факторної бази (для пошуку гладких чисел) триває довго, а оскільки ця частина є найбільш витратною, то алгоритм виявляється надто повільним[10].
Фактично, за схемою Діксона побудовано метод ланцюгових дробів (опублікований 1975 року), а також набагато потужніше квадратичне решето (1982). Однак, в обох згаданих методах замість випадкового вибору та послідовного ділення на елементи факторної бази застосовують інші шляхи побудови пар та пошуку в них гладких чисел [9].
Цей розділ потребує доповнення. |
- ↑ а б Метод Діксона (як і інші методи із застосуванням факторних баз) неефективний для факторизації чисел, що являють собою степінь простого числа . Такі числа вельми рідкісні.
- ↑ Спосіб побудови пар метод не визначає — їх значення вважаються випадковими. Наприклад, можна брати послідовні , починаючи з , як у методі Ферма.
- ↑ а б Ишмухаметов, 2011, 4.1. Идея Мориса Крейтчика и алгоритм Диксона (115—117).
- ↑ а б Василенко, 2003, с. 77.
- ↑ Василенко, 2003, § 3.2. Метод Диксона (78—79).
- ↑ Василенко, 2003, с. 80.
- ↑ Василенко, 2003, с. 79.
- ↑ Ишмухаметов, 2011, с. 118.
- ↑ Dixon, 1981, с. 257.
- ↑ 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=
(довідка) - ↑ а б в Василенко, 2003, с. 83.
- ↑ Ишмухаметов, 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 с.(рос.)