# Fermat's Factorization Method

• Let n be a +ve odd integer. Using Fermat’s factorization method we can efficiently factorise n into p and q (n = p * q) provided the difference between p and q is small.
• n can be of any length.
• In badly implemented RSA, it may be possible that the difference between the 2 randomly selected prime numbers is small. Fermat’s factorization method can hence be used to break such RSA keys.
``````n = a^2 - b^2
n = (a + b) * (a - b)  - I

n = p * q              - II
``````

Comparing equation I and II,

``````p = a + b
q = a - b
``````
``````#!/usr/bin/python3

from math import floor, sqrt

def factorize(n):
# since even nos. are always divisible by 2, one of the factors will always
# be 2
if (n & 1) == 0:
return (n/2, 2)

a = floor(sqrt(n))

# if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
if a * a == n:
return (a, a)

# n = (a - b) * (a + b)
# n = a^2 - b^2
# b^2 = a^2 - n
while True:
a += 1
_b = a * a - n
b = int(sqrt(_b))
if (b * b == _b):
break

return (a + b, a - b)

print(factorize(105327569))
``````