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

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

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

Метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что ведёт к разложению .

История[править | править вики-текст]

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

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

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

Если нечетно, то существует взаимно однозначное соответствие между разложениями на множители и представлениями в виде разности квадратов с , задаваемое формулами


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

Для разложения на множители нечётного числа ищется пара чисел таких, что , или . При этом числа и являются множителями , возможно, тривиальными (то есть одно из них равно 1, а другое — .)

В нетривиальном случае , равенство равносильно , то есть тому, что является квадратом.

Поиск квадрата такого вида начинается с  — наименьшего числа, при котором разность неотрицательна.

Для каждого значения начиная с , вычисляют и проверяют, не является ли это число точным квадратом. Если не является — то увеличивают на единицу и переходят на следующую итерацию.

Если является точным квадратом, т.е. то получено разложение:

в котором

Если оно является тривиальным и единственным, то  — простое.

На практике значение выражения на -ом шаге вычисляется с учётом значения на -ом шаге:

где

Примеры[править | править вики-текст]

Пример с малым числом итераций[править | править вики-текст]

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

1 363 19,052
2 576 24

Как видно из таблицы, уже на втором шаге итерации было получено целое значение .

Таким образом имеет место следующее выражение: . Отсюда следует, что

Пример с большим числом итераций[править | править вики-текст]

Пусть Тогда или

77 52374 228,854
78 53129 230,497
79 53886 232,134
80 54645 233,763
81 55406 235,385
82 56169 237

Данное разложение является не конечным, т.к., очевидно, что число не является простым:

В итоге, конечное разложение исходного числа на произведение простых множителей

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

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

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

т.е., очевидно, что оно имеет порядок

Метод факторизации Ферма будет работать не хуже метода перебора делителей, если отсюда можно получить оценку для большего делителя Следовательно, метод Ферма имеет экспоненциальную оценку и, как метод пробного деления, не подходит для разложения больших чисел. Можно повысить эффективность, если выполнить сначала пробное деление числа на числа от 2 до некоторой константы B. После этого, выполнить поиск делителей методом Ферма. Такой поход помогает избавиться от малых делителей числа [6].

Метод Крайчика-Ферма[править | править вики-текст]

Обобщение метода Ферма было предложено Морисом Крайчиком[en] в 1926 году. Он предложил рассматривать вместо пар чисел которые удовлетворяют соотношению искать пары чисел, удовлетворяющих более общему сравнению Такое сравнение можно найти, перемножив несколько сравнений вида , где — небольшие числа, произведения которых будет квадратом. Для этого можно рассмотреть пары чисел , где - целый числа чуть больше , а . Крайчик заметил, что многие из полученных таким образом чисел раскладываются на небольшие простые множители, т.е. числа являются гладкими[7].


Пример [9][править | править вики-текст]

С помощью метода Крайчика-Ферма разложим число Число является первым чей квадрат больше числа :

Вычислим значение функции для всех Мы получим

По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика-Ферма далее нужно последовательно искать такие , для которых Тогда

Из алгоритма Крайчика-Ферма следует, что все полученные числа можно легко факторизовать.

Действительно:

Очевидно, что произведение полученных четырех чисел будет квадратом: Тогда теперь можно вычислить

Далее с помощью алгоритма Евклида находим .

Таким образом,

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

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

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

Другие простые методы для  факторизации[править | править вики-текст]

Метод пробного деления, метод Ферма , метод Лемана , метод Полларда , метод Брента - p−1, метод Полларда - p+1, метод Вильямса , Оптимизация методов Полларда и Вильямса , метод Женга, метод Макки.

Применение[править | править вики-текст]

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

которых являлся метод Ферма.

Примечания[править | править вики-текст]

  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.