Метод Лемана

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

Опис

Спочатку алгоритм перевіряє чи має $n$ прості дільники, які не перевищують $\lfloor n^{1/3}\rfloor$.

Далі метод Лемана розвиває ідеї, що закладені в алгоритмі Ферма, і шукає дільники числа $n$, використовуючи рівність $x^{2}-y^{2}=4bn$ для деякого цілого числа $b$. Він базується на наступній теоремі.

Формулювання теореми

Нехай $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$ на простоту.

Псевдокод

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

if $a\mod n=0$ 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)$ 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

Пояснення:

Функція $isSquare(a)$ повертає $true$, якщо $a$ є повним квадратом і $false$ — в іншому випадку.

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

Приклад

Розглянемо приклад $n=1387$, $\lfloor n^{1/3}\rfloor =11$.
Для $a=2,\;3,\;5,\;7,\;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, яке є квадратом: $256=16^{2}$. Відповідно, $A=\lfloor {\sqrt {4\times 3\times 1387}}\rfloor +1=130$ і $B=16$. Тоді $d^{*}=(A-B;\;n)=19$, задовольняє нерівності $1<d^{*}<n$ і є дільником числа $n$.
У результаті, ми розклали число $1387$ на два множники: $73$ і $19$.

Складність

Кількість операцій

На першому кроці треба зробити $\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})$ операцій.

Залежність від розрядності

Для великих чисел існує залежність часу виконання операцій від їх розрядності. Наприклад, складання двох чисел потребує часу, що лінійно залежить від довжини (більшого з них), а час множення й ділення ще більший, тобто, залежить від довжини чисел нелінійно (поліноміально). Отже, метод потребує поліноміальної кількості операцій ($O(n^{1/3})$), але час кожної операції щонайменше лінійно залежить від довжини (розрядності) числа. Таким чином виникає експоненційна залежність часу виконання алгоритму від розрядності числа, що факторизується — $O(n^{(n^{1/3})})$.

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

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

Порівняння з іншими методами

Як покращення методу Ферма, метод Лемана також істотно залежить від відстані між множниками числа: час його виконання лінійно залежить від дистанції^{[джерело?]}. Однак, якщо різниця між множниками мала, то метод Лемана значно програє методу Ферма^{[джерело?]}.

Для чисел із невеликим простим дільником ситуація інша — метод Лемана завдяки послідовному діленню на першому кроці досить швидко виділить простий множник.

Можливість паралельних обчислень

Загальна ідея

Паралельна реалізація базується на наступному підході:

Крок 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. Для кожної операції алгоритму вирішити, де варто її виконувати: на ЦП чи на графічному процесорі.
2. Визначити кількість ядер графічного процесора, що застосовуються.

Описаний вище підхід можна застосовувати для розбиття задачі.

Крок 2: Усі операції цього кроку слід виконувати на графічному процесорі.

Нехай $ker$ - кількість доступних ядер графічного процесора, $la$ - кількість елементів множини $\{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}$. Розглянемо два випадки:

1. $la\leqslant ker$: Використаємо $la$ ядер графічного процесора.
2. $la>ker$: Виконаємо $\left\lceil {\frac {la}{ker}}\right\rceil$ ітерацій. На кожній ітерації виконуємо $ker$ операцій ділення на $ker$ ядрах. У кінці кожної ітерації визначаємо завершити процес чи ні.

Крок 2: Розподілити $k$ між ядрами графічного процесора так же, як і в кроці 1. На кожному ядрі виконати 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$.

Останній пункт краще виконувати на ЦП, оскільки ймовірність виконання цих операцій досить мала, а така перевірка на графічному процесорі відбувається досить повільно.

Література

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.