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

Метод факторизації Ферма — алгоритм факторизації (розклад на множники) непарного цілого числа 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$.

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

Відсіювання

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

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

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

Як модуль можна застосовувати й степені простих чисел, зокрема, двійки. Наприклад, по модулю 16 усі квадрати рівні 0, 1, 4 або 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})$ арифметичних операцій, однак у XXI сторіччі становить тільки історичний інтерес і на практиці майже не застосовується.

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

Узагальнення методу Ферма запропонував Моріс Крайчик в 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$. Крайчик не запропонував конкретного алгоритму пошуку пар $u,v$ та способу їх складання, однак зауважив, що багато з отриманих таким чином чисел $v_{i}$ розкладаються на невеликі прості множники, тобто числа $v_{i}$ є гладкими

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

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

Визначимо функцію $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}}.$

Деякі з отриманих чисел $(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 . На час публікації алгоритму RSA (1977 рік) було відомо небагато алгоритмів факторизації, найвідомішим серед яких був метод Ферма.

Цікаві факти

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

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

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

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

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

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

Література

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

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

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М. : МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань : Казан. ун, 2011. — 190 с.
• Нестеренко А.Ю. Теоретико-числовые методы в криптографии. — учебное пособие. — Москва : Московский государственный институт электроники и математики, 2012. — 223 с. — ISBN 978-5-94506-320-4.
• Коблиц Н. Курс теории чисел и криптографии. — М. : Научное издательство ТВП, 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.

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

1. 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.