Timeline for How many cpus needed to check a 100 million digit prime number efficiently?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2011 at 12:45 | comment | added | user9072 | S. Carnaham, thanks, so I definitely should not have taken 4 as approximation...I believe I wanted to use the ceiling to rather give a too low estimate for the primes, and somehow confused base 2 and natural. | |
| Jul 24, 2011 at 7:12 | comment | added | S. Carnahan♦ | Incidentally, the natural log of 10 is closer to 2 than it is to 3. | |
| Jul 23, 2011 at 2:01 | comment | added | user9072 | d. One more data point. Acording to Ribenboim, The little book of bigger primes (2004) the (then) largest number proved prime (in 03) with a general purpose algorithm was (only) 5878 digits, using about 3500 hours on a then good processor. The method used was ECPP (eliptic curve primality proving) by Atkin--Morain; this is parallizable, search for papers of Morain. END | |
| Jul 23, 2011 at 2:00 | comment | added | user9072 | c. Prime testing is a complicated. There are many test and good progs combine various test. This can include trial divison up to some threshold. See for example for an overview of methods en.wikipedia.org/wiki/Primality_test and math.u-bordeaux.fr/~belabas/pari/doc/faq.html#primetest for some words what is done in an actual program. As AKS got mentioned, it is my understanding, from e.g. the PARI link above, despite its great theoretical importance, it is not actually used much (this info is a bit dated 2006, but also in 06 the algo was around since a while). | |
| Jul 23, 2011 at 1:58 | comment | added | user9072 | a. Do you want to find a prime of this size or test one specific number (if the latter I would be curious why)? For the former: there is a monetary award of the EFF of 150.000$ for the first 100 million digit prime. So, besides scientific interest, there would be a simple economic interest in finding such a prime, if it were feasible (with a cost of less than that amount). b. The largest known primes are all Mersenne primes and as such of a particular form. It also makes a difference if you want to test a generic number or one of a particular form. | |
| Jul 23, 2011 at 1:58 | comment | added | user9072 | Adam F, regarding 'storing primes' to do something for 100 million digit numbers. Note that up to size x there are about x/log x primes. Thus up to 10^50000000 there are something like (taking 4 as approx for nat log of 10) 10^50000000/ (2 *10^8) = 5 * 10^4999991 primes. This is an insanely large number relative to say a Terabyte (10^12). I do not know about the specifics of Map Reduce, but a couple more general remarks/questions: | |
| Jul 22, 2011 at 23:33 | comment | added | Gerhard Paseman | As a first step, you could do Euclid's gcd algorithm with products of some of the primes. Even if you could do this quickly with, say, products of a million primes each time, that only reduces the exponent above by one or two orders of magnitude. There is still the problem of generating the products for use in such an endeavour. Better to read up on AKS. Gerhard "Ask Me About System Design" Paseman, 2011.07.22 | |
| Jul 22, 2011 at 21:51 | vote | accept | Adam F | ||
| Jul 22, 2011 at 21:40 | comment | added | Adam F | I could store all of the known contiguous prime numbers and check against those and then perform trial division of odd numbers up to the square root. If I don't do trial division, how else will I divide and conquer in map-reduce? | |
| Jul 22, 2011 at 20:43 | comment | added | Will Jagy | See Mariano's post, it refers to Joel David Hamkins: tea.mathoverflow.net/discussion/482/… | |
| Jul 22, 2011 at 20:28 | history | answered | user9072 | CC BY-SA 3.0 |