Re: Rabin-Miller Pseudoprime Test?

From: Alan Eliasen (eliasen_at_mindspring.com)
Date: 04/02/04 

Date: Fri, 02 Apr 2004 08:26:37 GMT

Korejwa wrote:
> The Rabin Miller pseudoprime test requires a "random" number to test if
> a given number is prime. Either the random number proves that the given
> number is composite (not prime), or is a "witness" that the given number
> is likely prime. If the test is run multiple times, and all the random
> numbers are "witnesses" and can not identify the given number is
> composite, then the given number can be assumed prime.
>
> For those of you who have practical experience with the Rabin-Miller
> test: Are there any methods to intelligently select the "random"
> numbers to use in this test?
>
> I've read some texts that suggest using the smallest numbers possible to
> make the calculation time short. I've read other texts that recommend
> using a sequence of small prime numbers.
>
> I'm trying to write code, and I simply can't accept using random numbers
> which make the code non-repeatable. If it doesn't matter which number I
> randomly select, then there is no reason why I can't just select numbers
> sequentially. If sequential numbers are known to make the test weak and
> unreliable, then there must be a way to select "witnesses" to maximize
> the effectiveness of the test. (Is there any advantage to using
> sequential prime numbers?)
>
> Any comments/suggestions are appreciated.

   I guess it all depends on what you're using the primality test for.

   If someone's trying to "fool" your primality test into declaring a
composite number a probable prime, then if they know the bases you're testing,
that will help them beat it. There are published procedures to construct
composite numbers that will pass the test for specified bases. (See
references below.)

   If you're just devising a good, fast primality test that will work for
almost any random number, and you don't care too much about the rare case
where someone intentionally constructs one of these numbers just to fool your
routine, then, probabilistically, you're fine using the smaller primes.
Smaller numbers will make the calculation go faster, and you can make the
worst-case random error arbitrarily small.

   Of course, the Rabin-Miller test works better on large numbers, so the
number of bases that you test may decrease with the size of the numbers in a
practical, fast test.

   If you combine this with a Lucas test, (this combination is often called
the Baillie-PSW test,) there are no known composite numbers that slip by this
combination of tests. It's very strong, although Carl Pomerance has proposed
some heuristics to try and find one:

http://www.pseudoprime.com/dopo.ps

   And, if you find a counterexample in the process, you'll be able to collect
a few thousand dollars in prizes.

   So what are you using your test for? Is there a chance someone's trying to
intentionally fool you?

Also see:

 F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to
several bases, J. Symbolic Computation 20 (1995), 151-161.

 G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993),
915-926.

  Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp.
70 (2001), 863-872. 

-- 
  Alan Eliasen                 | "You cannot reason a person out of a
  eliasen@mindspring.com       |  position he did not reason himself
  http://futureboy.homeip.net/ |  into in the first place."
                               |     --Jonathan Swift

Relevant Pages

  • Re: need code to re-sequence incremental control when record(s) re
    ... LN) to let users retain the same value of the Patient Number when enumerating ... >> in my a2k mdb file, i have a form which has a composite PK in its ... >> the sequence looking like 1,2,4,5,7, that user would probably want to ... >> automate the process of re-sequencing the values of this control. ...
    (microsoft.public.access.modulesdaovba)
  • Re: Rabin-Miller Pseudoprime Test?
    ... If the test is run multiple times, ... I've read other texts that recommend ... > using a sequence of small prime numbers. ... gave no better information on primality than the underlying prime. ...
    (sci.crypt)
  • Re: Prime challenge & fractional part
    ... Odd sequences imbedded in larger composite sequences ... The next term in sequence -- ... 1169 = composite with the first term sum identified with 4 or more factors. ... first odd term in the inbedded odd sequence. ...
    (sci.math)
  • Re: 2*k+3 = p
    ... just once giving of the form 2n+3= composite. ... Representing all the primes. ... Comparing this sequence above with A067076 -- ... N che appartiene alla matrice, per esempio 109, il numero degli elementi che la precedono? ...
    (sci.math)
  • Re: pre, post increment standard behaviour, and friend function declaration
    ... >>result of the chained function calls? ... > It's the result of changing k's value multiple times without a sequence ... There are a number of sequence points (before each function ... It's unspecified behavior due to the order of ...
    (comp.lang.cpp)