- 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))
```