Truncation error in taking square root in python

1k views Asked by At

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"
3

There are 3 answers

9
Sergii Dymchenko On BEST ANSWER

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

0
user448810 On

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.

1
Abhishek Bera On

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