The Lehmann primality test.

Consider n = 1729 = 7 * 13 * 19. (n-1)/2 = 864 = 2^5 * 3^3.<p>For any value 0 &#60; a &#60; n, a^((n-1)/2) = (a^6)^144 = 1^144 = 1 mod 7.<p>For any value 0 &#60; a &#60; n, a^((n-1)/2) = (a^12)^72 = 1^72 = 1 mod 13.<p>For any value 0 &#60; a &#60; n, a^((n-1)/2) = (a^18)^48 = 1^48 = 1 mod 19.<p>Thus 1729 will pass the Lehmann test for all a. (Unsurprisingly 1729 is a Carmichael number; not all Carmichael numbers will pass all Lehmann tests, but any number which passes all Lehmann tests will be Carmichael.)

<p><pre><code> The Solovay–Strassen and Miller–Rabin tests, which are fast and accurate, but not easy to implement: the former requires understanding the Legendre and Jacobi symbols (arcane mathematical concepts) and the latter requires an efficient factorisation algorithm. </code></pre> Its very frustrating how often this comes up: an answer is well known but "hard to implement". The answer here should have clearly been "so then I used Solovay–Strassen and Miller–Rabin". You'd think there would be SOME sample code out there or that translating the math wouldn't be too difficult, yet I often run into this problem myself. The divide between mathematical notation, or perhaps the "language of CS papers" and actual code is distressing.

I can't guarantee the correctness of the implementation, but a friend (burke on HN, I believe) and I wrote a version of the Miller-Rabin primality test in Ruby &#38; C that you may want to use as reference.<p>IIRC numbers under 341,550,071,728,321 could be accurately tested for primality on the "instant" timescale.<p>See the repo on github: <a href="https://github.com/rkneufeld/mr_prime/blob/master/lib/mr_prime/mr_prime_rb.rb" rel="nofollow">https://github.com/rkneufeld/mr_prime/blob/master/lib/mr_pri...</a>

Don't forget AKS, which is deterministic and faster than trial division. Can be a bit of a pain to implement though.

"On my machine, testing the prime number 27,644,437 took about 1.2 milliseconds with a k value of 50 (far higher than you’ll probably need for your applications.)"<p>I'm sorry, but WHAT?<p>Writing the dumbest implementation of trial-division that I could, in C++ on my laptop, in Debug mode, took 0.0247046 ms to determine definitively if 27,644,437 is prime.<p>My dumbest-possible implementation, in Debug mode, is 48.5 times faster, and doesn't get confused by Carmichael numbers.<p>Move along, folks, nothing to see here.<p>"The trial-division method... gets slow quickly."<p>That may be true, but using the number 27,644,437 as a benchmark will not get you anywhere near that "slow" point.

&#62; The Solovay–Strassen and Miller–Rabin tests, which are fast and accurate, but not easy to implement: the former requires understanding the Legendre and Jacobi symbols (arcane mathematical concepts) and the latter requires an efficient factorisation algorithm.<p>The author is a bit confused. Miller-Rabin, when testing n, only requires factoring to the extent of determining the largest power of 2 that divides n-1. In other words, you have to have factor n-1 into the form 2^s d, where d is odd. This is trivial to do efficiently.

I gave the implementation a go in R. lets say it didn't go so well. <a href="http://bit.ly/uv2MoQ" rel="nofollow">http://bit.ly/uv2MoQ</a>

&#62;&#62; Otherwise, n is definitely composite — no fooling<p>This assertion is false if I understood the test correctly.<p>Take n = 5, a = 2.<p>a ^ ((n - 1) / 2) = 2 ^ ((5 - 1) / 2) = 2 ^ 2 = 4 and 4 mod 5 = 4.<p>Therefore the test will say 5 is composite.