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

Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.

Для разложения на множители нечётного числа \( n \) ищется пара чисел \( (x,y) \) таких, что \( x^2-y^2=n \), или \( (x-y)\cdot (x+y) = n \). При этом числа \( (x+y) \) и \( (x-y) \) являются множителями \( n \), возможно, тривиальными (то есть одно из них равно 1, а другое — \( n \)).

Равенство \( x^2 - y^2 = n \) равносильно \( x^2-n=y^2 \), то есть тому, что \( x^2-n \) является квадратом.

Поиск квадрата такого вида начинается с \( x=\left\lceil\sqrt{n}\right\rceil \) — наименьшего числа, при котором разность \( x^2-n \) неотрицательна. Для каждого значения \( k \in \mathbb{N} \), начиная с \( k=1 \), вычисляют \( (\left\lceil\sqrt{n}\right\rceil+k)^2-n \) и проверяют, не является ли это число точным квадратом. Если не является — то \( k \) увеличивают на единицу и переходят на следующую итерацию.

Если \( (\left\lceil\sqrt{n}\right\rceil+k)^2-n \) является точным квадратом, т.е. \( x^2-n=(\left\lceil\sqrt{n}\right\rceil+k)^2-n=y^2 \), то получено разложение:

\( n = x^2-y^2 = (x+y)(x-y) = a \cdot b \), в котором \( x=(\left\lceil\sqrt{n}\right\rceil+k) \)