Русская Википедия:Метод факторизации Ферма
Метод факторизации Ферма — алгоритм факторизации (разложения на множители) нечётного целого числа <math>n</math>, предложенный Пьером Ферма (1601—1665) в 1643 году.
Метод основан на поиске таких целых чисел <math>x</math> и <math>y</math>, которые удовлетворяют соотношению <math>x^2-y^2=n</math>, что ведёт к разложению <math>n=(x-y)\cdot (x+y)</math>.
История
В начале XVII века во Франции математические идеи начали активно распространяться между учёными посредством переписки. В 1638 году к кругу переписывающихся учёных присоединился Пьер Ферма. Переписка была удобным способом общения, так как Ферма жил в Тулузе, а многие его знакомые учёные жили в Париже. Одним из таких учёных был Марен Мерсенн, занимавшийся распространением писем, пересылкой и связью многих учёных между собой. 26 декабря 1638 года в письме Мерсенну Ферма упомянул, что нашёл метод, с помощью которого можно находить делители положительных чисел, но какие-либо подробности и описание метода он опустил. На тот момент Мерсенн также вёл переписку с французским математиком Бернаром Френиклем де Бесси, занимавшимся, как и Ферма, теорией чисел, в частности, делителями натуральных чисел и совершенными числами. В начале 1640 года, узнав о том, что Ферма получил метод нахождения делителей, Френикль пишет Мерсенну, и тот пересылает письмо Ферма. Мерсенн долгое время был связующим звеном между двумя математиками в их переписке. Именно в письмах Френиклю Ферма смог доказать корректность метода факторизации, а также впервые сформулировать и обосновать основные положения теоремы, которая позже была названа малой теоремой Ферма[1][2].
Обоснование
Метод Ферма основан на теореме о представлении числа в виде разности двух квадратов:
Шаблон:Рамка Если <math>n > 1</math> нечётно, то существует взаимно однозначное соответствие между разложением на множители <math>n = a \cdot b</math> и представлением в виде разности квадратов <math>n = x^2 - y^2</math> с <math>x > y > 0</math>, задаваемое формулами <math>x = (a + b) / 2,</math> <math>y = (a - b) / 2,</math> <math>a = x + y,</math> <math>b = x - y.</math> Шаблон:Конец рамки
Описание алгоритма
Для разложения на множители нечётного числа <math>n</math> ищется пара чисел <math>(x, y)</math> таких, что <math>x^2 - y^2 = n</math>, или <math>(x - y) \cdot (x + y) = n</math>. При этом числа <math>(x + y)</math> и <math>(x - y)</math> являются делителями <math>n</math>, возможно, тривиальными (то есть одно из них равно 1, а другое — <math>n</math>).
В нетривиальном случае равенство <math>x^2 - y^2 = n</math> равносильно <math>x^2 - n = y^2</math>, то есть тому, что <math>x^2 - n</math> является квадратом.
Поиск квадрата такого вида начинается с <math>x = \left\lceil\sqrt{n}\right\rceil</math> — наименьшего числа, при котором разность <math>x^2 - n</math> неотрицательна.
Для каждого значения <math>k \in \mathbb{N},</math> начиная с <math>k = 1</math>, вычисляют <math>\left(\left\lceil\sqrt{n}\right\rceil + k\right)^2 - n</math> и проверяют, не является ли это число точным квадратом. Если не является, то <math>k</math> увеличивают на единицу и переходят на следующую итерацию.
Если <math>\left(\left\lceil\sqrt{n}\right\rceil + k\right)^2 - n</math> является точным квадратом, то есть <math>x^2 - n = \left(\left\lceil\sqrt{n}\right\rceil + k\right)^2 - n = y^2,</math> то получено разложение:
- <math>n = x^2 - y^2 = (x + y)(x - y) = a \cdot b,</math>
в котором <math>x = \left\lceil\sqrt{n}\right\rceil + k.</math>
Если оно является тривиальным и единственным, то <math>n</math> — простое.
На практике значение выражения на <math>(k + 1)</math>-м шаге вычисляется с учётом значения на <math>k</math>-м шаге:
- <math>(s + 1)^2 - n = s^2 + 2s + 1 - n,</math>
где <math>s= \left\lceil\sqrt{n}\right\rceil + k.</math>
Примеры
Пример с малым числом итераций
Возьмём число <math>n=10873</math>. Вычислим <math>s = \left\lceil\sqrt{n}\right\rceil = 105.</math> Для <math>k=0, 1, 2, ...</math> будем вычислять значения функции <math>s+k</math>. Для дальнейшей простоты построим таблицу, которая будет содержать значения <math>y=(s+k)^2-n</math> и <math>\sqrt{y}</math> на каждом шаге итерации. Получим:
<math>k</math> | <math>y</math> | <math>\sqrt{y}</math> |
---|---|---|
1 | 363 | 19,052 |
2 | 576 | 24 |
Как видно из таблицы, уже на втором шаге итерации было получено целое значение <math>\sqrt{y}</math>.
Таким образом имеет место следующее выражение: <math>(105+2)^2-n=24^2</math>. Отсюда следует, что <math>n=107^2-24^2=131\cdot 83=10873.</math>
Пример с большим числом итераций
Пусть <math>n=89755.</math> Тогда <math>\sqrt{n}\approx 299,591 </math> или <math>s = \left\lceil\sqrt{n}\right\rceil = 300.</math>
<math>k</math> | <math>y</math> | <math>\sqrt{y}</math> |
---|---|---|
77 | 52374 | 228,854 |
78 | 53129 | 230,497 |
79 | 53886 | 232,134 |
80 | 54645 | 233,763 |
81 | 55406 | 235,385 |
82 | 56169 | 237 |
- <math>\sqrt{y} = 237</math>
- <math>a = s + k + \sqrt{y} = 300 + 82 + 237 = 619</math>
- <math>b = s + k - \sqrt{y} = 300 + 82 - 237 = 145</math>
Данное разложение является не конечным, так как, очевидно, что число <math>145</math> не является простым: <math>145=29 \cdot 5.</math>
В итоге, конечное разложение исходного числа <math>n</math> на произведение простых множителей <math>89755=5 \cdot 29 \cdot 619.</math>
Оценка производительности
Наибольшая эффективность расчёта методом факторизации Ферма достигается в случае, когда множители числа <math>n</math> примерно равны между собой. Это обеспечивает относительно короткий поиск последовательности[3]
- <math>s^2 - n,\ (s + 1)^2 - n,\ (s + 2)^2 - n,\ \dots\ (s + k)^2 - n.</math>
В наихудшем варианте, когда, к примеру, <math>a</math> близко к <math>n,</math> а <math>b</math> близко к 1, алгоритм Ферма работает хуже по сравнению с методом перебора делителей. Число итераций для данного случая
- <math>\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,</math>
то есть, очевидно, что оно имеет порядок <math>O(n).</math>
Метод факторизации Ферма будет работать не хуже метода перебора делителей, если <math>\operatorname{Iter}(n) < n^{1/2},</math> отсюда можно получить оценку для большего делителя <math>a < 4n^{1/2}.</math> Следовательно, метод Ферма имеет экспоненциальную оценку и, как метод пробного деления, не подходит для разложения больших чисел. Можно повысить эффективность, если выполнить сначала пробное деление числа <math>n</math> на числа от 2 до некоторой константы B, а затем выполнить поиск делителей методом Ферма. Такой поход помогает избавиться от малых делителей числа <math>n</math>Шаблон:Sfn.
Оптимизация методом перебора делителей
Предположим, что мы пытаемся разложить на множители число Шаблон:Nowrap методом Ферма, но кроме b вычисляем также и Шаблон:Nowrap. Начиная с <math>\sqrt{n}</math>, можно записать:
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 |
Если бы теперь для разложения числа <math>n</math> стали использовать метод перебора делителей, то имело бы смысл проверять делители <math>n</math> только до 47 830, а не до 48 432, так как если бы существовал делитель больше, то он был бы найден методом Ферма. Итак, всего за четыре этапа методом Ферма были проверены все делители <math>n</math> от 47 830 до 48 432.
Таким образом, можно комбинировать метод Ферма с методом перебора делителей. Достаточно выбрать число <math>c > \sqrt{n}</math> и использовать метод Ферма для проверки делителей между <math>c</math> и <math>\sqrt{n}</math>, а оставшиеся делители можно проверить методом перебора делителей, причём проверять делители нужно только до числа <math>c - \sqrt{c^2 - n}</math>[4].
В примере выше, когда <math>c = 48436</math>, делители необходимо перебирать до числа 47830. Также, к примеру, можно выбрать число <math>c = 55000</math>, дающее границу 28937.
Комбинация методов хороша, так как при достаточной разнице между делителями числа <math>n</math> метод перебора делителей эффективнее метода ФермаШаблон:Sfn. Это иллюстрирует следующий пример:
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 |
Метод решета
При поиске квадрата натурального числа в последовательности чисел <math>a^2 - n</math> можно не вычислять квадратный корень из каждого значения этой последовательности, и даже не проверять все возможные значения для Шаблон:Mvar. Для примера рассмотрим число <math>n = 2345678917</math>:
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 |
Можно сразу, не вычисляя квадратного корня, сказать, что ни одно из значений <math>b^2</math> в таблице не является квадратом. Достаточно, например, воспользоваться тем, что все квадраты натуральных чисел, взятые по модулю 20, равны одному из следующих значений: 0, 1, 4, 5, 9, 16. Эти значения повторяются при каждом увеличении Шаблон:Mvar на 10. В примере <math>n = 17</math> по модулю 20, поэтому отнимая 17 (или добавляя 3), получаем, что число <math>b^2</math> по модулю 20 равно одному из следующих: 3, 4, 7, 8, 12, 19. Но так как <math>b</math> — натуральное число, то отсюда получаем, что <math>b^2</math> по модулю 20 может быть равно только 4. Следовательно, <math>a^2 = 1</math> по модулю 20 и <math>a = 1</math> или <math>a = 9</math> по модулю 10. Таким образом, можно проверять корень выражения <math>a^2 - n</math> не для всех <math>a</math>, а только для тех, которые оканчиваются на 1 или 9[4].
Аналогично в качестве модуля можно использовать любые степени различных простых чисел. Например, взяв то же число <math>n = 2345678917</math>, находим
По модулю 16: | Квадраты равны | 0, 1, 4 или 9 |
n mod 16 равно | 5 | |
следовательно, <math>a^2</math> равно | 9 | |
и Шаблон:Mvar равно | 3, 5, 11 или 13 по модулю 16 | |
По модулю 9: | Квадраты равны | 0, 1, 4, или 7 |
n mod 9 равно | 7 | |
следовательно, <math>a^2</math> равно | 7 | |
и Шаблон:Mvar равно | 4 или 5 по модулю 9 |
Оптимизация множителем
Метод Ферма хорошо работает в случае, когда у числа <math>n</math> есть множитель, приблизительно равный квадратному корню из <math>n</math>Шаблон:Sfn.
Если известно примерное соотношение <math>d/c</math> между множителями числа <math>n</math>, то можно выбрать рациональное число <math>u/v</math>, приблизительно равное этому соотношению. Тогда можно записать следующее равенство: <math>nuv = cu \cdot dv</math>, где множители <math>cu</math> и <math>dv</math> близки в силу сделанных предположений. Поэтому применив метод Ферма для разложения числа <math>nuv</math>, их можно быстро найти. Далее для нахождения <math>c</math> и <math>d</math> можно использовать равенства <math>\gcd(n,cu)=c</math> и <math>\gcd(n,dv)=d</math> (в случае, если <math>u</math> не делится на <math>c</math> и <math>v</math> не делится на <math>d</math>).
В общем случае, когда соотношение между множителями <math>n</math> не известно, можно попытаться использовать разные соотношения <math>u/v</math>, и пробовать разложить получившееся в результате число <math>nuv</math>. Алгоритм, основанный на данном методе, был впервые предложен американским математиком Шерманом Леманом в 1974 году[5] и называется метод Лемана. Алгоритм детерминированно раскладывает данное натуральное число <math>n</math> на множители за <math>O(n^{1/3})</math> арифметических операций[6], однако в настоящее время представляет только исторический интерес и на практике почти не используетсяШаблон:Sfn.
Метод Крайчика — Ферма
Обобщение метода Ферма было предложено Шаблон:Нп5 в 1926 году. Он предложил рассматривать вместо пар чисел <math>(x, y),</math> которые удовлетворяют соотношению <math>x^2 - y^2 = n,</math> искать пары чисел, удовлетворяющих более общему сравнению <math>x^2 \equiv y^2 \pmod{n}.</math> Такое сравнение можно найти, перемножив несколько сравнений вида <math>u_i^2 \equiv v_i</math>, где <math>v_i</math> — небольшие числа, произведения которых будет квадратом. Для этого можно рассмотреть пары чисел <math>(u_i, v_i)</math>, где <math>u_i</math> — целый числа чуть больше <math>\sqrt n</math>, а <math>v_i = u_i^2 - n</math>. Крайчик заметил, что многие из полученных таким образом чисел <math>v_i</math> раскладываются на небольшие простые множители, то есть числа <math>v_i</math> являются гладкимиШаблон:Sfn.
Пример[7]
С помощью метода Крайчика — Ферма разложим число <math>n = 2041.</math> Число <math>46</math> является первым, чей квадрат больше числа <math>n</math>: <math>46^2 = 2116.</math>
Вычислим значение функции <math>v(u) = u^2 - n</math> для всех <math>u = 46, 47, \dots</math> Мы получим <math>75, 168, 263, 360, 459, 560, \dots</math>
По методу Ферма, нужно было бы продолжать вычисления пока не был бы найден квадрат какого-либо числа. По методу Крайчика — Ферма далее нужно последовательно искать такие <math>u_k</math>, для которых <math>v(u_1) v(u_2) \dots v(u_k) = y^2, u_1 u_2 \dots u_k = x.</math> Тогда
- <math>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}.</math>
Из алгоритма Крайчика — Ферма следует, что все полученные числа <math>(u_k^2 - n)</math> можно легко факторизовать.
Действительно: <math>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.</math>
Очевидно, что произведение полученных четырёх чисел будет квадратом: <math>2^{10} \cdot 3^4 \cdot 5^4 \cdot 7^2.</math> Тогда теперь можно вычислить <math>(x, y):</math>
- <math>x = 46 \cdot 47 \cdot 49 \cdot 51 \equiv 311 \pmod{2041},</math>
- <math>y = 2^5 \cdot 3^2 \cdot 5^2 \cdot 7 \equiv 1416 \pmod{2041}.</math>
Далее с помощью алгоритма Евклида находим <math>\gcd(1416 - 311, 2041) = 13</math>.
Таким образом, <math>2041 = 13 \cdot 157.</math>
Алгоритм Диксона
В 1981 году математик Карлтонского университета Джон Диксон опубликовал разработанный им метод факторизации на основе идей Крайчика[8]Шаблон:SfnШаблон:SfnШаблон:Sfn.
Алгоритм Диксона основан на понятии о факторных базах и является обобщением алгоритма факторизации Ферма. В алгоритме вместо пар чисел, удовлетворяющих уравнению <math>x^2 - y^2 = n</math> ищутся пары чисел, удовлетворяющих более общему уравнению <math>x^2 \equiv y^2\pmod{n}</math>, для решения которого Крайчиком было замечено несколько полезных фактов. Вычислительная сложность алгоритмаШаблон:Sfn
- <math>T = O\left({L\left({n}\right)}^{2}\right),</math>
где <math>L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}.</math>
Другие улучшения
Идея метода факторизации Ферма лежит в основе одних из самых быстрых алгоритмов для факторизации больших полупростых чисел — методе квадратичного решета и общем методе решета числового поля. Основное отличие метода квадратичного решета от метода Ферма заключается в том, что вместо поиска квадрата в последовательности <math>a^2 - n</math> находятся пары таких чисел, чьи квадраты равны по модулю <math>n</math> (каждая из этих пар может являться разложением числа <math>n</math>). Затем уже среди найденных пар чисел ищется та пара, которая и является разложением числа <math>n</math>.[9]
Развитием метода факторизации Ферма является метод квадратичных форм Шенкса (также известен как SQUFOF), основанный на применении квадратичных форм. Интересно то, что для 32-разрядных компьютеров алгоритмы, основанные на данном методе, являются безусловными лидерами среди алгоритмов факторизации для чисел от <math>10^{10}</math> до <math>10^{18}</math>Шаблон:Sfn.
Применение
Алгоритм факторизации Ферма может быть применён для криптоанализа RSA. Если случайные числа <math>p, q</math>, произведение которых равно <math>n</math>, близки друг другу, то они могут быть найдены методом факторизации Ферма. После чего можно найти секретную экспоненту <math>d</math>, взломав таким образом RSA[10][11]. На момент опубликования алгоритма RSA было известно лишь небольшое количество алгоритмов факторизации, самым известным из которых являлся метод Ферма.
Интересные факты
Известный английский экономист и логист У. С. Джевонс сделал в своей книге «Принципы науки» (Шаблон:Lang-en, 1874 год) следующее предположение[12]: Шаблон:Начало цитаты По данным двум числам можно найти их произведение простым и надёжным способом, но совсем другое дело, когда для большого числа необходимо найти его множители. Можно ли сказать, какие два числа перемножены, чтобы получилось число Шаблон:Val? Я думаю, что вряд ли кто-либо кроме меня знает это. Шаблон:Конец цитаты
Интересно то, что указанное Джевонсом число может быть разложено вручную методом Ферма с применением метода решета примерно за 10 минут. Действительно, <math>\left\lceil\sqrt{n}\right\rceil = 92\,825</math>. Используя метод решета, можно быстро прийти к соотношению
- <math>92\,880^2 - n = 10\,233\,601 = 3199^2.</math>
Таким образом разложение на простые множители имеет вид <math>8\,616\,460\,799 = 89\,681 \cdot 96\,079</math>.
Основная же мысль Джевонса о сложности разложения чисел на простые множители по сравнению с их перемножением справедлива, но только в том случае, когда речь идёт о произведении чисел, не настолько близких друг к другуШаблон:Sfn.
См. также
- Метод пробных делений
- Метод Лемана
- P-1 алгоритм Полларда
- Ро-алгоритм Полларда
- P+1 алгоритм Уильямса
- Факторизация с помощью эллиптических кривых
- Общий метод решета числового поля
- Алгоритм Диксона
- Метод квадратичных форм Шенкса
- Метод квадратичного решета
Примечания
Литература
- на русском языке
- Шаблон:Книга Шаблон:Wayback
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга Шаблон:Wayback
- Шаблон:Книга
- на английском языке
- на французском языке
Ссылки
Шаблон:Теоретико-числовые алгоритмы
- ↑ Шаблон:СтатьяШаблон:Недоступная ссылка
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ 4,0 4,1 Шаблон:Cite news
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Cite news
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Principles of Science, Macmillan & Co., 1874, p. 141.