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 only checking the numbers

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?

Edit: I am aware of the AKS Primality test but I need a way to break a test down into map-reduce. Which primality tests are best suited for this divide and conquer thinking? I have a grant to use the Amazon Web Services Map-Reduce framework and I am looking for a way to efficiently distribute the workload among the fewest compute instances for the least amount of time (hence, why I asked this question).