Метод Ферма разложения на множители

Общий смысл

Метод факторизации (разложения на множители) Ферма состоит в вычислении квадратов по модулю n для целых x, чуть больших $\sqrt{n}$, в надежде встретить полный квадрат y². Метод быстро работает, если n = p * q и числа p и q близки друг к другу. (Вот почему в p, q.)

Метод

Пусть надо разложить на множители число n. Если удастся найти два числа x и y такие, что x² − y² = n, то (x + y) * (x − y) = n.

Числа (x + y) и (x − y) являются множителями n, возможно, тривиальными (т.е. одно из этих чисел 1, а другое n.)

Эти два числа x и y, дающие x² − y² = n, найдутся, если найдётся такое целое x, что x² − n является квадратом. Тогда x² − (x² − n) — разность квадратов, равная n.

Поиск начинают с $x=\mathcal{b}\sqrt{n}\mathcal{c}+1$ - наименьшего возможного числа, при котором разность x² − n положительна. Увеличивают x на 1 и вычисляют x² − n, пока x² − n не окажется точным квадратом. Если это произошло, пытаются разложить n как $(x-\sqrt{x^2-n})*(x+\sqrt{x^2-n})$. Если это разложение тривиально, продолжают увеличивать x.

См. также

• Факторизация
• RSA