20200626, 02:01  #1 
Sep 2002
Database er0rr
10275_{8} Posts 
Strengthening the BailliePSW primality test
There is a new paper for BaiiliePSW fans.

20200626, 02:10  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
3×31×71 Posts 
Re: STRENGTHENING THE BAILLIEPSW PRIMALITY TEST
Quote:


20200626, 02:16  #3 
Sep 2002
Database er0rr
5·857 Posts 
I merely copied and pasted the title.
I just updated the title. Thanks Last fiddled with by paulunderwood on 20200626 at 02:32 
20200626, 02:35  #4 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
3×31×71 Posts 

20200626, 22:11  #5  
Jun 2015
Vallejo, CA/.
3·13·29 Posts 
Quote:
I just wonder if we can have an educated guess of how many pseudoprimes would result in a hypothetical search up to 10^{1000} 

20200627, 16:24  #6 
Sep 2009
2,389 Posts 
The paper says that all composite Mersenne numbers (2^p1 where p is an odd prime) are 2PSP. But it doesn't say if they are likely to be LucasPSP. So would checking Mersenne numbers be a good place to look for BPSW pseudoprimes?
Chris 
20200627, 18:09  #7  
Sep 2002
Database er0rr
5×857 Posts 
Quote:
I believe the $2000 prize will not be claimed. Last fiddled with by paulunderwood on 20200627 at 18:21 

20200627, 21:13  #8  
Einyen
Dec 2003
Denmark
2·1,693 Posts 
Even the normal BPSW test has no known counterexamples and now they add a new test with only 5 vpsp under 10^{15}. There must be only finitely many composites passing this stronger version and maybe none, I wonder if something like this will ever be proved.
Regarding the normal BPSW test: https://mathworld.wolfram.com/Bailli...alityTest.html Quote:
https://math.stackexchange.com/quest...tooopti?rq=1 See the bottom answer "Determinism to 2^{64}" Apparently the constructed set of primes where many normal BPSW counter examples should exist is a weaker version of BPSW. So they are no proofs that normal BPSW psp's exists? https://en.wikipedia.org/wiki/Bailli...primality_test Quote:
Last fiddled with by ATH on 20200627 at 21:25 

20200630, 13:01  #9  
Feb 2017
Nowhere
2·5·599 Posts 
Quote:
My old PariGP manual says that no examples of composite numbers which "pass" BPSW are known, but that it is thought that there are infinitely many such numbers. I mention that, a number of years ago I conceived the notion of a generalization of Carmichael numbers that enlarged the scope of testing to the algebraic integers in a number field. I was unable to prove my suspicion that for a given number field K there are infinitely many "KCarmichael numbers," or that there were infinitely many Carmichael numbers composed of primes which "split completely" in K/Q. However, Jon Grantham subsequently succeeded in proving this, and kindly sent me a copy of the paper, There are Inﬁnitely Many Perrin Pseudoprimes. The ne plus ultra of "generalized Carmichael numbers" appears to be described in a paper entitled Higherorder Carmichael numbers by Everett W. Howe. 

20200630, 19:28  #10  
"Sam"
Nov 2016
5×67 Posts 
Quote:
n such that p^m1  n^m1 for each prime p  n n such that Phi(d,p)  Phi(d,n) for each prime p  n and each divisor d of m. With m=2, there are plenty examples of the former, but the latter is still unknown. Any n with p1  n1 and p+1  n+1 for each prime p  n must have at least four distinct prime factors (see paper). If n ≠ 1 mod 24, then n must have at least 5 prime factors. I suppose for higher m, the minimum number of prime factors dividing n will be higher too. Last fiddled with by carpetpool on 20200630 at 19:36 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
BailliePSW Primality Test  flouran  Math  0  20090516 18:27 
N1 primality test  Citrix  Math  3  20050919 15:06 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 