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

     Доказательство. Всего имеется r^r * r = r^r+1 различных пар (f, x₀). Пар (f, x₀), у которых x₀, x₁, x₂, . . . ,x_l попарно различны будет 

r(r − 1) . . . (r− l) * r^r−l. 

Доля  таких пар составляет величину 

 

Поскольку при 0 < x < 1 выполнено неравенство log(1 − x) < −x, то 

что и требовалось доказать.

     Для чего нужно доказанное утверждение? Если у n есть небольшой простой делитель p, то величина l = l(n) = 1+ [√2λn] имеет порядок n^1/2, в то время как величина l = l(p) = 1 + [√2λp] существенно меньше. А доля наборов (f, x₀ (mod n)), где f : Z/nZ −→ Z/nZ, у которых элементы длинного набора x₀(mod n), . . . , x_l(n)(mod n) различны, не превосходит той же величины e^−λ, что и доля наборов (f, x₀ (mod p)), где f : Z/pZ −→ Z/pZ, у которых различны элементы короткого набора x₀ (mod p), . .. , x_l(p) (mod p).

     Теорема 1. Пусть n — нечетное составное число, p — простой делитель n, p < √n, f (x) ∈ Z[x] , x₀ ∈ Z, причем f хорошо редуцируется к модулю n, т. е. f корректно определяет отображение 

f : Z/nZ −→ Z/nZ. 

Предположим также, что f (x) хорошо редуцируется к модулю p. Если пара (f, x₀(mod p)) является не слишком редкой по своим статистическим свойствам, то p-метод Полларда найдет p за O(n^1/4 log³ n) битовых операций.

     Точнее, существует константа c, такая, что для любого λ>0 вероятность не найти нетривиальный делитель n за c·√λn^1/4 * log³n битовых операций будет меньше, чем e^−λ.

 

Метод Шермана—Лемана. 

Алгоритм.

     Пусть n нечетно, n > 8.

     1 шаг. Для a = 2, 3, . . ., [n^1/3] проверить условие a | n. Если на этом шаге мы не разложили n на множители, то переходим к шагу 2.

     2 шаг. Если на 1 шаге делитель не найден и n —составное, то n = pq, где p, q — простые числа, и 

n^1/3 < p ≤ q < n^2/3. 

Тогда для всех k = 1, 2, . . ., [n^1/3] и всех d = 0, 1, . . ., [n^1/6/(4√k)] +1 проверить, является ли число 

([√4kn] + d)² − 4kn 

квадратом натурального числа. Если является, то для A = [√4kn] + d и         B = √(A² − 4kn) выполнено сравнение 

A² ≡ B² (mod n). 

В этом случае проверить условие 

1 < (A B, n) < n. 

Если  это условие выполнено, то мы разложили  n на два множителя и алгоритм останавливается.

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

     Если  алгоритм не нашел разложение n на два множителя, то n — простое число. Докажем это. Нам нужно рассмотреть лишь случай n = pq, где p, q—простые числа, 

n^1/3 < p ≤  q < n^2/3. 

     Лемма 1. При этих условиях существуют натуральные числа r, s такие, что 

rs < n^1/3, |pr −qs| < n^1/3. 

     Воспользуемся этой леммой и положим в алгоритме k = rs≤ [n^1/3] .

Тогда 

4kn = 4rspq = (pr + qs)² − (pr − qs)². 

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

(pr + qs)² − 4kn = (pr− qs)² =B²,

где B = |pr −qs| < n^1/3. Пусть 

d = pr + qs − [√4kn] . 

Тогда 

n^2/3 > (pr+ qs)² − 4kn = (pr +qs+√4kn) (pr+ qs−√4kn) ≥ 2√4kn(d −1). 

Отсюда  получаем

d < n^2/3/(4√kn)+ 1= n^1/6/(4√k)+ 1.

Значит, k и d лежат в установленных в алгоритме пределах. Поэтому в алгоритме мы найдем число A = pr + qs = [√4kn] + d такое, что                           B = √(A² − 4kn) = |pr − qs| является натуральным числом. При этом             A² − B² = 4kn ≡ 0(mod n). Далее, одно из двух чисел A B равно 2pr  и имеет с n общий делитель, равный p, так как n нечетно и не делится на все числа, не превосходящие n^1/3, а r< n^1/3. То есть мы с помощью НОД(A ±B, n) разложим n на множители.

     Доказательство. Если p = q, т.е. n = p², то утверждение леммы выполнено для r = s = 1. Далее будем считать p < q.

     Разложим q/p в непрерывную дробь. Мы обозначаем p_j/q_j j-ю подходящую дробь к q/p. Тогда 

p₀ = [q/p] , q₀ = 1, 0 <p₀q₀ < n^1/3, 

поскольку q/p<n^2/3/n^1/3 = n^1/3. Выберем первый номер m такой, что        p_mq_m < n^1/3, p_m+1q_m+1 > n^1/3.

     Такой номер обязательно найдется, поскольку у последней подходящей дроби знаменатель _{^{. Докажем, что} и удовле}творяют утверждению леммы. Очевидно, что ^{. Далее}, 
 
 

по  свойствам подходящих дробей.

     Рассмотрим  сначала случай . В этом случае 

что и требовалось доказать.

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

     . 

     Отсюда 
 

Лемма доказана.

     Замечание 5. При реализации алгоритма Шермана—Лемана возможно эффективное использование параллельных вычислений. 

 

Алгоритм  Ленстры. 

     Теорема 2. Пусть r, s, n—натуральные числа, удовлетворяющие условиям 

1≤ r< s< n, n^1/3 <s, (r, s) = 1. 

Тогда существует не более 11 делителей r_i числа n таких, что r_i ≡ r (mod s). Имеется алгоритм, который находит все эти r_i за O(log n) арифметических операций.

     Следствие 1. Используя алгоритм из теоремы 2, можно получить метод факторизации числа n за O(n^1/3 log²n) арифметических операций. Положим s = [n^1/3] +1. С помощью алгоритма Евклида представим n в виде n = n₁n₂, где (n₁,s) = 1, а число n₂ равно произведению степеней тех простых чисел, которые делят s. Мы факторизуем n₁, а для факторизации n₂ поступим аналогично, заменив s на s+ 1. Теперь перебираем                         r = 1, 2, . . . , s −1 и для тех r, которые взаимно просты с s, находим с помощью алгоритма теоремы делители r_i числа n₁, r_i ≡ r (mod s). В силу взаимной простоты n₁ и s мы полностью разложим n₁ на множители.