Метод Лемана

Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число n на множители за O(n1/3) арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел, имеющим оценку меньшую, чем O(n). В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.

Алгоритм


 Пусть n нечетно и n>8.
Шаг 1. Для a=2,3,,n1/3 проверить условие an. Если на этом шаге мы не разложили n на множители, то переходим к шагу 2.
Шаг 2. Если на шаге 1 делитель не найден и n — составное, то n=pq, где p,q — простые числа, и $n^{1/3}
A2B2(modn) или (AB)(A+B)0(modn).
  В этом случае для d=gcd(AB,n) проверяется неравенство $1 Если алгоритм не нашел разложение n на два множителя, то n — простое число.
 Данный алгоритм в начале проверяет имеет ли n простые делители не превосходящие n1/3, а после устраивает перебор значений k и d для проверки выполнимости указанной ниже Теоремы. В случае, если искомые значения x и y, не найдены, то мы получаем что число n простое. Таким образом мы можем рассматривать данный алгоритм как тест числа n на простоту

Доказательство


 Метод Лемана развивает идеи, заложенные в алгоритме Ферма и ищет делители числа n, используя равенство x2y2=4kn для некоторого целого числа b. Он основан на следующей теореме.
Теорема: Пусть n=pq составное число, являющееся произведением двух нечетных взаимно простых чисел, удовлетворяющих неравенствам n1/3<p<q<n2/3. Тогда, найдутся натуральные числа x,y и k1 такие, что\\
 1. Выполнено равенство x2y2=4kn при k<n1/3,\\ 2. Выполнено неравенство 0x4kn<n1/64k+1.
 Для доказательства данной теоремы нам потребуется следующая Лемма.
Лемма: Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа r,s такие что rs<n1/3 и prqs∣<n1/3.
Доказательство Леммы: Если p=q, т.е. n=p2, то утверждение теоремы выполнено для r=s=1. Далее будем считать $p Разложим qp в непрерывную дробь. Мы обозначаем pjqj j-ю подходящую дробь к qp. Тогда
p0=[qp], q0=1, $0 поскольку qp<n2/3n1/3=n1/3. Выберем первый номер m такой, что
pmqm<n1/3, pm+1qm+1>n1/3.
 Такой номер обязательно найдется, поскольку у последней подходящей дроби знаменатель qN=p>n1/3. Докажем, что r=pm и s=qm удовлетворяют утверждению леммы. Очевидно, что rs<n1/3. Далее,
|rsqp||rspm+1qm+1|=1sqm+1
 по свойствам подходящих дробей.
 Рассмотрим сначала случай pm+1qm+1qp. В этом случае
|prqs|=ps|rsqp|pssqm+1=pqm+1=pqm+1pqm+1pqm+1qpm+1=npm+1qm+1<n1/2n1/6=n1/3,
 что и требовалось доказать.
 Теперь рассмотрим случай pm+1qm+1>qp. Тогда перевернем неравенства pm+1qm+1>qp>pmqm, откуда qmpm>pq>qm+1pm+1. Следовательно, по свойствам непрерывных дробей, выполнены неравенства
1rq|srpq||srqm+1pm+1|=1rpm+1. Отсюда
1|sqpr|=rq|srpq|rqrpm+1=qpm+1=qpm+1qpm+1qpm+1pqm+1=npm+1qm+1<n1/2n1/6=n1/3
 Лемма доказана.
Доказательство Теоремы: Пусть p и q нечетные делители числа n. Пусть x=pr+qs и y=prqs, где r и s удовлетворяют утверждению Леммы, тогда выполнено равенство\\ x2y2=(pr+qs)2(prqs)2=4rspq=4kn,\\ где k=rs. В силу Леммы, целое число k удовлетворяет неравенству k<n1/3. Следовательно выполнено первое утверждение Теоремы.
 Для доказательства второго утверждения положим z=x4bn=pr+qs4bn, Так как x2=4kn+y2, то x4kn и z0. Используя оценку сверху для y, получаем\\ n2/3>y2=x24kn=(pr+qs+4kn)(pr+qs4kn)24kn(pr+qs4kn)24kn(z1).\\ Откуда следует, что z<n2/324kn+1=n1/64k+1. Теорема доказана.

Трудоемкость


 На первом шаге нам требуется произвести n1/3 операций деления для поиска маленьких делителей числа n.
 Трудоемкость второго шага оценивается в операциях тестирования числа (4kn+d)24kn, на то, является ли оно полным квадратом. В начале заметим, что для всех k>n1/64 выполняется только одна проверка: d=1. Тогда, трудоемкость второго этапа оценивается сверху величиной
n1/64k=1n1/61k+2(n1/3n1/6)<3n1/3.\\ Таким образом трудоемкость всего есть величина O(n1/3).

Пример


 Разберем пример с n=1387, тогда для a=1,2,3,,n1/3, где n1/3=11, проверяем является ли число a делителем числа n. Не трудно убедится, что таких нет, тогда переходим к следующему пункту.
 Для всех k=1,2,3,,11 и всех d=0,1,,4 проверяем, является ли число (4kn+d)24kn квадратом натурального числа. В нашем случае существуют такие k=3 и d=1, что выражение (4kn+d)24kn является полным квадратом и равно 256=162. Следовательно A=130 и B=16. Тогда d=(AB;n)=19, удовлетворяет неравенству 1<d<n и является делителем числа n. В итоге, мы разложили число 1387 на два множителя: 73 и 19.