View Single Post
Old 2010-06-01, 01:17   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33×131 Posts
Default

See here for a list of exceptions to multiple Rabin-Miller tests. From the GMP-ECM source:
Code:
  if (SP_NUMB_BITS <= 32)
    {
      /* 32-bit primality test
       * See http://primes.utm.edu/prove/prove2_3.html */
      
      if (!sp_spp (2, x, d) || !sp_spp (7, x, d) || !sp_spp (61, x, d))
        return 0;
    }
  else
    {
      ASSERT (SP_NUMB_BITS <= 64);
      /* 64-bit primality test
       * follows from results by Jaeschke, "On strong pseudoprimes to several
       * bases" Math. Comp. 61 (1993) p916 */
      
      if (!sp_spp (2, x, d) || !sp_spp (3, x, d) || !sp_spp (5, x, d)
        || !sp_spp (7, x, d) || !sp_spp (11, x, d) || !sp_spp (13, x, d)
        || !sp_spp (17, x, d) || ! sp_spp (19, x, d) || !sp_spp (23, x, d)
        || !sp_spp (29, x, d))
          return 0;
    }
There is no Rabin-Miller version of Carmichael numbers; the asymptotic probability of failure is the same for any input. This makes R-M nice for cryptographic applications that need large random primes in a fixed time with fixed chance of an error.
jasonp is offline   Reply With Quote