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

     xa₀ +yb₀ =xs≥0, xa_t + yb_t =yb_t ≤0, 

то  найдется четный номер i такой, что 

xa_i + yb_i _≥0, xa_i+2 + yb_i+2 ≤ 0. 

Если xa_i + yb_i <γs или xa_i+2 + yb_i+2 > -γs, то все доказано. Если же xa_i +yb_i ≥γs и xa_i+2 + yb_i+2 ≤-γs, то по лемме 2 имеем 

. 

Тогда xa_i + yb_i ≥ γb_i+1a_i, откуда в силу неположительности yb_i находим, что x ≥ γb_i+1 (заметим, что a_{i 0}, так как I < t). Кроме того, 
 
 

откуда xa_i+2 + yb_i+2 ≤ γb_i+2a_i+1, и в силу неотрицательности xa_i+2 получаем yb_i+2 ≤γb_i+2a_i+1. Заметим, что b_i+2 < 0, так как xa_i+2 +yb_i+2 ≤ -γs < 0. Тогда     y ≥ γai₊₁.

     Из  доказанных оценок снизу для x и y получаем 

xa_i+1 + yb_i+1 ≥ 2γa_i+1b_i+1, 

т. е. выполнено нижнее неравенство  утверждения леммы для нечетного

номера i + 1. Также 

(x−γb_i+1) (y−γa_i+1) ≥ 0. 

Поэтому 

xy−γa_i+1x -γb_i+1y+γ²b_i+1a_i+1 ≥ 0. 

Следовательно 

γ(a_i+1x+ b_i+1y) ≤ xy+γ²b_i+1a_i+1, 

отсюда следует и верхнее неравенство для номера i +1.

     Теперь  докажем, что алгоритм находит все  делители числа n, сравнимые с r по модулю s. Пусть xs +r —такой делитель (число x ∈ Z_≥0 нам неизвестно). Тогда при некотором d ∈ N выполнено равенство          (xs+ r)d = n, откуда dr ≡ n (mod s) и d ≡ nr* ≡ r’ (mod s). Значит, d =r’ + ys, где y ∈ Z_≥0, поскольку r’< s. Отсюда 

(xs +r) (ys + r’) =n. 

Тогда 

rr’ +s(xr’ + yr) ≡n (mod s²),

и

xr’ + yr ≡ n− rr’/s(mod s). 

Отсюда

xr’r* + y≡ (n− rr’)*r*/s (mod s),

т. е.

xa₁ +yb₁ ≡c₁ (mod s).

Сравнение xa₀ + yb₀ ≡ c₀ (mod s) также выполняется очевидным образом. Тогда с помощью рекуррентных формул находим, что 

xa_i +yb_i ≡c_i (mod s), i= 0, . . ., t. 

Применим  лемму 3 при γ=1. Найдется i такое, что либо

|xa_i +yb_i|<s, если i четно,

либо

2a_ib_i ≤ xa_i + yb_i ≤ xy+ a_ib_i, если i нечетно.

Фиксируем это i и положим c = xa_i +yb_i. Тогда c ≡ c_i (mod s). Из неравенства 
 
 

мы  получим, что

|c|< s, если i четно,

2a_ib_i ≤c n/s2 + a_ib_i, еслиi нечетно.

Значит, c попадает в множество значений, проверяемых на 3 шаге алгоритма. Мы уже заметили ранее, что для четного i таких значений будет не более двух. Для нечетного i число c лежит на отрезке                 [2a_ib_i, n/s² + a_ib_i] длины n/s²− a_ib_i < n/s². Поскольку n/s³ < 1, то только один элемент из арифметической прогрессии c_i(mod s) может попасть в этот отрезок. Итак, в алгоритме на 3 шаге мы дойдем до этого значения     c = xa_i + yb_i. Решив систему на 4 шаге, мы найдем x и y, и, следовательно, найдем делитель xs + r.

     Теперь  оценим сложность алгоритма. Так  как a_i получаются с помощью алгоритма Евклида, то t = O(log n). Шаги 2, 3, 4 можно выполнить за O(1) арифметических операций, поскольку извлечение квадратного корня из целого числа имеет такую же сложность, как умножение. В итоге мы доказали теоретическую оценку сложности       O(log n) арифметических операций, хотя реально неоднократное извлечение квадратного корня из дискриминанта на 4 шаге является трудоемким, как уже отмечалось. 
 
 

Алгоритм  Полларда—Штрассена. 

Алгоритм  основан на следующей теореме.

     Теорема 3. Пусть z ∈ N, y = z². Тогда для любого натурального числа t наименьший простой делитель числа НОД(t, y!) может быть найден за    O(z log² z log² t) арифметических операций.

     Алгоритм .

     Положим z = [n^1/4] +1, y = z² > n^1/2, t = n. Далее с помощью алгоритма теоремы 3 найдем наименьший простой делитель числа НОД(n, y!). Поскольку y! делится на наименьший простой делитель p числа n (так как p ≤ n^1/2 < y), то алгоритм выдаст именно это число p. Сложность алгоритма Полларда—Штрассена O(z log² z log² t) = O(n^1/4 log⁴ n).

     Доказательство  теоремы 3. Справедливо равенство  
 
 

Если  мы будем вычислять 

НОД(t, ) , j= 1, . . . , z, 

то  первый нетривиальный НОД покажет, что минимальный простой делитель числа НОД(t, y!) лежит среди чисел 

(j − 1)z +1, (j −1)z + 2, . .. , jz. 

Тогда первое число в этом наборе, которое  делит t будет искомым минимальным простым делителем числа НОД(t, y!); для его нахождения потребуется не более чем z операций деления t на числа данного набора.

Обозначим f (x) =. Тогда 

f (jz) = . 

Набор чисел f(jz) (mod t), j = 1, . .., z, можно найти за O(z log² z log² t) арифметических операций. Кроме того, для нахождения первого нетривиального 

НОД(t, f (jz) (mod t)), j = 1, . .., z, 

надо  затратить zO(log t) = O(z log t) арифметических операций. Итоговая оценка сложности составляет 

O(z log² z log² t) + O(z log t) + z = O(z log² z log² t), 

что и завершает доказательство теоремы.

     Алгоритм  Полларда—Штрассена может использоваться как непосредственно для факторизации не очень больших целых чисел, так и в качестве вспомогательного алгоритма в дополнительной стратегии PS в субэкспоненциальных алгоритмах факторизации целых чисел. 

 

  (P+ 1)-метод Уильямса и его обобщения. 

     Этот  метод аналогичен (P − 1)-методу Полларда, но использует разложение на множители числа P + 1. Суть (P + 1)-метода заключается в следующем. Рассматривается последовательность чисел Люка, определяемая соотношениями