 mersenneforum.org > Math Is 3 always a primitive root for mersenne primes?
 Register FAQ Search Today's Posts Mark Forums Read  2004-03-07, 13:48 #1 juergen   Mar 2004 111012 Posts Is 3 always a primitive root for mersenne primes? Hello, the subject sais it all. Is 3 always a primitive root for primes of the form 2^x-1 for x>2? In other words: If 2^x-1 is prime is then Ord 3 (mod 2^x-1) always 2^x-2 = 2(2^(x-1)-1)? Sorry, I already posted it, but by accident in the programming forum and I think this is a better place for this question :o) I guess if my suspicion is right I guess this has already been proofed. Thank you in advance Juergen   2004-03-08, 14:22   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts Quote:
 Originally Posted by juergen Hello, the subject sais it all. Is 3 always a primitive root for primes of the form 2^x-1 for x>2? In other words:
You have Mersenne primes confused with Fermat primes.   2004-03-08, 19:12 #3 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 112010 Posts I don't think juergen has them confused, as he stated in the programming thread that he had tested all exponents up to 127. However, I just checked that Ord 3 (2^13 - 1) = 910, not 8190 according to his conjecture. So he may have overlooked something in doing his computations. Last fiddled with by philmoore on 2004-03-08 at 19:13   2005-03-07, 04:07 #4 abiessu   Mar 2005 23 Posts yes 3^(2^(p-1)) = -3 (mod 2^p-1) if 2^p-1 is prime. This translates to 3^(2^p-2) = 1 (mod 2^p-1); square and multiply by 3^-2. This congruence is necessary for 2^p-1 to be prime, but I don't know yet whether it is sufficient. Last fiddled with by abiessu on 2005-03-07 at 04:10   2005-03-07, 21:01   #5
ewmayer
2ω=0

Sep 2002
República de California

267538 Posts Quote:
 3^(2^(p-1)) = -3 (mod 2^p-1)
This is just an Euler pseudoprime test (EPT) in a very slight disguise. Divide both sides by 3 to get

3^(2^(p-1) - 1) = -1 (mod 2^p-1)

The exponent of 3 on the left-hand side is just (2^p-1)/2, i.e. what one would expect in an EPT of 2^p-1. More generally, Euler's criterion says for q an odd prime and a positive integer A which is not a multiple of q,

A^((q-1)/2) == (A|q) mod q

where (A|q) is the Legendre symbol, i.e. the right-hand-side = +1 or -1, depending on whether A is a quadratic residue mod q or not, respectively. In the problem at hand we need to see whether or not 3 is a QR modulo 2^p-1. It is well-known that for 3 to be a QR modulo q, the modulus in question must have the form q = 12*k +- 1 for some integer k, i.e. q == +-1 modulo 12.

Now it's simple to show that moduli q = 2^p-1 cannot have this form for *any* positive exponent p > 1, whether it be odd or even, prime or nonprime. For p=2, 2^p = 4, i.e. 2^p-1 == 3 modulo 12. Going back to 2^p, multiplying this by 4 gives 16, which is again == 4 modulo 12, and thus it's clear that for any even power, 2^p-1 == 3 modulo 12. We proceed analogously for odd p's starting with p=3, and quickly establish that for any odd exponent p, 2^p-1 == 7 mod 12, so 3 is not a QR modulo 2^p-1, which is why an EPT of a Mersenne prime always yields -1. (And why your version of the test always yields -3).

Except for numbers of special form (e.g. Fermats), the EPT is necessary but not sufficient to establish primality. Thus you would expect the result to apply for all known Mersenne primes, but cannot rule out the possibility that there are some primes p for which the congruence holds but for which 2^p-1 is nevertheless composite.   2005-03-08, 03:12 #6 abiessu   Mar 2005 23 Posts necessary but not sufficient? Hmm... please explain why it is not sufficient. I understand that (given a single a) a^p = a mod p is necessary but not sufficient... There's two special considerations I'm giving this congruence: 1) The power series used to establish the congruence could be p-1 steps (square, mod by M_p), or it could be (p-1)/2 steps (square twice, mod by M_p). Any chance that the latter is 'twice as fast', computationally (or even theoretically)? 2) 3 is the only prime known (so far) to have the property that it is a quadratic non-residue mod M_p for any prime M_p > 3. Even better, if 3 is a quadratic residue mod M_p, then M_p is not prime.   2005-03-08, 13:26   #7
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts Quote:
 Originally Posted by abiessu Hmm... please explain why it is not sufficient. I understand that (given a single a) a^p = a mod p is necessary but not sufficient... There's two special considerations I'm giving this congruence: 1) The power series used to establish the congruence could be p-1 steps (square, mod by M_p), or it could be (p-1)/2 steps (square twice, mod by M_p). Any chance that the latter is 'twice as fast', computationally (or even theoretically)? 2) 3 is the only prime known (so far) to have the property that it is a quadratic non-residue mod M_p for any prime M_p > 3. Even better, if 3 is a quadratic residue mod M_p, then M_p is not prime.

It is not sufficient because there exists composite values of 2^p-1 that
satisfy the congruence. Why is this difficult?

There is not only ZERO chance that it would be faster than the L-L test,
it would actually be slower. (Hint: look at the binary representation of
2^n-1; each iteration would be more than a simple squaring)

It is probably true that 3 is the only known QNR for all Mersenne primes.   2005-03-08, 18:00   #8
dave_dm

May 2004

24·5 Posts Quote:
 Originally Posted by R.D. Silverman It is probably true that 3 is the only known QNR for all Mersenne primes.
And -1 Not that this could ever be a primitive root though.

Dave   2005-03-08, 20:41   #9
ewmayer
2ω=0

Sep 2002
República de California

5·2,351 Posts I'll only comment on the number-of-iterations point - abiessu, I urge you to invest in a decent introductory text on number theory, preferably one that also discusses computational aspects (either Riesel or Crandall/Pomerance would be a good choice, IMO) if you want to understand things like the properties of the common compositeness tests, false primes, etc.

Quote:
 Originally Posted by abiessu 1) The power series used to establish the congruence could be p-1 steps (square, mod by M_p), or it could be (p-1)/2 steps (square twice, mod by M_p). Any chance that the latter is 'twice as fast', computationally (or even theoretically)?
Bob's point here was that since the power one raises the initial seed to in the Euler test consists entirely of binary ones in the Mersenne case ((2^p-1)-1)/2 = 2^(p-1)-1, a string of (p-1) binary ones) as opposed to a single leading binary one and the rest all zeros in the Fermat case, doing the modular powering is more expensive for Mersenne-mod since we'll need modular multiplies x*y mod q rather than simpler modular squarings x^2 mod q. However, as long as the initial seed A is small (e.g. of order unity), this is no big deal - we do a left-to-right-binary powering (if you're not familiar with that, there are plenty of paper and online references - go look it up yourself), which means each of the (p-1)-1 = (p-2) iterations (the additional minus one is because we don't need a modsquare for the MSB in the LR powering) for the Mersenne case needs a modsquare and a scalar multiply by the seed A - the latter can easily be interleaved in the carry step of each iteration, i.e. it's basically free. So on a per-iteration basis an LL iteration, a Fermat-mod Euler-test squaring, and a Mersenne-mod Euler-test multiply are all roughly equivalent in terms of cost (and I'm not just speaking abstractly here - I've coded them all and know whereof I speak on this particular issue).

However, even assuming you can do each iteration as fast as one of the LL test, this saves you nothing in terms of number of modular squarings needing to be done. To test q = 2^p - 1 for primality, the LL test needs (p-2) squarings modulo q; we've just established that the Euler test needs the same number. Note that the factor of two in the modular powering you seem so fascinated with amounts to just a *single* iteration, i.e. to evaluate 3^((2^p-2)/2) mod q (Euler compositeness test) needs (p-2) modsquares, whereas 3^(2^p-2) mod q (Fermat compositeness test) needs (p-1) modsquares, but of course that difference is completely negligible in terms of runtime for p large.

In other words, cutting the exponent of the modular powering in half saves just *one* iteration, not half of them, as you hoped.   2005-03-09, 04:06   #10
abiessu

Mar 2005

23 Posts "there exist..."

My apologies for making wild conjectures... I'll look into a number theory book or two.
Quote:
 Originally Posted by R.D. Silverman It is not sufficient because there exists composite values of 2^p-1 that satisfy the congruence. Why is this difficult?
Only difficult because I haven't seen any yet... but let me make sure we're talking about the same congruence:

3^(2^(p-1)) = -3 (mod 2^p - 1) where p is prime and 2^p - 1 is not prime. (Or written as an Euler pseudoprime test as desired.)

Again, I haven't seen such a p yet, and others have mentioned that none exist up to p = 132049 (the limit checked at that time).

Otherwise, I'm done. My apologies for not studying more carefully beforehand.    2005-03-09, 04:35   #11
abiessu

Mar 2005

23 Posts (edit limit exceeded...)

Sorry... one thing I missed...
Quote:
 Except for numbers of special form (e.g. Fermats), the EPT is necessary but not sufficient to establish primality. Thus you would expect the result to apply for all known Mersenne primes, but cannot rule out the possibility that there are some primes p for which the congruence holds but for which 2^p-1 is nevertheless composite.
I'm thinking of '...cannot rule out the possibility...'. There is a way I can rule it out: with a proof of sufficiency (given no known counterexamples). Also, yes, a Fermat number is in a special form. So is a Mersenne number. "Special enough" is still in the "to be determined" category from what I can see.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Miscellaneous Math 7 2016-04-18 23:49 mart_r Math 0 2013-07-20 12:23 Fusion_power Math 29 2010-10-14 17:05 __HRB__ Math 0 2009-07-10 00:41 juergen Programming 9 2005-03-08 03:51

All times are UTC. The time now is 03:28.

Mon Feb 6 03:28:16 UTC 2023 up 172 days, 56 mins, 1 user, load averages: 1.01, 0.93, 0.93