mersenneforum.org A Restricted Domain Lucas Probable Prime Test paper
 Register FAQ Search Today's Posts Mark Forums Read

2021-11-07, 02:18   #12
paulunderwood

Sep 2002
Database er0rr

10001100010002 Posts

Quote:
 Originally Posted by Nick 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.
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 post #1.

2021-11-08, 06:35   #13
paulunderwood

Sep 2002
Database er0rr

23×3×11×17 Posts

Quote:
 Originally Posted by paulunderwood Enjoy the latest incarnation found in post #1.
A new copy has been uploaded with more statistics. I am waiting for the final data to come in. ETA: a few weeks

 2021-11-20, 14:01 #14 paulunderwood     Sep 2002 Database er0rr 448810 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.
 2022-01-07, 22:32 #15 paulunderwood     Sep 2002 Database er0rr 118816 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 wishy-washy paragraph about segmentation. Last fiddled with by paulunderwood on 2022-01-08 at 12:38
2022-01-15, 16:57   #16
paulunderwood

Sep 2002
Database er0rr

23×3×11×17 Posts

Quote:
 Originally Posted by paulunderwood EDIT: I have removed the wishy-washy paragraph about segmentation.
I can now clarify. Take the example n=2499327041 with 30258 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 2231542 solutions in total, as r goes up to (n-1)/2. Maybe this is not the correct reasoning

Last fiddled with by paulunderwood on 2022-01-15 at 17:58

 2022-02-19, 13:20 #17 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts 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. Last fiddled with by paulunderwood on 2022-02-19 at 15:52
 2022-02-20, 07:35 #18 paulunderwood     Sep 2002 Database er0rr 23×3×11×17 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^(d-1)
 2022-02-20, 15:29 #19 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 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] 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] So pseudoprimes can be expected at about 14 and 19 digits (resp.). The prize money is within reach!
 2022-10-26, 12:27 #20 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts Timing comparisons The matrix approach: Code: {lucas_matrix(n)= T=4;r=2;while(kronecker(T^2-8,n)!=-1,r++;T*=2); P=T;Q=2;Mod([P,-Q;1,0],n)^(n+1)==Q;} The characteristic approach: Code: {lucas_characteristic(n)= T=4;r=2;while(kronecker(T^2-8,n)!=-1,r++;T*=2); P=T;Q=2;Mod(Mod(x,n),x^2-P*x+Q)^(n+1)==Q;} Optimised code of the paper: Code: {lucas_optimised(n)= T=4;r=2;while(kronecker(T^2-8,n)!=-1,r++;T*=2); r2m2=2*r-2;B=binary(n+1);L=length(B)-1;s=2;t=0; for(k=2,L,temp2=t-s;temp=(s*(s<
2022-10-26, 20:59   #21
paulunderwood

Sep 2002
Database er0rr

23·3·11·17 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
mpz_probab_prime_p does some trial division and a 2-PRP test + a lucas test.

gmp_optimised_lucas is a self-contained Fermat+Lucas test which, for speed, can be preceded by TF and non-base 2 Fermat tests.
Attached Files
 gmp_optimised_lucas.c (3.4 KB, 58 views)

Last fiddled with by paulunderwood on 2022-10-27 at 11:40 Reason: updated code. Had gcd with n instead of n_minus_1

 Similar Threads Thread Thread Starter Forum Replies Last Post SELROC Math 1 2019-07-31 09:54 MrRepunit Math 9 2012-05-10 03:50 T.Rex Math 5 2009-01-30 22:50 MESCALINE1968 Lone Mersenne Hunters 2 2005-06-06 22:06 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 00:06.

Tue Jan 31 00:06:59 UTC 2023 up 165 days, 21:35, 1 user, load averages: 1.45, 1.17, 1.01