 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 2×1,637 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

Jun 2011
Thailand

3·2,861 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

2·1,637 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 2×1,637 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

838410 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 293 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

2×1,637 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

33×112 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

1538 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 Programming 19 2019-11-08 22:31 cmd cmd 51 2019-09-28 14:56 a1call Miscellaneous Math 41 2019-07-21 14:19 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 02:32.

Wed Jul 8 02:32:47 UTC 2020 up 105 days, 5 mins, 0 users, load averages: 2.74, 2.62, 2.40