CODEWITHSUNDEEP
pythonpython-3.xrsainteger-overflow
jopp
jopp

Reputation: 193

Integeroverflow when trying large values - factorization algorithm

I tried to implement Fermat's factorization method (see https://en.wikipedia.org/wiki/Fermat%27s_factorization_method), here's the code:

import math
def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x + (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

def fermat(n):
    a = math.ceil(math.sqrt(int(n)))
    b2 = a*a - n
    while not is_square(b2):
        a = a+1
        b2 = a*a - n
    return (a-math.sqrt(b2))

So my goal is to factorize the integer n. To do so I define two other variables: a is defined as the rounded up squareroot of n and b is the difference between a squared and the number I want to factorize.

The while-loop says, if b2 isn't a square, increment a and define b2 to be the difference between the square of the new a and the number I want to factorize. If b2 is a square then a-squareroot of b2 will be a factor.

The problem works fine when I call the function like this print(fermat(133)) which gives me the answer 7 since it is the lowest prime factor and then I just have to divide 133 by 7 to get 19. So far so good.

But I want to use this code to break an Rsa cryptosystem where I have to factor

n = 507204827540547635003188460612372848602900324231921153214257357007181658245923199433998982097775501221867848469443624920597607769543938674944505236183262115817470130367565835690961161034764686003873284004530093885216278169686899261491680377671371989819332490227245364291020052993400797298847667351869225677060848581769823704347697557065010283805595504356259635995676212493990051132738242918342267376701

But since n is so large I get an overflow error, ofcourse, where it says "int too large to convert to float".

This error made me do some research and I found from decimal import Decimal. Since I am pretty new to programming, I tried to implement it everywhere in the function fermat(n) like this:

def fermat(n):
        a = Decimal(math.ceil(math.sqrt(int(n))))
        b2 = Decimal(a*a - n)
        while not is_square(b2):
            a = Decimal(a+1)
            b2 = Decimal(a*a - n)
        return (Decimal(a-math.sqrt(b2)))

But, after that, I still had the exact same problem. I don't really understand what "Decimal" is supposed to do, evern after reading about it though. Any idea what I could do to make this code work with large n?

I'm sure I have forgot to share some, which I think, important information. But can't remember what at the moment. I will update later if it something I have forgotten. Hope someone can help me, thanks :)

Upvotes: 1

Views: 93

Answers (1)

mugabits
mugabits

Reputation: 1035

You will need to redefine your maximum for your computation to run. Look at 

import sys
sys.maxsize

and you will see that number is much smaller than your value for n. In your case, I recommend not using math library, and use your own implementation.

The math.ceil() returns a float and it doesn't fit your long integer.

Upvotes: 1

Related Questions