If I had access to potentially unlimited 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 1-1000, Instance 2: checks divisors 1001-2000, ... etc.).


Definitions: 



> 
> **quickly** means checking a 100 million digit number within 30-60 minutes.
> 
> 
> **efficient division** means checking odd numbers up to the square root.
> 
> 
> **1 CPU** is the equivalent CPU capacity of a 1.0-1.2 GHz 2007 Opteron or 2007 Xeon processor.
> 
> 
> 


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?



How many cpus needed to check a 100 million digit prime number efficiently?
This question is a bit unclear, still I will try to give some sort of answer. 


Some intial remarks: 


First, at the moment noone suceed in proving primality for a 100 million (decimal) digit number. The current record is (I believe) close to 13 million digits (in binary this would still not be 100 million).


Second, one does not do these test by trial division as your description seems to suggest. 


Having said this, as a thought experiment a very rough and overly optimistic calculation: 


Suppose you have a 100 million digit number. Then you will have to test whether it is divisibile by numbers of size up to its square root, that is 50 million digit numbers. 
So, you test $10^{50 000 000}$ numbers. 


Suppose you do your divison with only one processor instruction. I am not overly knowledgeable on processor speeds but according to [the list here](http://en.wikipedia.org/wiki/Instructions%252Dper%252Dsecond) let's assume you do 50 GIPS so $5\*10^9$ instruction per second. 


Now, in an hour you will do, let's be generous, $2\*10^{12}$ instructions, by our assumption divisoions.


So you need $10^{50 000 000}/(2\*10^{12}) = 5 \* 10^{49 999 987}$ processors.


As said, you cannot do this like this. Also note that using the approach you sketch you would effectively find a factor and thus a factorization. For factoring the current records are way smaller then the ones for primes I mentioned above. It is a major challenge to factor numbers with (low) hundreds of digits. Note that that current RSA-keys are of size a a thousand or two (maybe four) thousand bits. So (higher) hundreds to a thousand decimal digits only. 


P.S. Towards the end of my writing, I saw paul garrett's comment which is similar. Perhaps the details are useful. And, sorry to those who mind, for answering the off-topic question. 


