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

 2016-06-08, 01:20 #1 paulunderwood     Sep 2002 Database er0rr 393210 Posts Alternative to LL Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2 Seems to be 10 times slower than LL.
2016-06-08, 02:03   #2
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

231208 Posts

Quote:
 Originally Posted by paulunderwood Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2 Seems to be 10 times slower than LL.
it only works for odd p

2017-11-13, 23:49   #3
paulunderwood

Sep 2002
Database er0rr

22·983 Posts

Quote:
 Originally Posted by paulunderwood Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2 Seems to be 10 times slower than LL.
I found another one:

Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+3/a));a==0
If only there was some better-than-squaring-computationally way of taking an inverse mod a Mersenne number. Or being able to solve x^2+6 == 0 mod mp without exponentiation.

Last fiddled with by paulunderwood on 2017-11-13 at 23:56

2017-11-13, 23:56   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by paulunderwood Or being able to solve x^2+6 == 0 mod mp without exponentiation.
comes down to where the squares are on the arithmetic progression y(mp)-6. parity of x is the parity of y.

Last fiddled with by science_man_88 on 2017-11-13 at 23:57

 2017-12-11, 00:56 #5 paulunderwood     Sep 2002 Database er0rr 22×983 Posts Here is another test for Mersennes: Code: f(p)=local(mp=2^p-1,a=Mod(2,mp),b);for(b=3,p,a=a^2*2-1);a==0
2017-12-11, 01:05   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by paulunderwood Here is another test for Mersennes: Code: f(p)=local(mp=2^p-1,a=Mod(2,mp),b);for(b=3,p,a=a^2*2-1);a==0
we know about it ... see: https://oeis.org/A002812 like with most alterations of the LL test it's got many start values.

Last fiddled with by science_man_88 on 2017-12-11 at 01:08

 2017-12-11, 02:54 #7 carpetpool     "Sam" Nov 2016 23×41 Posts I don't know if this is useful but https://oeis.org/A002812 happens to be the subset of the sequence https://oeis.org/A110293. Like the Mersenne sequence 2^n-1, this is also a divisibility sequence. a(n) = 2*a(n-1)^2 - 1, starting a(0)=n b(n) = b(n-1)^2-2, starting b(0)=n are generalizations of https://oeis.org/A110293 I don't know the sequences which a(n) or b(n) are subsets of. That is, there exists sequences A(n) and B(n) such that A(2^n) = a(n) B(2^n) = b(n) The sequences a(n) and b(n) For further discussion let ll(2^n) be the sequence in https://oeis.org/A002812 and ll(n) be the sequence in https://oeis.org/A110293 Another question that comes up is how are ll(n) and 2^n-1 related to eachother other than the fact that if 2^n-1 is prime, then 2^n-1 divides ll(2^(n-2)).
2018-05-02, 15:37   #8
paulunderwood

Sep 2002
Database er0rr

22×983 Posts

Quote:
 Originally Posted by paulunderwood I found another one: Code: f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+3/a));a==0 If only there was some better-than-squaring-computationally way of taking an inverse mod a Mersenne number. Or being able to solve x^2+6 == 0 mod mp without exponentiation.
The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime:

1^2+6 == 0 mod 2^3-1
5^2+6 == 0 mod 2^5-1
11^2+6 == 0 mod 2^7-1
1405^2+6 == 0 mod 2^13-1

Last fiddled with by paulunderwood on 2018-05-02 at 15:40

2018-05-02, 17:32   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by paulunderwood The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime: 1^2+6 == 0 mod 2^3-1 5^2+6 == 0 mod 2^5-1 11^2+6 == 0 mod 2^7-1 1405^2+6 == 0 mod 2^13-1
12²+6== 0 mod 2^4-1

Last fiddled with by science_man_88 on 2018-05-02 at 17:32

2018-05-02, 17:57   #10
Dr Sardonicus

Feb 2017
Nowhere

2·3·23·37 Posts

Quote:
 Originally Posted by paulunderwood The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime: 1^2+6 == 0 mod 2^3-1 5^2+6 == 0 mod 2^5-1 11^2+6 == 0 mod 2^7-1 1405^2+6 == 0 mod 2^13-1
2968558982^2 + 6 == 0 (mod 2^37 - 1)
;-)

Last fiddled with by Dr Sardonicus on 2018-05-02 at 18:05

2018-05-02, 18:40   #11
ONeil

Dec 2017

24×3×5 Posts

Quote:
 Originally Posted by paulunderwood The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime: 1^2+6 == 0 mod 2^3-1 5^2+6 == 0 mod 2^5-1 11^2+6 == 0 mod 2^7-1 1405^2+6 == 0 mod 2^13-1
Paul can you elaborate on this concept of rapid verification of Mprime?.

 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 11:43.

Sun Nov 28 11:43:13 UTC 2021 up 128 days, 6:12, 0 users, load averages: 0.58, 0.80, 0.91