mersenneforum.org Primality test for Riesel and Proth prime ?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-12-05, 21:28 #1 kijinSeija   Mar 2021 France 2·32 Posts Primality test for Riesel and Proth prime ? Here is what I observed : For Riesel prime : Let Rq = k*n^q-1, S(0) = n^k and S(i+1)= S(i)^n Rq is prime iff S(q) = n^2 For example with 10*11^3-1, 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) 121 = n^2 so 13309 is prime. I used this code on Pari Gp : q=3;Wq=10*11^q-1;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(q-1) = 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) And 193 is prime 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,q-1,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 :)
2021-12-05, 21:52   #2
paulunderwood

Sep 2002
Database er0rr

F8016 Posts

Quote:
 Originally Posted by kijinSeija If you find a counterexample for one of primality test please tell me thanks :)
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
561 is a Carmichael number.

Last fiddled with by paulunderwood on 2021-12-05 at 21:55

 2021-12-05, 22:06 #3 kijinSeija   Mar 2021 France 1810 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 2021-12-05 at 22:08
2021-12-05, 22:19   #4
paulunderwood

Sep 2002
Database er0rr

27·31 Posts

Quote:
 Originally Posted by kijinSeija Oh I see I forgot to check Carmichael numbers. I forgot to say than k>, n>1 and q>1 otherwise you can get false positive but maybe it is not enough to avoid Carmichael numbers :/
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 2021-12-05 at 22:26

 2021-12-05, 22:22 #5 kijinSeija   Mar 2021 France 2·32 Posts Oh thanks for your quick reply so it definitely doesn't work for Proth prime :(
2021-12-05, 22:42   #6
paulunderwood

Sep 2002
Database er0rr

27·31 Posts

Quote:
 Originally Posted by kijinSeija Oh thanks for your quick reply so it definitely doesn't work for Proth prime :(
Nor Riesel

Code:
q=4;Wq=557*2^q-1;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)
In general a single parameter test with one Lucas -- not Fermat -- test can be fooled. Similarly, n parameters with n Lucas tests can be fooled. Fermat tests are superfluous. This is the received wisdom.

Last fiddled with by paulunderwood on 2021-12-05 at 22:50

 2021-12-05, 23:47 #7 kijinSeija   Mar 2021 France 2·32 Posts With this formula, I haven't the Carmichael numbers at least the 8911 one Code: T(q)={Wq=557*2^q-1;S0=2^557;S=S0;print("q= ",q);for(i=1,q-1,S=Mod(S^2,Wq));if(S==2,print("prime"))} For the Riesel prime and it seems it works with others primes of the form 557*2^q-1 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,q-1,S=Mod(S^2,Wq));if(S==Wq-1,print("prime"))} But with that sometimes I miss some primes numbers. I don't know if it possible to get a perfect formula for this but I will search again :)
 2021-12-06, 01:14 #8 paulunderwood     Sep 2002 Database er0rr 27·31 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^2-1;S0=2^3;S=S0;print("q= ",q);for(i=1,q-1,S=Mod(S^2,Wq));if(S==2,print("prime"))} Testing 11: T(2) q= 2 Code: T(q)={Wq=401878969*2^q-1;S0=Mod(2,Wq)^401878969;S=S0;print("q= ",q);for(i=1,q-1,S=S^2);if(S==2,print("prime"))} T(3) q= 3 prime...false Last fiddled with by paulunderwood on 2021-12-06 at 01:17
 2021-12-07, 17:50 #9 kijinSeija   Mar 2021 France 2×32 Posts I observed new things about 3*2^q-1 and 3*2^q+1 with the same seed S(0) = 2/3 and S(i+1) = S(i)^2-2 Let Rq = 3*2^q-1 and Pq = 3*2^q+1 Rq or Pq is prime iff S(q-1) = 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) And 3*2^6-1 : Code: Mod(128, 191) Mod(147, 191) Mod(24, 191) Mod(1, 191) Mod(190, 191) Mod(190, 191) 769 and 191 are both prime. 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,q-1,S=Mod(S^2-2,Wq));if(S==2,print("prime"),S==Wq-1,print("prime")) This is just an observation of course :) I hope there are no "false positive" with Carmichael numbers this time
2021-12-07, 20:55   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×7×461 Posts

Quote:
 Originally Posted by kijinSeija ...I hope there are no "false positive" with Carmichael numbers this time
"Lasciate ogne speranza, voi ch'intrate"

 2021-12-08, 13:26 #11 kijinSeija   Mar 2021 France 2×32 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post patnashev Number Theory Discussion Group 11 2020-06-03 14:02 Godzilla Miscellaneous Math 40 2018-10-17 00:11 lukerichards Number Theory Discussion Group 7 2018-01-20 16:47 amcfarlane Math 1 2006-07-23 18:29 robert44444uk Math 1 2005-09-24 10:35

All times are UTC. The time now is 09:41.

Sun Jan 16 09:41:44 UTC 2022 up 177 days, 4:10, 0 users, load averages: 0.70, 0.70, 0.77