mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-11-26, 22:14   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

32·103 Posts
Default Universal seeds of the LLT for Mersenne and Wagstaff numbers

You probably know that there are 3 Universal Seeds for starting the LLT for Mersenne numbers: 4, 10, and 2/3.
It appears that 2/3 modulo Mq = (2^q+1)/3 = Wq, a Wagstaff number.

Also, you may know that there is a conjecture about proving that a Wagstaff number Wq is prime by using a cycle of the DiGraph under x^2-2 modulo Wq. The seed we found years ago is : 1/4. And kijinSeija found that 1/4 = W(q-2).

Moreover, I've found that 1/10 and 1/Mq seem also to be usable as Universal Seed for this conjecture, building a new bridge between Mersenne and Wagstaff primes, since the seeds of the Wagstaff conjecture are inverse modulo Wq of the Universal Seeds of the Mersenne LLT.

Pari/gp:
T(q)={M=2^q-1;W=(2^q+1)/3;S0=Mod(1/4,W);S=S0;print(S);for(i=1,q+1,S=Mod(S^2-2,W);print(S))}

Try and replace 1/4 by 1/10 and 1/Mq.
It's perfectly clear for 1/4 and 1/10.
It's a little bit different for 1/Mq. It seems to depend if q=4k+1 or 4k-1. It needs deeper study.
T.Rex is offline   Reply With Quote
Old 2021-11-26, 22:38   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×5×397 Posts
Default

Quote:
Originally Posted by T.Rex View Post
You probably know that there are 3 Universal Seeds for starting the LLT for Mersenne numbers: 4, 10, and 2/3.
It appears that 2/3 modulo Mq = (2^q+1)/3 = Wq, a Wagstaff number.

Also, you may know that there is a conjecture about proving that a Wagstaff number Wq is prime by using a cycle of the DiGraph under x^2-2 modulo Wq. The seed we found years ago is : 1/4. And kijinSeija found that 1/4 = W(q-2).

Moreover, I've found that 1/10 and 1/Mq seem also to be usable as Universal Seed for this conjecture, building a new bridge between Mersenne and Wagstaff primes, since the seeds of the Wagstaff conjecture are inverse modulo Wq of the Universal Seeds of the Mersenne LLT.

Pari/gp:
T(q)={M=2^q-1;W=(2^q+1)/3;S0=Mod(1/4,W);S=S0;print(S);for(i=1,q+1,S=Mod(S^2-2,W);print(S))}

Try and replace 1/4 by 1/10 and 1/Mq.
It's perfectly clear for 1/4 and 1/10.
It's a little bit different for 1/Mq. It seems to depend if q=4k+1 or 4k-1. It needs deeper study.
I just found this works for (2/3)^-1

Code:
wag(q)=W=(2^q+1)/3;S0=S=Mod(3/2,W);for(i=2,q,S=S^2-2);S==S0;
So maybe there is some relationship between inverse seeds for Mersenne and Wagstaff. I.e if S0 is a Mersenne seed then 1/S0 is a Wagstaff seed.

Are 4, 10 and 2/3 the only ones for Mersenne? I remember Lehmer had said something about these.

Last fiddled with by paulunderwood on 2021-11-26 at 22:48
paulunderwood is offline   Reply With Quote
Old 2021-11-26, 23:49   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F8216 Posts
Default

More on the seed 3/2 for Wagstaff numbers.

Mod(Mod(x,W),x^2-3/2*x+1) is at the heart because S = S0 = 3/2 = x+1/x which leads to the recurrence S=S^2-2 mod W

The solution for x is ( 3/2 +- sqrt( (3/2)^2-4 ) / 2 = ( 3 +- 2 * sqrt(2) ) / 4

That is 4*x - 3 == +- 2 * sqrt(2)

So we can use a power of Mod(Mod(4*x-3,W),x^2-8).

By trial and error Mod(Mod(4*x-3,W),x^2-8)^(W+1)+119 == 0

Edit. That marked red is wrong, but somehow the result is good!

Stumped!

Last fiddled with by paulunderwood on 2021-11-27 at 01:30
paulunderwood is offline   Reply With Quote
Old 2021-11-27, 00:35   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·761 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Are 4, 10 and 2/3 the only ones for Mersenne? I remember Lehmer had said something about these.
https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.

The ninth page of Bas Jensen's PhD number theory thesis https://scholarlypublications.univer...3A2919366/view makes reference to a 1996 conjecture by G. Woltman, proven 4 years later.

Last fiddled with by kriesel on 2021-11-27 at 00:37
kriesel is online now   Reply With Quote
Old 2021-11-27, 05:08   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5×11×59 Posts
Default

Quote:
Originally Posted by kriesel View Post
https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.

The ninth page of Bas Jensen's PhD number theory thesis https://scholarlypublications.univer...3A2919366/view makes reference to a 1996 conjecture by G. Woltman, proven 4 years later.
There are at least 2 infinite series of universal starting values starting from the known 4 and 10
https://www.mersenneforum.org/showpo...0&postcount=46

A0=A1=4, AN=14*AN-1-AN-2
B0=B1=10, BN=98*BN-1-BN-2

Last fiddled with by ATH on 2021-11-27 at 05:11
ATH is online now   Reply With Quote
Old 2021-11-27, 08:52   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

92710 Posts
Default

Quote:
Originally Posted by kriesel View Post
https://en.wikipedia.org/wiki/Lucas%...tarting_values states there are an infinite number of universal starting values.
Not exactly. There are 2^x (cannot remember the exact value, x depends on q, and I'm now typing on my phone) seeds for each Mq. But there are only 3 F IXED values which can be used for all Mq.

I see that 2/3 = Wq was already known.
T.Rex is offline   Reply With Quote
Old 2021-11-27, 08:54   #7
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

32·103 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I just found this works for (2/3)^-1
Good !
Thanks !
I should have checked Yesterday.
T.Rex is offline   Reply With Quote
Old 2021-11-27, 09:22   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×5×397 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Good !
Thanks !
I should have checked Yesterday.
It is not so great since (3/2)^2-2 = 1/4 which is already known.

Just as (3)^((Mp - 1)/2) == -1 mod Mp for Mersenne primes, we have (-7)^((Wq - 1)/2) == 1 mod Wq for Wagstaff PRPs. The latter can be 7^((Wq - 1 )/2) == -1 mod Wq.

Last fiddled with by paulunderwood on 2021-11-27 at 10:09
paulunderwood is offline   Reply With Quote
Old 2021-11-27, 13:35   #9
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×761 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Not exactly.
I thought later after I posted that, that seed > Mp or Mp2 would be some sort of problem. But it seems to work, at least in a very small sample tried.
The wikipedia article should be updated if it's wrong.
kriesel is online now   Reply With Quote
Old 2021-11-30, 22:15   #10
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16378 Posts
Default

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
Attached Files
File Type: pdf WagstaffLLT.pdf (70.1 KB, 31 views)
T.Rex is offline   Reply With Quote
Old 2021-12-08, 01:15   #11
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11×13×17 Posts
Default

Probably a stupid question, but my knowledge is not up to scratch.

It is my understanding that "2/3" is shorthand for (2 mod M(p))(3 mod M(p))-1 = W(p). I was indeed able to confirm that W(p) works as a seed value when testing whether M(p) is prime. However, it's not clear how (2 mod M(p))(3 mod M(p))-1 evaluates to a Wagstaff number.

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?
ixfd64 is online now   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 01:33.


Mon Jan 17 01:33:33 UTC 2022 up 177 days, 20:02, 0 users, load averages: 0.90, 1.09, 1.14

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.

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