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

Пьер Ферма

Метод факторизации Ферма — алгоритм факторизации нечётного целого числа $n$, предложенный Пьером Ферма (1601-1665) в 1643 году.

Метод основан на поиске таких целых чисел $x$ и $y$, которые удовлетворяют соотношению $x^2-y^2=n$, что ведёт к разложению $n=(x-y)\cdot (x+y)$.

История

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

Обоснование

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

Если $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.$

Доказательство^[4]  

Если задана факторизация $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$ и $\sqrt{y}$ на каждом шаге итерации. Получим:

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

$x$	$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 + x + \sqrt{y} = 300 + 82 + 237 = 619$

$b = s + x - \sqrt{y} = 300 + 82 - 237 = 145$

Данное разложение является не конечным, т.к., очевидно, что число $145$ не является простым. Применив метод Ферма получим $145=29 \cdot 5.$

В итоге, конечное разложение исходного числа $n$ на произведение простых множителей $89755=5 \cdot 29 \cdot 619.$

Оценка производительности

Наибольшая эффективность расчета методом факторизации Ферма достигается в случае, когда множители числа $n$ примерно равны между собой. Это обеспечивает относительно короткий поиск последовательности ^[5]

$s^2 - n, \ (s+1)^2 - n, \ (s+2)^2 - n \ ... \ (s+k)^2-n.$

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

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

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

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

Обобщение метода Ферма было предложено Морисом Крайчиком (1882-1957). Он предложил рассматривать вместо пар чисел $(x,y),$ которые удовлетворяют соотношению $x^2-y^2=n,$ искать пары чисел, удовлетворяющих более общему уравнению $x^2 \equiv y^2 \pmod{n}.$ Крайчик заметил, что многие из чисел, получаемых по формуле $y(x)=(s+x)^2-n$ раскладываются на простые множители, т.е. числа $y(x)$ являются гладкими^[7].

Последовательность действий по Крайчику ^[8]  

1. Найти множество пар $(x,y),$которые удовлетворяют соотношению $x^2 \equiv y^2 \pmod{n}.$

2. Определить полное или частное разложение чисел $x$ и $y$ на множители для каждой пары $(x,y).$

3. Выбрать пары $(x,y),$ произведение которых удовлетворит соотношению $x^2 \equiv y^2 \pmod{n}.$

4. Разложить число $n$ на множители.

Пример ^[9]

С помощью метода Крайчика-Ферма разложим число $n=2041.$ Число $46$ является первым чей квадрат больше числа $n$: $46^2=2116.$

Вычислим значение функции $v(u)=u^2-n$ для всех $u=46, 47, \dots \,$ Мы получим $75, 168, 263, 360, 560, \dots \,$

По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика-Ферма далее нужно последовательно искать такие $u_k$, для которых $\ 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}.$

Далее с помощью алгоритма Евклида находим $\gcd(1416 - 311, 2041) = 13$.

Таким образом, $2041=13 \cdot 157.$

Алгоритм Диксона

Основная статья: Алгоритм Диксона

В 1981 году математик Карлтонского университета Джон Диксон опубликовал разработанный им метод факторизации на основе идей Крайчика^{[10][11][12][13]}.

Алгоритм Диксона основан на понятии о факторных базах и является обобщением алгоритма факторизации Ферма.

Применение

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

Примечания

1. ↑ Fletcher, Colin R. (1991). «A reconstruction of the Frenicle-Fermat correspondence of 1640». Historia Mathematica 18 (4): 311-410.
2. ↑ Fletcher, Colin R. (1989). «Fermat's theorem». Historia Mathematica 16 (2): 149-153.
3. ↑ Pierre de Fermat; Paul Tannery; Charles Henry; Apollonius, of Perga.; Jacques de Billy 2 // Œuvres de Fermat. — Paris: Gauthier-Villars et fils, 1894.
4. ↑ Коблиц, 2001, с. 161
5. ↑ David Bishop Introduction to Cryptography with Java Applets. — Jones and Bartlett Inc., 2003. — С. 224. — 384 с. — ISBN 0-7637-2207-3
6. ↑ Ишмухаметов, 2011, с. 54
7. ↑ Ишмухаметов, 2011, с. 115
8. ↑ Нестеренко, 2011, с. 164
9. ↑ Carl Pomerance A Tale of Two Sieves (Английский) // Notices Amer. Math. Soc. — 1996. — Т. 43. — № 12. — С. 1473–1485.
10. ↑ Dixon, J. D. (1981). «Asymptotically fast factorization of integers». Math. Comp. 36 (153): 255–260. DOI:10.1090/S0025-5718-1981-0595059-1.
11. ↑ Ишмухаметов, 2011, с. 117
12. ↑ Черемушкин, 2002, с. 77-80
13. ↑ Василенко, 2001, с. 78-81
14. ↑ Benne de Weger Revisiting Fermat’s Factorization for the RSA Modulus (Английский) // Appl. Algebra Eng. Commun. Comput. : journal. — 2002. — Т. 13. — № 1. — С. 17–28. — DOI:10.1007/s002000100088
15. ↑ Sounak Gupta, Goutam Paul Revisiting Fermat’s Factorization for the RSA Modulus (Английский) // CoRR : journal. — 2009. — Т. abs/0910.4179.

Литература

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

1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
2. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун., 2011. — 190 с.
3. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — 254 с. — ISBN 5-94057-103-4
4. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
5. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — 104 с. — ISBN 5-94057-060-7

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

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. Kraitchik M. Factorization and Primality Testing. — Paris: Gauthier-Villars, 1926. — Т. 2. — С. 195-208. — 251 с. — ISBN 0-387-97040-1

Ссылки

• Алгоритмы факторизации на сайте Института дистанционного обучения Интуит

Для улучшения этой статьи желательно?: Исправить статью согласно стилистическим правилам Википедии. Проставив сноски, внести более точные указания на источники.

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.