Перегляд вихідного коду сторінки Метод факторизації Ферма

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

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

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

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

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

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

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

{{Hider|title=Доведення|hidden=1|title-style=text-align: left;|content-style=text-align: left;|content=Якщо задана факторизація <math>n = a\cdot b</math>, тоді має місце відношення:  <math>n = a\cdot b = (\tfrac{a+b}{2})^2-(\tfrac{a-b}{2})^2</math>. Таким чином виходить уявлення у вигляді різниці двох квадратів. Назад, якщо дано, що <math>n=x^2-y^2</math>, то праву частину можна розкласти на множники: <math>(x-y)(x+y)</math>.}}

== Опис алгоритму ==
Для [[Факторизація|розкладання на множники]] [[Парність (математика)|непарного числа]] <math>n</math> шукається пара чисел <math>(x,y)</math> таких, що <math>x^2-y^2=n</math>, або <math>(x-y)\cdot (x+y) = n</math>. При цьому числа <math>(x+y)</math> і <math>(x-y)</math> є множниками <math>n</math>, можливо, тривіальними (тобто одне з них дорівнює 1, а інше&nbsp;— <math>n</math>.)

У нетривіальною випадку, рівність <math>x^2-y^2=n</math> рівносильно <math>x^2-n=y^2</math>, тобто того, що <math>x^2-n</math> є [[Квадрат (алгебра)|квадратом]].

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

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

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

Якщо воно є тривіальним і єдиним, то <math>n</math>&nbsp;— просте.

На практиці значення виразу на <math>(k+1)</math>-ому кроці вираховується з врахуванням значення на <math>k</math>-ому кроці:
: <math>\left( s + 1 \right)^2 - n = s^2 + 2s + 1 - n,</math> де <math>s=\left\lceil\sqrt{n}\right\rceil+k.</math>

== Приклади ==

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

{| class="prettytable"
!<math>k</math>
!<math>y</math>
!<math>\sqrt{y}</math>
|-
|1
|363
|19,052
|-
|2
|576
|24
|-
|}

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

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

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


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

{| class="prettytable"
!<math>k</math>
!<math>y</math>
!<math>\sqrt{y}</math>
|-
|77
|52374
|228,854
|-
|78
|53129
|230,497
|-
|79
|53886
|232,134
|-
|80
|54645
|233,763
|-
|81
|55406
|235,385
|-
|82
|56169
|237
|-
|}

: <math>\sqrt{y} = 237</math>
: <math>a = s + k + \sqrt{y} = 300 + 82 + 237 = 619</math>
: <math>b = s + k - \sqrt{y} = 300 + 82 - 237 = 145</math>

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

У підсумку, остаточний розклад початкового числа <math>n</math> на добуток [[Простий множник|простих множників]] <math>89755=5 \cdot 29 \cdot 619.</math>
<!-- Приклад не дуже добрий: відразу видно, що 89755 ділиться на 5. Добре б навести приклад без малих дільників -->

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

<math>s^2 - n,  \ (s+1)^2 - n,  \ (s+2)^2 - n  \ ...  \ (s+k)^2-n</math>.

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

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

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

== Удосконалення ==
=== Відсіювання ===

При пошуку квадрата [[Натуральне число | натурального числа]] в послідовності чисел <math>v_i = a_i^2 - n</math> не обов'язково обчислювати квадратний корінь із кожного значення цієї послідовності.
Для попереднього відсіювання можна скористатися тим, що квадрат натурального числа [[Порівняння по модулю | по модулю]] будь-якого числа має бути [[Квадратичний лишок|квадратичним лишком]]. 

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

Можна попередньо обчислити квадратичні лишки для кількох [[просте число|простих чисел]] <math>p_j</math>, і перевіряти чи належить <math>v_i\mod p</math> до обчисленої множини. Лише коли <math>v_i</math> є квадратичним лишком за всіма вибраними <math>p_j</math>, здійснюється [[Цілочисельний квадратний корінь|обчислення кореня]]{{sfn|Нестеренко|2011|loc= 7.2.2 Как быстро проверить, что число является полным квадратом (стор. 145—148)}}.

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

=== Удосконалення шляхом домноження ===
Метод Ферма добре працює коли у числа <math>n</math> є множник, близький до квадратного кореня з <math>n</math>.

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

У загальному випадку, коли співвідношення між множниками <math>n</math> невідоме, можна перебрати різні співвідношення <math>u_i/v_i</math>, і спробувати розкласти числа <math>n \cdot u_i \cdot v_i</math>. Алгоритм, заснований на цьому методі, запропонував американський математик Шерман Леман в 1974 році. Алгоритм Лемана детерміновано [[Факторизація | розкладає на множники]] задане [[натуральне число]] <math>n</math> за <math>O(n^{1/3})</math> арифметичних операцій, однак у XXI сторіччі становить тільки історичний інтерес і на практиці майже не застосовується{{sfn|Нестеренко|2012|loc= 7.3 Метод Лемана (стор. 149)}}.
{{Main|метод Лемана}}

=== Метод Крайчика ===
Узагальнення методу Ферма запропонував Моріс Крайчик в 1926 році. Замість пар чисел <math>(x,y),</math> які задовольняють співвідношенню <math>x^2-y^2 = n</math>, Крайчик запропонував шукати пари чисел, що задовольняють більш загальному порівнянню <math>x^2\equiv y^2 \pmod{n}.</math> Таке порівняння можна знайти, перемноживши кілька порівнянь виду <math>u_i^2 \equiv v_i</math>, де <math>v_i</math>&nbsp;— невеликі числа, добуток яких буде квадратом. Для цього можна розглянути пари чисел <math>(u_i,v_i)</math>, де <math>u_i</math>&nbsp;— цілий числа трохи більше <math>\sqrt n</math>, а <math>v_i = u_i^2-n </math>. Крайчик не запропонував конкретного алгоритму пошуку пар <math>u,  v</math> та способу їх складання, однак зауважив, що багато з отриманих таким чином чисел <math>v_i</math> розкладаються на невеликі прості множники, тобто числа <math>v_i</math> є [[Гладке число | гладкими]]
{{Hider|
  title = Послідовність дій по Крайчику {{sfn|Нестеренко|2012|loc=Метод Крайчика (с. 173)}}|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
: '''1.''' Знайти багато пар <math>(x,y),</math>які задовольняють відношення <math>x \equiv y \pmod{n}.</math>
: '''2.''' Визначити повний або частковий розклад чисел <math>x</math> і <math>y</math> на множники для кожної пари <math>(x,y).</math>
: '''3.''' Вибрати пари <math>(x,y),</math> результати яких задовольняють відношення <math>x^2 \equiv y^2 \pmod{n}.</math>
: '''4.''' Розкласти число <math>n</math> на множники.
}}

==== Приклад ====

За допомогою методу Крайчика розкладемо число <math>n=2041</math>. Число <math>46</math> є першим, чий квадрат більший за число <math>n</math>: <math>46^2=2116</math>{{sfn|C. Pomerance. A Tale of Two Sieves|1996|p=1495}}.

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

За методом Ферма, потрібно було б продовжувати розрахунок, доки не буде знайдено квадрат якого-небудь числа. За методом Крайчика потрібно знайти кілька таких <math>v_i</math>, добуток яких являє собою квадрат. Якщо <math>\ v(u_1)v(u_2) ... v(u_k)=y^2</math> і <math> u_1 u_2 \dots u_k=x</math>, тоді
: <math>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}.</math>{{sfn|C. Pomerance. A Tale of Two Sieves|1996|p=1495}}

Деякі з отриманих чисел <math>(u_k^2-n)</math> можна легко факторизувати.

Справді: <math>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.</math>

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

<math>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}.</math>

Оскільки <math> 311 \not\equiv \pm 1416\pmod{2041}</math>, то за [[Алгоритм Евкліда|алгоритмом Евкліда]] обчислюємо [[найбільший спільний дільник|найбільшого спільного дільника]] (1416 - 311) та 2041:
:<math>\gcd(1416 - 311, 2041) = 13</math>.

Таким чином, <math>2041=13 \cdot 157.</math>

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

: <math>T = O\left({L\left({n}\right)}^{2}\right),</math>

де <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}.</math>

=== Подальші вдосконалення ===
Ідея Крайчика лежить в основі найшвидших відомих методів факторизації великих напівпростих чисел&nbsp;— [[Квадратичне решето | методу квадратичного решета]] і [[Загальний метод решета числового поля | загального методу решета числового поля]]. Основна відмінність методу квадратичного решета від методу Ферма полягає в тому, що замість пошуку квадрата в послідовності <math> a^2-n </math> шукають пари таких чисел, чиї квадрати [[Порівняння по модулю |рівні по модулю]] <math>n</math> (кожна з цих пар може бути розкладанням числа <math>n</math>). Потім вже серед знайдених пар чисел шукають ту пару, яка і є розкладанням числа <math>n</math>

Розвитком методу факторизації Ферма є [[Метод квадратичних форм Шенкса|метод квадратичних форм Шенкса]]{{Джерело?}}{{сумнівно}} (також відомий як SQUFOF), ґрунтований на застосуванні [[Квадратична форма|квадратичних форм]]. Для 32-розрядних комп'ютерів алгоритми, які ґрунтуються на цьому методі, є безумовними лідерами серед алгоритмів факторизації для чисел від <math>10^{10}</math> до <math>10^{18}</math>{{sfn|Василенко|2003|loc=75—76}}.

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

Алгоритм факторизації Ферма можна застосувати для [[криптоаналіз]]у [[RSA]]. Якщо випадкові числа <math>p, q</math>, добуток яких дорівнює <math>n</math>, близькі одне до одного, то їх можна знайти методом факторизації Ферма. Після чого можна знайти секретну експоненту <math>d</math>, «зламавши» таким чином RSA
<ref name="Benne de Weger">{{стаття
 |автор    = Benne de Weger
 |заголовок = Cryptanalysis of RSA with Small Prime Difference
 |посилання   = http://www.enseignement.polytechnique.fr/profs/informatique/Francois.Morain/Master1/Crypto/projects/Weger02.pdf
 |мова     = en
 |видавництво  = Appl. Algebra Eng. Commun. Comput.
 |тип      = journal
 |рік      = 2002
 |том      = 13
 |номер    = 1
 |сторінки = 17–28
 |doi      = 10.1007/s002000100088
 |issn     = 
}}</ref>
<ref name="Gupta">{{стаття
 |автор    = Sounak Gupta, Goutam Paul
 |заголовок = Revisiting Fermat’s Factorization for the RSA Modulus
 |посилання   = http://arxiv.org/pdf/0910.4179v1.pdf
 |мова     = en
 |видавництво  = CoRR
 |тип      = journal
 |рік      = 2009
 |том      = abs/0910.4179
 |номер    = 
 |сторінки = 
 |doi      = 
 |issn     = 
}}</ref>. На час публікації алгоритму RSA (1977 рік) було відомо небагато алгоритмів факторизації, найвідомішим серед яких був метод Ферма.

== Цікаві факти ==

Відомий англійський економіст і логіст У.&nbsp;С.&nbsp;Джевонс зробив у своїй книзі «Принципи науки» («The Principles of Science», 1874 року таке припущення:
{{початок цитати}}
За даними двома числами можна знайти їх добуток простим і надійним способом, але зовсім інша справа, коли для великого числа необхідно знайти його множники. Чи можна сказати, які два числа перемножити, щоб вийшло число 8 616 460 799? Я думаю, що навряд чи хто-небудь окрім мене знає це.<ref>[https://archive.org/stream/principlesofscie00jevorich#page/n165/mode/2up ''Principles of Science''], Macmillan & Co., 1874, p. 141.</ref>
{{кінець цитати}}

Вказане Джевонсом число може бути розкладено вручну методом Ферма {{Джерело?|приблизно за 10 хвилин}}. Справді, <math>\left\lceil {\sqrt {n}}\right\rceil = 92 825</math>. За 55 кроків можна дійти до співвідношення:

<math>92880^2 - n = 10 233 601 = 3199^2.</math>

Таким чином розклад на прості множники має вигляд <math>8 616 460 799 = 89681 \cdot 96079</math>.

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

== Примітки ==
{{Примітки}}

== Література ==
* [[Задирака Валерій Костянтинович|Задірака В. К.]], Олексюк О.&nbsp;С.&nbsp;Комп'ютерна арифметика багаторозрядних чисел: наукове видання.&nbsp;— К.: 2003.&nbsp;— 264 с.
* Метод факторизації: навч. посіб. для студентів ВНЗ / Г.&nbsp;Я.&nbsp;Попов, В.&nbsp;І.&nbsp;Острик ; М-во освіти і науки України, Одес. нац. ун-т ім. І.&nbsp;І.&nbsp;Мечникова.&nbsp;— [[Одеса]]: ОНУ, 2014.&nbsp;— 118 с. : іл.&nbsp;— Бібліогр.: с. 114—116 (32 назви).&nbsp;— ISBN 978-617-689-066-9
* {{Публікація |стаття |назва=Удосконалений метод Ферма факторизації чисел |автор= Л. Тимошенко, С. Івасьєв, К. Вербик |видання= Проблеми становлення інформаційної економіки в Україні: матеріали Всеукр. наук.-практ. конф. |місце= Львів |день=23-25 |місяць=10 |видавець=МОН України, Львівський нац. ун-т ім. І. Франка |видавництво=Ліга-Прес |рік=2014 |сторінки=280—283 |посилання= https://econom.lnu.edu.ua/wp-content/uploads/2019/07/materialy_konfer_2014.pdf}}
; російською мовою
* {{книга
 |автор         = Василенко О. Н.
 |частина         =
 |заголовок      = Теоретико-числовые алгоритмы в криптографии
 |оригінал     = 
 |посилання        = http://www.ict.edu.ru/ft/002416/book.pdf
 |видавництво       = 
 |відповідальний = 
 |місто         = М.
 |видавництво   = [[МЦНМО]]
 |рік          = 2003
 |том           = 
 |сторінка      = 
 |сторінок       = 328
 |isbn          = 5-94057-103-4
 |ref           = Василенко
}}
* {{книга
 |автор         = Ишмухаметов Ш. Т.
 |частина         =
 |заголовок      = Методы факторизации натуральных чисел: учебное пособие
 |оригінал      = 
 |посилання        = http://window.edu.ru/resource/980/73980/files/Monograph_ishm.pdf
 |видавництво       = 
 |відповідальний = 
 |місто         = Казань
 |видавництво       = Казан. ун.
 |рік          = 2011
 |том           = 
 |сторінки      = 
 |сторінок       = 190
 |isbn          = 
 |ref           = Ишмухаметов
}}
* {{книга
 |автор         = Нестеренко А.Ю.  
 |заголовок     = Теоретико-числовые методы в криптографии 
 |оригінал      = 
 |посилання     = https://publications.hse.ru/pubs/share/folder/wsuo4iwl1j/68297429.pdf
 |видання       = учебное пособие 
 |місце         = Москва
 |видавництво   = Московский государственный институт электроники и математики
 |рік           = 2012
 |сторінок      = 223
 |isbn          = 978-5-94506-320-4
 |ref           = Нестеренко}}
* {{книга
 |автор         = Коблиц Н.
 |частина         =
 |заголовок      = Курс теории чисел и криптографии
 |оригінал      = 
 |посилання        = http://www.padabum.com/data/Физика/Коблиц%20Н.%20-%20Курс%20теории%20чисел%20и%20криптографии.%20М..%202001.pdf
 |видавництво       = 2-е
 |відповідальний = 
 |місто        = М.
 |видавництво   = Научное издательство ТВП
 |рік           = 2001
 |том           = 
 |сторінка      = 
 |сторінок       = 254
 |isbn          = 5-94057-103-4
 |ref           = Коблиц
}}

; англійською мовою
* {{книга |автор                        = Bressoud D. M.
 |частина                    = 
 |посилання частина = 
 |заголовок                = Factorization and Primality Testing
 |оригінал                  = 
 |посилання                = http://cs5594.userapi.com/u11728334/docs/6d00c4236a7f/David_M_Bressoud_Factorization_and_primality.pdf
 |відповідальний      = 
 |видавництво            = Springer-Verlag
 |місто                        = New York
 |рік                            = 1989
 |том                            = 
 |сторінки                  = 
 |сторінок                  = 260
 |серія                        = 
 |isbn                              = 0-387-97040-1
 |тираж                        = 
 |ref                               = Bressoud
 |url-access                        = registration
 |url                               = https://archive.org/details/factorizationpri0000bres
}}
* {{книга
 |автор         = Mahoney M. S. 
 |частина         = 
 |посилання частина  = 
 |заголовок      = The Mathematical Career of Pierre de Fermat
 |оригінал      = 
 |посилання     = http://books.google.ru/books?id=My19IcewAnoC&printsec=frontcover&dq=M.+S.+Mahoney+The+Mathematical+Career+of+Pierre+de+Fermat&hl=en&sa=X&ei=1IePUL6DKuWn4gTZr4HoAw&ved=0CCsQ6AEwAA#v=onepage&q=M.%20S.%20Mahoney%20The%20Mathematical%20Career%20of%20Pierre%20de%20Fermat&f=false
 |вікітека      = 
 |видавництво   = 2
 |місто         = Paris
 |видавництво   = Princeton Univ. Press
 |рік           = 1994
 |том           = 
 |сторінки      = 324-332
 |сторінок       = 438 
 |серія         = 
 |isbn          = 0-691-03666-7
 |тираж         = 
 |ref           = Mahoney
}}
* {{стаття
 |автор    = Carl Pomerance
 |заголовок = A Tale of Two Sieves 
 |посилання  = http://www.ams.org/notices/199612/pomerance.pdf
 |мова     = en
 |видавництво  = Notices Amer. Math. Soc
 |тип      = 
 |рік      = 1996
 |том      = 43
 |номер    = 12
 |сторінки = 1473–1485
 |doi      = 
 |issn     =
 |ref      = C. Pomerance. A Tale of Two Sieves
}}

;французькою мовою
# {{книга |автор                        = Kraitchik M.
 |частина                    = ANALYSE INDÉTERMINÉE DU SECOND DEGRÉ ET FACTORISATION. CHAPITRE XIV.
 |посилання частина = https://archive.org/details/factorizationpri0000bres/page/195
 |заголовок                = THEORIE DES NOMBRES
 |оригінал                  = 
 |посилання                = http://ia601209.us.archive.org/1/items/thoriedesnombres02krai/thoriedesnombres02krai.pdf
 |вікітека                  = 
 |відповідальний      = 
 |видавництво            = Gauthier-Villars
 |місто                        = Paris
 |рік                            = 1926
 |том                            = 2
 |сторінки                  = 195-208
 |сторінок                  = 251
 |серія                        = 
 |isbn                              = 0-387-97040-1
 |тираж                        = 
 |ref                               = Kraitchik
 |url                               = https://archive.org/details/factorizationpri0000bres/page/195
}}

{{Алгоритми теорії чисел}}
[[Категорія:Алгоритми факторизації]]