20211205, 21:28  #1 
Mar 2021
France
2·3^{2} Posts 
Primality test for Riesel and Proth prime ?
Here is what I observed :
For Riesel prime : Let Rq = k*n^q1, S(0) = n^k and S(i+1)= S(i)^n Rq is prime iff S(q) = n^2 For example with 10*11^31, S(0)=11^10 and S(i+1) = S(i)^11 This is what i found on Pari Gp : Code:
3 13309 Mod(6934, 13309) Mod(8092, 13309) Mod(822, 13309) Mod(121, 13309) I used this code on Pari Gp : q=3;Wq=10*11^q1;S0=11^10;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q,S=Mod(S^11,Wq);print(S)) You can try with q=37 for example it works too :) Now for Proth prime : Let Pq = k*n^q+1, S(0) = n^k and S(i+1)= S(i)^n Pq is prime iff S(q1) = 1 For example with 3*2^6+1, S(0) = 2^3 and S(i+1)=S(i)^2 Again, this is what I found on Pari Gp : Code:
6 193 Mod(8, 193) Mod(64, 193) Mod(43, 193) Mod(112, 193) Mod(192, 193) Mod(1, 193) For the code I use : q=6;Wq=3*2^q+1;S0=8;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q1,S=Mod(S^2,Wq);print(S)) I guess this is not very useful but still interesting. If you find a counterexample for one of primality test please tell me thanks :) 
20211205, 21:52  #2  
Sep 2002
Database er0rr
3^{2}·443 Posts 
Quote:
Code:
q=1;Wq=80*7^1+1;S0=7^80;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q,S=Mod(S^7,Wq);print(S));print(S==S0) 1 561 Mod(1, 561) Mod(1, 561) 1 Last fiddled with by paulunderwood on 20211205 at 21:55 

20211205, 22:06  #3 
Mar 2021
France
2×3^{2} Posts 
Oh I see I forgot to check Carmichael numbers. I forgot to say than k>1, n>1 and q>1 otherwise you can get false positive but maybe it is not enough to avoid Carmichael numbers :/
Last fiddled with by kijinSeija on 20211205 at 22:08 
20211205, 22:19  #4  
Sep 2002
Database er0rr
3^{2}·443 Posts 
Quote:
Code:
q=4;Wq=35*2^q+1;S0=2^35;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q,S=Mod(S^2,Wq);print(S));print(S==S0) 4 561 Mod(263, 561) Mod(166, 561) Mod(67, 561) Mod(1, 561) Mod(1, 561) 0 Last fiddled with by paulunderwood on 20211205 at 22:26 

20211205, 22:22  #5 
Mar 2021
France
2·3^{2} Posts 
Oh thanks for your quick reply so it definitely doesn't work for Proth prime :(

20211205, 22:42  #6  
Sep 2002
Database er0rr
3^{2}·443 Posts 
Quote:
Code:
q=4;Wq=557*2^q1;S0=2^557;print(q," ",Wq);print(Mod(S0,Wq));S=S0;for(i=1,q,S=Mod(S^2,Wq);print(S)) 4 8911 Mod(2860, 8911) Mod(8213, 8911) Mod(6010, 8911) Mod(3817, 8911) Mod(4, 8911) Last fiddled with by paulunderwood on 20211205 at 22:50 

20211205, 23:47  #7 
Mar 2021
France
12_{16} Posts 
With this formula, I haven't the Carmichael numbers at least the 8911 one
Code:
T(q)={Wq=557*2^q1;S0=2^557;S=S0;print("q= ",q);for(i=1,q1,S=Mod(S^2,Wq));if(S==2,print("prime"))} And for the Proth number I use another seeds for S0 to avoid Carmichael numbers too for example Code:
T(q)={Wq=35*2^q+1;S0=3^35;S=S0;print("q= ",q);for(i=1,q1,S=Mod(S^2,Wq));if(S==Wq1,print("prime"))} 
20211206, 01:14  #8 
Sep 2002
Database er0rr
3^{2}·443 Posts 
To fool these "semi Euler" PRP tests, find a prime number with kronecker(2,n)==1 and kronecker(1,n)==1 respectively....
The first: Code:
T(q)={Wq=3*2^21;S0=2^3;S=S0;print("q= ",q);for(i=1,q1,S=Mod(S^2,Wq));if(S==2,print("prime"))} T(2) q= 2 Code:
T(q)={Wq=401878969*2^q1;S0=Mod(2,Wq)^401878969;S=S0;print("q= ",q);for(i=1,q1,S=S^2);if(S==2,print("prime"))} q= 3 prime...false Last fiddled with by paulunderwood on 20211206 at 01:17 
20211207, 17:50  #9 
Mar 2021
France
22_{8} Posts 
I observed new things about 3*2^q1 and 3*2^q+1 with the same seed S(0) = 2/3 and S(i+1) = S(i)^22
Let Rq = 3*2^q1 and Pq = 3*2^q+1 Rq or Pq is prime iff S(q1) = 2 or Rq  1 (or Pq  1) (mod Rq or Pq) For example with 3*2^8+1 : Code:
Mod(257, 769) Mod(682, 769) Mod(646, 769) Mod(516, 769) Mod(180, 769) Mod(1, 769) Mod(768, 769) Code:
Mod(128, 191) Mod(147, 191) Mod(24, 191) Mod(1, 191) Mod(190, 191) Mod(190, 191) I used this code to check the primality of the number and it seems it works : Code:
T(q)={Wq=3*2^q+1;S0=2/3;S=S0;print("q= ",q);for(i=1,q1,S=Mod(S^22,Wq));if(S==2,print("prime"),S==Wq1,print("prime")) I hope there are no "false positive" with Carmichael numbers this time 
20211207, 20:55  #10  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{5}·3·101 Posts 
Quote:


20211208, 13:26  #11 
Mar 2021
France
10010_{2} Posts 
I get a false positive with n = 4 for 3*2^n+1. So it doesn't works for Pq at least when n < 5.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Efficient Proth/PRP Test Proof Scheme  patnashev  Number Theory Discussion Group  11  20200603 14:02 
Prime numbers test primality  with proof written in invisible ink  Godzilla  Miscellaneous Math  40  20181017 00:11 
Proth and Riesel Primes  lukerichards  Number Theory Discussion Group  7  20180120 16:47 
Proth Test Limits  amcfarlane  Math  1  20060723 18:29 
Proth Riesel Drag Racing  robert44444uk  Math  1  20050924 10:35 