Метод факторизації Ферма

Метод факторизації Ферма — алгоритм факторизації (розклад на множники) непарного цілого числа n, представлений П'єром Ферма (1601—1665) у 1643 році.

П'єр Ферма

Метод заснований на пошуку таких цілих чисел $x$ і $y$ , які задовольняють відношення $x^{2}-y^{2}=n$ , що веде до розкладу $n=(x-y)\cdot (x+y)$ .

Історія

На початку XVII століття у Франції математичні ідеї почали активно поширюватися між вченими за допомогою листування. В 1638 році до кола вчених, які листувалися приєднався П'єр Ферма. Листування було зручним способом спілкування, так як Ферма жив в Тулузі, а багато його знайомих вчених жили в Парижі.

Одним таким вченим був Марен Мерсенн, який займався розповсюдженням листів, пересиланням і зв'язком багатьох вчених між собою. 26 грудня 1638 року в листі Мерсенну Ферма згадав, що знайшов метод, за допомогою якого можна знаходити подільники позитивних чисел, але будь-які подробиці і опис методу він опустив. На той момент Мерсенн також вів листування з французьким математиком Бернаром Френіклєм де Бессі, який займався, як і Ферма, теорією чисел, зокрема, дільниками натуральних чисел і досконалими числами. На початку 1640 року, дізнавшись про те, що Ферма отримав метод знаходження дільників, Френікль пише Мерсенну, і той пересилає лист Ферма.

Мерсенн довгий час був сполучною ланкою між двома математиками в їх листуванні. Саме в листах Френіклю Ферма зміг довести коректність методу факторизації, а також вперше сформулювати і обґрунтувати основні положення теореми, яка пізніше була названа Малою теоремою Ферма.

Обґрунтування

Метод Ферма заснований на теоремі про подання числа у вигляді різниці двох квадратів :

Якщо $n>1$ непарне, то існує взаємно однозначна відповідність між розкладанням на множники $n=a\cdot b$ і поданням у вигляді різниці квадратів $n=x^{2}-y^{2}$ з $x>y>0$ , що задається формулами $x={\tfrac {a+b}{2}},$ $y={\tfrac {a-b}{2}},$ $a=x+y,$ $b=x-y.$

Доведення

Якщо задана факторизація $n=a\cdot b$ , тоді має місце відношення: $n=a\cdot b=({\tfrac {a+b}{2}})^{2}-({\tfrac {a-b}{2}})^{2}$ . Таким чином виходить уявлення у вигляді різниці двох квадратів. Назад, якщо дано, що $n=x^{2}-y^{2}$ , то праву частину можна розкласти на множники: $(x-y)(x+y)$ .

Опис алгоритму

Для розкладання на множники непарного числа $n$ шукається пара чисел $(x,y)$ таких, що $x^{2}-y^{2}=n$ , або $(x-y)\cdot (x+y)=n$ . При цьому числа $(x+y)$ і $(x-y)$ є множниками $n$ , можливо, тривіальними (тобто одне з них дорівнює 1, а інше — $n$ .)

У нетривіальною випадку, рівність $x^{2}-y^{2}=n$ рівносильно $x^{2}-n=y^{2}$ , тобто того, що $x^{2}-n$ є квадратом.

Пошук квадрата такого виду починається з $x=\left\lceil {\sqrt {n}}\right\rceil$ — найменшого числа, при якому різниця $x^{2}-n$ невід'ємна.

Для кожного значення $k\in \mathbb {N} ,$ починаючи з $k=1$ , обчислюють $(\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n$ і перевіряють, чи не є це число точним квадратом. Якщо не є, то $k$ збільшують на одиницю і переходять на наступну ітерацію.

Якщо $(\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n$ є точним квадратом, тобто $x^{2}-n=(\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n=y^{2},$ то отримано розкладання:

n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b,

в якому

x=(\left\lceil {\sqrt {n}}\right\rceil +k)

Якщо воно є тривіальним і єдиним, то $n$ — просте.

На практиці значення виразу на $(k+1)$ -ому кроці вираховується з врахуванням значення на $k$ -ому кроці:

\left(s+1\right)^{2}-n=s^{2}+2s+1-n,

де

s=\left\lceil {\sqrt {n}}\right\rceil +k.

Приклади

Приклад з малим числом ітерацій

Візьмемо число $n=10873$ . Обчислимо $s=\left\lceil {\sqrt {n}}\right\rceil =105.$ Для $k=1,2,...$ будемо обчислювати значення функції $s+k$ . Для подальшої простоти побудуємо таблицю, яка буде містити значення $y=(s+k)^{2}-n$ і ${\sqrt {y}}$ на кожному кроці ітерації. отримаємо:

$k$	$y$	${\sqrt {y}}$
1	363	19,052
2	576	24

Як видно з таблиці, вже на другому кроці ітерації було отримано ціле значення ${\sqrt {y}}$ .

Таким чином має місце такий вираз: $(105+2)^{2}-n=24^{2}$ . Звідси випливає, що $n=107^{2}-24^{2}=131\cdot 83=10873.$

Приклад з великим числом ітерацій

Нехай $n=89755.$ Тоді ${\sqrt {n}}\approx 299,591$ або $s=\left\lceil {\sqrt {n}}\right\rceil =300.$

$k$	$y$	${\sqrt {y}}$
77	52374	228,854
78	53129	230,497
79	53886	232,134
80	54645	233,763
81	55406	235,385
82	56169	237

{\sqrt {y}}=237

a=s+k+{\sqrt {y}}=300+82+237=619

b=s+k-{\sqrt {y}}=300+82-237=145

Цей розклад не є остаточним, оскільки число $145$ не є простим: $145=29\cdot 5.$

У підсумку, остаточний розклад початкового числа $n$ на добуток простих множників $89755=5\cdot 29\cdot 619.$

Оцінка складності

Найбільша ефективність розрахунку методом факторизації Ферма досягається в разі, коли множники числа $n$ приблизно рівні між собою. Це забезпечує відносно короткий пошук послідовності

$s^{2}-n,\ (s+1)^{2}-n,\ (s+2)^{2}-n\ ...\ (s+k)^{2}-n.$

У найгіршому варіанті, коли, наприклад, $a$ близько до $n$ а $b$ близько до 1, алгоритм Ферма працює гірше в порівнянні з методом перебору дільників. Число ітерацій для даного випадку:

$\operatorname {Iter} (n)={\tfrac {a+b}{2}}-\left\lceil {n}^{1/2}\right\rceil \thickapprox {\tfrac {n}{2}}-\left\lceil {n}^{1/2}\right\rceil ,$ тобто, очевидно, що воно має порядок $O(n).$

Метод факторизації Ферма буде працювати не гірше методу перебору дільників, якщо $\operatorname {Iter} (n)<{n}^{1/2}$ , звідси можна отримати оцінку для більшого дільника $a<4{n}^{1/2}.$ Отже, метод Ферма має експонентну оцінку і, як метод пробного поділу, не підходить для розкладання великих чисел. Можна вдосконалити його, якщо виконати спочатку пробний поділ $n$ на числа від 2 до деякої константи B, а потім виконати пошук дільників методом Ферма. Такий похід допомагає позбутися від малих дільників числа $n$ .

Удосконалення

Комбінація з методом перебору дільників

Припустимо, що ми намагаємося розкласти на множники число n = 2345678917 методом Ферма, але крім b обчислюємо також і a − b. Починаючи з ${\sqrt {n}}$ , можна записати:

a	48 433	48 434	48 435	48 436
b²	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9
a − b	48 156,3	48 017,5	47 915,1	47 830,1

Якщо тепер для розкладання числа $n$ застосувати метод перебору дільників, то доцільно перевіряти дільники $n$ лише до 47 830 (а не до 48 432), бо якби існував більший дільник, то його було б знайдено методом Ферма. Отже, можна сказати, що за чотири кроки методу Ферма було перевірено всі можливі дільники $n$ у діапазоні від 47 830 до 48 432.

Таким чином, можна комбінувати метод Ферма з методом перебору дільників. Досить вибрати число $c>{\sqrt {n}}$ і застосовувати метод Ферма для перевірки дільників між $c$ і ${\sqrt {n}}$ , а дільники, що залишилися, перевірити методом перебору дільників, причому перевіряти потрібно тільки до числа $c-{\sqrt {c^{2}-n}}$ .

У наведеному вище прикладі, коли $c=48436$ , перебирати дільники необхідно до числа 47830. Можна вибрати більше число с. Наприклад $c=55000$ знижує межу для перебирання дільників до 28937.

Комбінація методів дає кращий результат, бо якщо різниця між дільниками числа $n$ велика, то метод перебору дільників ефективніший методу Ферма. Це ілюструє наступний приклад:

a	60 001	60 002
b²	1 254 441 084	1 254 561 087
b	35 418,1	35 419,8
a − b	24 582,9	24 582,2

Метод решета

При пошуку квадрата натурального числа в послідовності чисел $a^{2}-n$ годі й обчислювати квадратний корінь з кожного значення цієї послідовності, і навіть не перевіряти всі можливі значення для $a$ . Для прикладу розглянемо число $n=2345678917$ :

a	48 433	48 434	48 435	48 436
b²	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9

Можна відразу, не обчислюючи квадратного кореня, сказати, що жодне зі значень $b^{2}$ в таблиці не є квадратом. Досить, наприклад, скористатися тим, що всі квадрати натуральних чисел, взяті по модулю 20, дорівнюють одному з наступних значень: 0, 1, 4, 5, 9, 16. Ці значення повторюються при кожному збільшенні $a$ на 10. У прикладі $n=17$ по модулю 20, тому віднімаючи 17 (або додаючи 3), отримуємо, що число $b^{2}$ по модулю 20 дорівнює одному з наступних: 3, 4, 7, 8, 12, 18. Але оскільки $b$ — натуральне число, то звідси отримуємо, що $b^{2}$ по модулю 20 може дорівнювати лише 4. Отже, $a^{2}=1$ по модулю 20 і $a=1$ або $a=9$ по модулю 10. Таким чином, можна перевіряти корінь виразу $a^{2}-n$ не для всіх $a$ , а тільки для тих, які закінчуються на 1 або 9.

Аналогічно як модуль можна використовувати будь-які ступені різних простих чисел. Наприклад, взявши те ж число $n=2345678917$ , знаходимо:

По модулю 16:	Квадрати рівні	0, 1, 4 або 9
	n mod 16 рівне	5
	отже, $a^{2}$ рівне	9
	і $a$ рівне	3, 5, 11 або 13 по модулю 16
По модулю 9:	Квадрати рівні	0, 1, 4, або 7
	n mod 9 рівне	7
	отже, $a^{2}$ рівне	7
	і $a$ рівне	4 або 5 по модулю 9

Удосконалення шляхом домноження

Метод Ферма добре працює коли у числа $n$ є множник, близький до квадратного кореня з $n$ .

Якщо ж відомо приблизне співвідношення $d/c$ між множниками числа $n$ , то можна вибрати раціональне число $u/v$ , приблизно рівне цьому співвідношенню. Тоді можна записати таку рівність: $nuv=cv\cdot du$ , де множники $cv$ і $du$ близькі в силу зроблених припущень. Тому застосувавши метод Ферма для розкладання числа $nuv$ , їх можна досить швидко знайти. Далі для пошуку $c$ і $d$ можна застосувати рівності $\gcd(n,cv)=c$ і $\gcd(n,du)=d$ (у разі, якщо $u$ не ділиться на $c$ і $v$ не ділиться на $d$ ).

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

Метод Крайчика—Ферма

Узагальнення методу Ферма запропонував Моріс Крайчик в 1926 році. Замість пар чисел $(x,y),$ які задовольняють співвідношенню $x^{2}-y^{2}=n$ , Крайчик запропонував шукати пари чисел, що задовольняють більш загальному порівнянню $x^{2}\equiv y^{2}{\pmod {n}}.$ Таке порівняння можна знайти, перемноживши кілька порівнянь виду $u_{i}^{2}\equiv v_{i}$ , де $v_{i}$ — невеликі числа, добуток яких буде квадратом. Для цього можна розглянути пари чисел $(u_{i},v_{i})$ , де $u_{i}$ — цілий числа трохи більше ${\sqrt {n}}$ , а $v_{i}=u_{i}^{2}-n$ . Крайчик зауважив, що багато з отриманих таким чином чисел $v_{i}$ розкладаються на невеликі прості множники, тобто числа $v_{i}$ є гладкими

Послідовність дій по Крайчику [1]

1. Знайти багато пар

(x,y),

які задовольняють відношення

x\equiv y{\pmod {n}}.

2. Визначити повний або частковий розклад чисел

x

і

y

на множники для кожної пари

(x,y).

3. Вибрати пари

(x,y),

результати яких задовольняють відношення

x^{2}\equiv y^{2}{\pmod {n}}.

4. Розкласти число

n

на множники.

Приклад

За допомогою метода Крайчика-Ферма розкладемо число $n=2041$ . Число $46$ є першим, чий квадрат більший за число $n$ : $46^{2}=2116$ [2].

Визначимо функцію $v(u)=u^{2}-n$ для всіх $u=46,47,\dots$ Ми отримаємо $75,168,263,360,459,560,\dots$

За методом Ферма, потрібно було б продовжувати розрахунок, доки не буде знайдено квадрат якого-небудь числа. За методом Крайчика—Ферма потрібно знайти кілька таких $v_{i}$ , добуток яких являє собою квадрат. Якщо $\ v(u_{1})v(u_{2})...v(u_{k})=y^{2}$ і $u_{1}u_{2}\dots u_{k}=x$ , тоді

x^{2}=u_{1}^{2}u_{2}^{2}...u_{k}^{2}\equiv (u_{1}^{2}-n)\cdot (u_{2}^{2}-n)\cdots (u_{k}^{2}-n)=v(u_{1})\cdot v(u_{2})\cdots v(u_{k})=y^{2}{\pmod {n}}.

[2]

Крайчик відзначив, що деякі з отриманих чисел $(u_{k}^{2}-n)$ можна легко факторизувати.

Справді: $75=3\cdot 5^{2},\ 168=2^{3}\cdot 3\cdot 7,\ 360=2^{3}\cdot 3^{2}\cdot 5,\ 560=2^{4}\cdot 5\cdot 7.$

А з отриманого розкладу можна побачити, що добуток цих чотирьох чисел являє собою повний квадрат: $2^{10}\cdot 3^{4}\cdot 5^{4}\cdot 7^{2}.$ Тепер можна обчислити $x,y:$

$x=46\cdot 47\cdot 49\cdot 51\equiv 311{\pmod {2041}},\ y=2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\equiv 1416{\pmod {2041}}.$

Оскільки $311\not \equiv \pm 1416{\pmod {2041}}$ , то за алгоритмом Евкліда обчислюємо найбільшого спільного дільника (1416 - 311) та 2041:

\gcd(1416-311,2041)=13

.

Таким чином, $2041=13\cdot 157.$

Алгоритм Діксона

У 1981 році математик Карлтонського університету Джон Діксон опублікував розроблений ним метод факторизації на основі ідеї Крайчика. Алгоритм Діксона заснований на понятті про факторні бази і є узагальненням алгоритму факторизації Ферма. В алгоритмі замість пар чисел, що задовольняють рівняння $x^{2}-y^{2}=n$ шукають пари чисел, що задовольняють більш загальному порівнянню $x^{2}\equiv y^{2}{\pmod {n}}$ , для розв'язку якого Крайчиком помітив декілька корисних фактів. Обчислювальна складність алгоритму

T=O\left({L\left({n}\right)}^{2}\right),

де $L\left({n}\right)=\exp {\left({\sqrt {\ln {n}\cdot \ln {\ln {n}}}}\right)}.$

Інші вдосконалення

Ідея методу факторизації Ферма лежить в основі найшвидших відомих методів факторизації великих напівпростих чисел — методу квадратичного решета і загального методу решета числового поля. Основна відмінність методу квадратичного решета від методу Ферма полягає в тому, що замість пошуку квадрата в послідовності $a^{2}-n$ шукають пари таких чисел, чиї квадрати рівні по модулю $n$ (кожна з цих пар може бути розкладанням числа $n$ ). Потім вже серед знайдених пар чисел шукають ту пару, яка і є розкладанням числа $n$

Розвитком методу факторизації Ферма є метод квадратичних форм Шенкса (також відомий як SQUFOF), ґрунтований на застосуванні квадратичних форм. Цікаво, що для 32-розрядних комп'ютерів алгоритми, ґрунтуються на даному методі, і є безумовними лідерами серед алгоритмів факторизації для чисел від $10^{10}$ до $10^{18}$ ^{[джерело?]}.

Застосування

Алгоритм факторизації Ферма можна застосувати для криптоаналізу RSA. Якщо випадкові числа $p,q$ , добуток яких дорівнює $n$ , близькі одне до одного, то їх можна знайти методом факторизації Ферма. Після чого можна знайти секретну експоненту $d$ , зламавши таким чином RSA [3] [4]. На час публікації алгоритму RSA (1977 рік) було відомо небагато алгоритмів факторизації, найвідомішим серед яких був метод Ферма.

Цікаві факти

Відомий англійський економіст і логіст У. С. Джевонс зробив у своїй книзі «Принципи науки» («The Principles of Science», 1874 року таке припущення:

За даними двома числами можна знайти їх добуток простим і надійним способом, але зовсім інша справа, коли для великого числа необхідно знайти його множники. Чи можна сказати, які два числа перемножити, щоб вийшло число 8 616 460 799? Я думаю, що навряд чи хто-небудь окрім мене знає це.[5]

Вказане Джевонсом число може бути розкладено вручну методом Ферма із застосуванням методу решета приблизно за 10 хвилин. Справді, $\left\lceil {\sqrt {n}}\right\rceil =92825$ . Використовуючи метод решета, можна швидко прийти до співвідношення:

$92880^{2}-n=10233601=3199^{2}.$

Таким чином розклад на прості множники має вид $8616460799=89681\cdot 96079$ .

Втім, основна думка Джевонса — про складність розкладання чисел на прості множники в порівнянні з їх перемноженням — справедлива, але тільки в тому випадку, коли мова про добуток чисел, що не настільки близькі одне до одного.

Примітки

Нестеренко, 2011, с. 164.
C. Pomerance. A Tale of Two Sieves, 1996, с. 1495.
Benne de Weger. Revisiting Fermat’s Factorization for the RSA Modulus. — Appl. Algebra Eng. Commun. Comput., 2002. — Т. 13, № 1. — С. 17–28. — DOI:10.1007/s002000100088.
Sounak Gupta, Goutam Paul. Revisiting Fermat’s Factorization for the RSA Modulus. — CoRR, 2009. — Т. abs/0910.4179.
Principles of Science, Macmillan & Co., 1874, p. 141.

Література

Задірака В. К., Олексюк О. С. Комп'ютерна арифметика багаторозрядних чисел: наукове видання. — К.: 2003. — 264 с.
Метод факторизації великорозрядних чисел у базисі Радемахера / С. В. Івасьєв // Вісн. Нац. ун-ту «Львів. політехніка». — 2012. — № 745. — С. 85-91. — Бібліогр.: 6 назв.
Метод факторизації: навч. посіб. для студентів ВНЗ / Г. Я. Попов, В. І. Острик ; М-во освіти і науки України, Одес. нац. ун-т ім. І. І. Мечникова. — Одеса: ОНУ, 2014. — 118 с. : іл. — Бібліогр.: с. 114—116 (32 назви). — ISBN 978-617-689-066-9
Удосконалений метод Ферма факторизації чисел / Л. Тимошенко, С. Івасьєв, К. Вербик // Проблеми становлення інформаційної економіки в Україні: матеріали Всеукр. наук.-практ. конф.; м. Львів, 23-25 жовтня 2014 р. МОН України, Львівський нац. ун-т ім. І. Франка. — Л. : Ліга-Прес, 2014. — С. 280—283

російською мовою

Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М. : МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казан. ун, 2011. — 190 с.
Коблиц Н. Курс теории чисел и криптографии. — М. : Научное издательство ТВП, 2001. — 254 с. — ISBN 5-94057-103-4.

англійською мовою

Bressoud D. M. Factorization and Primality Testing. — New York : Springer-Verlag, 1989. — 260 с. — ISBN 0-387-97040-1.
Mahoney M. S. The Mathematical Career of Pierre de Fermat. — Paris : Princeton Univ. Press, 1994. — С. 324-332. — ISBN 0-691-03666-7.
Carl Pomerance. A Tale of Two Sieves. — Notices Amer. Math. Soc, 1996. — Vol. 43, no. 12. — P. 1473–1485.

французькою мовою

Kraitchik M. ANALYSE INDÉTERMINÉE DU SECOND DEGRÉ ET FACTORISATION. CHAPITRE XIV. // THEORIE DES NOMBRES. — Paris : Gauthier-Villars, 1926. — Т. 2. — С. 195-208. — ISBN 0-387-97040-1.

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

[FOOTNOTEНестеренко2011164-1] Нестеренко, 2011, с. 164.

[FOOTNOTEC._Pomerance._A_Tale_of_Two_Sieves19961495-2] C. Pomerance. A Tale of Two Sieves, 1996, с. 1495.

[Benne_de_Weger-3] Benne de Weger. Revisiting Fermat’s Factorization for the RSA Modulus. — Appl. Algebra Eng. Commun. Comput., 2002. — Т. 13, № 1. — С. 17–28. — DOI:10.1007/s002000100088.

[Gupta-4] Sounak Gupta, Goutam Paul. Revisiting Fermat’s Factorization for the RSA Modulus. — CoRR, 2009. — Т. abs/0910.4179.

[5] Principles of Science, Macmillan & Co., 1874, p. 141.