Метод Лемана

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

Опис

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

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

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

Нехай ${\displaystyle n}$ — додатне непарне ціле число, а ${\displaystyle r}$ — ціле число таке, що ${\displaystyle 1\leqslant r<n^{1/2}}$. Якщо ${\displaystyle n=pq}$, де ${\displaystyle p}$ і ${\displaystyle q}$ прості, а також

${\displaystyle \left({\frac {n}{r+1}}\right)^{1/2}<p\leqslant n^{1/2}}$, то тоді існують такі невід'ємні цілі числа ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle k}$, що

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

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

${\displaystyle x\equiv k+1{\pmod {4}}}$, якщо ${\displaystyle k}$ непарне,

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

і

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

Якщо ${\displaystyle n}$ — просте, то таких чисел ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle k}$ не знайдеться.

Теоретичне обґрунтування

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

Нехай ${\displaystyle n=pq}$ можна записати як добуток двох непарних взаємно простих чисел, що задовольняють нерівностям ${\displaystyle n^{1/3}<p<q<n^{2/3}}$. Тоді знайдуться такі натуральні числа ${\displaystyle x,\;y}$ і ${\displaystyle k\geqslant 1}$, що
1. Виконується рівність ${\displaystyle x^{2}-y^{2}=4kn}$ при ${\displaystyle k<n^{1/3}}$,
2. Виконується нерівність ${\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}}$.

Доведення леми  

Якщо ${\displaystyle p=q}$, тобто ${\displaystyle n=p^{2}}$, то твердження теореми виконується для ${\displaystyle r=s=1}$. Далі будемо вважати ${\displaystyle p<q}$.

Розкладемо ${\displaystyle {\frac {q}{p}}}$ в ланцюговий дріб. Позначимо ${\displaystyle {\frac {p_{j}}{q_{j}}}}$ ${\displaystyle j}$-тий наближений дріб до ${\displaystyle {\frac {q}{p}}}$. Тоді

${\displaystyle p_{0}=\left[{\frac {q}{p}}\right]}$, ${\displaystyle q_{0}=1}$, ${\displaystyle 0<p_{0}q_{0}<n^{1/3}}$,

оскільки ${\displaystyle {\frac {q}{p}}<{\frac {n^{2/3}}{n^{1/3}}}=n^{1/3}}$. Оберемо перший номер ${\displaystyle m}$ такий, що

${\displaystyle p_{m}q_{m}<n^{1/3}}$, ${\displaystyle p_{m+1}q_{m+1}>n^{1/3}}$.

Такий номер обов'язково знайдеться, бо в останньому наближеному дробі знаменник ${\displaystyle q_{N}=p>n^{1/3}}$. Доведемо, що ${\displaystyle r=p_{m}}$ і ${\displaystyle s=q_{m}}$ задовольняють твердженню леми. Очевидно, що ${\displaystyle rs<n^{1/3}}$. Далі,

${\displaystyle \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}}}}$

за властивостями ланцюгового дробу.

Розглянемо спочатку випадок ${\displaystyle {\frac {p_{m+1}}{q_{m+1}}}\leqslant {\frac {q}{p}}}$. В цьому випадку

${\displaystyle |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}}$,

що і потрібно було довести.

Тепер розглянемо випадок ${\displaystyle {\frac {p_{m+1}}{q_{m+1}}}>{\frac {q}{p}}}$. Нерівності приймуть вигляд ${\displaystyle {\frac {p_{m+1}}{q_{m+1}}}>{\frac {q}{p}}>{\frac {p_{m}}{q_{m}}}}$, і тоді ${\displaystyle {\frac {q_{m}}{p_{m}}}>{\frac {p}{q}}>{\frac {q_{m+1}}{p_{m+1}}}}$. Відповідно, за властивостями ланцюгових дробів, виконуються нерівності

${\displaystyle {\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}}}}$. І тоді

${\displaystyle 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}}$.

Лему доведено.

Доведення теореми

Припустимо, що ${\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}$. Теорему доведено.

Алгоритм

Нехай ${\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}$ — просте число.

Цей алгоритм спочатку перевіряє чи має ${\displaystyle n}$ прості дільники, які не перевищують ${\displaystyle \lfloor n^{1/3}\rfloor }$, а потім починає перебір значень ${\displaystyle k}$ і ${\displaystyle d}$ для перевірки виконання теореми. У випадку коли шукані значення ${\displaystyle x}$ і ${\displaystyle y}$ не знайдено, отримуємо, що число ${\displaystyle n}$ — просте. Таким чином можна розглядати цей алгоритм і як тест числа ${\displaystyle n}$ на простоту.

Псевдокод

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

if ${\displaystyle a\mod n=0}$ 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)}$ 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 isSquare(a)}$ повертає ${\displaystyle true}$, якщо ${\displaystyle a}$ є повним квадратом і ${\displaystyle false}$ — в іншому випадку.

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

Приклад

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

Складність

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

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

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

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

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

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

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

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

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

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

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

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

Крок 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 процес-координатор періодично «опитує» процеси щодо знайдення дільника і приймає рішення про припинення чи продовження обчислень.

Застосування цього підходу дозволяє отримати лінійне прискорення при збільшенні кількості процесів на комп'ютері з розділеною пам'яттю.

Реалізація із застосуванням технології GPGPU

Для успішної реалізації алгоритму із застосуванням технології GPGPU треба вирішити два питання:

1. Для кожної операції алгоритму вирішити, де варто її виконувати: на ЦП чи на графічному процесорі.
2. Визначити кількість ядер графічного процесора, що застосовуються.

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

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

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

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

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

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

Примітки

1. Lehman, R. Sherman. Factoring Large Integers. — Mathematics of Computation, 1974. — Т. 28, № 126. — С. 637-646. — DOI:10.2307/2005940.
2. Нестеренко, 2011, с. 140.
3. Василенко, 2003, с. 65—66.
4. Нестеренко, 2011, с. 142.
5. Василенко, 2003, с. 65.
6. Нестеренко, 2011, с. 143.
7. Макаренко А.В.,Пыхтеев А. В., Ефимов С. С. ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ФАКТОРИЗАЦИИ ЦЕЛЫХ ЧИСЕЛ В ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРНЫХ СИСТЕМАХ // Омский государственный университет им. Ф.М. Достоевского (Омск). — 2012. — Т. 4, № 66. — С. 149—158.
8. Желтов С. А. АДАПТАЦИЯ МЕТОДА ШЕРМАНА–ЛЕМАНА РЕШЕНИЯ ЗАДАЧИ ФАКТОРИЗАЦИИ К ВЫЧИСЛИТЕЛЬНОЙ АРХИТЕКТУРЕ CUDA // Российский государственный гуманитарный университет (Москва). — 2012. — Т. 14, № 94. — С. 84-91.

Література

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