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

     Следствие 2. Приведено описание схемы алгоритма Ленстры для проверки простоты натуральных чисел. Оценка сложности этого алгоритма зависит от начальных простых чисел p₁, . . . , p_l, таких, что 
 
 

Теорема 2 позволяет уменьшить количество простых чисел p₁, . . . , p_l и ослабить это неравенство до s> n^1/3. Затем на последней стадии алгоритма проверки простоты нам придется восстанавливать возможные делители числа n по остаткам r_j (mod s).

     Это усовершенствование на практике позволяет  ускорить работу алгоритма проверки простоты чисел.

     Мы  докажем здесь теорему 2 лишь частично. А именно, мы полностью опишем алгоритм нахождения всех r_i ≡r (mod s) и докажем оценку сложности. Доказательство того, что таких делителей может быть не более 11 .

     Замечание 6. Можно доказать, что для любой постоянной α , , существует постоянная c(α) > 0 такая, что при 1 ≤ r < s<n, (r, s) = 1, s > n, существует не более c(α) положительных делителей числа n, сравнимых с r по модулю s. Однако полиномиальный алгоритм для их нахождения пока неизвестен.

     Алгоритм.

     На  входе заданы числа r, s, n ∈ N, удовлетворяющие условиям теоремы.

     1 шаг. С помощью обобщенного алгоритма Евклида найти r' ∈ N,     r*r ≡1 (mod s). Найти r’ такое, что r’ ≡ r*n (mod s), 0 ≤ r’ <s.

     2 шаг. Для очередного значения I = 0, 1, 2, . .. найти числа a_i, b_i, c_i по следующим правилам: 

a₀ = s, b₀ =0, c₀ = 0,

a₁ ≡ r’r* (mod s), 0< a₁ ≤s, b₁ = 1, c₁ ≡ *r* (mod s) 

и при i≥2 

a_i = a_i−2 − q_ia_i−1, b_i = b_i−2 − q_ib_i−1, c_i ≡ c_i−2 −q_ic_i−1 (mod s). 

Здесь целые числа q_i однозначно определяются условиями

0≤a_i <a_i−1 при i четном,

0< a_i ≤a_i−1 при i нечетном. 

Фактически, q_i—частное от деления a_i−2 на a_i−1, за исключением случая, когда i нечетно и остаток от деления равен нулю. Отметим, что a_i монотонно не возрастают и на четных номерах — убывают.

     3 шаг. Для очередного набора a_i, b_i, c_i найти все целые числа c, удовлетворяющие условиям c= c_i (mod s), 

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

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

Таких c будет не более двух; для четного i это очевидно, а для нечетных i мы докажем это ниже.

     4 шаг. Для каждого c из шага 3 решить в целых числах систему уравнений 
 
 

Если x и y окажутся неотрицательными целыми числами, то добавить     xs+ r к списку искомых делителей.

     5 шаг. Если a_i = 0, то алгоритм заканчивает работу. Иначе возвращаемся на шаг 2 к следующему значению i.

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

     Замечание 7. Систему линейных уравнений, возникающую на 4 шаге алгоритма, можно свести к одному квадратному уравнению. Положим 

     u= a_i (xs +r), v = bi (ys+r’).

Тогда 

uv = na_ib_i, u +v = s(a_ix +b_iy) +a_ir+ b_ir’ = cs+ a_ir+ b_ir’, 

т. е. числа u и v являются корнями многочлена 

T² − (cs+ a_ir + b_ir’)T + a_ib_in. 

Эти корни должны быть целыми числами, одно из которых делится на a_i, а другое—на b_i. Поскольку мы работаем с большими целыми числами, на практике многократное извлечение корня из дискриминанта для нахождения корней многочлена является достаточно трудоемким.

     Замечание 8. Обозначим через t номер, для которого a_t =0. Поскольку a_i получается с помощью алгоритма Евклида, примененного к a₀ = s и a₁,   a₁ ≤ s, то очевидно, что t = O(log s). Кроме того, по определению чисел a_i номер t четен.

     Лемма 2. Числа a_i, b_i обладают следующими свойствами: 

1. a_i >0, b_i > 0 для нечетных i, 0 < i<t;

2. a_i ≥0, b_i ≤ 0, (a_i, b_i) (0, 0) для четных i, 0≤i≤t;

3. b_i+1a_i − a_i+1b_i = (−1)ⁱ ·s для 0 ≤i <t. 

     Доказательство. Свойство 1 для i=1, свойства 2 и 3 для i =0 выполняются по определению a₀, b₀, a₁ и b₁. Дальнейшее доказательство проведем по индукции.

     Свойство 3 следует из соотношения 

b_i+2a_i+1 − a_i+2b_i+1 = (b_i − q_i+2b_i+1)a_i+1 − (a_i − q_i+2a_i+1)b_i+1 = −(b_i+1a_i − a_i+1b_i). 

Неравенства a_i > 0 для нечетных i и a_i ≥ 0 для четных i следуют из определения a_i, а неравенство (a_i, b_i) (0, 0) следует из свойства3.

     Докажем неравенства для b_i.

     Если i нечетно, то i< t. Тогда 

b_i = b_i−2 − q_ib_i−1 > 0, 

поскольку b_i−2 > 0 и b_i−1 ≤ 0 по предположению индукции и числа q_i неотрицательны по определению. Точнее, в этом случае справедливо более сильное неравенство: b_i ≤ b_i−2.

     Пусть i четно, i ≤ t. Тогда по предположению индукции b_i−2 ≤ 0,       b_i−1 > 0, и здесь q_i —настоящее частное, т. е. q_i ≥ 1. Тогда                                     b_i = b_i−2 − q_ib_i−1 < 0, и даже b_i < b_i−2.

     Лемма 3. Пусть a_i, b_i, t — числа из алгоритма. Пусть x, y ∈ R_≥0, γ∈ R_>0. Тогда найдется номер i, 0≤ i≤t, такой,  что либо 

-γs< xa_i +yb_i <_s, если i четно, 

либо 

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

     Доказательство. Если x= y=0, то утверждение леммы очевидно. Пусть далее x или y отлично от нуля. Поскольку по лемме 2