Метод Лемана

Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число $~n$ на множители за $~O(n^{1/3})$ арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году.^[1]. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел чисел, имеющим оценку меньшую, чем $~O( \sqrt{n} )$. В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.^[2]

Алгоритм

Пусть $~n$ нечетно и $~n>8$.

Шаг 1. Для $a=2,\;3,\;\ldots,\;\lfloor n^{1/3}\rfloor$ проверить условие $a\mid n$. Если на этом шаге мы не разложили $~n$ на множители, то переходим к шагу 2.

Шаг 2. Если на шаге 1 делитель не найден и $~n$ — составное, то $~n=pq$, где $p,\;q$ — простые числа, и $n^{1/3}<p\leqslant q<n^{2/3}$. Тогда для всех $k=1,\;2,\;\ldots,\;\lfloor n^{1/3}\rfloor$ и всех $d=0,\;1,\;\ldots,\;\left\lfloor\frac{n^{1/6}}{4\sqrt{k}}\right\rfloor+1$ проверить, является ли число $\left(\left\lfloor\sqrt{4kn}\right\rfloor+d\right)^2-4kn$ квадратом натурального числа. Если является, то для $A=\left\lfloor\sqrt{4kn}\right\rfloor+d$ и $B=\sqrt{A^2-4kn}$ выполнено сравнение:

$A^2\equiv B^2\pmod{n}$ или $(A-B)(A+B)\equiv 0\pmod{n}$.

В этом случае для $d^{*}=(A-B,\;n)$ проверяется неравенство $~1<d^{*}<n$. Если оно выполнено, то $n=d^{*}\cdot(n/d^{*})$ — разложение $~n$ на два множителя.

Если алгоритм не нашел разложение $~n$ на два множителя, то $~n$ — простое число.^[3]

Данный алгоритм в начале проверяет имеет ли $n$ простые делители не превосходящие $\lfloor n^{1/3} \rfloor$, а после устраивает перебор значений $k$ и $d$ для проверки выполнимости указанной ниже Теоремы. В случае, если искомые значения $x$ и $y$, не найдены, то мы получаем что число $n$ простое. Таким образом мы можем рассматривать данный алгоритм как тест числа $n$ на простоту^[4]

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

Метод Лемана развивает идеи, заложенные в алгоритме Ферма и ищет делители числа $n$, используя равенство $x^2-y^2=4kn$ для некоторого целого числа $b$. Он основан на следующей теореме.

Теорема: Пусть $n = pq$ составное число, являющееся произведением двух нечетных взаимно простых чисел, удовлетворяющих неравенствам $n^{1/3} < p < q < n^{2/3}$. Тогда, найдутся натуральные числа $x,\;y$ и $k \geqslant 1$ такие, что

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$.

Для доказательства данной теоремы нам потребуется следующая Лемма.^[2]

Лемма: Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа $r, \;s$ такие что $rs < n^{1/3}$ и $\mid pr - qs \mid < n^{1/3}$.

Доказательство Леммы: Если $p = q$, т.е. $n = p^2$, то утверждение теоремы выполнено для $r = s = 1$. Далее будем считать $p<q$.
Разложим $\frac {q}{p}$ в непрерывную дробь. Мы обозначаем $\frac{p_j}{q_j}$ $j$-ю подходящую дробь к $\frac{q}{p}$. Тогда

$p_0 = [\frac{q}{p}]$, $q_0=1$, $0<p_0 q_0< n^{1/3}$,

поскольку $\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}$
Лемма доказана.^[5]

Доказательство Теоремы: Пусть $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$. Теорема доказана. ^[6]

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

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

Пример

Разберем пример с $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$.

Примечания

Имеется викиучебник по теме
«Программные реализации метода Лемана»

1. ↑ Lehman, R. Sherman Factoring Large Integers // Mathematics of Computation. — 1974. — Т. 28. — № 126. — С. 637-646. — DOI:10.2307/2005940
2. ↑ ^{1 2} Нестеренко, 2011, p. 140
3. ↑ Василенко, 2003, p. 65
4. ↑ ^{1 2} Нестеренко, 2011, p. 143
5. ↑ Василенко, 2003, p. 65-66
6. ↑ Нестеренко, 2011, p. 142

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.

Литература

1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
2. Алексей Нестеренко. Введение в современную криптографию. — МЦНМО, 2011. — 190 с.
3. Richard Crandall, Carl Pomerance A Computational Perspectives. — 2nd. — Springer, 2011. — 597 с. — ISBN 0-387-25282-7