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:

quicklymeans checking a single divisor against the 100 million digit number within 30-60 minutes.

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

1 CPUis 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.

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