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

2021-12-08, 01:39   #12
charybdis

Apr 2020

22×3×72 Posts

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

 2021-12-08, 01:55 #13 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 97F16 Posts 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.
2021-12-08, 11:51   #14
T.Rex

Feb 2004
France

32·103 Posts

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

2021-12-10, 10:08   #15
kijinSeija

Mar 2021
France

2·32 Posts

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

2021-12-10, 13:16   #16
T.Rex

Feb 2004
France

92710 Posts

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

 2021-12-11, 15:58 #17 kijinSeija   Mar 2021 France 2×32 Posts 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
2021-12-11, 16:06   #18
paulunderwood

Sep 2002
Database er0rr

3·1,327 Posts

Quote:
 Originally Posted by kijinSeija ... I found a primality test ...
It is a probable prime test; no proof of primality.

 2021-12-11, 16:12 #19 kijinSeija   Mar 2021 France 2·32 Posts 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
2021-12-11, 16:35   #20
paulunderwood

Sep 2002
Database er0rr

3×1,327 Posts

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

 2021-12-11, 16:40 #21 kijinSeija   Mar 2021 France 2·32 Posts Ok thank you for that information. I only know ECCP in your list
2021-12-11, 16:58   #22
paulunderwood

Sep 2002
Database er0rr

3·1,327 Posts

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

 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 21:50.

Sat Jan 22 21:50:09 UTC 2022 up 183 days, 16:19, 0 users, load averages: 1.83, 1.44, 1.36