Метод Лемана

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

Метод Лемана

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

Формулировка теоремы

Предположим, что $n$ — положительное нечетное целое, а $r$ — целое такое, что $1\leqslant r<n^{1/2}$. Если $n=pq$, где $p$ и $q$ простые и

$\left({\frac {n}{r+1}}\right)^{1/2}<p\leqslant n^{1/2}$

тогда существуют такие неотрицательные целые числа $x$, $y$ и $k$, что

$x^{2}-y^{2}=4kn,1\leqslant k\leqslant r$,

$x\equiv k+1{\pmod {2}}$,

$x\equiv k+1{\pmod {4}}$, если $k$ нечетное,

$0\leqslant x-(4kn)^{1/2}\leqslant {\frac {1}{4(r+1)}}\left({\frac {n}{k}}\right)^{1/2}$

и

$p=\min(\gcd(x+y,\;n),\;\gcd(x-y,\;n))$.

Если $n$ — простое, таких чисел $x$, $y$ и $k$ не существует.

Модифицированный метод Лемана

Формулировка теоремы

Пусть $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$. Для доказательства данной теоремы нам потребуется следующая Лемма.

Лемма

Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа $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}=\left[{\frac {q}{p}}\right]$, $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}$. Далее,

$\left|{\frac {r}{s}}-{\frac {q}{p}}\right|\leqslant \left|{\frac {r}{s}}-{\frac {p_{m+1}}{q_{m+1}}}\right|={\frac {1}{sq_{m+1}}}$

по свойствам подходящих дробей.

Рассмотрим сначала случай ${\frac {p_{m+1}}{q_{m+1}}}\leqslant {\frac {q}{p}}$. В этом случае

$|pr-qs|=ps\left|{\frac {r}{s}}-{\frac {q}{p}}\right|\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 \left|{\frac {s}{r}}-{\frac {p}{q}}\right|\leqslant \left|{\frac {s}{r}}-{\frac {q_{m+1}}{p_{m+1}}}\right|={\frac {1}{rp_{m+1}}}$. Отсюда

$1\leqslant |sq-pr|=rq\left|{\frac {s}{r}}-{\frac {p}{q}}\right|\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$. Теорема доказана.

Алгоритм (модифицированный)

Пусть $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,\;\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^{*}=\gcd(A-B,\;n)$ проверяется неравенство $1<d^{*}<n$. Если оно выполнено, то $n=d^{*}\cdot (n/d^{*})$ — разложение $n$ на два множителя.

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

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

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

Вычисление зависимости от величины факторизуемого числа

На первом шаге нужно произвести $\lceil n^{1/3}\rceil$ операций деления для поиска маленьких делителей числа $n$.

Трудоёмкость второго шага оценивается в операциях тестирования числа $\left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn$, на то, является ли оно полным квадратом. Трудоёмкость второго этапа оценивается сверху величиной

${\frac {n^{1/6}}{4}}\sum _{k=1}^{\lfloor n^{1/6}\rfloor }{{\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\simeq 2^{l}$ , где $l$ — разрядность.

$O(n^{1/3})=O(2^{l/3})=O(e^{l/3})$

Некоторые частные случаи

Как усовершенствование метода Ферма метод Лемана также существенно зависит от расстояния между множителями числа, время его выполнения линейно зависит от дистанции. Однако если расстояние между множителями мало метод Лемана значительно проигрывает методу Ферма.

Для чисел с небольшим простым делителем ситуация обратная — метод Лемана благодаря последовательным делениям на шаге один достаточно быстро выделит простой множитель.

Псевдокод

for $a\gets 2$ to $\lfloor n^{1/3}\rfloor$ do

if $a\vdots n$ then

return $a$

end if

end for for $k\gets 1$ to $\lfloor n^{1/3}\rfloor$ do

for $d\gets 0$ to $\left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1$ do

if $isSquare((\lfloor {\sqrt {4kn}}\rfloor +d)^{2}-4kn)=true$ then

$A\gets \lfloor {\sqrt {4kn}}\rfloor +d$

$B\gets {\sqrt {A^{2}-4kn}}$

if $1<gcd(A+B,n)<n$ then

return $gcd(A+B,n)$

else if $1<gcd(A-B,n)<n$ then

return $gcd(A-B,n)$

end if

end if

end for

end for

Пояснения:

$a\vdots n$ означает, что $n$ целочисленно делится на $a$.

Функция $isSquare(a)$ возвращает $true$, если $a$ является полным квадратом и $false$ в противном случае.

Функция $gcd(a,b)$ возвращает наибольший общий делитель чисел $a$ и $b$.

Возможности параллельной реализации метода

Общая идея

Параллельная реализация основана на следующем подходе:

Шаг 1:
Каждому вычислительному процессу, участвующему в факторизации, выдаётся свой набор потенциальных делителей из множества $\{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}$. Вычислительный процесс поочерёдно проверяет $n$ на делимость на элементы своего набора делителей. Через некоторые промежутки времени главный процесс-координатор «опрашивает» вычислительные процессы на предмет выявления делителя. В случае, когда достаточно проверить $n$ на простоту, процесс-координатор, получив информацию о нахождении делителя, посылает остальным процессам сигнал на завершение работы. Если же делитель не найден, или поставлена цель найти все делители, поиск делителей продолжается.

Шаг 2:
Каждому вычислительному процессу аналогично с шагом 1 выдаётся свой набор чисел $k$ из множества $\{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}$. Вычислительный процесс поочерёдно проверяет все условия, описанные в алгоритме, определяя, найден ли нетривиальный множитель. Аналогично с шагом 1 процесс-координатор периодически опрашивает процессы на момент нахождения делителя и принимает решение о завершении или не завершении вычислений.

Применение данного подхода позволяет получить линейное ускорение при увеличении количества процессов на машине с распределенной памятью.

Реализация с применением технологии GPGPU

Для успешной реализации алгоритма с применением технологии GPGPU нужно решить две проблемы:
1. Для каждой операции алгоритма решить, стоит ли выполнять её на CPU или на GPU.
2. Определить число используемых ядер GPU.

Описанный выше подход можно использовать для разбиения задачи.

Шаг 1:
Все операции этого шага следует выполнять на GPU.

Пусть $ker$ — число доступных ядер GPU, $la$ — число элементов множества $\{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}$. Рассмотрим два случая:
1. $la\leqslant ker$: Используем $la$ ядер GPU.
2. $la>ker$: Организуем $\left\lceil {\frac {la}{ker}}\right\rceil$ итераций. На каждой итерации выполняем очередные $ker$ делений на $ker$ ядрах. В конце каждой итерации определяем, завершить или продолжить исполнение.

Шаг 2:

Распределить $k$ между ядрами GPU аналогично шагу 1. На каждом ядре GPU выполнить пункты 1—3:
1. Проверить, является ли число $\left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn$ квадратом натурального числа.
2. В случае получения положительного результата в предыдущем пункте, вычислить $A=\left\lfloor {\sqrt {4kn}}\right\rfloor +d$ и $B={\sqrt {A^{2}-4kn}}$.
3. Для значений $A$ и $B$ проверить условие $A^{2}\equiv B^{2}{\pmod {n}}$.
4. Для значений $A$ и $B$, прошедших последнюю проверку, проверить выполнение двойного условия $0<\gcd(A\pm B,\;n)<n$.

Последний пункт целесообразно выполнять на CPU, так как вероятность исполнения данных операций мала, а проверка ветвлений на GPU выполняется достаточно медленно.

Пример

Разберём пример с $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. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
2. Алексей Нестеренко. Введение в современную криптографию. — МЦНМО, 2011. — 190 с.
3. Richard Crandall, Carl Pomerance. A Computational Perspectives. — 2nd. — Springer, 2011. — 597 с. — ISBN 0-387-25282-7.