Метод Лемана

${\displaystyle x^{2}-y^{2}=4kn}$

${\displaystyle k<n^{1/3}}$

${\displaystyle 0\leqslant x-\lfloor {\sqrt {4kn}}\rfloor <{\frac {n^{1/6}}{4{\sqrt {k}}}}+1}$

Лемма

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

Доказательство Теоремы

Пусть ${\displaystyle p}$ и ${\displaystyle q}$ нечётные делители числа ${\displaystyle n}$. Пусть ${\displaystyle x=pr+qs}$ и ${\displaystyle y=pr-qs}$, где ${\displaystyle r}$ и ${\displaystyle s}$ удовлетворяют утверждению Леммы, тогда выполнено равенство
${\displaystyle x^{2}-y^{2}=(pr+qs)^{2}-(pr-qs)^{2}=4rspq=4kn}$,
где ${\displaystyle k=rs}$. В силу Леммы, целое число ${\displaystyle k}$ удовлетворяет неравенству ${\displaystyle k<n^{1/3}}$. Следовательно выполнено первое утверждение Теоремы.

Для доказательства второго утверждения положим ${\displaystyle z=x-\lfloor {\sqrt {4bn}}\rfloor =pr+qs-\lfloor {\sqrt {4bn}}\rfloor }$, Так как ${\displaystyle x^{2}=4kn+y^{2}}$, то ${\displaystyle x\geqslant {\sqrt {4kn}}}$ и ${\displaystyle z\geqslant 0}$. Используя оценку сверху для ${\displaystyle y}$, получаем
${\displaystyle 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)}$.
Откуда следует, что ${\displaystyle z<{\frac {n^{2/3}}{2{\sqrt {4kn}}}}+1={\frac {n^{1/6}}{4{\sqrt {k}}}}+1}$. Теорема доказана. ^[4]

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

Пусть ${\displaystyle n}$ нечётно и ${\displaystyle n>8}$.

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

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

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

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

Если алгоритм не нашёл разложение ${\displaystyle n}$ на два множителя, то ${\displaystyle n}$ — простое число.^[5]

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

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

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

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

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

${\displaystyle {\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 }$.
Таким образом трудоёмкость всего есть величина ${\displaystyle O(n^{1/3})}$. ^[6]

Зависимость от разрядности факторизуемого числа

В большинстве случаев более важную роль играет зависимость времени исполнения от разрядности исследуемого числа. Имея полиномиальную зависимость для величины получаем экспоненциальную зависимость времени выполнения метода Лемана от разрядности факторизуемого числа. ^[7]

${\displaystyle n\simeq 2^{l}}$ , где ${\displaystyle l}$ — разрядность.

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

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

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

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

Псевдокод

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

if ${\displaystyle a\vdots n}$ then

return ${\displaystyle a}$

end if

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

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

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

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

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

if ${\displaystyle 1<gcd(A+B,n)<n}$ then

return ${\displaystyle gcd(A+B,n)}$

else if ${\displaystyle 1<gcd(A-B,n)<n}$ then

return ${\displaystyle gcd(A-B,n)}$

end if

end if

end for

end for

Пояснения:

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

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

Функция ${\displaystyle gcd(a,b)}$ возвращает наибольший общий делитель чисел ${\displaystyle a}$ и ${\displaystyle b}$. ^[7]

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

Общая идея

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

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

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

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

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

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

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

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

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

Шаг 2:

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

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

Пример

Разберём пример с ${\displaystyle n=1387}$, тогда для ${\displaystyle a=1,\;2,\;3,\;\ldots ,\;\lfloor n^{1/3}\rfloor }$, где ${\displaystyle \lfloor n^{1/3}\rfloor =11}$, проверяем является ли число ${\displaystyle a}$ делителем числа ${\displaystyle n}$. Нетрудно убедиться, что таких нет, тогда переходим к следующему пункту.

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