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

u₀ = 0, u₁ = u, u_n+1 = Pu_n − Qu_n−1, 

где P, Q—фиксированные целые числа. Пусть p — простой делитель факторизуемого натурального числа n такой, что p + 1 является                   B-степенно-гладким, т. е.  

, 

где _—простые числа, ≤B. Пусть числа ∈ N таковы, что 

≤B, >B, i=1, . . . , k. 

Положим R = . Тогда p + 1 | R. Если для последовательности чисел Люка параметр Q взаимно прост с n и выполнено условие 
 
 

(оба  эти условия эвристически обеспечиваются некоторым случайным перебором P и Q), то по свойствам последовательностей чисел Люка

p | НОД(u_R, n).

     Дальнейшая  работа алгоритма заключается в достаточно быстром вычислении элемента последовательности u_R и на хождении НОД(u_R, n).

Методы  Шэнкса. 

     Два метода факторизации целых чисел, использующих бинарные квадратичные формы, принадлежат Д.Шэнксу. Первый из них работает с положительно определенными бинарными квадратичными формами заданного отрицательного дискриминанта, и в группе классов форм он находит амбигову форму, которая дает разложение дискриминанта на множители. Сложность этого метода составляет O(n^1/5+ξ) арифметических операций при условии выполнения расширенной гипотезы Римана. Второй метод носит название SQUFOF и использует группу классов бинарных квадратичных форм с положительным дискриминантом. Здесь также происходит нахождение амбиговой формы, дающей разложение дискриминанта. Сложность SQUFOF составляет O(n^1/4+ξ) арифметических операций; при этом алгоритм работает с целыми числами, не превосходящими    2√n. Среди алгоритмов факторизации с экспоненциальной сложностью SQUFOF

считается одним из самых эффективных.

Заключение. 

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

     Теорема 4. Пусть b, k ∈ N, b > 1, n =b^k − 1. Если p—простое число, делящее n, то выполнено одно из двух утверждений:

1. p | b^d − 1 при некотором d <k, d | k;

2. p ≡1 (mod k).

При этом, если p > 2 и k — нечетно, то во втором случае p ≡ 1 (mod 2k).

     Доказательство. По малой теореме Ферма b^p−1 ≡ 1 (mod p), а так же    b^k ≡ 1 (mod p). Пусть d = НОД(k, p − 1), тогда b^d ≡ 1 (mod p). Если d < k, то это означает выполнение первого утверждения теоремы. Если же d = k, то         k | p −1, т. е. p ≡ 1 (mod k).

     Пример  1. Пусть n = 2¹¹ −1. Тогда первое утверждение теоремы не выполняется, так как 1 —простое число и d = 1 не подходит (2¹ – 1 = 1). Следовательно, p ≡ 1 (mod 22). После этого сразу находим n = 23 * 89.

     Однако  практическая значимость таких алгоритмов, как правило, невелика. Наиболее популярными в практических вычислениях являются (P − 1)-метод Полларда, p-метод Полларда и алгоритм Полларда—Штрассена. Они используются в сочетании с субэкспоненциальными методами факторизации и применяются, как правило, для предварительного отделения небольших простых делителей у факторизуемого числа. 

Список  используемой литературы. 

     1. Н. Коблиц «Курс теории чисел и криптографии», Москва: Научное издательство ТВП, 2001г. 

      2. О.Н. Василенко «Теоретико-числовые  алгоритмы в криптографии», Москва: МЦНМО, 2003г. 

      3. И.В. Агафонова «Факторизация  больших целых чисел и криптография», 2006г.