Processing math: 100%

Метод Лемана

Алгоритм Лемана (или алгоритм Шермана Лемана)детерминировано раскладывает данное натуральное число 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/64n1/6k=11k+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.