20-10-2023
Метод факторизации Ферма — алгоритм факторизации нечётного целого числа m, основанный на поиске таких целых чисел и , что , что ведёт к разложению .
Метод быстро работает, если m является произведением двух близких к друг другу сомножителей. В частности, именно поэтому в RSA требуют, чтобы разность между секретными простыми сомножителями модуля была велика.
Содержание |
Метод Ферма основан на теореме Эйлера о представлении числа в виде разности двух квадратов:
|
Если нечетно, то существует взаимно однозначное соответствие между разложениями на множители и представлениями в виде разности квадратов с , задаваемое формулами , , , . |
Если задана факторизация , то имеет место соотношение: Невозможно разобрать выражение (лексическая ошибка): m = a\cdot b = \left(\tfrac{a+b}2\right\)^2-\left(\tfrac{a-b}2\right)^2 . Таким образом получается представление в виде разности двух квадратов.
Обратно, если дано, что , то правую часть можно разложить на множители: .
Для разложения на множители нечётного числа n ищутся два числа и такие, что , или . При этом числа и являются множителями , возможно, тривиальными (то есть одно из них равно 1, а другое — .)
Равенство равносильно , то есть тому, что является квадратом. Поиск квадрата такого вида начинается с — наименьшего числа, при котором разность неотрицательна. Для каждого значения вычисляют и проверяют, не является ли это число точным квадратом. Если не является — то x увеличивают на единицу и переходят на следующую итерацию, если является — то получено разложение:
Если оно является тривиальным, то — простое.
Метод факторизации Ферма.