Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

Метод Лемана

Алгоритм Лемана (или алгоритм Шермана Лемана)детерминировано раскладывает данное натуральное число 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 и k такие, что\\
 1. Выполнено равенство x^2-y^2=4kn при k < n^{1/3},\\ 2. Выполненонеравенство0 \leqslant x - \lfloor \sqrt{4kn} \rfloor < \frac{n^{1/6}}{4\sqrt{k}} + 1.
 Для доказательства данной теоремы нам потребуется следующая Лемма.
Лемма: Пусть выполнены условия Теоремы. Тогда найдутсянатуральные числа r, \;s такие что rs < n^{1/3} и\mid pr - qs \mid < n^{1/3}.
Доказательство Леммы: Если p = q, т.е. n = p^2, тоутверждение теоремы выполнено для r = s = 1. Далее будем считать$p Разложим \frac {q}{p} в непрерывную дробь. Мы обозначаем\frac{p_j}{q_j} j-ю подходящую дробь к \frac{q}{p}. Тогда
p_0 = [\frac{q}{p}], q_0=1, $0 поскольку \frac{q}{p} < \frac {n^{2/3}}{n^{1/3}} = n^{1/3}. Выберемпервый номер m такой, что
p_m q_m < n^{1/3}, p_{m+1} q_{m+1} > n^{1/3}.
 Такой номер обязательно найдется, поскольку у последней подходящей дробизнаменатель q_N = p > n^{1/3}. Докажем, что r = p_m и s = q_mудовлетворяют утверждению леммы. Очевидно, что rs < n^{1/3}. Далее,
|\frac{r}{s} - \frac{q}{p}| \leqslant |\frac{r}{s} - \frac{p_{m+1}}{q_{m+1}}| = \frac{1}{s q_{m+1}}
 по свойствам подходящих дробей.
 Рассмотрим сначала случай\frac{p_{m+1}}{q_{m+1}} \leqslant \frac {q}{p}. В этом случае
|pr - qs| = ps|\frac{r}{s} - \frac{q}{p}| \leqslant \frac {ps}{sq_{m+1}} = \frac {p}{q_{m+1}} = \sqrt{\frac{p}{q_{m+1}}\frac {p}{q_{m+1}}} \leqslant \sqrt{\frac{p}{q_{m+1}}} \sqrt{\frac{q}{p_{m+1}}} = \sqrt{\frac{n}{p_{m+1}q_{m+1}}} < \frac{n^{1/2}}{n^{1/6}} = n^{1/3},
 что и требовалось доказать.
 Теперь рассмотрим случай \frac{p_{m+1}}{q_{m+1}} > \frac{q}{p}. Тогдаперевернем неравенства\frac{p_{m+1}}{q_{m+1}} > \frac{q}{p} > \frac{p_m}{q_m}, откуда\frac{q_{m}}{p_{m}} > \frac{p}{q} > \frac{q_{m+1}}{p_{m+1}}.Следовательно, по свойствам непрерывных дробей, выполнены неравенства
\frac{1}{rq} \leqslant |\frac{s}{r} - \frac{p}{q}| \leqslant |\frac{s}{r} - \frac{q_{m+1}}{p_{m+1}}| = \frac{1}{r p_{m+1}}.Отсюда
1 \leqslant |sq - pr| = rq|\frac{s}{r} - \frac{p}{q}| \leqslant \frac {rq}{rp_{m+1}} = \frac {q}{p_{m+1}} = \sqrt{\frac{q}{p_{m+1}}\frac {q}{p_{m+1}}} \leqslant \sqrt{\frac{q}{p_{m+1}}} \sqrt{\frac{p}{q_{m+1}}} = \sqrt{\frac{n}{p_{m+1}q_{m+1}}} < \frac{n^{1/2}}{n^{1/6}} = n^{1/3}
 Лемма доказана.
Доказательство Теоремы: Пусть p и q нечетные делители числаn. Пусть x = pr + qs и y = pr - qs, где r и s удовлетворяютутверждению Леммы, тогда выполнено равенство\\x^2 - y^2 = (pr +qs)^2 - (pr - qs)^2 = 4rspq = 4kn,\\ где k = rs. Всилу Леммы, целое число k удовлетворяет неравенству k < n^{1/3}.Следовательно выполнено первое утверждение Теоремы.
 Для доказательства второго утверждения положимz = x - \lfloor \sqrt{4bn} \rfloor = pr + qs - \lfloor \sqrt{4bn} \rfloor,Так как x^2 = 4kn + y^2, то x \geqslant\sqrt{4kn} и z \geqslant 0.Используя оценку сверху для y, получаем\\n^{2/3} > y^2 = x^2 - 4kn = (pr + qs + \sqrt{4kn})(pr + qs - \sqrt{4kn}) \geqslant 2\sqrt{4kn}(pr + qs - \sqrt{4kn}) \geqslant 2\sqrt{4kn}(z - 1).\\Откуда следует, чтоz < \frac{n^{2/3}}{2\sqrt{4kn}} + 1 = \frac{n^{1/6}}{4\sqrt{k}} + 1.Теорема доказана.

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


 На первом шаге нам требуется произвести \lceil n^{1/3} \rceil операцийделения для поиска маленьких делителей числа n.
 Трудоемкость второго шага оценивается в операциях тестирования числа\left(\left\lfloor\sqrt{4kn}\right\rfloor+d\right)^2-4kn, на то,является ли оно полным квадратом. В начале заметим, что для всехk > \frac{n^{1/6}}{4} выполняется только одна проверка: d = 1.Тогда, трудоемкость второго этапа оценивается сверху величиной
\frac {n^{1/6}}{4} \sum^{\lfloor n^{1/6} \rfloor}_{k=1} {\frac {1}{ \sqrt{k} } + 2(\lceil n^{1/3} \rceil - \lfloor n^{1/6} \rfloor)} < 3 \lceil n^{1/3} \rceil.\\Таким образом трудоемкость всего есть величина O(n^{1/3}).

Пример


 Разберем пример с n = 1387, тогда дляa = 1,\;2,\;3,\;\ldots,\;\lfloor n^{1/3} \rfloor, где\lfloor n^{1/3} \rfloor = 11, проверяем является ли число aделителем числа n. Не трудно убедится, что таких нет, тогда переходимк следующему пункту.
 Для всех k = 1,\;2,\;3,\;\ldots,\;11 и всех d = 0,\;1,\;\ldots,\;4проверяем, является ли число\left(\left\lfloor\sqrt{4kn}\right\rfloor+d\right)^2-4kn квадратомнатурального числа. В нашем случае существуют такие k = 3 и d = 1,что выражение \left(\left\lfloor\sqrt{4kn}\right\rfloor+d\right)^2-4knявляется полным квадратом и равно 256 = 16^2. Следовательно A = 130и B = 16. Тогда d^{*} = (A - B; n) = 19, удовлетворяет неравенству1 < d^{*} < n и является делителем числа n. В итоге, мы разложиличисло 1387 на два множителя: 73 и 19.