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
Domanda
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"
Soluzione
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
Altri suggerimenti
You can use Newton's method to find the integer square root of a number:
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
This returns the largest integer x such that x × x does not exceed n.
But it is highly unlikely that Fermat's method will be able to factor your 95-digit RSA semi-prime. You should look at the quadratic sieve or the number field sieve to factor a number of that size.
You can try to make usage of sqrt() function out of module math. The code could look like:
import math
n = math.sqrt(int(raw_input("Enter a number\n")))
print n