mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Strengthening the Baillie-PSW primality test (https://www.mersenneforum.org/showthread.php?t=25668)

paulunderwood 2020-06-26 02:01

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

retina 2020-06-26 02:10

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

paulunderwood 2020-06-26 02:16

[QUOTE=retina;549094]Ugh, the all-caps title makes it look like spam. :no:[/QUOTE]

I merely copied and pasted the title. :smile:

I just updated the title. Thanks

retina 2020-06-26 02:35

[QUOTE=paulunderwood;549095]I just updated the title.[/QUOTE]:tu: Much better.

rudy235 2020-06-26 22:11

[QUOTE=paulunderwood;549093]There is [URL="https://arxiv.org/pdf/2006.14425.pdf"]a new paper[/URL] for Baiilie-PSW 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]

chris2be8 2020-06-27 16:24

The paper says that all composite Mersenne numbers (2^p-1 where p is an odd prime) are 2-PSP. But it doesn't say if they are likely to be Lucas-PSP. So would checking Mersenne numbers be a good place to look for BPSW pseudoprimes?

Chris

paulunderwood 2020-06-27 18:09

[QUOTE=chris2be8;549221]The paper says that all composite Mersenne numbers (2^p-1 where p is an odd prime) are 2-PSP. But it doesn't say if they are likely to be Lucas-PSP. 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 2-PSP.

I believe the $2000 prize will not be claimed.

ATH 2020-06-27 21:13

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/Baillie-PSWPrimalityTest.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/isnt-the-estimate-for-the-smallest-counterexample-of-the-bpsw-test-far-too-opti?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]

Dr Sardonicus 2020-06-30 13:01

[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 Pari-GP 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 "K-Carmichael 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 Infinitely 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]Higher-order Carmichael numbers[/url] by Everett W. Howe.

carpetpool 2020-06-30 19:28

[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]Higher-order 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^m-1 | n^m-1 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 p-1 | n-1 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.