Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #13251

Re: Prime numbers and primality tests

From RBaillie <bobbaillie@frii.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: Prime numbers and primality tests
Date 2013-01-23 04:18 +0000
Message-ID <kdnob4$72b$1@smc.vnet.net> (permalink)
References <kd2lt4$co5$1@smc.vnet.net>
Organization Time-Warner Telecom

Show all headers | View raw


The original post had this comment:
"It is interesting to note, however, that the Lucas pseudo prime
method of primality testing apparently does not have the handy
"feature" of the Miller-Rabin test, namely, the provable, and bounded
low probability of a wrong answer, from whence an estimate of
primality for any number can be made without finding a counter
example!"

I just found this interesting article:
"The Rabin-Monier Theorem for Lucas Pseudoprimes", by F. Arnault, in
Mathematics of Computation, April, 1997.
You can download it from http://www.ams.org/journals/mcom/1997-66-218/S0025-5718-97-00836-3

Theorem 1.3 in that article shows that the probability for each strong
Lucas pseudoprime test is 4/15 (analogous to the probability 1/4 for a
Miller-Rabin test).

The key points, though, are these:  First, if N is a strong
pseudoprime base 2, it is more likely than the average number about
that size to also be a strong pseudoprime base 3 (and other bases).
So, if you make lists of strong pseudoprimes base 2 and base 3, those
lists will overlap, meaning that there are composite numbers that are
strong pseudoprimes bases 2 and 3 (and 5, and 7, ...).

Second, if you use any of the algorithms in the "Lucas Pseudoprime"
paper at
  http://mpqs.free.fr/LucasPseudoprimes.pdf
to make a list of strong Lucas pseudoprimes, then this list has no
known overlap with the list of strong pseudoprimes base 2.  It has
been checked that any number up to at least 10^16 that passes both
types of these strong pseudoprime tests is a prime.

This is why many prime-testing functions (e.g, PrimeQ) do at least one
of each type of test, instead of just doing standard strong
pseudoprime tests to a bunch of different bases 2, 3, ... .

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

Prime numbers and primality tests johnfeth@gmail.com - 2013-01-15 04:28 +0000
  Re: Prime numbers and primality tests amzoti <amzoti@gmail.com> - 2013-01-19 06:14 +0000
  Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-20 06:25 +0000
    Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-21 05:06 +0000
  Re: Prime numbers and primality tests RBaillie <bobbaillie@frii.com> - 2013-01-23 04:18 +0000

csiph-web