# 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
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 :)

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.