mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-11-15, 20:47   #1
ETLem
 
Nov 2021

2×3 Posts
Default (unproven) Potential new primality conjecture for Mersenne numbers

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.


Code:
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 is offline   Reply With Quote
Old 2021-11-22, 20:19   #2
ETLem
 
Nov 2021

616 Posts
Question Follow up

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 ;-).
ETLem is offline   Reply With Quote
Old 2021-11-22, 20:42   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

Quote:
Originally Posted by ETLem View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-11-22, 21:15   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

5×109 Posts
Default

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:

Quote:
Originally Posted by ETLem View Post
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.
charybdis is offline   Reply With Quote
Old 2021-11-22, 21:15   #5
ETLem
 
Nov 2021

616 Posts
Default Correction needed ...

Quote:
Originally Posted by R. Gerbicz View Post
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 => e2^(q-3) == 1 ...


I will amend the post based on your comment. Thanks.
ETLem is offline   Reply With Quote
Old 2021-11-23, 08:38   #6
ETLem
 
Nov 2021

68 Posts
Talking Downgraded from lemma to conjecture

Quote:
Originally Posted by charybdis View Post
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 r2.

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 ...
ETLem is offline   Reply With Quote
Old 2021-11-23, 10:16   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

Quote:
Originally Posted by ETLem View Post
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.

Last fiddled with by LaurV on 2021-11-23 at 10:24
LaurV is offline   Reply With Quote
Old 2021-11-23, 15:03   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·11·23 Posts
Default

Quote:
Originally Posted by ETLem View Post
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).

Quote:
Originally Posted by LaurV View Post
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).

Last fiddled with by R. Gerbicz on 2021-11-23 at 15:09
R. Gerbicz is offline   Reply With Quote
Old 2021-11-29, 21:04   #9
ETLem
 
Nov 2021

2·3 Posts
Question

Quote:
Originally Posted by LaurV View Post
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 is offline   Reply With Quote
Old 2021-11-29, 21:15   #10
ETLem
 
Nov 2021

616 Posts
Default Recap

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

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

Is it reasonable to make the following conjecture:

for q > 3 a prime, p = 2q - 1 and a = 2(q+1)/2 + 1
if a2^(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.
ETLem is offline   Reply With Quote
Old 2021-11-29, 21:38   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×11×19×23 Posts
Default

Quote:
Originally Posted by ETLem View Post
Is it reasonable to make the following conjecture:

for q > 3 a prime, p = 2q - 1 and a = 2(q+1)/2 + 1
if a2^(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.

Quote:
Originally Posted by ETLem View Post
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."
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Potential primality of F33, F34, and F35 siegert81 FermatSearch 37 2018-07-22 22:09
14° Primality test and factorization of Lepore ( conjecture ) Alberico Lepore Alberico Lepore 48 2017-12-30 09:43
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
conjecture about mersenne numbers sascha77 Math 2 2010-01-07 08:06

All times are UTC. The time now is 07:18.


Tue Nov 30 07:18:17 UTC 2021 up 130 days, 1:47, 0 users, load averages: 0.63, 0.94, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.