Факторизация целых чисел с экспоненциальной сложностью

     Итак, мы достигнем в алгоритме точки (x_k, y_k) = (u, v), получим значение r_k = 0 и найдем a = u −v, что и требовалось доказать.

 

(P− 1)-метод Полларда. 

     Он  основан на следующей идее. Допустим, что у числа n, которое мы хотим разложить на множители, есть простой делитель p такой, что число p − 1 является B-степенно-гладким для некоторой границы гладкости        B > 0. Это означает, что для любого простого числа q, q | p − 1,

выполнено неравенство 

q^{vq (p−1)} ≤B. 

Отсюда  следует, что p − 1 |НОК(1, 2, . . . , B). Если мы выберем a ∈ N такое, что (a, n) = 1, то по малой теореме Ферма 

a^{НОК(1,2,. . . ,B)} ≡1 (mod p). 

Следовательно, НОД(a^{НОК(1,2,. . . ,B)} − 1, n) делится на p и поэтому содержит нетривиальный делитель n (НОД может быть и равен n). 

1 стадия (P −1)-метода Полларда.

     В (P − 1)-методе Полларда мы выбираем априорную границу гладкости B, исходя из возможностей нашего компьютера и времени, которое мы рассчитываем потратить. Обычно B = 10⁵—10⁶. Далее составляем таблицу q₁ < q₂ < ...< q_k ≤ B всех простых чисел, не превосходящих B, и для каждого q_i полагаем 

, т.е. q_i^β(qi)≤B, q_i^β(qi)+1>B 

Далее мы выбираем значение a (например, a= 2). Затем последовательными возведениями в степень и приведениями по модулю n вычисляем 

 

(параметр 20 также априорный). Далее вычисляем НОД(P₂₀, n). Если этот НОД тривиальный, то добавляем к P₂₀ следующее произведение длины 20, т. е. находим 

 

снова считаем НОД(P40, n) и так далее. Предположим, что при некотором k ≥ 1 оказалось, что НОД(P20k, n) > 1. Тогда мы возвращаемся к значению k −1 и начинаем последовательно вычислять наибольшие общие делители 

 

до  первого нетривиального общего делителя.

     Значение  нахождения P₂₀, P₄₀, P₆₀, . . . состоящих из порций по 20 степеней простых чисел, состоит именно в экономии на вычислениях наибольшего общего делителя. Заметим, что поскольку количество простых чисел q_i не обязано делится на 20, то последняя порция может быть неполной. 

2 стадия (P − 1)-метода Полларда.

     Предположим, что p | n, p − 1 не является B-степенно-гладким числом, но p −1 =f * r, где f — B-степенно-гладкое число и r — простое число, B < r < B1. Допустим, что на 1 - й стадии (P − 1)-метода Полларда мы вычислили 

b =a^{НОК(1,2,. . . ,B)} (mod n). 

Тогда b^r ≡1 (mod p), и НОД(b^r −1 (mod n), n) будет делиться на p по малой теореме Ферма.

     Поэтому на 2 стадии (P − 1)-метода Полларда мы находим все простые числа r₁ , . . . , r_N, B < r₁ < r₂ < ...<r_N < B₁, и составляем разности      d_i = r_i − r_i−1, i=2, . . . , N. Эти разности обычно невелики и количество различных таких разностей также невелико (при подходящем выборе B₁). Затем мы табулируем элементы b^di (mod n) для всех различных

значений d_i.

     После этого в алгоритме мы находим 

x₁ ≡b^r1 (mod n), 

после чего вычисляем 

x_i ≡b^ri (mod n) ≡ x_i−1 * b^di (mod n), i= 2, . .., N,

и находим 

НОД(x_i −1 (mod n), n), i=1, . . . , N. 

Здесь также возможна организация вычислений порциями по 20 для экономии количества нахождений наибольших общих делителей.

     Замечание 1. Оценка сложности (P −1)-метода Полларда в худшем случае составляет O(n^1/2 log^c n) арифметических операций. Однако в некоторых случаях алгоритм может быстро выдать делитель числа n. Во всех случаях алгоритм хорошо находит небольшие простые делители n, потому что они являются степенно-гладкими для небольшой границы гладкости B.

     Замечание 2. Если какой-либо из вычисляемых в алгоритме наибольших общих делителей оказался равным n, то имеет смысл попробовать другое основание a, например, a= 3.

     На  практике (P − 1)-метод Полларда обычно используют

до  применения более сильных алгоритмов факторизации для того, чтобы

отделить  небольшие простые делители числа n.

 

p-метод Полларда. 

     С его помощью было разложено на множители число Ферма

     F₈ = 2²⁵⁶ + 1.

Схема p-метода.

     На  входе задано число n ∈ N, которое мы хотим разложить на множители.

     1 шаг. Выбрать отображение 

f : Z/nZ −→ Z/nZ. 

Обычно f (x) —многочлен степени большей или равной 2, например,             f (x) = x2 +1.

     2 шаг. Случайно выбрать x₀ ∈ Z/nZ и вычислять члены рекуррентной последовательности x₀, x₁, x₂, . . . по правилу 

x_i ≡ f (x_i−1) (mod n). 

     3 шаг. Для некоторых номеров j, k проверять условие 

1<НОД(x_j −x_k, n) <n 

до  тех пор, пока не будет найден делитель числа n, или пока не закончится время, отведенное для работы алгоритма.

     Конец алгоритма.

     Замечание 3. Выбор номеров j, k на третьем шаге алгоритма обычно делают одним из следующих способов.

     1. Для каждого j перебирают все k, k < j; это долго, и требуется большая память компьютера.

     2. Рассматривают пары k и 2k, т. е. проверяют условие                               1 < НОД(x_2k − x_k, n) < n.

     3. Если j заключено в пределах 2^h ≤ j < 2^h+1, где h ∈ N, то полагают        k = 2h − 1.

     Замечание 4. Основная идея p-метода очень проста. Если период последовательности x_i(mod n) может быть порядка n, то период последовательности x_i(mod p) для простого делителя p числа n не превосходит p. Это значит, что x_j и x_k могут быть различными по модулю n, но совпадать по модулю p, т.е. p | НОД(x_j −x_k, n).

     Утверждение 1. Пусть S — фиксированное множество из r элементов, f — какое-либо отображение f : S→S, x₀ ∈ S, последовательность x₀, x₁, x₂, . . . определяется соотношением x_j = f (x_j−1). Пусть λ > 0, l = 1 + [√2λr] < r. Тогда доля тех пар (f, x₀) (где f пробегает все отображения из S в S и x₀ пробегает все множество S), у которых x₀, x₁, x₂, . . . ,x_l попарно различны, среди всех пар (f, x₀) не превосходит e^−λ.