0

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"
  • 1
    `math.sqrt()` operates on `float` (which cannot hold the range you seem to need). I'd say use `Decimal`, or better yet one of the math libraries.. – thebjorn Dec 13 '13 at 22:14
  • 1
    You can use the well-known `SymPy` library to do that: http://sympy.org/fr/index.html – Laurent LAPORTE Dec 13 '13 at 22:17

3 Answers3

2

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

Community
  • 1
  • 1
Sergii Dymchenko
  • 6,890
  • 1
  • 21
  • 46
  • So why does this work better def isqrt(n): i = int(sqrt(n) + 0.5) if i**2 == n: return i #raise ValueError('input was not a perfect square') else: return 0 –  Dec 13 '13 at 22:30
  • I meant code from the best answer, not code from the question. I've corrected the link to make it more precise. – Sergii Dymchenko Dec 13 '13 at 22:35
  • Thank you, Sergey. What does // do? –  Dec 13 '13 at 22:47
  • "//" is integer division. 7 // 2 is 3. "/" can work as integer division in early Python versions, but in newer versions 7 / 2 is 3.5 – Sergii Dymchenko Dec 13 '13 at 22:50
  • so does // apply in python 2.7? –  Dec 13 '13 at 23:09
  • In python 2.7 you can use "//" or "/" for integer division. But it's better to use "//" to communicate the intention and to make the code future-proof. – Sergii Dymchenko Dec 13 '13 at 23:14
  • **Sorry somehow the format doesn't work here. I have reproduced this code in my original question. Does this still work in the following range for i? 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" Sorry somehow the format doesn't work here. I have reproduced this code in my original question. –  Dec 13 '13 at 23:31
  • isqrt linked from my answer will work for any arbitrary large integer numbers. The only limiting factor is available memory. – Sergii Dymchenko Dec 13 '13 at 23:36
  • For large numbers, how efficient is this algorithm? Thanks. –  Dec 14 '13 at 02:42
1

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.

user448810
  • 17,381
  • 4
  • 34
  • 59
0

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
Abhishek Bera
  • 121
  • 1
  • 5
  • This won't help for the large numbers the OP uses, because `math.sqrt` converts its argument to `float` first, and there is a rounding error there, and some very large integers are too large to fit into a `float`. – pts Aug 22 '16 at 19:29