mersenneforum.org > Math (unproven) Potential new primality conjecture for Mersenne numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-15, 20:47 #1 ETLem   Nov 2021 2·3 Posts (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 && echo "Prime!" || echo "Not prime" or to start squaring from t*a, call: Bash> python3 mptest.py - && 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)
 2021-11-22, 20:19 #2 ETLem   Nov 2021 1102 Posts 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 ;-).
2021-11-22, 20:42   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

Quote:
 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.

2021-11-22, 21:15   #4
charybdis

Apr 2020

3·199 Posts

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

2021-11-22, 21:15   #5
ETLem

Nov 2021

2·3 Posts
Correction needed ...

Quote:
 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 => e2^(q-3) == 1 ...

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

2021-11-23, 08:38   #6
ETLem

Nov 2021

1102 Posts

Quote:
 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 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 ...

2021-11-23, 10:16   #7
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

232268 Posts

Quote:
 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.

Last fiddled with by LaurV on 2021-11-23 at 10:24

2021-11-23, 15:03   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts

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

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

Last fiddled with by R. Gerbicz on 2021-11-23 at 15:09

2021-11-29, 21:04   #9
ETLem

Nov 2021

2×3 Posts

Quote:
 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?

 2021-11-29, 21:15 #10 ETLem   Nov 2021 610 Posts 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.
2021-11-29, 21:38   #11
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25·3·101 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 FermatSearch 37 2018-07-22 22:09 Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 T.Rex Math 12 2016-04-03 22:27 primus Miscellaneous Math 1 2014-10-12 09:25 sascha77 Math 2 2010-01-07 08:06

All times are UTC. The time now is 08:40.

Fri Jan 28 08:40:22 UTC 2022 up 189 days, 3:09, 2 users, load averages: 1.16, 1.30, 1.32