20211107, 02:18  #12  
Sep 2002
Database er0rr
4666_{10} Posts 
Quote:
Enjoy the latest incarnation found in post #1. 

20211120, 14:01  #14 
Sep 2002
Database er0rr
2·2,333 Posts 
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 post #1. Please enjoy the read  it is less that 3 pages long  and let me know about any improvements that could be made. 
20220107, 22:32  #15 
Sep 2002
Database er0rr
2×2,333 Posts 
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. Last fiddled with by paulunderwood on 20220108 at 12:38 
20220115, 16:57  #16 
Sep 2002
Database er0rr
2·2,333 Posts 
I can now clarify. Take the example n=2499327041 with 30258 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 2231542 solutions in total, as r goes up to (n1)/2. Maybe this is not the correct reasoning
Last fiddled with by paulunderwood on 20220115 at 17:58 
20220219, 13:20  #17 
Sep 2002
Database er0rr
123A_{16} Posts 
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. Last fiddled with by paulunderwood on 20220219 at 15:52 
20220220, 07:35  #18 
Sep 2002
Database er0rr
4666_{10} Posts 
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] Last fiddled with by paulunderwood on 20220220 at 08:04 
20220220, 15:29  #19 
Sep 2002
Database er0rr
2·2,333 Posts 
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:
[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] 
20221026, 12:27  #20 
Sep 2002
Database er0rr
2·2,333 Posts 
Timing comparisons
The matrix approach:
Code:
{lucas_matrix(n)= T=4;r=2;while(kronecker(T^28,n)!=1,r++;T*=2); P=T;Q=2;Mod([P,Q;1,0],n)^(n+1)==Q;} Code:
{lucas_characteristic(n)= T=4;r=2;while(kronecker(T^28,n)!=1,r++;T*=2); P=T;Q=2;Mod(Mod(x,n),x^2P*x+Q)^(n+1)==Q;} Code:
{lucas_optimised(n)= T=4;r=2;while(kronecker(T^28,n)!=1,r++;T*=2); r2m2=2*r2;B=binary(n+1);L=length(B)1;s=2;t=0; for(k=2,L,temp2=ts;temp=(s*(s<<r2m2+temp2)<<1)%n;t=(temp2*(t+s))%n;s=temp; if(B[k],temp=(((s<<r2m2s)<<1+t)<<1)%n;t=s<<1;s=temp));t%=n;s==0&&t==2;} Code:
lucas_matrix 122512ms = 6.8846 selfridges lucas_characteristic 99918ms = 5.6149 selfridges lucas_optimised 47072ms = 2.6452 selfridges (Note: trivial n and square n have not been considered in the above scripts. Nor has gcd((r1)*(2*r1),n1)==1 been done.) Last fiddled with by paulunderwood on 20221026 at 16:20 Reason: updated optimisation code and timings (again) 
20221026, 20:59  #21 
Sep 2002
Database er0rr
2×2,333 Posts 
GMP program
I tested the attached GMP code against mpz_probab_prime_p(n,0) on the number (2^44497+1)/3 with the following results:
Code:
mpz_probab_prime_p(n,0) 65.69 seconds gmp_optimised_lucas 46.58 seconds gmp_optimised_lucas is a selfcontained Fermat+Lucas test which, for speed, can be preceded by TF and nonbase 2 Fermat tests. Last fiddled with by paulunderwood on 20221027 at 11:40 Reason: updated code. Had gcd with n instead of n_minus_1 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Conference paper: On the Combined Fermat/Lucas Probable Prime Test  SELROC  Math  1  20190731 09:54 
Question on Lucas Lehmer variant (probably a faster prime test)  MrRepunit  Math  9  20120510 03:50 
An interesting paper: PomeranceLucas  T.Rex  Math  5  20090130 22:50 
Lucas test for billion bit prime  MESCALINE1968  Lone Mersenne Hunters  2  20050606 22:06 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 