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

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

П'єр Ферма

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

Історія

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

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

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

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

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

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

Доведення  

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

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

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

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

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

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

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

${\displaystyle n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b,}$ в якому ${\displaystyle x=(\left\lceil {\sqrt {n}}\right\rceil +k)}$

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

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

${\displaystyle \left(s+1\right)^{2}-n=s^{2}+2s+1-n,}$ де ${\displaystyle s=\left\lceil {\sqrt {n}}\right\rceil +k.}$

Приклади

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

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

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

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

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

Приклад із більшою кількістю ітерацій

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

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

${\displaystyle {\sqrt {y}}=237}$

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

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

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

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

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

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

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

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

${\displaystyle \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 ,}$ тобто, очевидно, що воно має порядок ${\displaystyle O(n).}$

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

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

Відсіювання

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

Наприклад, будь-який квадрат по модулю 5 дорівнює одному з наступних значень: 0, 1, 4.

Можна попередньо обчислити квадратичні лишки для кількох простих чисел ${\displaystyle p_{j}}$, і перевіряти чи належить ${\displaystyle v_{i}\mod p}$ до обчисленої множини. Лише коли ${\displaystyle v_{i}}$ є квадратичним лишком за всіма вибраними ${\displaystyle p_{j}}$, здійснюється обчислення кореня.

Як модуль можна застосовувати й степені простих чисел, зокрема, двійки. Наприклад, по модулю 16 усі квадрати рівні 0, 1, 4 або 9.

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

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

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

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

Докладніше: метод Лемана

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

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

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

1. Знайти багато пар ${\displaystyle (x,y),}$які задовольняють відношення ${\displaystyle x\equiv y{\pmod {n}}.}$

2. Визначити повний або частковий розклад чисел ${\displaystyle x}$ і ${\displaystyle y}$ на множники для кожної пари ${\displaystyle (x,y).}$

3. Вибрати пари ${\displaystyle (x,y),}$ результати яких задовольняють відношення ${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}.}$

4. Розкласти число ${\displaystyle n}$ на множники.

Приклад

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

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

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

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

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

Справді: ${\displaystyle 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.}$

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

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

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

${\displaystyle \gcd(1416-311,2041)=13}$.

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

У 1981 році математик Карлтонського університету Джон Діксон опублікував розроблений ним метод факторизації на основі ідеї Крайчика.

Докладніше: Метод факторизації Діксона

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

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

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

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

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

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

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

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

Цікаві факти

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

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

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

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

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

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

Примітки

1. Нестеренко, 2011, 7.2.2 Как быстро проверить, что число является полным квадратом (стор. 145—148).
2. Нестеренко, 2012, 7.3 Метод Лемана (стор. 149).
3. Нестеренко, 2012, Метод Крайчика (с. 173).
4. C. Pomerance. A Tale of Two Sieves, 1996, с. 1495.
5. Василенко, 2003, 75—76.
6. Benne de Weger. Cryptanalysis of RSA with Small Prime Difference. — Appl. Algebra Eng. Commun. Comput., 2002. — Vol. 13, no. 1. — P. 17–28. — DOI:10.1007/s002000100088.
7. Sounak Gupta, Goutam Paul. Revisiting Fermat’s Factorization for the RSA Modulus. — CoRR, 2009. — Vol. abs/0910.4179.
8. Principles of Science, Macmillan & Co., 1874, p. 141.

Література

• Задірака В. К., Олексюк О. С. Комп'ютерна арифметика багаторозрядних чисел: наукове видання. — К.: 2003. — 264 с.
• Метод факторизації: навч. посіб. для студентів ВНЗ / Г. Я. Попов, В. І. Острик ; М-во освіти і науки України, Одес. нац. ун-т ім. І. І. Мечникова. — Одеса: ОНУ, 2014. — 118 с. : іл. — Бібліогр.: с. 114—116 (32 назви). —
• Л. Тимошенко, С. Івасьєв, К. Вербик. Удосконалений метод Ферма факторизації чисел // Проблеми становлення інформаційної економіки в Україні: матеріали Всеукр. наук.-практ. конф.. — Львів : Ліга-Прес, 2014. — 24 жовтня. — С. 280—283.

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

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М. : МЦНМО, 2003. — 328 с. — .
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казан. ун, 2011. — 190 с.
• Нестеренко А.Ю. Теоретико-числовые методы в криптографии. — учебное пособие. — Москва : Московский государственный институт электроники и математики, 2012. — 223 с. — .
• Коблиц Н. Курс теории чисел и криптографии. — М. : Научное издательство ТВП, 2001. — 254 с. — .

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

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

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

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