Alternative to LL

[paulunderwood]

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.

[ONeil]

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!

[paulunderwood]

I now have a new test to add to the previous 2:

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?

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

[science_man_88]

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

[paulunderwood]

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

[paulunderwood]

Originally Posted by paulunderwood

I now have a new test to add to the previous 2:

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

I have not tested this very far.

[science_man_88]

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.

[ATH]

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.

[paulunderwood]

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

[paulunderwood]

Here is another test for Wagstaff (2^p+1)/3:

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