Fermat Factorization

Fermat's Factorization Method is a mathematical algorithm devised by Pierre de Fermat, a French mathematician from the 17th century. It's a technique used to factorize composite numbers into their prime factors.

Fermat's factorization method,  is based on the representation of an odd integer as the difference of two squares:

${\displaystyle �={�}^2-{�}^2.}$

That difference is algebraically factorable as ${\displaystyle (�+�)(�-�)}$; if neither factor equals one, it is a proper factorization of N.

Each odd number has such a representation. Indeed, if ${\displaystyle �=��}$ is a factorization of N, then

${\displaystyle �={\left(\frac{�+�}{2}\right)}^2-{\left(\frac{�-�}{2}\right)}^2}$

Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)

In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either by itself.

Basic method

One tries various values of a, hoping that ${\displaystyle {�}^2-�={�}^2}$, a square.

FermatFactor(N): // N should be odd
    a ← ceiling(sqrt(N))
    b2 ← a*a - N
    repeat until b2 is a square:
        a ← a + 1
        b2 ← a*a - N 
    return a - sqrt(b2) // or a + sqrt(b2)

For example, to factor ${\displaystyle �=5959}$, the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then, ${\displaystyle {�}^2={78}^2-5959=125}$. Since 125 is not a square, a second try is made by increasing the value of a by 1. The second attempt also fails, because 282 is again not a square.

Try:	1	2	3
a	78	79	80
b2	125	282	441
b	11.18	16.79	21

The third try produces the perfect square of 441. So, ${\displaystyle �=80}$, ${\displaystyle �=21}$, and the factors of 5959 are ${\displaystyle �-�=59}$ and ${\displaystyle �+�=101}$.

Example:

Suppose $N=91$

$91=10^2-3^2$

So the factors are $(10+3)$ and $(10-3)$ ie 13 and 7.

Python Code:
import math

def fermat_factorization(n):
    a = math.ceil(math.sqrt(n))
    b2 = a * a - n
    while not math.sqrt(b2).is_integer():
        a += 1
        b2 = a * a - n
        b = int(math.sqrt(b2))
    p = a + b
    q = a - b
    return p, q

# Example usage:
n = 5959
p, q = fermat_factorization(n)
print("Factors of", n, "are:", p, "and", q)