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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:56, 14 мая 2016.
(перенаправлено с «Метод Ферма»)

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

Пусть – известное целое число, являющееся произведением двух неизвестных простых чисел и , которые требуется найти. Большинство современных методов факторизации основано на идее, предложенной еще Пьером Ферма, заключающейся в поиске пар натуральных чисел и таких, что выполняется соотношение:

Алгоритм 1

  1. Вычислим целую часть от квадратного корня из :
  2. Для будем вычислять значения до тех пор, пока не окажется равным полному квадрату.
  3. Пусть является полным квадратом, например, числа :. Определим , откуда из равенства найдем , и искомые делители и вычисляются как , .

Пример

Пусть . Вычислим .

1 190 13,78
2 473 21.75
3 758 27.53
4 1045 32.33
5 1334 36,52
6 1625 40,31
7 1918 43,79
8 2213 47,04
9 2510 50,10
10 2809 53

Из последнего столбца получим: , откуда

Улучшение алгоритма

Метод факторизации Ферма можно значительно улучшить. Для этого необходимо получить сравнение вида с . В этом случае можно сразу найти множитель числа , вычисляя НОД . Действительно, делит , но не делит ни , ни . Тогда НОД должен быть собственным делителем числа , и тогда делит НОД .

Под понятием "наименьший абсолютный вычет" числа по модулю будем понимать целое число в интервале , сравнимое с .

TemplateDifinitionIcon.svg Определение «Факторная база»
Факторной базой[1] называется множество , где -либо простое, либо , остальные числа - простые. Будем говорить, что квадрат числа есть -число, если наименьший абсолютный вычет можно записать как произведение чисел из .

Пример

Пусть и . Тогда квадраты чисел 67, 68, 69 являются -числами.



Рассмотрим векторное пространство , где . Сопоставим каждому -числу вектор . Запишем в виде . Тогда числу соответствует вектор , .

Пусть у нас есть такое множество -чисел, что сумма соотвествующих векторов есть нулевой вектор. Тогда произведение наименьших абсолютных вычетов равно произведению четных степеней всех , следовательно, . Показатель каждого - четное число. Тогда правая часть равенства есть квадрат числа , где . Таким образом получили, что и имеют равные квадраты.В случае необходимо выбрать другую факторную базу и продолжить.

Таким образом, и . Так как , то делитель равен НОД . Получаем, что .


Примечания

  1. 'Коблиц Н, Курс теории чисел и криптографии. — М. : ТВП, 2001. — С. 254.