20120320, 15:12  #1 
Jan 2005
Transdniestr
503 Posts 
Composites that pass Mathematica's pseudoprime test
http://mathworld.wolfram.com/LucasPseudoprime.html
"Mathematica versions 2.2 and later have implemented the multiple RabinMiller 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 
20120320, 15:40  #2  
Nov 2003
16444_{8} Posts 
Quote:
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. 

20120320, 15:43  #3 
Mar 2009
2×19 Posts 
Depends on the exact implementation, but I guess from the description that it includes the BPSW test. For this test there are no known counterexamples. See http://www.trnicely.net/misc/bpsw.html and http://gilchrist.ca/jeff/factoring/pseudoprimes.html

20120320, 17:00  #4 
Jan 2005
Transdniestr
503 Posts 
True, Dr.. It's odd that they use the terms interchangeably at MathWorld. They do the same for the MillerRabin test.
Would you have anything online regarding that search? Gammatester: Different but interesting. 
20120321, 01:51  #5  
Aug 2006
1733_{16} Posts 
Quote:


20120321, 09:27  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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().

20120321, 22:22  #7  
Nov 2006
Terra
2·3·13 Posts 
Quote:
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 . 2Fermat , 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 . Is there a deterministic MR test ? 

20120321, 23:12  #8 
Nov 2003
2^{2}·5·373 Posts 

20120321, 23:15  #9  
Nov 2003
16444_{8} Posts 
Quote:
actually having read about the algorithms. Quote:
??? 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. 

20120322, 00:01  #10  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
http://en.wikipedia.org/wiki/Miller%...ts_of_the_test Quote:
Quote:


20120322, 00:56  #11  
∂^{2}ω=0
Sep 2002
República de California
2×5×13×89 Posts 
Quote:
An aside regarding "proper terminology": When I gave my little talk on the determination of compositeness of F_{24} 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SPRP pseudoprime search.  3.14159  Miscellaneous Math  6  20100714 23:00 
Strong Pseudoprime Distribution  flouran  Math  3  20090601 05:04 
please help me pass the test.  caliman  Hardware  2  20071108 06:12 
Mathematica 6 Released  jinydu  Lounge  0  20070507 05:05 
Is Mathematica really slow?  wakko  Software  4  20050211 01:45 