I'm trying to use Fermat's factorization method
http://en.wikipedia.org/wiki/Fermat%27s_factorization_method
to factor a RSA exercise with n = pq = 17113393402958118715148546526344227921781458985077442510282855190555424972779474416264134494113
Here's my python code:
def isSquare(x):
return pow(int(sqrt(x)),2) - x == 0
n = 17113393402958118715148546526344227921781458985077442510282855190555424972779474416264134494113
for i in xrange(10):
print isSquare(n+i*i)
When I execute, it prints all True
s, which isn't correct. I think it's truncation error in python. How should I deal with it? Thanks.
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
print isqrt(99999999999**2)
for i in xrange(130000,140000):
if isqrt(n + i*i) ** 2 == n + i*i:
print isqrt(n + i*i)
print "done"
math.sqrt uses floating point numbers, which are inexact.
The easiest way is probably to change sqrt to integer isqrt function, and you can just copy decent isqrt implementation from https://stackoverflow.com/a/15391420/220700