mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-03-07, 13:48   #1
juergen
 
Mar 2004

29 Posts
Question 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
juergen is offline   Reply With Quote
Old 2004-03-08, 14:22   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Talking

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:

<snip>
You have Mersenne primes confused with Fermat primes.
R.D. Silverman is offline   Reply With Quote
Old 2004-03-08, 19:12   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

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
philmoore is offline   Reply With Quote
Old 2005-03-07, 04:07   #4
abiessu
 
Mar 2005

23 Posts
Smile 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
abiessu is offline   Reply With Quote
Old 2005-03-07, 21:01   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

9,791 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-03-08, 03:12   #6
abiessu
 
Mar 2005

10002 Posts
Default 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.
abiessu is offline   Reply With Quote
Old 2005-03-08, 13:26   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-03-08, 18:00   #8
dave_dm
 
May 2004

24×5 Posts
Default

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
dave_dm is offline   Reply With Quote
Old 2005-03-08, 20:41   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

9,791 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-03-09, 04:06   #10
abiessu
 
Mar 2005

23 Posts
Default "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.
abiessu is offline   Reply With Quote
Old 2005-03-09, 04:35   #11
abiessu
 
Mar 2005

23 Posts
Default (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.
abiessu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primitive Root of Mersenne Numbers PawnProver44 Miscellaneous Math 7 2016-04-18 23:49
Primitive roots for a set of primes mart_r Math 0 2013-07-20 12:23
Finding the square root of a large mersenne number Fusion_power Math 29 2010-10-14 17:05
Primitive root question __HRB__ Math 0 2009-07-10 00:41
Is 3 always a primitive root for mersenne primes? juergen Programming 9 2005-03-08 03:51

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

Sat Oct 24 18:53:16 UTC 2020 up 44 days, 16:04, 0 users, load averages: 2.13, 1.99, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.