Timeline for How many cpus needed to check a 100 million digit prime number efficiently? [closed]
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2011 at 23:11 | comment | added | Dror Speiser | I think the final form of the question is pretty clear and research level. My interpretation of the question is: "is it possible given an unlimited amount of cpus to check the primality of a 100 million digits number in under an hour". Looking up the specs and time it took for verifying the primality of the 46th Mersenne prime, the answer is surely no, but not too far from a yes (5 days on 4 quadcores). To be able to do a 100 million digits number, a huge amount of work and money must go into developing extremely faster memory, as it is the primary bottleneck of a parallel implementation. | |
| Jul 22, 2011 at 21:51 | vote | accept | Adam F | ||
| Jul 22, 2011 at 21:49 | history | closed |
Will Jagy Igor Rivin Daniel Litt user6976 Felipe Voloch |
not a real question | |
| Jul 22, 2011 at 21:48 | history | edited | Adam F | CC BY-SA 3.0 |
added 17 characters in body; deleted 416 characters in body
|
| Jul 22, 2011 at 21:35 | comment | added | Adam F | I realize there are more efficient ways but how would you go about dividing the problem for map-reduce? Say I used AKS Primality testing or one of the other more efficient algorithms? | |
| Jul 22, 2011 at 21:32 | history | edited | Adam F | CC BY-SA 3.0 |
See "Edit:" section
|
| Jul 22, 2011 at 20:28 | answer | added | user9072 | timeline score: 3 | |
| Jul 22, 2011 at 20:17 | comment | added | paul garrett | The question implicitly assumes that the primality testing is by trial division, which is actually a bad primality test, even with massive parallelization. Nevertheless, if the question is roughly how many trial divisions are needed, it's about the square root of the number. Ok, so a $10^8$ decimal digit number needs about $10^{\frac{1}{2}10^8}$ trial divisions. No, no typo. With, let's say, $10^{10}$ CPUs (is this how many substantial computers exist in the world?), each one would need to do about $10^{\frac{1}{2}10^8−10}$ trial divisions. That −10 in the exponent is not helping much... | |
| Jul 22, 2011 at 20:17 | comment | added | Will Jagy | read en.wikipedia.org/wiki/AKS_primality_test and then try math.stackexchange.com/questions?sort=newest | |
| Jul 22, 2011 at 20:10 | comment | added | Adam F | Anyone know how to approach this? | |
| Jul 22, 2011 at 20:09 | history | edited | Adam F | CC BY-SA 3.0 |
mispelled primality
|
| Jul 22, 2011 at 20:04 | comment | added | Will Jagy | Well, one to hold the light bulb, | |
| Jul 22, 2011 at 19:50 | comment | added | Stopple | OK, but what's 'primeality'? | |
| Jul 22, 2011 at 19:39 | history | asked | Adam F | CC BY-SA 3.0 |