mersenneforum.org > Math Universal seeds of the LLT for Mersenne and Wagstaff numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-26, 22:14 #1 T.Rex     Feb 2004 France 3×311 Posts 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.
2021-11-26, 22:38   #2
paulunderwood

Sep 2002
Database er0rr

5×29×31 Posts

Quote:
 Originally Posted by T.Rex 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

 2021-11-26, 23:49 #3 paulunderwood     Sep 2002 Database er0rr 106178 Posts 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
2021-11-27, 00:35   #4
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·29·127 Posts

Quote:
 Originally Posted by paulunderwood 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

2021-11-27, 05:08   #5
ATH
Einyen

Dec 2003
Denmark

2×32×191 Posts

Quote:
 Originally Posted by kriesel 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

2021-11-27, 08:52   #6
T.Rex

Feb 2004
France

3·311 Posts

Quote:
 Originally Posted by kriesel 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.

2021-11-27, 08:54   #7
T.Rex

Feb 2004
France

3·311 Posts

Quote:
 Originally Posted by paulunderwood I just found this works for (2/3)^-1
Good !
Thanks !
I should have checked Yesterday.

2021-11-27, 09:22   #8
paulunderwood

Sep 2002
Database er0rr

5×29×31 Posts

Quote:
 Originally Posted by T.Rex 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

2021-11-27, 13:35   #9
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·29·127 Posts

Quote:
 Originally Posted by T.Rex 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.

2021-11-30, 22:15   #10
T.Rex

Feb 2004
France

3×311 Posts

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
 WagstaffLLT.pdf (70.1 KB, 79 views)

 2021-12-08, 01:15 #11 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 5×499 Posts 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post GP2 Wagstaff PRP Search 414 2020-12-27 08:11 T.Rex Wagstaff PRP Search 6 2019-11-23 22:46 axn Software 10 2018-07-24 06:27 AntonVrba Math 96 2009-02-25 10:37 fivemack Factoring 4 2008-02-24 00:39

All times are UTC. The time now is 13:23.

Sat Feb 4 13:23:03 UTC 2023 up 170 days, 10:51, 1 user, load averages: 0.85, 0.87, 0.87