(unproven) Potential new primality conjecture for Mersenne numbers

[ETLem]

I would like to suggest this potential new Mersenne primality test for your review:


First some notations:
x == y mod p is x congruent to y modulo p
2^x two to the power of x
(x|p) is the Legendre symbol
Gaussian Integer Z[i]: e in Z[i], e = a + bi with a in Z and b in Z
The Norme of e: N(e) = a^2 + b^2 mod p
In this post p is a Mersenne number p = 2^q -1 with q odd > 2

Inverse of 2 mod p: 2^-1 == 2^(q-1) mod p


Now the proposed test:


Lemma: q a rational prime q > 2
p = 2^q - 1 a mersenne number
let a = (2^((q+1)/2) + 1)
p is prime if and only if a^(2^(q-1)) == a mod p


Proof:

Creutzburg and Tasche in Mathematic of Computation Vol 52 Num 185 Jan 1989
Proved the following:
if p = 2^q - 1 is a Mersenne prime
it exist e in Z[i] such that e^(2^(q+1)) == 1 mod p
i.e: e is a primitive (2^(q+1))th root of unity modulo p

starting from e^(2^(q+1)) == 1 mod p
The following square roots modulo p in Z[i] are:
sqrt(1) == -1 mod p N(1) == N(-1) == 1 mod p
sqrt(-1) == (+/-)i mod p N(i) == 1 mod p
then as q is odd
sqrt(i) == (2^((q-1)/2) + 2^((q-1)/2)*i) mod p
N(2^((q-1)/2) + 2^((q-1)/2)*i) == 1 mod p

for the next square root lets write
(r + m*i)^2 == (2^((q-1)/2) + 2^((q-1)/2)*i) with r and m in Z
we have:
r^2 - m^2 == 2^((q-1)/2) mod p (eq1)
2*r*m == 2^((q-1)/2) mod p (eq2)
N(r+m*i) = r^2 + m^2 == 1 mod p (eq3)

eq1 + eq3: 2(r^2) == 2^((q-1)/2) + 1 mod p

r^2 == (2^(q-1))*(2^((q-1)/2) + 1) mod p
r^2 == 2^(q-1) + 2^((q-3)/2) mod p
factoring 2^((q-3)/2) one get:
r^2 == (2^((q-3)/2))*(2^((q+1)/2) + 1)

lets set t = 2^((q-3)/2)
r^2 == t*a and by Creutzburg and Tasche t*a is a quadratic residue modulo p and r exist.
(t*a|p) = 1 <=> (t|p)*(a|p) = 1

By Euler criterion: (t|p) == t^((p-1)/2) == t^(2^(q-1)-1) mod p
(t|p) == 2^(((q-3)/2)*(2^(q-1)-1)) mod p

reducing the exponent mod q:
((q-3)/2)*(2^(q-1)-1) == ((q-3)/2)*((2^q)/2 - 1) mod q
2^q = 2 mod q (q is a rational prime for p to be prime)
((q-3)/2)*(2^(q-1)-1) == ((q-3)/2)*(2/2 - 1) == 0 mod q

Therefore (t|p) == 2^0 == 1 mod p

Again by Euler criterion:
(a|p) == a^(2^(q-1)-1) mod p
(t|p) == 1 mod p => a^(2^(q-1)-1) == 1 mod p iff p is prime
By Wilson: (p-1)! == -1 mod p iff p prime and (p-1)! == -1*(a|p)*(a^((p-1)/2))

(a^(2^(q-1)))*(a^-1) == 1 mod p

a^(2^(q-1)) == a mod p

In summary Creutzburg and Tasche give (a|p) = 1 if p prime
Wilson give (p-1)! == -1 iff p prime
combine with the Euler criteria giving a^((p-1)/2) == 1 mod p
we get

p = 2^q - 1 is a Mersenne Prime
IFF
a = (2^((q+1)/2) + 1), a^(2^(q-1)) == a mod p

Voila,

-ETL.


Below is a Python3 program using gmpy2:
Caveats it is my first non trivial Python program ...
En passant: One can start squaring from
t * a = 2^(q-1) + 2^((q-3)/2)
instead of:
a = 2^((q+1)/2) + 1

if the program is named mptest.py
to start squaring from a, call:
Bash> python3 mptest.py <q> && echo "Prime!" || echo "Not prime"
or
to start squaring from t*a, call:
Bash> python3 mptest.py -<q> && echo "Prime!" || echo "Not prime"
q = 607 is the default value.

import sys
import gmpy2
from gmpy2 import mpz, xmpz

def mptest(a,q,hb,lb):
    msb = xmpz(0)
    a[hb] = 1
    a[lb] = 1
    a[q:2*q] = 0
    n = q - 1 
    while n > 0:
        a[0:2*q] *= a[0:q]
        msb[0:q] = a[q:2*q]
        a[q]=0
        a += msb
        a += a[q]
        a[q:2*q] = 0 
        n -= 1
    return a

if len(sys.argv) > 1: q = int(sys.argv[1])
else: q = 607 

if q < 0:
    q = -q
    hb = q - 1
    lb = (q-3) // 2
else:
    hb = (q+1) // 2
    lb = 0

v = xmpz(0)
x = mptest(v,q,hb,lb) 

if (x[hb]+x[lb]) == 2:
    x[hb] = 0 
    x[lb] = 0
    if x == 0: 
        print ("M",q," is prime")
        sys.exit (0)
sys.exit(1)

[ETLem]

So, is the proof above correct? Is it something already known?
While I studied mathematics at the university way back then I did not study number theory.
I am getting up to speed since last year as I have now plenty of time in my hands.

This test has the same computing complexity as the Lucas Lehmer test
and if it is valid, it gives an other venue for verification.

For further clarification the r and m can be calculated as:
r == ((2^q-1) + 2^((q-3)/2))^(2^(q-2)) mod p as p == 3 mod 4.
m == ((2^q-1) - 2^((q-3)/2))^(2^(q-2)) mod p
let h = 2^(q-1) and t = 2^((q-3)/2)
r == (h + t)^(h/2) mod p
m == (h - t)^(h/2) mod p

equation (2) was not used to calculate r or m.
2*r*m == 2^((q-1)/2) mod p
r*m == 2^(q-1)*2^((q-1)/2) == 2^((q-3)/2) == t mod p
replacing r and m by their values:
((h+t)*(h-t))^(h/2) == (h^2-t^2)^(h/2) == t mod p

(h^2 - t^2) = 2^(2*(q-1)) - 2^(q-3) == 2^(q-2) - 2^(q-3) == 2^(q-3) mod p
then:
r*m == (2^(q-3))^(2^(q-2)) mod p

q being prime we get:
2^(q-2) == 2^q * 2^-2 == 2*2^-2 == 2^-1 mod q

r*m == (2^(q-3))^(1/2) == 2^((q-3)/2) == t mod p.
therefore r and m satisfy equation (2) without the requirement for p to be prime.

However equation (1) and (3):

(h+t)^h - (h-t)^h == 2^(q-1)/2 mod p

(h+t)^h + (h-t)^h == 1 mod p

are only true if p is prime (and the previous post proof correct ;-).

[R. Gerbicz]

Originally Posted by ETLem

I would like to suggest this potential new Mersenne primality test for your review:

Lemma: q a rational prime q > 2
p = 2^q - 1 a mersenne number
let a = (2^((q+1)/2) + 1)
p is prime if and only if a^(2^(q-1)) == a mod p

We use different letters, but never mind.
For q=3 (p=7) your test fails, otherwise it is good up to at least q=1000.
I don't know how it could be good with correct proof after q=3 (not checked the whole writing), as that is "only" a prp test for a given (changing with q) base. Really not a big deal, because we use a fixed base=3, and so far there is no known false hit.

[charybdis]

This may be a valid PRP test (i.e. "p is prime" => "condition holds") for q > 3. But you haven't proved anything in the other direction, namely "condition holds" => "p is prime". Things break down around here:

Originally Posted by ETLem

Again by Euler criterion:
(a|p) == a^(2^(q-1)-1) mod p
(t|p) == 1 mod p => a^(2^(q-1)-1) == 1 mod p iff p is prime
By Wilson: (p-1)! == -1 mod p iff p prime and (p-1)! == -1*(a|p)*(a^((p-1)/2))

We want to go from "a^(2^(q-1)) == a mod p" to "p is prime". But everything that you've done up to this point (e.g. the use of Euler's criterion) is based on the assumption that p is prime, so the "iff" in the third line above should just be an "if".

Wilson's theorem does indeed have an "iff". But "(p-1)! == -1*(a|p)*(a^((p-1)/2)) mod p" is clearly invalid when p isn't prime, as the LHS is just 0. So you haven't actually used the "condition holds" => "p is prime" direction of Wilson.

[ETLem]

Originally Posted by R. Gerbicz

We use different letters, but never mind.
For q=3 (p=7) your test fails, otherwise it is good up to at least q=1000.
I don't know how it could be good with correct proof after q=3 (not checked the whole writing), as that is "only" a prp test for a given (changing with q) base. Really not a big deal, because we use a fixed base=3, and so far there is no known false hit.

My bad, I should have specified q > 3.

q=3 doesn't work because the test value is based on the existence of a primitive 2^(q+1) root of unit of a e in Z[i] and then going backward from unity.

2^(q+1) : 1 --> 2^(q): -1 --> 2^(q-1): i --> 2^(q-2): 2^(q-1)/2 + 2^(q-1)/2*i --> 2^(q-3): r+m*i

and q=3 => e^{2^(q-3)} == 1 ...


I will amend the post based on your comment. Thanks.

[ETLem]

Originally Posted by charybdis

This may be a valid PRP test (i.e. "p is prime" => "condition holds") for q > 3. But you haven't proved anything in the other direction, namely "condition holds" => "p is prime". Things break down around here:



We want to go from "a^(2^(q-1)) == a mod p" to "p is prime". But everything that you've done up to this point (e.g. the use of Euler's criterion) is based on the assumption that p is prime, so the "iff" in the third line above should just be an "if".

Wilson's theorem does indeed have an "iff". But "(p-1)! == -1*(a|p)*(a^((p-1)/2)) mod p" is clearly invalid when p isn't prime, as the LHS is just 0. So you haven't actually used the "condition holds" => "p is prime" direction of Wilson.

OK, I see that the Wilson theorem alone doesn't bring the iff to the proof.

However the premises from the Creutzburg and Tasche theorem guaranty the existence of the root of unity if and only if p prime.

I thought that I had bracketed (a|p) == 1 mod p from both the Euler criterion and the root of unity that force the existence of the square root of r².

I guess I have to go back to the drawing board so to speak ...

Thank you Charybdis for the review.

Until I found a better proof, if any one want to chime in ...

[LaurV]

Originally Posted by ETLem

However the premises from the Creutzburg and Tasche theorem guaranty the existence of the root of unity if and only if p prime.

Nope. They say the root exists for primes. They won't say what happens with composites.

Generally, roots of unity are tricky, i.e. always exist modulo n, but are unique (in pairs) only when n is prime. For example, modulo any prime, you only have two of them, which are 1 and -1, but modulo a composite you will have more. For example, modulo 2047 (which is 2^11-1=23*89) you have 4 roots: beside of 1 and 2046, the 622 and its negative also work: 622^2=1 (mod 2047).

What you want to do is to find a 1-selfridge test for primality. Such tests can't exist, for a simple reason, called Carmichael numbers. A test of the form:

1. Pick a base which is a function of n (the number to be factored), by however complicate or simple method or calculus.
2. If some power of b (mod n or a function of n) is equal to some constant, then n is prime.

This will never work.

Assume you want to prove primality of some n, then you use some "rule" to pick a base b, like "the larger prime smaller than the last 13 bits of n", then compute b^(n-1) (mod n), and if this is 1, then n is prime. Regardless of the rule you use, when you will run into a Carmichael number (i.e. your n is such a number, or it has similar properties), you will get 1 for every base you chose, unless you run into a factor of n as a base. To avoid getting 1 for Carmichael numbers, (i.e. to make your test "work"), it would mean that you have already a "rule" to pick a base which is a factor of n, and in that case, you already have a method to factor n, you won't need a primality proof.

[R. Gerbicz]

Originally Posted by ETLem

Proof:

Creutzburg and Tasche in Mathematic of Computation Vol 52 Num 185 Jan 1989
Proved the following:
if p = 2^q - 1 is a Mersenne prime
it exist e in Z[i] such that e^(2^(q+1)) == 1 mod p
i.e: e is a primitive (2^(q+1))th root of unity modulo p

Here it is that free article: https://www.ams.org/journals/mcom/19...-0946602-9.pdf
You want to use theorem 6, then check it again, what they write, also see the definition of the root, and primitive root. You're very far from a proof, btw theorem 6 is quite trivial in Maths, for the previous corollary 4 you need that 3 is a primitive root mod 2^p-1, what currently gimps is using base=3. (you need that 2^p-1 is a Mersenne prime for corollary 4, so when we see a false hit in Gimps you can't apply that corollary because you can't even apply it for composite 2^p-1 values).

Originally Posted by LaurV

What you want to do is to find a 1-selfridge test for primality. Such tests can't exist, for a simple reason, called Carmichael numbers.
...
This will never work.

I've some doubts. First of all, we are speaking about special numbers, not a test for all integers.
In another ring there is such close type of theorem, that is exactly the Lucas Lehmer, an equivalent version:
(2+sqrt(3))^(2^(p-2))=k*sqrt(3) in Z[n,sqrt(3)] if and only if n=2^p-1 is prime (for odd p prime).

[ETLem]

Originally Posted by LaurV

Nope. They say the root exists for primes. They won't say what happens with composites.

Generally, roots of unity are tricky, i.e. always exist modulo n, but are unique (in pairs) only when n is prime. For example, modulo any prime, you only have two of them, which are 1 and -1, but modulo a composite you will have more. For example, modulo 2047 (which is 2^11-1=23*89) you have 4 roots: beside of 1 and 2046, the 622 and its negative also work: 622^2=1 (mod 2047).

What you want to do is to find a 1-selfridge test for primality. Such tests can't exist, for a simple reason, called Carmichael numbers. A test of the form:

1. Pick a base which is a function of n (the number to be factored), by however complicate or simple method or calculus.
2. If some power of b (mod n or a function of n) is equal to some constant, then n is prime.

This will never work.

Assume you want to prove primality of some n, then you use some "rule" to pick a base b, like "the larger prime smaller than the last 13 bits of n", then compute b^(n-1) (mod n), and if this is 1, then n is prime. Regardless of the rule you use, when you will run into a Carmichael number (i.e. your n is such a number, or it has similar properties), you will get 1 for every base you chose, unless you run into a factor of n as a base. To avoid getting 1 for Carmichael numbers, (i.e. to make your test "work"), it would mean that you have already a "rule" to pick a base which is a factor of n, and in that case, you already have a method to factor n, you won't need a primality proof.

I got that, but this particular test target Mersenne numbers and Mersenne primes, which give us additional information about the number under test, after all as pointed out by R. Gerbicz, we already have the Lucas Lehmer test.

By the way is there known Carmichael number(s) that are also Mersenne number(s)? Or could it be proven that it exist Mersenne numbers that are also Carmichael numbers?

[ETLem]

To recap the discussion so far:
I have only proved that

if p=2^q - 1 is prime, q > 3
then for a = 2^(q+1)/2 + 1
a^{2^(q-1)} == a mod p

Is it reasonable to make the following conjecture:

for q > 3 a prime, p = 2^q - 1 and a = 2^(q+1)/2 + 1
if a^{2^(q-1)} == a mod p then p is prime

?

As an aside the thread title was changed to "unproven ... conjecture".
That seems a tad redoundant ;-)
How about "A new conjecture about Mersenne Primes".

Thank you all for indulging my sudden venture into the Mersenne numbers world.

[Batalov]

Originally Posted by ETLem

Is it reasonable to make the following conjecture:

for q > 3 a prime, p = 2^q - 1 and a = 2^(q+1)/2 + 1
if a^{2^(q-1)} == a mod p then p is prime

?

Unreasonable.
Because it is 100-200 years too late (as a string of letters).
If there is not even shard of a proof or even a sketch, then what does it add?
If there is, we are eager to hear it.

Originally Posted by ETLem

Thank you all for indulging my sudden venture into the Mersenne numbers world.

Well, for sure, it will cause much less harm compared to walking into a brain surgery O.R. with a stunning announcement: "Step back, I have a sudden urge to try something - I have a totally novel idea! I've never done it, but I am sure I can do it."