Fermat's Factorisation

Prerequisites:

1. RSA Encryption/Decryption

Fermat's Factorisation is based on the representation of odd integer as difference of two squares: This difference is factorable as (a+b)*(a-b) We can use the above property to factorise modulus N in RSA when the difference between the primes is small: Difference ~ (N)^1/4

Basic Fermat's Factorisation

To implement basic approach of Fermat's Factorisation, we can do the following:

1. Calculate a as ceil of square root of N

2. Calculate b2 = a**2 - N

3. Check if b2 is a perfect square. If b2 is a perfect square then return a - Square_root(b2) and a + Square_root(b2) as the factors. If not, do the following:

   • Increment a by 1, i.e. a += 1

   • Calculate b2 again as a**2 - N

   • Repeat Step-3

Check out the implementation of basic Fermat's Factorisation here

References

1. Fermat's Factorisation