# How many cpus needed to check a 100 million digit prime number efficiently?

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 30-60 minutes.

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.

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

-
Is it 100 numbers, each number with a million digits, or is it numbers with 100 million digits? Zypher's answer is still correct, but it might help to clarify. – Mark Henderson Jul 22 '11 at 22:12
Additionally, using a serial divisor strategy like this is hopelessly inefficient. I'm not a mathematician, but surely there are other methods of verifying prime numbers that can still be used with reduce? – Mark Henderson Jul 22 '11 at 22:28
@Mark; I'm sure he was just giving those ranges as a simple example. You only need to check the primes less than sqrt(n) as possible divisors. – Chris S Jul 23 '11 at 3:32