Метод Лемана

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

Метод Лемана

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

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

Нехай $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$ не знайдеться.[1]

Модифікованй метод Лемана

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

Нехай $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

.[2] Для доведення даної теореми нам потрібна наступна лема. Лема

Нехай виконані умови теореми. Тоді можна знайти такі натуральні числа

r,\;s

, що

rs<n^{1/3}

і

\mid pr-qs\mid <n^{1/3}

.[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}$ .

Лема доведена.[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

. Теорема доведена. [4]

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

Нехай $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$ - просте число.[5]

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

Швидкість

Обчислення залежності від величини числа, що факторизується

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

.[6]

Залежність від розрядності числа, що факторизується

В більшості випадків більш важливу роль грає залежність часу виконання від розрядності числа, що досліджується. Маючи поліноміальну залежність для величини отримуємо експоненціальну залежність часу виконання методу від розрядності числа, що факторизується.[7]

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

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

Деякі частинні випадки

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

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

Псевдокод

for

a\gets 2

to

\lfloor n^{1/3}\rfloor

do

if

a\vdots n

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)=true

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 for

Пояснення:

$a\vdots n$ означає, що $n$ націло ділиться на $a$ .

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

Функція $gcd(a,b)$ повертає НСД чисел $a$ і $b$ .[7]

Можливості паралельної реалізації методу

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

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

Крок 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 процес-координатор періодично "опитує" процеси на момент знаходження дільника і приймає рішення про припинення чи продовження обчислень. Застосування даного підходу дозволяє отримати лінійне прискорення при збільшенні кількості процесів на комп'ютері з розділеною пам'яттю.[7]

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

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

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

2. Визначити число ядер графічного процесора, що використовуються. Описаний вище підхід можна використовувати для розбиття задачі.[8] Крок 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

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

Приклад

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

Примітки

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

Література

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Lehman-1] Lehman, R. Sherman. Factoring Large Integers. — Mathematics of Computation, 1974. — Т. 28, № 126. — С. 637-646. — DOI:10.2307/2005940.

[FOOTNOTEНестеренко2011140-2] Нестеренко, 2011, с. 140.

[FOOTNOTEВасиленко200365—66-3] Василенко, 2003, с. 65—66.

[FOOTNOTEНестеренко2011142-4] Нестеренко, 2011, с. 142.

[FOOTNOTEВасиленко200365-5] Василенко, 2003, с. 65.

[FOOTNOTEНестеренко2011143-6] Нестеренко, 2011, с. 143.

[Алгоритмы-7] Макаренко А.В.,Пыхтеев А. В., Ефимов С. С. ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ФАКТОРИЗАЦИИ ЦЕЛЫХ ЧИСЕЛ В ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРНЫХ СИСТЕМАХ // Омский государственный университет им. Ф.М. Достоевского (Омск). — 2012. — Т. 4, № 66. — С. 149—158.

[CUDA-8] Желтов С. А. АДАПТАЦИЯ МЕТОДА ШЕРМАНА–ЛЕМАНА РЕШЕНИЯ ЗАДАЧИ ФАКТОРИЗАЦИИ К ВЫЧИСЛИТЕЛЬНОЙ АРХИТЕКТУРЕ CUDA // Российский государственный гуманитарный университет (Москва). — 2012. — Т. 14, № 94. — С. 84-91.