View Single Post
Old 2011-04-20, 14:20   #12
CRGreathouse's Avatar
Aug 2006

2×3×977 Posts

Originally Posted by R.D. Silverman View Post
You really should consider just a SINGLE MR test followed by either a
Lucas test or a Frobenius-Grantham. There is no known pseudoprime
for a single MR followed by a single Lucas test. (Preda Mihailescu
and I looked for one without success).
That's what I already use for day-to-day probable-prime testing.

Originally Posted by R.D. Silverman View Post
If the objective is proved primes, one can just trial divide N-1 and N+1
to N^(1/6), and apply the Selfridge-Lehmer-Brillhart test that allows
one to prove primality if enough factors of N-1 and N+1 are known.
Do you think this would be faster than three MR tests for 64-bit numbers? Either way you'd start with an MR test to weed out composites, and the combined test (given the factorization) should be slower than a single MR test, so it would be close. Fortunately not much trial division should be needed -- though don't you need factored part at least N^(1/6), not factoring up to N^(1/6)? That matters when you have a prime between two fairly rough numbers (e.g., members of A106639).

Last fiddled with by CRGreathouse on 2011-04-20 at 15:09
CRGreathouse is offline   Reply With Quote