Alternative to LL

[paulunderwood]

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.

[LaurV]

Originally Posted by paulunderwood

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

[paulunderwood]

Originally Posted by paulunderwood

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:

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.

[science_man_88]

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.

[paulunderwood]

Here is another test for Mersennes:

f(p)=local(mp=2^p-1,a=Mod(2,mp),b);for(b=3,p,a=a^2*2-1);a==0

[science_man_88]

Originally Posted by paulunderwood

Here is another test for Mersennes:

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.

[carpetpool]

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)).

[paulunderwood]

Originally Posted by paulunderwood

I found another one:

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

[science_man_88]

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

[Dr Sardonicus]

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)
;-)

[ONeil]

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?.