mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Probability & Probabilistic Number Theory

Reply
 
Thread Tools
Old 2021-11-07, 02:18   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
paulunderwood is offline   Reply With Quote
Old 2021-11-08, 06:35   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×2,179 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

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
paulunderwood is offline   Reply With Quote
Old 2021-11-20, 14:01   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×2,179 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2022-01-07, 22:32   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

104068 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-01-15, 16:57   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2022-02-19, 13:20   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×2,179 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-02-20, 07:35   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default

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

Last fiddled with by paulunderwood on 2022-02-20 at 08:04
paulunderwood is offline   Reply With Quote
Old 2022-02-20, 15:29   #19
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default 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!
paulunderwood is offline   Reply With Quote
Old 2022-10-26, 12:27   #20
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×2,179 Posts
Default 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<<r2m2+temp2)<<1)%n;t=(temp2*(t+s))%n;s=temp;
  if(B[k],temp=(((s<<r2m2-s)<<1+t)<<1)%n;t=-s<<1;s=temp));t%=n;s==0&&t==2;}
The above tests were run on (2^11213+1)/3. This number has a balance of 1's and 0's. The tests are measured against a 3-PRP test which took 17795ms and is 1 selfridge. The results are as follows:

Code:
lucas_matrix         122512ms = 6.8846 selfridges
lucas_characteristic  99918ms = 5.6149 selfridges
lucas_optimised       47072ms = 2.6452 selfridges
When I get time, I shall write a version of the "optimised" code in GMP (with word alignment to the left) and, using round off correction, in GWNUM.

(Note: trivial n and square n have not been considered in the above scripts. Nor has gcd((r-1)*(2*r-1),n-1)==1 been done.)

Last fiddled with by paulunderwood on 2022-10-26 at 16:20 Reason: updated optimisation code and timings (again)
paulunderwood is offline   Reply With Quote
Old 2022-10-26, 20:59   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·2,179 Posts
Default 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
File Type: c gmp_optimised_lucas.c (3.4 KB, 30 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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conference paper: On the Combined Fermat/Lucas Probable Prime Test SELROC Math 1 2019-07-31 09:54
Question on Lucas Lehmer variant (probably a faster prime test) MrRepunit Math 9 2012-05-10 03:50
An interesting paper: Pomerance-Lucas T.Rex Math 5 2009-01-30 22:50
Lucas test for billion bit prime MESCALINE1968 Lone Mersenne Hunters 2 2005-06-06 22:06
about Lucas-Lehmer test and Prime 95 Annunaki Math 22 2003-08-05 21:52

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


Tue Nov 29 04:06:49 UTC 2022 up 103 days, 1:35, 0 users, load averages: 1.13, 1.02, 1.02

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔