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).
 A: 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.
A: 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.
A: 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.
