mersenneforum.org Alternative to LL
 Register FAQ Search Today's Posts Mark Forums Read

2018-05-02, 18:54   #12
paulunderwood

Sep 2002
Database er0rr

5·29·31 Posts

Quote:
 Originally Posted by ONeil Paul can you elaborate on this concept of rapid verification of Mprime?.
It is defunct point now that Dr Sardonicus has shown it fails as a concept for non-prime 2^37-1, but the idea was to take x, square and add 6.

2018-05-02, 18:58   #13
ONeil

Dec 2017

24×3×5 Posts

Quote:
 Originally Posted by paulunderwood It is defunct point now that Dr Sardonicus has shown it fails as a concept for non-prime 2^37-1, but the idea was to take x, square and add 6.
oh well I was rooting for you in your corner:)
37 is an anomaly in my book it always screws us!

 2018-05-02, 20:03 #14 paulunderwood     Sep 2002 Database er0rr 5·29·31 Posts I now have a new test to add to the previous 2: Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2 f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+3/a);a==0 f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2-1/a);a==0 [new] Can you find any more such tests?
 2018-05-02, 23:06 #15 ATH Einyen     Dec 2003 Denmark 2·32·191 Posts I do not think I understand them, I do not use Pari/GP. f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2 You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes? What about a/2 when a is odd? is that integer division?
2018-05-02, 23:16   #16
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

Quote:
 Originally Posted by ATH I do not think I understand them, I do not use Pari/GP. f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2 You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes? What about a/2 when a is odd? is that integer division?
Modularly it should be 1 mod mp in the first case and 1/a in that same case would be 2^(p-1) mod mp

2018-05-02, 23:31   #17
paulunderwood

Sep 2002
Database er0rr

106178 Posts

Quote:
 Originally Posted by ATH I do not think I understand them, I do not use Pari/GP. f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2+1/a);a==2 You start with a=2 and then you to (p-1) steps: a=(a/2 + 1/a)%Mp where 1/a is the modular inverse mod Mp, and the result after (p-1) steps a==2 for Mersenne primes? What about a/2 when a is odd? is that integer division?
For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). Then 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7).

Inverses are usually computed by the "extended Euclidean algorithm" which really slows down "f".

Last fiddled with by paulunderwood on 2018-05-02 at 23:47

2018-05-02, 23:43   #18
paulunderwood

Sep 2002
Database er0rr

118F16 Posts

Quote:
 Originally Posted by paulunderwood I now have a new test to add to the previous 2: Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=a/2-1/a);a==0 [new]
Interestingly, this algorithm works for Wagstaff (2^p+1)/3 by setting wp=2^p+1 and observing that the result is either -1 or 2:

f(p)=wp=2^p+1;a=Mod(2,wp);for(b=1,p-1,a=a/2-1/a);a==-1||a==2

(You have to fiddle with Mod and lift to get a good result for W3.)

I have not tested this very far.

Last fiddled with by paulunderwood on 2018-05-03 at 00:09

2018-05-03, 00:05   #19
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by paulunderwood For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). In the next iteration a/2 is 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7).
a/2 1/a a p
.......... 2 3
1 4 5 3
6 3 2 3

In other words.

Last fiddled with by science_man_88 on 2018-05-03 at 00:07

2018-05-03, 00:58   #20
ATH
Einyen

Dec 2003
Denmark

2×32×191 Posts

Quote:
 Originally Posted by paulunderwood For example a=Mod(2,7) sets up 2 (mod 7) -- it is a ring -- so a/2 is 1 (mod 7). Then 1/2 is 4 (mod 7) since 2*4 == 1 (mod 7). Inverses are usually computed by the "extended Euclidean algorithm" which really slows down "f".
Ok, it worked now, so a=(a*c + 1/a) (mod Mp) where c=2-1 (mod Mp) can be calculated in advance.

So testing all 3 algorithms for all primes up to 11K they finds all Mersenne Primes up to 11213, but that does not prove them. Though it would be weird for them to find so many Mersenne Primes and then fail for higher primes.

Last fiddled with by ATH on 2018-05-03 at 00:59

2018-05-03, 02:56   #21
paulunderwood

Sep 2002
Database er0rr

106178 Posts

Quote:
 Originally Posted by ATH Ok, it worked now, so a=(a*c + 1/a) (mod Mp) where c=2-1 (mod Mp) can be calculated in advance.
It is quicker to use a left shift by pre-computed t=p-1 bits: a=(a<<t+1/a) (mod Mp).
Or if a is even ">>1", else "<<t", but testing for even is slow in Pari-gp.

The hard thing remains computing of 1/s (mod Mp).

Last fiddled with by paulunderwood on 2018-05-03 at 03:05

 2018-05-04, 11:36 #22 paulunderwood     Sep 2002 Database er0rr 5·29·31 Posts Here is another test for Wagstaff (2^p+1)/3: Code: f(p)=wp=2^p+1;a=Mod(1/2,wp);for(b=1,p-1,a=a/2-1/a);lift(a*2)%(wp/3)==1 Last fiddled with by paulunderwood on 2018-05-04 at 11:40

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 46 2020-08-03 00:31 a1call Programming 19 2019-11-08 22:31 cmd cmd 51 2019-09-28 14:56 CEMPLLA Author Data 233 2019-06-28 17:18 ixfd64 Software 1 2008-04-26 21:28

All times are UTC. The time now is 15:00.

Sat Feb 4 15:00:47 UTC 2023 up 170 days, 12:29, 1 user, load averages: 0.97, 0.88, 0.87