mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-03-20, 15:12   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default Composites that pass Mathematica's pseudoprime test

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
grandpascorpion is offline   Reply With Quote
Old 2012-03-20, 15:40   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-03-20, 15:43   #3
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2×19 Posts
Default

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
Gammatester is offline   Reply With Quote
Old 2012-03-20, 17:00   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2012-03-21, 01:51   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173316 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
(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.
CRGreathouse is offline   Reply With Quote
Old 2012-03-21, 09:27   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
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().
akruppa is offline   Reply With Quote
Old 2012-03-21, 22:22   #7
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2·3·13 Posts
Default

Quote:
Originally Posted by akruppa View Post
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 .

Quote:
Originally Posted by R.D. Silverman View Post
(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).
Is there a deterministic MR test ?
Walter Nissen is offline   Reply With Quote
Old 2012-03-21, 23:12   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by akruppa View Post
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 is offline   Reply With Quote
Old 2012-03-21, 23:15   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Walter Nissen View Post
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.

Quote:

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.
R.D. Silverman is offline   Reply With Quote
Old 2012-03-22, 00:01   #10
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
??? 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
Quote:
Originally Posted by Wikipedia
The Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit.
Quote:
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.
Dubslow is offline   Reply With Quote
Old 2012-03-22, 00:56   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×5×13×89 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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
Quote:
Originally Posted by Wikipedia
The Miller–Rabin algorithm can be made deterministic by trying all possible a below a certain limit.
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 F24 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.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SPRP pseudoprime search. 3.14159 Miscellaneous Math 6 2010-07-14 23:00
Strong Pseudoprime Distribution flouran Math 3 2009-06-01 05:04
please help me pass the test. caliman Hardware 2 2007-11-08 06:12
Mathematica 6 Released jinydu Lounge 0 2007-05-07 05:05
Is Mathematica really slow? wakko Software 4 2005-02-11 01:45

All times are UTC. The time now is 15:31.

Wed Dec 2 15:31:17 UTC 2020 up 83 days, 12:42, 2 users, load averages: 1.54, 2.46, 2.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.