Module dsalgo::fermat_factorization_method

Functions

fermat_factorization_method

for odd integer n n = ab (\exist a, b are odd) a = x + y b = x - y n = x^2 - y^2 x^2 = n + y^2 brute force y=0..n/2 to find x. (because x > y) return x + y