Strengthening the BailliePSW primality test
There is [URL="https://arxiv.org/pdf/2006.14425.pdf"]a new paper[/URL] for BaiiliePSW fans.

Re: STRENGTHENING THE BAILLIEPSW PRIMALITY TEST
[QUOTE=paulunderwood;549093]There is [URL="https://arxiv.org/pdf/2006.14425.pdf"]a new paper[/URL] for BaiiliePSW fans.[/QUOTE]Ugh, the allcaps title makes it look like spam. :no:

[QUOTE=retina;549094]Ugh, the allcaps title makes it look like spam. :no:[/QUOTE]
I merely copied and pasted the title. :smile: I just updated the title. Thanks 
[QUOTE=paulunderwood;549095]I just updated the title.[/QUOTE]:tu: Much better.

[QUOTE=paulunderwood;549093]There is [URL="https://arxiv.org/pdf/2006.14425.pdf"]a new paper[/URL] for BaiiliePSW fans.[/QUOTE]
I read it. Looks like a significant improvement at a low cost. I just wonder if we can have an educated guess of how many pseudoprimes would result in a hypothetical search up to 10[SUP]1000[/SUP] 
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 
[QUOTE=chris2be8;549221]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[/QUOTE] I would think not. Proving LL is a sort of Lucas test. Also Mersenne have zero density in 2PSP. I believe the $2000 prize will not be claimed. 
Even the normal BPSW test has no known counterexamples and now they add a new test with only 5 vpsp under 10[SUP]15[/SUP]. 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: [url]https://mathworld.wolfram.com/BailliePSWPrimalityTest.html[/url] [QUOTE]However, the elliptic curve primality proving program PRIMO checks all intermediate probable primes with this test, and if any were composite, the certification would necessarily have failed. Based on the fact that this has not occurred in three years of usage, PRIMO author M. Martin estimates that there is no composite less than about 10000 digits that can fool this test.[/QUOTE] [url]https://math.stackexchange.com/questions/2902592/isnttheestimateforthesmallestcounterexampleofthebpswtestfartooopti?rq=1[/url] See the bottom answer "[B]Determinism to 2[SUP]64[/SUP][/B]" 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? [url]https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test[/url] [QUOTE]However, a heuristic argument by Pomerance suggests that there are infinitely many counterexamples.[5] Moreover, Chen and Greene [6] [7] have constructed a set S of 1248 primes such that, among the nearly 2[SUP]1248[/SUP] products of distinct primes in S, there may be about 740 counterexamples. However, they are talking about the weaker PSW test that substitutes a Fibonacci test for the Lucas one.[/QUOTE] 
[QUOTE=ATH;549244]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?[/QUOTE]
I believe there is indeed no such proof. One possible type of proof would be a numerical example. It is however not the only possibility. 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, [url=https://arxiv.org/abs/1903.06825]There are Inﬁnitely Many Perrin Pseudoprimes[/url]. The [i]ne plus ultra[/i] of "generalized Carmichael numbers" appears to be described in a paper entitled [url=https://arxiv.org/abs/math/9812089]Higherorder Carmichael numbers[/url] by Everett W. Howe. 
[QUOTE=Dr Sardonicus;549434]
The [i]ne plus ultra[/i] of "generalized Carmichael numbers" appears to be described in a paper entitled [url=https://arxiv.org/abs/math/9812089]Higherorder Carmichael numbers[/url] by Everett W. Howe.[/QUOTE] There appear to be two types of Higher order Carmichael numbers of order m: 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 [URL="https://www.sciencedirect.com/science/article/pii/S0022314X14002108"]paper[/URL]). 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. 
All times are UTC. The time now is 19:33. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.