Fermat Factorization

Fermat Factorization¶

https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

If you represent an odd integer as a difference of squares, then you can pull out two factors.

[A difference of cubes and a sum of cubes can also be factored, but the following code only looks for a difference of squares.]

In [1]:

from math import sqrt, ceil

In [2]:

def FermatFactorization(n):
    
    localFactorList = []
    
    # take out factors of 2, guarantee n is odd
    while n%2==0: 
        localFactorList.append(2)
        n = n/2
        
    s = int(ceil(sqrt(n)))
    
    while True:
        b2 = s*s - n
        t = int(sqrt(b2))

        if t*t == b2:
            return localFactorList+[s+t, s-t]
        else:
            s = s+1
        assert s <= (n+1)/2

In [3]:

FermatFactorization(999919*2)

Out[3]:

[2, 1009, 991]