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

Пьер Ферма

Метод факторизации Ферма — алгоритм факторизации (разложения на множители) нечётного целого числа $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=(a+b)/2,$ $y=(a-b)/2,$ $a=x+y,$ $b=x-y.$

Доказательство

Если задана факторизация $n=a\cdot b$, то имеет место соотношение: $n=a\cdot b=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{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(\left\lceil {\sqrt {n}}\right\rceil +k\right)^{2}-n$ и проверяют, не является ли это число точным квадратом. Если не является, то $k$ увеличивают на единицу и переходят на следующую итерацию.

Если $\left(\left\lceil {\sqrt {n}}\right\rceil +k\right)^{2}-n$ является точным квадратом, то есть $x^{2}-n=\left(\left\lceil {\sqrt {n}}\right\rceil +k\right)^{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$-м шаге:

$(s+1)^{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=0,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,\ \dots \ (s+k)^{2}-n.$

В наихудшем варианте, когда, к примеру, $a$ близко к $n,$ а $b$ близко к 1, алгоритм Ферма работает хуже по сравнению с методом перебора делителей. Число итераций для данного случая

$\operatorname {Iter} (n)={\frac {a+b}{2}}-\left\lceil n^{1/2}\right\rceil \approx {\frac {n}{2}}-\left\lceil n^{1/2}\right\rceil ,$

то есть, очевидно, что оно имеет порядок $O(n).$

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

Оптимизация методом перебора делителей

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

a	48 433	48 434	48 435	48 436
b2	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9
a − b	48 156,3	48 017,5	47 915,1	47 830,1

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

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

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

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

a	60 001	60 002
b2	1 254 441 084	1 254 561 087
b	35 418,1	35 419,8
a − b	24 582,9	24 582,2

Метод решета

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

a	48 433	48 434	48 435	48 436
b2	76 572	173 439	270 308	367 179
b	276,7	416,5	519,9	605,9

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

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

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

Оптимизация множителем

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

Если известно примерное соотношение $d/c$ между множителями числа $n$, то можно выбрать рациональное число $u/v$, приблизительно равное этому соотношению. Тогда можно записать следующее равенство: $nuv=cu\cdot dv$, где множители $cu$ и $dv$ близки в силу сделанных предположений. Поэтому применив метод Ферма для разложения числа $nuv$, их можно быстро найти. Далее для нахождения $c$ и $d$ можно использовать равенства $\gcd(n,cu)=c$ и $\gcd(n,dv)=d$ (в случае, если $u$ не делится на $c$ и $v$ не делится на $d$).

В общем случае, когда соотношение между множителями $n$ не известно, можно попытаться использовать разные соотношения $u/v$, и пробовать разложить получившееся в результате число $nuv$. Алгоритм, основанный на данном методе, был впервые предложен американским математиком Шерманом Леманом в 1974 году и называется метод Лемана. Алгоритм детерминированно раскладывает данное натуральное число $n$ на множители за $O(n^{1/3})$ арифметических операций, однако в настоящее время представляет только исторический интерес и на практике почти не используется.

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

Обобщение метода Ферма было предложено Морисом Крайчиком в 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$. Крайчик заметил, что многие из полученных таким образом чисел $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$

По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика — Ферма далее нужно последовательно искать такие $u_{k}$, для которых $v(u_{1})v(u_{2})\dots v(u_{k})=y^{2},u_{1}u_{2}\dots u_{k}=x.$ Тогда

$x^{2}=u_{1}^{2}u_{2}^{2}\dots 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})\dots 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}}.$

Далее с помощью алгоритма Евклида находим $\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 было известно лишь небольшое количество алгоритмов факторизации, самым известным из которых являлся метод Ферма.

Интересные факты

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

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

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

$92\,880^{2}-n=10\,233\,601=3199^{2}.$

Таким образом разложение на простые множители имеет вид $8\,616\,460\,799=89\,681\cdot 96\,079$.

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

См. также

• Метод пробных делений
• Метод Лемана
• 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.

Ссылки

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