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. 
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=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. 
[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 BailliePSW primality test" was deposited in arXiv in June 2021. Their email addresses are available in the pdf file, see [URL]https://arxiv.org/pdf/2006.14425.pdf[/URL]. 
Thanks again. This academic point has been corrected in my copy to be the paltry $30. A cheque for it would be worth more!

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] 
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. 
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=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. 
[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? 
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.

[QUOTE=Nick;592470]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.[/QUOTE]
I have gone for a mixture of what you wrote. The outlandish claims are back! The paper has undergone a major rewrite. Enjoy the latest incarnation found in [URL="https://mersenneforum.org/showthread.php?t=27288"]post #1[/URL]. 
[QUOTE=paulunderwood;592637]
Enjoy the latest incarnation found in [URL="https://mersenneforum.org/showthread.php?t=27288"]post #1[/URL].[/QUOTE] A new copy has been uploaded with more statistics. I am waiting for the final data to come in. ETA: a few weeks :smile: 
The row of data for 9 digits has been added. The data for 10 digits will take another month of so.
I have tried to make the English simpler. So it is worth downloading the latest copy from [URL="https://mersenneforum.org/showthread.php?t=27288"]post #1[/URL]. Please enjoy the read  it is less that 3 pages long  and let me know about any improvements that could be made. :smile: 
I am still gathering data, but post #1 has been updated with the latest paper. The idea of segmenting P is introduced with the idea of unlikely geometric progression of passes of the test. I also offer £100 for a composite that passes for any "r".
EDIT: I have removed the wishywashy paragraph about segmentation. 
[QUOTE=paulunderwood;597395]
EDIT: I have removed the wishywashy paragraph about segmentation.[/QUOTE] I can now clarify. Take the example n=2499327041 with [B]30258[/B] P <= (n1)/2 values that give rise to counterexamples. The multiplicative order of 2 is 560 meaning a single 2^r solution would give rise to [B]2231542[/B] solutions in total, as r goes up to (n1)/2. Maybe this is not the correct reasoning :unsure: 
I have collected all data for 10e10 for a "linear choice" for the parameter P in x^2P*x+2, which are attached to post #1.
There might be one more revision to the paper with better wording and a more granular calculation of "expectation" from the data. Feel free to download the data and draw your own conclusion  maybe post that here. :smile: 
Here is a more granular set of statistics for various digit lengths:
[CODE]? allocatemem(100000000) *** Warning: new stack size = 100000000 (95.367 Mbytes). ? V=readvec("data_10e10.txt"); ? for(d=5,10,c=0;ac=0.0;for(v=1,#V,[n,P]=V[v];if(10^(d1)<n&&n<10^d,z=znorder(Mod(2,n));ac=ac+z/n/2;c++));print([d,c,ac])) [5, 26, 0.0085802083661410656672684116520217542767] [6, 98, 0.0049638320851750657858193213094107895834] [7, 314, 0.0058614515164310000251931880685920512458] [8, 1608, 0.0070816941908042819767139890946524717003] [9, 15072, 0.030554972381921342409809684878746893179] [10, 101630, 0.021620787552043991286872665384670317646] [/CODE] Extrapolating the expectations, a pseudoprime to the basic test  without the extra factor of 0.16  might be around 120 digits. So a nonminimal "r" pseudoprime for the test RDPRP would be about 700 digits :geek: 
Gross over estimation in previous post
I used ac=ac+z/n/2 when it should have been ac=ac+2*z/n and for RDPRP ac=ac+0.16*2*z/n.
Along with accumulated figures: [CODE][5, 26, 0.03432083, 0.03432083] [6, 98, 0.01985533, 0.05417616] [7, 314, 0.02344581, 0.07762197] [8, 1608, 0.02832678, 0.1059487] [9, 15072, 0.1222199, 0.2281686] [10, 101630, 0.08648315, 0.3146518] [/CODE] For RDPRP: [CODE][5, 26, 0.005491333, 0.005491333] [6, 98, 0.003176853, 0.008668186] [7, 314, 0.003751329, 0.01241951] [8, 1608, 0.004532284, 0.01695180] [9, 15072, 0.01955518, 0.03650698] [10, 101630, 0.01383730, 0.05034429] [/CODE] So pseudoprimes can be expected at about 14 and 19 digits (resp.). The prize money is within reach! 
All times are UTC. The time now is 20:18. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.