is 2M^2-1 prime?

[1260]

I checked 31 of the 40 mersenne primes and found that 2*M^2-1 is prime only for 5 cases: M1 (n=2), M2 (n=3), M4 (n=7), M6 (n=17), and M7 (n=19).

2*(2^2-1)^2-1 is prime
2*(2^3-1)^2-1 is prime
2*(2^7-1)^2-1 is prime
2*(2^17-1)^2-1 is prime
2*(2^19-1)^2-1 is prime

The others are mostly divisible by 17.

Can it be proven that 2*M^2-1 is composite for the succeeding mersenne primes greater than M7?

Just suppose 2*M40^2-1 [i.e., 2*(2^20996011-1)^2-1 ] is prime, as it is over 10 million digits, could it qualify for the $100,000?

What software can test this? WinPFGW produced an error when I tried testing it.

[GP2]

Originally posted by 1260
Just suppose 2*M40^2-1 [i.e., 2*(2^20996011-1)^2-1 ] is prime, as it is over 10 million digits, could it qualify for the $100,000?

Yes, but only if you've come up with some new mathematical proof that it is prime. This is way, way beyond the range of any feasible Lucas-Lehmer test.

[wblipp]

Just suppose 2*M40^2-1 [i.e., 2*(2^20996011-1)^2-1 ] is prime, ...
What software can test this?

The first step of checking primality is trial factoring to some limit. Trial factoring is the same as looking at the value of the number "modulo" a trial-divisor and seeing if it is zero. You can perform these tests using the Zmath Excel Addin. You can quickly determine the 2*M40^2-1 is divisible by 383. The first interesting case is 30*M40^2-1. It has no divisors under 700,000. For the "plus one" case, there are no divisors under 700,000 for 40*M40^2+1.

[GP2]

Originally posted by GP2
Yes, but only if you've come up with some new mathematical proof that it is prime. This is way, way beyond the range of any feasible Lucas-Lehmer test.

OK, I think I misread this.

2*(2^20996011-1)^2-1 is more clearly written as 2*(2^20996011-1)²-1

[1260]

Originally posted by wblipp
You can perform these tests using the Zmath Excel Addin. You can quickly determine the 2*M40^2-1 is divisible by 383.

Joe's Number theory web states that the Zmath Excel provides arbitrary precision arithmetic on integers upto 250 digits. 2*M40^2-1 has over 10 million digits.

I got a Z_Err when I tried using it.

[ewmayer]

Originally posted by wblipp
The first step of checking primality is trial factoring to some limit. Trial factoring is the same as looking at the value of the number "modulo" a trial-divisor and seeing if it is zero. You can perform these tests using the Zmath Excel Addin. You can quickly determine the 2*M40^2-1 is divisible by 383. The first interesting case is 30*M40^2-1. It has no divisors under 700,000. For the "plus one" case, there are no divisors under 700,000 for 40*M40^2+1.

2*M40^2-1 also has the small factor 26633567. (I checked up to 10^9)

30*M40^2-1 has the small factor 5748019. (Nothing else < 10^9)

40*M40^2+1 has no factors < 10^9.

[1260]

Originally posted by ewmayer
2*M40^2-1 also has the small factor 26633567. (I checked up to 10^9)
30*M40^2-1 has the small factor 5748019. (Nothing else < 10^9)
40*M40^2+1 has no factors < 10^9.

What software did you use?

Originally posted by GP2
Yes, but only if you've come up with some new mathematical proof that it is prime.

Isn't the Brillhart-Lehmer-Selfridge test sufficient to prove that p=2*M^2-1 is composite or prime (since the factors of p+1 are 2 and M)?

[GP2]

Originally posted by 1260
Isn't the Brillhart-Lehmer-Selfridge test sufficient to prove that p=2*M^2-1 is composite or prime (since the factors of p+1 are 2 and M)?

For some reason I carelessly misread the original 2*(2^20996011-1)^2-1 and thought he was talking about something else entirely.

[ewmayer]

Originally posted by 1260
What software did you use?

A little C code I hacked together from other pieces of number-theoretic code I had lying around. It's not difficult - just write a little code that can quickly generate primes up to some desired size (say 2^32), then for each of the small primes p, do a modular binary exponentiation (this needs just 64-bit products, i.e. 'unsigned long long' operands) and subtract-one to get the M-part, a mod-square to get M^2, and another modular multiply for whatever is multiplying the M^2.

Isn't the Brillhart-Lehmer-Selfridge test sufficient to prove that p=2*M^2-1 is composite or prime (since the factors of p+1 are 2 and M)?

I believe BLS only works when N-1 (rather than N+1) has been factored (one only needs to go to cbrt(N-1), BTW), but there is a similar primality test when N+1 has been partially (or in this case, completely) factored. One would still need to do what amounts to multiple pseudoprime tests on N in order to find the "least witnesses" required by these tests. Each if these pseudoprime tests would need roughly double the number of modular squarings the primality test on M needed, each such mod-square would involve numbers roughly twice as large as M, and would probably need zero-padding of the inputs because such general non-Mersenne numbers don't admit of an eficient DWT-based modulo. So basically you'd be doing a lot more work to test such a number than it would take to test a Mersenne of size ~M^2, and the odds of it actually being prime would likely be no better.

[ET_]

It's not difficult - just write a little code that can quickly generate primes up to some desired size (say 2^32), then for each of the small primes p, do a modular binary exponentiation (this needs just 64-bit products, i.e. 'unsigned long long' operands) and subtract-one to get the M-part, a mod-square to get M^2, and another modular multiply for whatever is multiplying the M^2.

I thought I could find some ideas about "modular binary exponentiation" in Crandall, or Mathworld... altough maybe there was an algorithm about it in Giantint library. Even Google gave me nothing.

Any more links?

Ah, one more question: in

40*M40^2+1

you have to add one instead of subtracting, no?

Luigi

[ewmayer]

Originally posted by ET_


I thought I could find some ideas about "modular binary exponentiation" in Crandall, or Mathworld... altough maybe there was an algorithm about it in Giantint library. Even Google gave me nothing.

Any more links?

MBE simply means that e.g. to find 2^n mod p, we need only O(log2(n)) steps. There are two variants: the standard "right to left" method starts with a residue r of 1 and generates a sequence of successive modular squares s, and parses the binary bits of the exponent n from right to left: every time a ones bit is encountered, the residue r is multiplied by the current modsquare s. Here is some C-style pseudocode:

if(n == 0) 
    return 1;
r = 1:
s = a;
while(n)
{
    if(n & 1)
        r = (r*s)%p;
    s = (s*s)%p;
    // right-shift the exponent:
    n >>= 1;
}
return r;

For example, if n = 13 (= 1101 in binary form), during execution of this algorithm r stores the successive powers a^0,1,5,13.


The left-to-right variant of this (described in Knuth, I believe it's Vol. 2) similarly generates a sequence of modular squares, but it parses n from left to right, and requires no separate storage of a residue and a modsquare.

Here, n is a signed int (this is necessary for the < 0 compare to work) and i is an integer index (signed or unsigned). You also need a user-supplied function leadz(), which returns the number of leading (leftmost) binary zeros in its argument:

if(n == 0) 
    return 1;

//Number of bits to the right of leading ones bit.
leading_zeros = leadz(n);
nbits = 8*sizeof(n)-leading_zeros;

// Left-justify n and shift leftmost bit off.
n <<= (leading_zeros + 1);

r = a;

// Assumes the loop will not get executed if nbits < 1:
for(i = 1; i < nbits; i++)
{
    r = (r*r)%p;
    // If current (i.e. leftmost) bit = 1, multiply by a:
    if(n < 0)
        r = (a*r)%p;
    // left-shift the exponent:
    n <<= 1;
}
return r;

For n = 13, during execution of this algorithm r stores the successive powers a^1,3,6,13.

Ah, one more question: in

40*M40^2+1

you have to add one instead of subtracting, no?

Luigi

Yes. Don't worry, I used the proper sign in my code.