A Restricted Domain Lucas Probable Prime Test paper
 

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 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].

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 wishy-washy paragraph about segmentation.

[QUOTE=paulunderwood;597395]
EDIT: I have removed the wishy-washy paragraph about segmentation.[/QUOTE]

I can now clarify. Take the example n=2499327041 with [B]30258[/B] P <= (n-1)/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 (n-1)/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^2-P*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^(d-1)<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 non-minimal "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!