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

 2021-11-15, 20:47 #1 ETLem   Nov 2021 416 Posts Potential new primality test 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 22 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

37·41 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

53910 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

416 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

22 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

2×4,903 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

37×41 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

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 siegert81 FermatSearch 37 2018-07-22 22:09 primus Miscellaneous Math 1 2014-10-12 09:25 Prime95 Miscellaneous Math 19 2014-08-23 04:18 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 06:13.

Sat Nov 27 06:13:09 UTC 2021 up 127 days, 42 mins, 0 users, load averages: 1.42, 1.16, 1.11