 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?.   Thread Tools Show Printable Version Email this Page 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