Monday, July 20, 2009

Interesting comment in SICP

In the endnotes for 1.2:

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, 1005, 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 difference between mathematics and engineering

Interestingly, PGP uses the Fermat Primality Test in some of its algorithms, which according to wikipedia gives it less than a 1 in 1050 chance of hitting a Carmichael Number. Seems good enough for me.

No comments: