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

В начале XVII века во Франции математические идеи начали активно распространяться между учёными посредством переписки. В 1638 году к кругу переписывающихся учёных присоединился Пьер Ферма. Переписка была удобным способом общения, так как Ферма жил в Тулузе, а многие его знакомые учёные жили в Париже. Одним из таких учёных был Марен Мерсенн, занимавшийся распространением писем, пересылкой и связью многих учёных между собой. 26 декабря 1638 года в письме Мерсенну Ферма упомянул, что нашёл метод, с помощью которого можно находить делители положительных чисел, но какие-либо подробности и описание метода он опустил. На тот момент Мерсенн также вёл переписку с французским математиком Бернаром Френиклем де Бесси, занимавшимся, как и Ферма, теорией чисел, в частности, делителями натуральных чисел и совершенными числами. В начале 1640 года, узнав о том, что Ферма получил метод нахождения делителей, Френикль пишет Мерсенну, и тот пересылает письмо Ферма. Мерсенн долгое время был связующим звеном между двумя математиками в их переписке. Именно в письмах Френиклю Ферма смог доказать корректность метода факторизации, а также впервые сформулировать и обосновать основные положения теоремы, которая позже была названа Малой теоремой Ферма [1] [2].

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

Для разложения на множители нечётного числа ${\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}$ примерно равны между собой. Это обеспечивает относительно короткий поиск последовательности[4]

${\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}$[5].

Предположим, что мы пытаемся разложить на множители число n = 2345678917 методом Ферма, но кроме b вычисляем также и a − b. Начиная с ${\displaystyle {\sqrt {n}}}$, можно записать:

Если бы теперь для разложения числа ${\displaystyle n}$ стали использовать метод перебора делителей, то имело бы смысл проверять делители ${\displaystyle n}$ только до 47 830, а не до 48 432, так как если бы существовал делитель больше, то он был бы найден методом Ферма. Итак, всего за четыре этапа методом Ферма были проверены все делители ${\displaystyle n}$ от 47 830 до 48 432.

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

В примере выше, когда ${\displaystyle c=48436}$, делители необходимо перебирать до числа 47830. Также, к примеру, можно выбрать число ${\displaystyle c=55000}$, дающее границу 28937.

Комбинация методов хороша, так как при достаточной разнице между делителями числа ${\displaystyle n}$ метод перебора делителей эффективнее метода Ферма[5]. Это иллюстрирует следующий пример:

При поиске квадрата натурального числа в последовательности чисел ${\displaystyle a^{2}-n}$ можно не вычислять квадратный корень из каждого значения этой последовательности, и даже не проверять все возможные значения для a. Для примера рассмотрим число ${\displaystyle n=2345678917}$:

Можно сразу, не вычисляя квадратного корня, сказать, что ни одно из значений ${\displaystyle b^{2}}$ в таблице не является квадратом. Достаточно, например, воспользоваться тем, что все квадраты натуральных чисел, взятые по модулю 20, равны одному из следующих значений: 0, 1, 4, 5, 9, 16. Эти значения повторяются при каждом увеличении a на 10. В примере ${\displaystyle n=17}$ по модулю 20, поэтому отнимая 17 (или добавляя 3), получаем, что число ${\displaystyle b^{2}}$ по модулю 20 равно одному из следующих: 3, 4, 7, 8, 12, 19. Но так как ${\displaystyle b}$ — натуральное число, то отсюда получаем, что ${\displaystyle b^{2}}$ по модулю 20 может быть равно только 4. Следовательно, ${\displaystyle a^{2}=1}$ по модулю 20 и ${\displaystyle a=1}$ или ${\displaystyle a=9}$ по модулю 10. Таким образом, можно проверять корень выражения ${\displaystyle a^{2}-n}$ не для всех ${\displaystyle a}$, а только для тех, которые оканчиваются на 1 или 9[6].

Аналогично в качестве модуля можно использовать любые степени различных простых чисел. Например, взяв то же число ${\displaystyle n=2345678917}$, находим

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

Метод Ферма хорошо работает в случае, когда у числа ${\displaystyle n}$ есть множитель, приблизительно равный квадратному корню из ${\displaystyle n}$[5].

Если известно примерное соотношение ${\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/v}$, и пробовать разложить получившееся в результате число ${\displaystyle nuv}$. Алгоритм, основанный на данном методе, был впервые предложен американским математиком Шерманом Леманом в 1974 году[7] и называется метод Лемана. Алгоритм детерминированно раскладывает данное натуральное число ${\displaystyle n}$ на множители за ${\displaystyle O(n^{1/3})}$ арифметических операций[8], однако в настоящее время представляет только исторический интерес и на практике почти не используется[9].

Обобщение метода Ферма было предложено Морисом Крайчиком в 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 v_{i}}$ раскладываются на небольшие простые множители, то есть числа ${\displaystyle v_{i}}$ являются гладкими[10].

В 1981 году математик Карлтонского университета Джон Диксон опубликовал разработанный им метод факторизации на основе идей Крайчика[13][14][15][16].

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

${\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}$.[18]

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

Алгоритм факторизации Ферма может быть применён для криптоанализа RSA. Если случайные числа ${\displaystyle p,q}$, произведение которых равно ${\displaystyle n}$, близки друг другу, то они могут быть найдены методом факторизации Ферма. После чего можно найти секретную экспоненту ${\displaystyle d}$, взломав таким образом RSA[20][21]. На момент опубликования алгоритма RSA было известно лишь небольшое количество алгоритмов факторизации, самым известным из которых являлся метод Ферма.

Известный английский экономист и логист У. С. Джевонс сделал в своей книге «Принципы науки» («The Principles of Science», 1874 год) следующее предположение:

По данным двум числам можно найти их произведение простым и надёжным способом, но совсем другое дело, когда для большого числа необходимо найти его множители. Можно ли сказать, какие два числа перемножены, чтобы получилось число 8 616 460 799? Я думаю, что вряд ли кто-либо кроме меня знает это[22].

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

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

Таким образом разложение на простые множители имеет вид ${\displaystyle 8616460799=89681\cdot 96079}$.

Основная же мысль Джевонса о сложности разложения чисел на простые множители по сравнению с их перемножением справедлива, но только в том случае, когда речь идёт о произведении чисел, не настолько близких друг к другу[23].

• Метод пробных делений
• Метод Лемана
• P-1 алгоритм Полларда
• Ро-алгоритм Полларда
• P+1 алгоритм Уильямса
• Факторизация с помощью эллиптических кривых
• Общий метод решета числового поля
• Алгоритм Диксона
• Метод квадратичных форм Шенкса
• Метод квадратичного решета

на русском языке

1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун., 2011. — 190 с.
3. Коблиц Н. Курс теории чисел и криптографии. — 2-е. — М.: Научное издательство ТВП, 2001. — 254 с. — ISBN 5-94057-103-4.
4. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
5. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2002. — 104 с. — ISBN 5-94057-060-7. Архивная копия от 31 мая 2013 на Wayback Machine
6. Дональд Кнут. Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — 832 с. — ISBN 5-8459-0081-6.

на английском языке

1. Bressoud D. M. Factorization and Primality Testing. — New York: Springer-Verlag, 1989. — 260 с. — ISBN 0-387-97040-1. (недоступная ссылка)

1. Mahoney M. S. The Mathematical Career of Pierre de Fermat. — 2. — Paris: Princeton Univ. Press, 1994. — С. 324-332. — 438 с. — ISBN 0-691-03666-7.

1. Yike Guo, R.L. Grossman. High Performance Data Mining: Scaling Algorithms, Applications and Systems. — 2. — 2002. — 112 с. — ISBN 978-0792377450.

на французском языке

1. Kraitchik M. Factorization and Primality Testing. — Paris: Gauthier-Villars, 1926. — Т. 2. — С. 195-208. — 251 с. — ISBN 0-387-97040-1.

• Онлайн калькулятор на основе метода факторизации Ферма