Метод Лемана

Лемма

Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа ${\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]

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

Псевдокод

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]

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

Пример

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