# Checking very large prime numbers

• 02-11-2008
Checking very large prime numbers
I have to calculate very large prime numbers. I'm stuck on the first step though.

Code:

```unsigned long long int n = pow(2.0,257.0) - 1; cout << n;```
That should be 2.32 * 10^77, but in my program it says something like 9395932912. If this isn't possible in C++, can someone tell me about any program that can check very large prime numbers?

Thankful for help.
• 02-11-2008
matsp
It can be done with C++, but you have to use "high precision math libraries", such as GMP (Gnu MultiPrecission library or some such), as although the value can be described in a double, you do not have sufficient precision in the double to describe the entire number, just a 15-digit approximation. This is fine if you are counting the weight of the universe in terms of thousands of planets and such, but if you want to check if 2^257 - 1 is a prime or not, you will need all the digits of that number, something like 85 digits or so.

Edit: Note that the integer types normally supported by C are 32-bit, with several compilers allowing 64-bit numbers too. But you are looking for numbers that are 257 bits or more. Integer math for larger numbers isn't terribly hard to implement, but it's obviously not just a case of simple integers any longer.

--
Mats
• 02-11-2008
iMalc
Not only do you have to use a multi-precisionm math library, but you also can't use the usual algorithms to make the determination either due to because they can take literally hours, days, months, or years etc or because they require more memory than a PC has.
Numbers that large require complex pseudoprimality tests instead. That's difficult enough that it's the one thing I never implemented in my own bigint library.
You definitely need something like MPL, or GMP.