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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
П'єр Ферма

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

Метод заснований на пошуку таких цілих чисел і , які задовольняють відношення , що веде до розкладу .

Історія

[ред. | ред. код]

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

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

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

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

[ред. | ред. код]

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

Якщо непарне, то існує взаємно однозначна відповідність між розкладанням на множники і поданням у вигляді різниці квадратів з , що задається формулами

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

[ред. | ред. код]

Для розкладання на множники непарного числа шукається пара чисел таких, що , або . При цьому числа і є множниками , можливо, тривіальними (тобто одне з них дорівнює 1, а інше — .)

У нетривіальною випадку, рівність рівносильно , тобто того, що є квадратом.

Пошук квадрата такого виду починається з  — найменшого числа, при якому різниця невід'ємна.

Для кожного значення починаючи з , обчислюють і перевіряють, чи не є це число точним квадратом. Якщо не є, то збільшують на одиницю і переходять на наступну ітерацію.

Якщо є точним квадратом, тобто то отримано розкладання:

в якому

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

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

де

Приклади

[ред. | ред. код]

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

[ред. | ред. код]

Візьмемо число . Обчислимо Для будемо обчислювати значення функції . Для подальшої простоти побудуємо таблицю, яка буде містити значення і на кожному кроці ітерації. отримаємо:

1 363 19,052
2 576 24

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

Таким чином має місце рівність: . Звідки випливає, що

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

[ред. | ред. код]

Нехай Тоді або

77 52374 228,854
78 53129 230,497
79 53886 232,134
80 54645 233,763
81 55406 235,385
82 56169 237

Цей розклад не є остаточним, оскільки число не є простим:

У підсумку, остаточний розклад початкового числа на добуток простих множників

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

[ред. | ред. код]

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

.

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

тобто, очевидно, що воно має порядок

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

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

[ред. | ред. код]

Відсіювання

[ред. | ред. код]

При пошуку квадрата натурального числа в послідовності чисел не обов'язково обчислювати квадратний корінь із кожного значення цієї послідовності. Для попереднього відсіювання можна скористатися тим, що квадрат натурального числа по модулю будь-якого числа має бути квадратичним лишком.

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

Можна попередньо обчислити квадратичні лишки для кількох простих чисел , і перевіряти чи належить до обчисленої множини. Лише коли є квадратичним лишком за всіма вибраними , здійснюється обчислення кореня[1].

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

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

[ред. | ред. код]

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

Якщо ж відомо приблизне співвідношення між множниками числа , то можна вибрати раціональне число , приблизно рівне цьому співвідношенню. Тоді можна записати таку рівність: , де множники і близькі в силу зроблених припущень. Тому застосувавши метод Ферма для розкладання числа , їх можна досить швидко знайти. Далі для пошуку і можна застосувати рівності і (у разі, якщо не ділиться на і не ділиться на ).

У загальному випадку, коли співвідношення між множниками невідоме, можна перебрати різні співвідношення , і спробувати розкласти числа . Алгоритм, заснований на цьому методі, запропонував американський математик Шерман Леман в 1974 році. Алгоритм Лемана детерміновано розкладає на множники задане натуральне число за арифметичних операцій, однак у XXI сторіччі становить тільки історичний інтерес і на практиці майже не застосовується[2].

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

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

[ред. | ред. код]

Узагальнення методу Ферма запропонував Моріс Крайчик в 1926 році. Замість пар чисел які задовольняють співвідношенню , Крайчик запропонував шукати пари чисел, що задовольняють більш загальному порівнянню Таке порівняння можна знайти, перемноживши кілька порівнянь виду , де  — невеликі числа, добуток яких буде квадратом. Для цього можна розглянути пари чисел , де  — цілий числа трохи більше , а . Крайчик не запропонував конкретного алгоритму пошуку пар та способу їх складання, однак зауважив, що багато з отриманих таким чином чисел розкладаються на невеликі прості множники, тобто числа є гладкими

Приклад

[ред. | ред. код]

За допомогою методу Крайчика розкладемо число . Число є першим, чий квадрат більший за число : [4].

Визначимо функцію для всіх Ми отримаємо

За методом Ферма, потрібно було б продовжувати розрахунок, доки не буде знайдено квадрат якого-небудь числа. За методом Крайчика потрібно знайти кілька таких , добуток яких являє собою квадрат. Якщо і , тоді

[4]

Деякі з отриманих чисел можна легко факторизувати.

Справді:

А з отриманого розкладу можна побачити, що добуток цих чотирьох чисел являє собою повний квадрат: Тепер можна обчислити

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

.

Таким чином,

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

Алгоритм Діксона заснований на понятті про факторні бази і є узагальненням алгоритму факторизації Ферма. В алгоритмі замість пар чисел, що задовольняють рівнянню шукають пари чисел, що задовольняють більш загальному порівнянню . Обчислювальна складність алгоритму

де

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

Цікаві факти

[ред. | ред. код]

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

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

Вказане Джевонсом число може бути розкладено вручну методом Ферма приблизно за 10 хвилин[джерело?]. Справді, . За 55 кроків можна дійти до співвідношення:

Таким чином розклад на прості множники має вигляд .

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

Примітки

[ред. | ред. код]
  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 назви). — ISBN 978-617-689-066-9
  • Л. Тимошенко, С. Івасьєв, К. Вербик. Удосконалений метод Ферма факторизації чисел // Проблеми становлення інформаційної економіки в Україні: матеріали Всеукр. наук.-практ. конф.. — Львів : Ліга-Прес, 2014. — 24 жовтня. — С. 280—283.
російською мовою
англійською мовою
французькою мовою
  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.