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?