# How many cpus needed to check a 100 million digit prime number efficiently?

If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped compute instances would perform efficient checks against the number in question with an assigned range of divisors (e.g. Instance 1: checks divisors 2-1000, Instance 2: checks divisors 1001-2000, ... etc.).

Definitions:

quickly means checking a single divisor against the 100 million digit number within hours.

efficient division means only checking the odd numbers up to the square root. Lower divisors would be only the known prime numbers to speed up computation.

1 CPU is the equivalent CPU capacity of a 1.0-1.2 GHz 2007 Opteron or 2007 Xeon processor.

Yes, I know there are better algorithms like AKS but I need to be able to divide the work among the mapped instances. If there is a better way to divide and conquer I am all ears.

The better question to ask would probably be: what is the mathematical relationship between the number of CPUs and the amount of time it takes to verify a number of a given magnitude of digits?

I'm asking this because I am trying to figure out the number of Map Reduce instances I would need to buy on Amazon AWS to make the computation feasible (a couple months/less than a year).

-
why do you want to do that? – abcde Jul 22 '11 at 23:05
Some useful information is in comments on the same question on MathOverflow which had been closed. – Tsuyoshi Ito Jul 23 '11 at 0:19
"How many cpus...?" A lot. – Unreasonable Sin Jul 23 '11 at 0:45

## 4 Answers

Let's say for a moment that you are set on this trial-division form of primality testing. If you gave each computer 1000 numbers to test (what you suggested), then you would need approximately $\large10^{5*10^7 - 3}$ computers. (Why? - the square root of $10^{10^8}$ is $10^{5 * 10^7}$). You would also likely need a new data type, as a hundred-million digit number would itself take more than a gigabyte of memory (and let's not talk about the feasibility of the operations on it).

Fortunately, simply finding such a prime would partially offset the cost, as this would be the largest prime known to date. How much larger? About 90 million digits larger than the current largest-known prime.

In short, this is infeasible according to current methods. And the largest primes are Mersenne Primes, which are significantly easier to test. And even then, the programs that tested them were very witty.

Your last bit: what's the relationship between number of CPUs and the time it takes to test, is actually not so trivial either. One might imagine that in the beginning, there is a certain amount of computational work W to be done, and dividing it among x computers would mean that each computer takes $\frac{1}{x}$ amount of time. But that's not quite how it would work - as it assumes we know exactly how to divide the work. It's harder to do operations between large numbers, for example, so the computer dealing with the largest numbers actually manages 1000 of them, it will end up storing over a terabyte of info on just the numbers being tested, not counting the operations themselves (fortunately, not at one time - perhaps only several gigs at a time). The smallest number computer never even hits a megabyte. So that's hard, too. But one can bound the effort by assuming that the computers won't work synergistically, and so will do it no better than $\frac{1}{x}$ of the time.

-
Which programs were used to test those Mersenne primes? Do you have a link to the source code? – Frank Hubeny Mar 12 at 6:54

There are about $\sqrt{x}/2\log x$ primes to test, with $x\approx10^{10^8}$. The average size of the primes will be over 20 MB, but let's suppose you have some super-GPU that can handle numbers of that size. Further, it's as fast as a CPU -- 3 GHz -- and can do a multiprecision division in one cycle. (This is absurdly generous; in reality this would take billions of cycles.) With a thousand cores, you can do almost $10^{20}$ divisions per year, so you need $$\frac{\sqrt{10^{10^8}}}{2\log\left(10^{10^8}\right)}\cdot\frac{1}{10^{20}}= \frac{10^{5\cdot10^7}}{2\cdot10^{28}\log10}\approx2.17\cdot10^{49999971}$$ of these GPU computers to finish in a year. If they weigh a gram apiece, this is approximately $3.62\cdot10^{49999915}$ times the mass of the universe.

On the other hand, if you used a modern technique like fastECPP, it would take only $8.8\cdot10^{20}$ processor-days, extrapolating from the time taken for the record 2011 proof. So to get this done in a month you'd need only about 3,500,000,000,000,000,000 8-core instances. I'm sure Amazon would give a discount for this kind of bulk purchase...

Dividing up the work would not be trivial; this assumes the best-case scenario where it can be gridded efficiently.

-
(+1): I liked especially the mass of the universe ... – Gottfried Helms Apr 22 '13 at 15:09
@GottfriedHelms: I thought MixedMath's answer was good but lacked a sense of perspective, so I gave an answer with a bit more of that (plus a suggestion on a slightly more reasonable approach). – Charles Apr 22 '13 at 15:15

As the others have noted, trial division is simply not the way to go about it. You're essentially applying methods that would give the prime factorisation (rather than merely test for primality).

As an indication of what numbers are challanging to even sophisticated factorisation methods on costly hardware, we can look at the RSA numbers. RSA-768 was factored by a team of experts using the number field sieve method:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413


This has 232 decimal digits. You're talking about 100000000 digits using a far less efficient method.

More realistically, if you want to find a 100 million digit prime by whacking the problem with a host of computers (presumably in order to claim the $150,000 prize here), I suggest the following steps: • Find a class of numbers (such as Proth numbers) in which primality can be proved efficiently. • Generate a long list of candidates of numbers of this form, and perform trial division (i.e., sieving) on this list to get rid of non-primes. • Run the efficient primality test for each candidate on separate computers. This is how I proved the primality of the (at the time) 629-th largest known prime (ref.). There is already highly efficient software around that can do this for you (NewPGen for sieving, and LLR for primality testing). You can expect this to require several years, be costly and cause unnecessary CO$_2\$ emissions. You can also expect to be trounced by one of the thousands of others who are doing the same thing.

-
When you sieved to remove composites, how many primes were involved in those sieves? – Frank Hubeny Mar 12 at 6:47

I don't mean to thread on anyone's toes so please forgive me if I do.

I'm not a Mathematician but I am running four instances of Cudalucas on GTX 690 Gpu's for a few days now and its Eta is saying 190 days to test for four separate 100 million digit mersenne primes. ok its a long time to wait ( and probably another 190 days to double check it) to be told no its not a prime, but a lot shorter that the calculations above.

Regards

Rob.

-
What sieve did you run first to get those four candidates? – Frank Hubeny Mar 12 at 6:45
Yes -- Mersenne numbers are much easier to test than general numbers. – Charles Apr 12 at 18:05