Composites that pass Mathematica's pseudoprime test

[grandpascorpion]

http://mathworld.wolfram.com/LucasPseudoprime.html

"Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]."

This is probably old news for many here but:

Are there any known composites that pass these three tests? I was wondering if anyone has mounted a search (and perhaps failed through some bound).

Thanks

[R.D. Silverman]

Originally Posted by grandpascorpion

http://mathworld.wolfram.com/LucasPseudoprime.html

"Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]."

This is probably old news for many here but:

Are there any known composites that pass these three tests? I was wondering if anyone has mounted a search (and perhaps failed through some bound).

Thanks

(1) The quote is misworded. These are not pseudo-prime tests, they
are probable prime tests. A pseudoprime is a compositie integer
that happens to pass a PRP test.

(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).

(3) People (including a joint search by me and Preda Mihailescu about 12 years ago) have mounted searches. There is no "bound" on such searches
in the sense you mean. Instead, one constructs a special set of
primes such that some *subset* when multiplied together will yield a
desired composite. It is a (vary large!) combinatorial problem.

[Gammatester]

Depends on the exact implementation, but I guess from the description that it includes the BPSW test. For this test there are no known counter-examples. See http://www.trnicely.net/misc/bpsw.html and http://gilchrist.ca/jeff/factoring/pseudoprimes.html

[grandpascorpion]

True, Dr.. It's odd that they use the terms interchangeably at MathWorld. They do the same for the Miller-Rabin test.

Would you have anything on-line regarding that search?


Gammatester: Different but interesting.

[CRGreathouse]

Originally Posted by R.D. Silverman

(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).

(3) People (including a joint search by me and Preda Mihailescu about 12 years ago) have mounted searches. There is no "bound" on such searches
in the sense you mean. Instead, one constructs a special set of
primes such that some *subset* when multiplied together will yield a
desired composite. It is a (vary large!) combinatorial problem.

Exactly. Jon Grantham & Red Alford have such a list (A018188, incidentally); perhaps there are others.

[akruppa]

Originally Posted by grandpascorpion

True, Dr.. It's odd that they use the terms interchangeably at MathWorld. They do the same for the Miller-Rabin test.

Some time ago, "pseudoprime" was commonly used for any integer that passes a probable prime test, necessarily including all the primes. The meaning then changed to exclude actual primes. The old meaning of pseudoprime can still be found in some places, for example the Pari/GP probable prime test is called ispseudoprime().

[Walter Nissen]

Originally Posted by akruppa

Some time ago, "pseudoprime" ... probable prime test is called ispseudoprime().

Well said , Alex .

A lot of confusion arises because people keep wanting to use
the word "prime" to describe these tests of compositeness .
Primo provides a test of primality .
Full TD ( through sqrt ) is a test of primality .
2-Fermat , ECM , etc. , etc. , provide compositeness tests .
Another part of the probem is that it seems to be very difficult
to characterize the nature of the probabilty involved in the
"probable" part of "probable prime" .
"strong" also interacts .

Originally Posted by R.D. Silverman

(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).

Is there a deterministic MR test ?

[R.D. Silverman]

Originally Posted by akruppa

Some time ago, "pseudoprime" was commonly used for any integer that passes a probable prime test, necessarily including all the primes.

"Some time ago" was 30+ years.............

[R.D. Silverman]

Originally Posted by Walter Nissen

Well said , Alex .

A lot of confusion arises because people keep wanting to use
the word "prime" to describe these tests of compositeness .

No, the confusion occurs because people use terminology without
actually having read about the algorithms.

Is there a deterministic MR test ?

??? Are you asking if deterministic tests exist ???? Or do you
really mean "MR test"? If so, the answer is no. If a test is deterministic,
then it isn't MR.

[Dubslow]

Originally Posted by R.D. Silverman

??? Are you asking if deterministic tests exist ???? Or do you
really mean "MR test"? If so, the answer is no. If a test is deterministic,
then it isn't MR.

True in practice, but to be technically correct, there are deterministic variants. (These typically require the GRH, but there are "brute-forced" bounds known.
http://en.wikipedia.org/wiki/Miller%...ts_of_the_test

Originally Posted by Wikipedia

The Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit.

Originally Posted by Wikipedia

When the number n to be tested is small, trying all a < 2(ln n)2 is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Pomerance, Selfridge and Wagstaff[6] and Jaeschke[7] have verified that
if n < 1,373,653, it is enough to test a = 2 and 3;
if n < 9,080,191, it is enough to test a = 31 and 73;
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
Other criteria of this sort exist[8][9][10][11] and these results give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.

[ewmayer]

Originally Posted by Dubslow

True in practice, but to be technically correct, there are deterministic variants. (These typically require the GRH, but there are "brute-forced" bounds known.
http://en.wikipedia.org/wiki/Miller%...ts_of_the_test

The above Wikiarticle omits a crucial aspect of such "deterministic up to a limit" PRP tests; namely for a given set of bases, whether the limit can be determined (or at least bounded below) in a priori fashion. A test which cannot provide such a a priori bound is only "deterministic" in an extremely weak post hoc fashion.

An aside regarding "proper terminology": When I gave my little talk on the determination of compositeness of F₂₄ at the WCNTC some years back, John Brillhart at several points loudly objected to the effect that the Pe'pin test "was not a test." That was ... strange.