mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-12-05, 21:28   #1
kijinSeija
 
Mar 2021
France

2·32 Posts
Default 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 :)
kijinSeija is offline   Reply With Quote
Old 2021-12-05, 21:52   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F8016 Posts
Default

Quote:
Originally Posted by kijinSeija View Post

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
paulunderwood is offline   Reply With Quote
Old 2021-12-05, 22:06   #3
kijinSeija
 
Mar 2021
France

1810 Posts
Default

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
kijinSeija is offline   Reply With Quote
Old 2021-12-05, 22:19   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

27·31 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-12-05, 22:22   #5
kijinSeija
 
Mar 2021
France

2·32 Posts
Default

Oh thanks for your quick reply so it definitely doesn't work for Proth prime :(
kijinSeija is offline   Reply With Quote
Old 2021-12-05, 22:42   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

27·31 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-12-05, 23:47   #7
kijinSeija
 
Mar 2021
France

2·32 Posts
Default

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

27·31 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2021-12-07, 17:50   #9
kijinSeija
 
Mar 2021
France

2×32 Posts
Default

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
kijinSeija is offline   Reply With Quote
Old 2021-12-07, 20:55   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×7×461 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
...I hope there are no "false positive" with Carmichael numbers this time
"Lasciate ogne speranza, voi ch'intrate"
Batalov is offline   Reply With Quote
Old 2021-12-08, 13:26   #11
kijinSeija
 
Mar 2021
France

2×32 Posts
Default

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.
kijinSeija is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Efficient Proth/PRP Test Proof Scheme patnashev Number Theory Discussion Group 11 2020-06-03 14:02
Prime numbers test primality - with proof written in invisible ink Godzilla Miscellaneous Math 40 2018-10-17 00:11
Proth and Riesel Primes lukerichards Number Theory Discussion Group 7 2018-01-20 16:47
Proth Test Limits amcfarlane Math 1 2006-07-23 18:29
Proth Riesel Drag Racing 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

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.

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