Метод Лемана

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

Опис

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

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

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

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

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

$x^2-y^2=4kn,1⩽k⩽r$,

$x\equiv k+1(\mathrm{mod}2)$,

$x\equiv k+1(\mathrm{mod}4)$, якщо $k$ непарне,

$0⩽x-(4kn{)}^{1/2}⩽\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⩾1$, що
1. Виконується рівність $x^2-y^2=4kn$ при $k<n^{1/3}$,
2. Виконується нерівність $0⩽x-\lfloor \sqrt{4kn}\rfloor <\frac{n^{1/6}}{4\sqrt{k}}+1$.Шаблон:Sfn

Для доведення цієї теореми потрібна наступна лема.

Лема

Нехай виконано умови теореми. Тоді можна знайти такі натуральні числа $r,s$, що $rs<n^{1/3}$ і $\mid pr-qs\mid <n^{1/3}$.Шаблон:Sfn

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

Припустимо, що $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⩾\sqrt{4kn}$ і $z⩾0$. Використовуючи оцінку зверху для $y$, отримуємо
$n^{2/3}>y^2=x^2-4kn=(pr+qs+\sqrt{4kn})(pr+qs-\sqrt{4kn})⩾2\sqrt{4kn}(pr+qs-\sqrt{4kn})⩾2\sqrt{4kn}(z-1)$.
З цього випливає, що $z<\frac{n^{2/3}}{2\sqrt{4kn}}+1=\frac{n^{1/6}}{4\sqrt{k}}+1$. Теорему доведеноШаблон:Sfn.

Алгоритм

Нехай $n$ — непарне і $n>8$.

Крок 1. Для простих $a=2,3,\dots ,\lfloor n^{1/3}\rfloor$ перевірити умову $a\mid n$. Якщо на цьому кроці не вдалося розкласти $n$ на множники, то переходимо до кроку 2.

Крок 2. Якщо на кроці 1 дільник не знайдено і $n$ — складене число, то $n=pq$, де $p,q$ - прості числа, і $n^{1/3}<p⩽q<n^{2/3}$. Тоді для всіх $k=1,2,\dots ,\lfloor n^{1/3}\rfloor$ і всіх $d=0,\dots ,\lfloor \frac{n^{1/6}}{4\sqrt{k}}\rfloor +1$ перевірити чи є число ${(\lfloor \sqrt{4kn}\rfloor +d)}^2-4kn$ квадратом натурального числа. Якщо це так, то для $A=\lfloor \sqrt{4kn}\rfloor +d$ і $B=\sqrt{A^2-4kn}$ виконується взяття по модулю:

$A^2\equiv B^2(\mathrm{mod}n)$ чи $(A-B)(A+B)\equiv 0(\mathrm{mod}n)$.

У цьому випадку для $d^{*}=\gcd (A-B,n)$ перевіряється нерівність $1<d^{*}<n$ і, якщо ця нерівність виконується, то $n=d^{*}\cdot (n/d^{*})$ — розклад $n$ на два множники. Якщо ж алгоритм не знайшов розкладу $n$ на два множники, то $n$ — просте числоШаблон:Sfn.

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

Псевдокод

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

if $amodn=0$ then

return $a$

end if

end for

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

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

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

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

$B\leftarrow \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,\dots ,11$ і всіх $d=0,1,\dots ,4$ перевіряємо, чи є число ${(\lfloor \sqrt{4kn}\rfloor +d)}^2-4kn$ квадратом натурального числа. У нашому випадку для $k=3$ і $d=1$ вираз ${(\lfloor \sqrt{4kn}\rfloor +d)}^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$.

Складність другого кроку оцінюється в операціях перевірки чи є число ${(\lfloor \sqrt{4kn}\rfloor +d)}^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})$ операційШаблон:Sfn.

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

Для великих чисел існує залежність часу виконання операцій від їх розрядності. Наприклад, складання двох чисел потребує часу, що лінійно залежить від довжини (більшого з них), а час множення й ділення ще більший, тобто, залежить від довжини чисел нелінійно (поліноміально). Отже, метод потребує поліноміальної кількості операцій ($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,\dots \lfloor n^{1/3}\rfloor \}$. Обчислювальний процес почергово перевіряє $n$ на кратність числам зі свого набору дільників. Через деякі проміжки часу головний процес-координатор «опитує» обчислювальні процеси на предмет виявлення дільника. У випадку, коли достатньо перевірити $n$ на простоту, процес-координатор, отримавши інформацію про знайдення дільника, надсилає іншим процесам сигнал про завершення роботи. Якщо ж дільник не знайдено, чи потрібно знайти всі дільники, пошук продовжується.

Крок 2:

Кожному обчислювальному процесу аналогічно з кроком 1 видається свій набір чисел $k$ з множини $\{2,3,4,\dots \lfloor n^{1/3}\rfloor \}$. Обчислювальний процес по черзі перевіряє всі умови, описані в алгоритмі, визначаючи чи знайдений нетривіальний множник. Аналогічно з кроком 1 процес-координатор періодично «опитує» процеси щодо знайдення дільника і приймає рішення про припинення чи продовження обчислень.

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

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

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

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

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

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

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

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

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

1. Перевірити чи є число ${(\lfloor \sqrt{4kn}\rfloor +d)}^2-4kn$ квадратом натурального числа.
2. У випадку отримання позитивного результату на попередньому пункті, обчислити $A=\lfloor \sqrt{4kn}\rfloor +d$ і $B=\sqrt{A^2-4kn}$.
3. Для значень $A$ і $B$ перевірити умову $A^2\equiv B^2(\mathrm{mod}n)$.
4. Для значень $A$ і $B$, що пройшли останню перевірку, перевірити виконання умови $0<\gcd (A\pm B,n)<n$.

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

Література

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга