5 ms·
“Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmicha
by dnaquin 18y ago
“Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the differences between mathematics and engineering.” footnote pg. 53 SICP
- jacquesm 18y ago"In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm." Where are the numbers for that ? If the fermat test already fails for 255 numbers out of 100 million input values then that would make it one in about 400K numbers. I would really be surprised if computers were that susceptible to cosmic radiation. Or should I start shielding my machines with u-metal ?
- reitzensteinm 18y agoIt says for very large numbers. Presumably it's a reflection of the amount of computational power required, if a bit of your memory gets flipped every year by cosmic radiation it's not a serious problem, unless you're doing a calculation that takes 10 computer years (eg with 1000 machines over 3 days). Kind of like Google's terabyte sort test where each time they ran it at least one hard drive died.
- dnaquin 18y ago"Let C(n) denote the number of Carmichael numbers less than n. ... The upper bound C(n)<n*exp(-(lnnlnlnlnn)/(lnlnn)) (4) has also been proved (R. G. E. Pinch)." So that ratio isn't constant. Key is "...of very large numbers...". Clearly larger than 100,000,000.
- jacquesm 18y agoAye... I missed that. Thank you!
- atarashi 18y agoAccording to the Wikipedia entry on this, for very large numbers -- up to 1e18 -- about 1 in 700 billion is a Carmichael number. http://en.wikipedia.org/wiki/Carmichael_number http://en.wikipedia.org/wiki/Carmichael_number
- deleted 18y ago[deleted]
- zandorg 18y agoI have a result which shows that a squared number minus 2, if put through the fermat test (modular exponentiation), is always prime. I got some 30k digit primes this way, but I couldn't get mathematicians interested in it. They'd just ignore it and say it was obvious. Is anyone interested in me writing a little document and posting it to Hacker News?
- gjm11 18y agoDo you mean (1) n^2-2 always passes the Fermat test (to what base(s)?) or (2) if n^2-2 passes the Fermat test (to what base(s)?) then it is actually prime?
- zandorg 18y agoYes, that's exactly what I'm saying. I'll post about this to HN soon.
- gjm11 18y agoUm, I was asking which; #1 and #2 are very different. For instance: A result of the form "n^2-2 is always a Fermat pseudoprime to base SOME-FUNCTION-OF-N" would probably not be interesting. A result of the form "n^2-2 is always a prime provided it's a Fermat pseudoprime to base SOME-FUNCTION-OF-N" would be much more so. (Where "interesting" means "interesting to me"; no one else need share my interests.)
- zandorg 18y agoI just know I've never found a prime with this method, that PFGW didn't say was a prime. n^2-2 doesn't always pass the Fermat test, but if it does, it is always a prime. I think it's base 2. Is that an okay answer? I'll clarify in this thread if you need. (Posted Lisp code to: http://www.decompiler.org/r2primes.htm http://www.decompiler.org/r2primes.htm)
- dnaquin 18y ago
- nsrivast 18y agoRough estimate: 10^(-11)) errors per bit per hour. http://catless.ncl.ac.uk/Risks/23.47.html#subj7 http://catless.ncl.ac.uk/Risks/23.47.html#subj7
- jacquesm 18y agoThat is one very interesting link, I'm going to do some experimenting, I'll report back in a bit. thank you!
- 10ren 18y agohttp://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...