mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2020-06-26, 02:01   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,697 Posts
Default Strengthening the Baillie-PSW primality test

There is a new paper for Baiilie-PSW fans.
paulunderwood is offline   Reply With Quote
Old 2020-06-26, 02:10   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

572710 Posts
Default Re: STRENGTHENING THE BAILLIE-PSW PRIMALITY TEST

Quote:
Originally Posted by paulunderwood View Post
There is a new paper for Baiilie-PSW fans.
Ugh, the all-caps title makes it look like spam.
retina is offline   Reply With Quote
Old 2020-06-26, 02:16   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,697 Posts
Default

Quote:
Originally Posted by retina View Post
Ugh, the all-caps title makes it look like spam.
I merely copied and pasted the title.

I just updated the title. Thanks

Last fiddled with by paulunderwood on 2020-06-26 at 02:32
paulunderwood is offline   Reply With Quote
Old 2020-06-26, 02:35   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

165F16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I just updated the title.
Much better.
retina is offline   Reply With Quote
Old 2020-06-26, 22:11   #5
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

96110 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
There is a new paper for Baiilie-PSW fans.
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 101000
rudy235 is offline   Reply With Quote
Old 2020-06-27, 16:24   #6
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×33×5×7 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2020-06-27, 18:09   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

339410 Posts
Default

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

Last fiddled with by paulunderwood on 2020-06-27 at 18:21
paulunderwood is offline   Reply With Quote
Old 2020-06-27, 21:13   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

293310 Posts
Default

Even the normal BPSW test has no known counterexamples and now they add a new test with only 5 vpsp under 1015. 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:
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.

https://math.stackexchange.com/quest...-too-opti?rq=1 See the bottom answer "Determinism to 264"



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:
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 21248 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.

Last fiddled with by ATH on 2020-06-27 at 21:25
ATH is offline   Reply With Quote
Old 2020-06-30, 13:01   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1101100001002 Posts
Default

Quote:
Originally Posted by ATH View Post
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?
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, There are Infinitely Many Perrin Pseudoprimes.


The ne plus ultra of "generalized Carmichael numbers" appears to be described in a paper entitled Higher-order Carmichael numbers by Everett W. Howe.
Dr Sardonicus is offline   Reply With Quote
Old 2020-06-30, 19:28   #10
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

311 Posts
Post

Quote:
Originally Posted by Dr Sardonicus View Post

The ne plus ultra of "generalized Carmichael numbers" appears to be described in a paper entitled Higher-order Carmichael numbers by Everett W. Howe.
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 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 2020-06-30 at 19:36
carpetpool is offline   Reply With Quote
Reply

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 2020-02-11 19:49
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Baillie-PSW Primality Test flouran Math 0 2009-05-16 18:27
N-1 primality test Citrix Math 3 2005-09-19 15:06
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 18:03.

Mon Sep 21 18:03:44 UTC 2020 up 11 days, 15:14, 1 user, load averages: 1.02, 1.48, 1.47

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.