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

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

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

История

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

Обоснование

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

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

Описание алгоритма

Для разложения на множители нечётного числа ищется пара чисел таких, что , или . При этом числа и являются делителями , возможно, тривиальными (то есть одно из них равно 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

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

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

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

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

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

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

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

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

Предположим, что мы пытаемся разложить на множители число n = 2345678917 методом Ферма, но кроме b вычисляем также и ab. Начиная с , можно записать:

a 48 43348 43448 43548 436
b2 76 572173 439270 308367 179
b 276,7416,5519,9605,9
ab 48 156,348 017,547 915,147 830,1

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

Таким образом, можно комбинировать метод Ферма с методом перебора делителей. Достаточно выбрать число и использовать метод Ферма для проверки делителей между и , а оставшиеся делители можно проверить методом перебора делителей, причём проверять делители нужно только до числа [6].

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

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

a 60 00160 002
b2 1 254 441 0841 254 561 087
b 35 418,135 419,8
ab 24 582,924 582,2

Метод решета

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

a 48 43348 43448 43548 436
b2 76 572173 439270 308367 179
b 276,7416,5519,9605,9

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

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

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

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

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

Если известно примерное соотношение между множителями числа , то можно выбрать рациональное число , приблизительно равное этому соотношению. Тогда можно записать следующее равенство: , где множители и близки в силу сделанных предположений. Поэтому применив метод Ферма для разложения числа , их можно быстро найти. Далее для нахождения и можно использовать равенства и (в случае, если не делится на и не делится на ).

В общем случае, когда соотношение между множителями не известно, можно попытаться использовать разные соотношения , и пробовать разложить получившееся в результате число . Алгоритм, основанный на данном методе, был впервые предложен американским математиком Шерманом Леманом в 1974 году[7] и называется метод Лемана. Алгоритм детерминированно раскладывает данное натуральное число на множители за арифметических операций[8], однако в настоящее время представляет только исторический интерес и на практике почти не используется[9].

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

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

Пример[12]

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

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

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

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

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

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

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

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

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

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

Алгоритм Диксона основан на понятии о факторных базах и является обобщением алгоритма факторизации Ферма. В алгоритме вместо пар чисел, удовлетворяющих уравнению ищутся пары чисел, удовлетворяющих более общему уравнению , для решения которого Крайчиком было замечено несколько полезных фактов. Вычислительная сложность алгоритма[17]

где

Другие улучшения

Идея метода факторизации Ферма лежит в основе одних из самых быстрых алгоритмов для факторизации больших полупростых чисел — методе квадратичного решета и общем методе решета числового поля. Основное отличие метода квадратичного решета от метода Ферма заключается в том, что вместо поиска квадрата в последовательности находятся пары таких чисел, чьи квадраты равны по модулю (каждая из этих пар может являться разложением числа ). Затем уже среди найденных пар чисел ищется та пара, которая и является разложением числа .[18]

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

Применение

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

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

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

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

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

Таким образом разложение на простые множители имеет вид .

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

См. также

Примечания

  1. Fletcher, Colin R. A reconstruction of the Frenicle-Fermat correspondence of 1640 (англ.) // Historia Mathematica : journal. — 1991. Vol. 18, no. 4. P. 311—410. (недоступная ссылка)
  2. Pierre de Fermat; Paul Tannery; Charles Henry; Apollonius, of Perga.; Jacques de Billy. 2 // Œuvres de Fermat. — Paris: Gauthier-Villars et fils, 1894.
  3. Коблиц, 2001, с. 161.
  4. David Bishop. Introduction to Cryptography with Java Applets. — Jones and Bartlett Inc., 2003. — С. 224. — 384 с. — ISBN 0-7637-2207-3.
  5. Ишмухаметов, 2011, с. 54.
  6. McKee, James. Speeding Fermat's factoring method (1991).
  7. Lehman, R. Sherman. Factoring Large Integers // Mathematics of Computation. — 1974. Т. 28, № 126. С. 637—646. doi:10.2307/2005940.
  8. Lehman, R. Sherman. Factoring Large Integers (неопр.) // Mathematics of Computation. — 1974. Т. 28, № 126. С. 637—646. doi:10.2307/2005940.
  9. Нестеренко, 2011, p. 140.
  10. Ишмухаметов, 2011, с. 115.
  11. Нестеренко, 2011, с. 164.
  12. Carl Pomerance. A Tale of Two Sieves (англ.) // Notices Amer. Math. Soc. — 1996. Т. 43, № 12. С. 1473—1485.
  13. Dixon, J. D. Asymptotically fast factorization of integers (англ.) // Math. Comp. : journal. — 1981. Vol. 36, no. 153. P. 255—260. doi:10.1090/S0025-5718-1981-0595059-1. — .
  14. Ишмухаметов, 2011, с. 117.
  15. Черемушкин, 2002, с. 75-77.
  16. Василенко, 2003, с. 57-60.
  17. Черемушкин, 2002, с. 79-80.
  18. Pomerance, Carl. A Tale of Two Sieves (декабрь 1996), С. 1473–1485.
  19. Yike Guo, 2002, High Performance Data Mining: Scaling Algorithms, Applications and Systems..
  20. 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.
  21. Sounak Gupta, Goutam Paul. Revisiting Fermat’s Factorization for the RSA Modulus (англ.) // CoRR : journal. — 2009. Т. abs/0910.4179.
  22. Principles of Science, Macmillan & Co., 1874, p. 141.
  23. Кнут, 2007, с. 435.

Литература

на русском языке
  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.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.