mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Probability & Probabilistic Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=115)
-   -   A Restricted Domain Lucas Probable Prime Test paper (https://www.mersenneforum.org/showthread.php?t=27288)

paulunderwood 2021-10-30 15:45

A Restricted Domain Lucas Probable Prime Test paper
 
21 Attachment(s)
The attached paper is distilled from several threads. So I thought I'd start a new one specifically to criticize the paper. Any corrections to typos, spelling mistakes, grammatical errors, inaccuracies, ellipsis of ideas etc will be most welcome.

I am hoping this paper is good enough to put on arXiv. What do you think to that?

Enjoy!

I have noticed it was a method due to Pomerance and not to Wagstaff in the BPSW paper. Fixed in my copy.

Also a stray ")" has been deleted in my copy.

I will refrain from a new upload until I get some feedback.

Dobri 2021-10-30 18:39

It seems that the actual reward for a counterexample of the BPSW test was $30 but not $620, see [URL]https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test[/URL].

Concerning the use of an indefinite article, shouldn't it be "an LPRP test" instead of "a LPRP test" because even though 'L' is a consonant, the actual pronunciation 'eL' in the abbreviation starts with a vowel?

paulunderwood 2021-10-31 10:19

[QUOTE=Dobri;592076]It seems that the actual reward for a counterexample of the BPSW test was $30 but not $620, see [URL]https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test[/URL].

Concerning the use of an indefinite article, shouldn't it be "an LPRP test" instead of "a LPRP test" because even though 'L' is a consonant, the actual pronunciation 'eL' in the abbreviation starts with a vowel?[/QUOTE]

According to [URL="http://openproblemgarden.org/op/counterexamples_to_the_baillie_psw_primality_test"]this[/URL] it is a $620 prize for a counterexample, but also for a proof that none exist.

Along with many other changes, I have made it read "an LPRP". Thanks.

The paper in the OP is updated.

Dobri 2021-10-31 11:52

[QUOTE=paulunderwood;592114]According to [URL="http://openproblemgarden.org/op/counterexamples_to_the_baillie_psw_primality_test"]this[/URL] it is a $620 prize for a counterexample, but also for a proof that none exist.[/QUOTE]
It seems that the $620 reward is concerned with the PSW conjecture but not the BPSW conjecture, see [URL]https://en.wikipedia.org/wiki/John_Selfridge#Selfridge's_Conjecture_about_Primality_Testing[/URL].
Perhaps it would be appropriate to ask Baillie and Wagstaff about this matter.
An article by Robert Baillie, Andrew Fiori, and Samuel S. Wagstaff, Jr. entitled "Strengthening the Baillie-PSW primality test" was deposited in arXiv in June 2021. Their e-mail addresses are available in the pdf file, see [URL]https://arxiv.org/pdf/2006.14425.pdf[/URL].

paulunderwood 2021-10-31 12:03

Thanks again. This academic point has been corrected in my copy to be the paltry $30. A cheque for it would be worth more!

paulunderwood 2021-11-01 09:54

The paper is finished as far as I am concerned, but feedback from others might make me develop it more.

In the lastest upload I have added the sentence:

[QUOTE]For example, for an average 100 digit base 2 Fermat pseudoprime the chance of finding it pseudoprime for the Lucas
component of the test is, by extrapolation, reduced by a factor of about 10^80.6 over a linear method of choosing parameters, such as is calculated for the BPSW test.[/QUOTE]

paulunderwood 2021-11-03 02:56

I have moderated my outlandish claims. "Test Results" of the paper has been rewritten. I show now that a few GCDs is equivalent to two Euler PRP tests! At least in effect. Of course a few GCDs can be computed way quicker than a couple of EPRP tests.

The new paper is uploaded in post #1.

paulunderwood 2021-11-04 19:27

I have made my arguments clearer, but I am still unsure about my premise and of my analysis in "Test Results".

The latest incarnation is uploaded in post #1.

chalsall 2021-11-04 19:50

[QUOTE=paulunderwood;592444]I have made my arguments clearer, but I am still unsure about my premise and of my analysis in "Test Results". The latest incarnation is uploaded in post #1.[/QUOTE]

I cannot offer any insight. The Maths is well beyond me.

But, I would like to commend you for stepping forward.

It's how the Scientific Method works.

paulunderwood 2021-11-04 22:11

[QUOTE=chalsall;592447]I cannot offer any insight. The Maths is well beyond me.

But, I would like to commend you for stepping forward.

It's how the Scientific Method works.[/QUOTE]

Thanks for those kind words.

Maybe I should just drop my analysis and present the algorithm without it. Maybe an analyst would like to write a joint author the paper. What a quandary! Intuitively I know the test is very good. But how good in comparison to BPSW?

Nick 2021-11-04 23:11

This is not my area (as you know!) but I would say broadly speaking that you have 2 paths forward: either a mathematical proof that your method performs better or, alternatively, using formal statistical methods to show that the testing you have done is sufficient to be significant.


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.