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