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

Суть метода состоит в том, чтобы попробовать представить нечетное число n в виде n = х² - у², где х, у - неотрицательные целые числа. Если такие числа найдены, то n = х²- у² = (х - у) (х + у). Значит, (х – у) и (х + у) являются делителями (не обязательно простыми) числа n.

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

1. х = [ ], где [ ] – целая часть .

2. Если x = 1, то завершить работу.

3. Если n = х ², то завершить работу, т.к. х является делителем числа n. В противном случае x = x + 1.

4. Если х = (n + 1) / 2, то завершить работу, т.к. n – простое. В противном случае .

5. Если число у целое (т.е., если [ у ]² = х ² - n), то завершить работу, т.к. (х + у) и (х - у) является делителями числа n. В противном случае х = x + 1 и перейти к шагу 4.

Например, n = 1 342 127.

Таблица 8.4. Таблица итераций

Тогда делителями n = 1 342 127 являются (x + y) = (1164 + 113) = 1277 и (x - y) = (1164 - 113) = 1051.

Как отмечалось выше, если в результате работы алгоритма получены делители, то они могут, в свою очередь, оказаться составными числами. Например, при n = 120 уже на первой итерации мы получаем x = [ ] + 1 = [10.95..] + 1 = 10 + 1 = 11, = = 1, (x + y) = (11 + 1) = 12 и (x - y) = (11 - 1) = 10. Очевидно, что числа 12 и 10 составные.

Т.о., чтобы найти все простые делители числа n необходимо использовать описанный выше алгоритм рекурсивно для каждого вновь найденного делителя. Если для него соблюдается условие шага 4, то он действительно является простым делителем числа n.

Для вскрытия шифрограммы, полученной с помощью алгоритма RSA, требуется найти два простых делителя числа n = p * q (напомним, n – часть открытого ключа). Отсюда, достаточно единожды (без рекурсивных вызовов) применить метод Ферма и найти два делителя, чтобы вскрыть шифрограмму. Но, т.к. по рекомендациям Лаборатории RSA на сегодняшний день, длина числа n составляет 2048 битов (n ≈ 2 * 10⁶⁰⁰), использование метода Ферма неперспективно.

P-Метод Полларда

Оригинальная версия

Рассмотрим последовательность целых чисел , такую что и , где - число, которое нужно факторизовать. Оригинальный алгоритм выглядит следующим образом[6].

1. Будем вычислять тройки чисел

, где .

Причём каждая такая тройка получается из предыдущей.

2. Каждый раз, когда число кратно числу (скажем, ), будем вычислять наибольший общий делитель любым известным методом.

3. Если , то найдено частичное разложения числа , причём .

Найденный делитель может быть составным, поэтому его также необходимо факторизовать. Если число составное, то продолжаем алгоритм с модулем .

4. Вычисления повторяются раз. Например, можно прекратить алгоритм при . Если при этом число не было до конца факторизовано, можно выбрать, например, другое начальное число .

Современная версия

Пусть составное целое положительное число, которое требуется разложить на множители. Алгоритм выглядит следующим образом:[7]

Выбираем небольшое число и строим последовательность , определяя каждое следующее как .

Одновременно на каждом i-ом шаге вычисляем для каких-либо , таких, что , например, .

Если обнаружили, что , то вычисление заканчивается, и найденное на предыдущем шаге число является делителем . Если не является простым числом, то процедуру поиска делителей можно продолжить, взяв в качестве число .

Как на практике выбирать функцию ? Функция должна быть не слишком сложной для вычисления, но в то же время не должна быть линейным многочленом, а также не должна порождать взаимно однозначное отображение. Обычно в качестве берут функцию или [8]. Однако не следует использовать функции и [6].

Если известно, что для делителя числа справедливо при некотором , то имеет смысл использовать [6].

Существенным недостатком алгоритма в такой реализации является необходимость хранить большое число предыдущих значений .

P-1 Метод Полларда

Первая стадия

Задача состоит в том, чтобы найти делитель числа отличный от единицы. Прежде всего необходимо выбрать 2 числа , такие, что .

Вычислим теперь число , где — все простые числа меньшие . Здесь допускается некоторая свобода в выборе , однако точно известно, что для маленьких , должно быть больше единицы[1].

Выберем небольшое целое и вычислим

если мы нашли делитель , в противном случае переходим ко второй стадии.

Вторая стадия

На этом шаге необходимо вычислить последовательность

где — простое, , надеясь, что на каком-нибудь шаге получится

Легче всего[1] это сделать вычислением для каждого нечётного домножением на , беря через равные промежутки. Если делитель найден. Если же , то необходимо точнее исследовать этот участок.

Замечание

С помощью данного метода мы сможем найти только такие простые делители числа , для которых выполнено[1]:

или , где является -гладким, а — простое, такое что [1].