Fermat Factorization

Fermat factorization is a method for factoring an odd, composite (non-prime) natural number $ N $. It relies on the algebraic identity of the difference of two squares: $$ N = a^2 - b^2 = (a + b)(a - b) $$

The goal is to find two integers $ a $ and $ b $ such that $ a^2 - N $ is a perfect square $ b $.

When this is the case, this expression immediately yields two non-trivial factors of $ N $, namely $ c = (a+b) $ and $ d = (a-b) $

Fermat factorization is particularly efficient when $ N $ has two factors $ c $ and $ d $ that are close to each other, that is, when $ c \pm \epsilon_1 \approx d \pm \epsilon_2 \approx \sqrt{N} $.

In this case, the difference $ a^2 - N $ quickly becomes a perfect square.

Conversely, when $ N $ is prime or when its factors are very far from $ \sqrt{N} $, the method becomes inefficient and significantly less effective than other factorization algorithms.

Fermat's factorization algorithm applies the following steps:

1 - Initialize $ A $ to the smallest integer value such that $ A \ge \sqrt{N} $

2 - Calculate $ B^2 = A^2 - N $

3 - Test if $ B^2 $ is a perfect square

4 - If so, then $ N = (A+B)(A-B) $ and stop. Otherwise, increment $ A $ by 1 and repeat the calculation in step 2

The complexity of Fermat's factorization depends on the difference between the factors of $ N $.

— Favorable case: if $ N = c \times d $ with $ c \approx d \approx \sqrt{N} $, the number of iterations is small, often proportional to $ |d - c| $.

— Worst-case: if $ N $ is prime, the algorithm must test all integers up to $ \sqrt{N} $, making the method impractical for large numbers.

Here is the source code and a Python implementation:// Pseudo code

function fermat_factorization(N) {

if N is even {

return (2, N / 2)

}

A ← ceil(sqrt(N))

while true {

B2 ← A^2 - N

if B2 is a perfect square {

B ← sqrt(B2)

return (A - B, A + B)

}

A ← A + 1

}

}



// Python

import math

def fermat_factorization(N):

A = math.isqrt(N)

while True:

B2 = A * A - N

B = math.isqrt(B2)

if B * B == B2:

return (A - B, A + B)

A += 1