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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод факторизации Фермаалгоритм факторизации (разложения на множители) нечётного целого числа n, предложенный Пьером Ферма (16011665) в 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.


Описание алгоритма[править | править вики-текст]

Для разложения на множители нечётного числа 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} на каждом шаге итерации. Получим:

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.

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].


Пример [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.