Sqrt not giving the correct value

Hello, I’m new to Julia and I was trying to use for Fermat Factoring problem
I’m having issues with the sqrt not returning the correct value

``````function fermat(n::Int64)
x = isqrt(n); y = 0.1
while y%1 != 0
x+=1
y = sqrt(x^2 - n)
end
println((x-y)  ,", ", (x+y))
end
``````

This code works for small values like 187, and 161423 but when I use n = 171190005457, I was supposed to get 17 and 10070000321. Which I know that there are a few erros, because it doesn’t return me prime numbers at high values.
I tried calculating the sqrt(5035000169^2 - 171190005457) but it doesn’t return me the correct value.

It seems like you are getting integer overflow here, maybe try running it with a type supporting larger values such as Int128 or BigInt?

``````julia> 5035000169^2 - 171190005457
6904482456930471488

julia> big(5035000169)^2 - 171190005457
25351226530640023104

julia> typemax(Int)
9223372036854775807
``````
1 Like

in general be very careful when trying to run number theory stuff in languages with machine number types as default (or put it a different way, you don’t have to be as careful when using Mathematica)

i.e. you generally need to use `BigInt` types if you want to do number theory.

A few languages do this for you (Mathematica, Maple, and other computer algebra systems, and Python), but you pay a big performance price for this if you are working with ordinary integers (e.g. loop counters, array indices, etcetera), so performance-oriented languages typically require you to use bignums (arbitrary precision arithmetic) explicitly.

8 Likes

Note that in addition to the integer overflow issue, floating point precision means that you shouldn’t expect `sqrt` to do what you want. Instead, you should use `y = isqrt(x^2-n)` and check if `y*y == x^2-n`

3 Likes

You can use Int128(171190005457), that type is in Base. I’m not sure it’s good advice since it can overflow too, unlike BigInt, though increasingly rare, with larger types. It’s going to be much faster… and e.g.:

You can also use:

`Int1024`, `UInt1024`

You can also use integer types which check for overflow, and/or use those types.

And do:

``````function fermat(n::Integer)
[..]
y = isqrt(x^2 - n)