From: "Markku-Juhani O. Saarinen" <mjos@math.jyu.fi>
Newsgroups: sci.math.research
Subject: Re: Primes
Date: 20 Nov 1997 14:08:45 GMT

David Kastrup <dak@fsnif.neuroinformatik.ruhr-uni-bochum.de> wrote:

> > I'm currently working on an algorythm to determine if a number with about 100
> > digits is or is not a prime number. If you know such algorythm, could you tell me
> > how to do this faster than factorizing ?

> Pick a random number n (not 0, obviously) and verify that n^{p-1} = 1
> modulo p.  Repeat any number of times.  If you get something non-equal
> to 1, p is not prime.  The probability for a number to pass one such
> test even though not being a prime is about 25%, and tests are
> independent.

  This test is often called "Fermat's test". Composites that pass this
  test with any number of iterations are called Carmichael numbers. It has
  been shown that there are infinitely many Carmichael numbers [1].

  Composites that satisfy the above equation are called pseudoprimes to
  the base n. It has been conjectured [2] ("based on extensive experience
  and analysis") that the number of pseudoprimes less than m is at most:

      n / L(m)^(1+O(1))
    where
      L(m) = exp( log m log log log m / log log m ) 

  This means that Fermat's test is reasonably good for large, random p.

  (the 25% figure is false; you probably were thinking about the 
   Miller-Rabin test, where 25% is a upper bound.)

  Cryptography textbooks have sections on probabilistic primality testing
  that are easy to read. [3]

- mj

[1] A. Granville, "Primality testing and Carmichael numbers", Notices
    Amer. Math. Soc. 39 (1992), 696--700  

[2] R. L. Rivest, "Finding Four Million Large Random Primes", proceedings
    of CRYPTO 90, Springer 1991, p. 625--626, 

[3] A. Menezes, P. van Oorschot, and S. Vanstone: "Handbook of Applied
    Cryptography", CRC Press 1997

  __
\/ 8\ Markku-Juhani O. Saarinen <mjos@math.jyu.fi> http://www.math.jyu.fi/~mjos
/\__/ pgp key id 1E12258D  fingerprint DF09 D7AA D9D2 18E9  343F 194D 9E79 692B