Truncation error in taking square root in python

Question

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 Trues, 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"

Answer 1

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

Answer 2

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.

Answer 3

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