mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-12-08, 01:39   #12
charybdis
 
charybdis's Avatar
 
Apr 2020

58410 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
I can see where the "2/3" comes from because 2 mod M(p) = 2 and 3 mod M(p) = 3 for p > 2. But it doesn't make sense to use a fraction as a seed value. Or does (3 mod M(p))-1 mean something other than 1 / (3 mod M(p)) in this case?
No, it means exactly that, but in the ring of integers mod M(p), rather than in the rational numbers.

The rational number 1/3 is the thing that makes 1 when you multiply it by 3. Similarly (3 mod M(p))-1 is the thing that makes 1 mod M(p) when you multiply it by 3 mod M(p). So "2/3" is just the value that makes 2 when multiplied by 3 mod M(p).

And if we take W(p) and multiply it by 3, we get 2^p+1, which is indeed 2 mod M(p).

Last fiddled with by charybdis on 2021-12-08 at 01:40 Reason: field -> ring: M(p) isn't necessarily prime!
charybdis is offline   Reply With Quote
Old 2021-12-08, 01:55   #13
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11×13×17 Posts
Default

I see, thanks.

The Wikipedia article isn't very clear and doesn't mention rings until much later. I should update it when I have time.
ixfd64 is offline   Reply With Quote
Old 2021-12-08, 11:51   #14
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16378 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
Probably a stupid question, but my knowledge is not up to scratch.
There is no stupid question. What is stupid is to not ask when you don't understand. And, some years ago, I was at your place, wondering what 2/3 mod N means.

I see that you got your answer. What I could add is about how to compute 2/3 mod Mq by hand and find an integer between 0 and Mq-1.
Since Mq = 0 mod Mq, x*Mq/3 is still 0 mod Mq. So you can write : (x*Mq+2)/3 = 0 mod Mq . Now, forget mod Mq and try to find an integer x*Mq+2 which is divisible by 3. Let's try with x= 1.... . First, x=1 : (Mq+2)/3=(2^q-1+2)/3 = (2^q+1)/3 which is a Wagstaff number, thus an integer, when q is prime.
Moreover, does 1/3 mod Mq always exist ? even when Mq is not a prime ? Yes, since (2*Mq+1)/3 is always an integer.
1/3 mod 31 = 21
1/3 mod 127 = 85
1/3 mod 2047 = 1365
Try : Pari/gp : forprime(q=3,1000,Mq=2^q-1;print(q," ",((2*Mq+1)/3)-lift(Mod(1/3, Mq))))
T.Rex is offline   Reply With Quote
Old 2021-12-10, 10:08   #15
kijinSeija
 
Mar 2021
France

100102 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Hello.
I've spent some time searching for Universal Seeds for the LLT-like test for Wagstaff numbers.
Here attached is a first set of findings.
Everything has been checked for all known Wagstaff primes and for Wagstaff not-primes up to q = 10,000.
It may be strange, but 23/8 mod Wq is a Universal seed!
And 1/10 is, sometimes...
Enjoy
Tony
I tried some new seeds and -9/8 works for Wagstaff numbers. At least until 1000
kijinSeija is offline   Reply With Quote
Old 2021-12-10, 13:16   #16
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

32·103 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
I tried some new seeds and -9/8 works for Wagstaff numbers. At least until 1000
It seems that -9/8 mod Wq ~= M(q-3) = 2^(q-3)-1 .
Moreover, 9/8 should be ok too.
T.Rex is offline   Reply With Quote
Old 2021-12-11, 15:58   #17
kijinSeija
 
Mar 2021
France

1216 Posts
Default

I don't know if it fits with this topic but maybe I found a probable primality test for the number of the form (3^p-1)/2. I don't if it's new at all :


Let N = (3^p−1)/2 when p is a prime number p>3

Let S(i) =S(i−1)^3−3*S(i−1) with S0=52 . Then N is prime if and only if S(p−1) ≡ S0 (modN).

I choose 52 because this is one of the seeds for the test of Lucas-Lehmer and it seems it works with this seed (see here : https://oeis.org/A018844 )

I checked until p=2000 and I didn't find counterexample.

Last fiddled with by kijinSeija on 2021-12-11 at 16:13
kijinSeija is offline   Reply With Quote
Old 2021-12-11, 16:06   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×5×199 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
... I found a primality test ...
It is a probable prime test; no proof of primality.
paulunderwood is offline   Reply With Quote
Old 2021-12-11, 16:12   #19
kijinSeija
 
Mar 2021
France

2×32 Posts
Default

Sure sorry I will edit.

I don't know if "probable primality test" exists by the way :)

Nevermind it exists.

So when a prime is found by some primality test with no proof for the primality test it's a PRP right ?

Last fiddled with by kijinSeija on 2021-12-11 at 16:30
kijinSeija is offline   Reply With Quote
Old 2021-12-11, 16:35   #20
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1111100011002 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
So when a prime is found by some primality test with no proof for the primality test it's a PRP right ?

When a probable prime (PRP) is found by some PRP test then it may or may not be prime. A deterministic test such as BLS/KP/CGH/ECCP or others is needed to be 100% sure.
paulunderwood is offline   Reply With Quote
Old 2021-12-11, 16:40   #21
kijinSeija
 
Mar 2021
France

1810 Posts
Default

Ok thank you for that information.

I only know ECCP in your list
kijinSeija is offline   Reply With Quote
Old 2021-12-11, 16:58   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F8C16 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
Ok thank you for that information.

I only know ECCP in your list
BLS and some others: https://primes.utm.edu/prove/ 33% factorization if N-1 and/or N+1
KP: https://math.dartmouth.edu/~carlp/PDF/110.pdf 30%
CHG: https://primes.utm.edu/bios/page.php?id=797 (could not find a paper) >25%

The last two algorithms can be found somewhere in the depths of this forum. https://mersenneforum.org/showthread.php?t=24853

Last fiddled with by paulunderwood on 2021-12-11 at 17:15
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness GP2 Wagstaff PRP Search 414 2020-12-27 08:11
(New ?) Wagstaff/Mersenne related property T.Rex Wagstaff PRP Search 6 2019-11-23 22:46
P-1 bounds calculation for Wagstaff numbers axn Software 10 2018-07-24 06:27
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37
Bernoulli and Euler numbers (Sam Wagstaff project) fivemack Factoring 4 2008-02-24 00:39

All times are UTC. The time now is 02:07.


Fri Jan 21 02:07:15 UTC 2022 up 181 days, 20:36, 0 users, load averages: 2.35, 2.08, 1.78

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.

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