Primitive Root Question
KSchmidt10
>there a method (short of solving for all the powers of x) to determine
>whether x is a primitive root mod p? In other words, is there a formula for
>determining the order of x mod p? Many thanks for any assistance. --
The order of every non-identity x will be p, if p is prime (and the order of
the identity, will, of course, be 1).
For more explanation, see an elementary text on group theory--arithmetic modulo
any number p forms a group. The theory says, every x will have order dividing
the modulus (and hence the result that if the modulus is prime, all elts
without order 1 have order p).
tul...@my-dejanews.com
there a method (short of solving for all the powers of x) to determine
whether x is a primitive root mod p? In other words, is there a formula for
determining the order of x mod p? Many thanks for any assistance. --
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Gerry Myerson
kschm...@aol.com (KSchmidt10) wrote:
> >Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> >there a method (short of solving for all the powers of x) to determine
> >whether x is a primitive root mod p? In other words, is there a formula for
> >determining the order of x mod p? Many thanks for any assistance. --
>
> The order of every non-identity x will be p, if p is prime
That's if the group is the additive group mod p, but it's clear that the
question concerned the multiplicative group.
The order of x will be a divisor of p - 1 so instead of computing all the
powers of x you can get a way with computing just x^d for all divisors d
of p - 1. E.g., when p = 71, you just need to compute x^d for d = 1, 2, 5,
7, 10, 14, and 35; if none of these is 1, x is a primitive root.
In fact, you can get away with just testing those d that are of the form
(p - 1)/q, where q is prime. For p = 71, that's d = 10, 14, and 35.
Exercise: prove these assertions.
All of this assumes that you can factor p - 1 (and that you know the
efficient methods for computing x^d (mod p)).
Gerry Myerson (ge...@mpce.mq.edu.au)
JarWeinst
>>there a method (short of solving for all the powers of x) to determine
>>whether x is a primitive root mod p? In other words, is there a formula for
>>determining the order of x mod p? Many thanks for any assistance. --
>
>the identity, will, of course, be 1).
>For more explanation, see an elementary text on group theory--arithmetic
>modulo
>any number p forms a group. The theory says, every x will have order
>dividing
>the modulus (and hence the result that if the modulus is prime, all elts
>without order 1 have order p).
>
>
The question, I presume, was about determining the multiplicative order of x,
not the additive order. In this case all the possible orders divide p-1,
making it a bit harder.
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::::::::::::::::::::::::::
Jared Weinstein
jarw...@aol.com
Harvard Class of 2002
"I am a
fish."::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::::::::::
Robin Chapman
tul...@my-dejanews.com wrote:
> Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> there a method (short of solving for all the powers of x) to determine
> whether x is a primitive root mod p? In other words, is there a formula for
> determining the order of x mod p? Many thanks for any assistance. --
x is a primitive root modulo p if the least positive n with x^n = 1 (mod p)
is n = p-1. In all cases this n is a factor of p-1. If it's not equal
to p-1 then it divides (p - 1)/q for some prime factor q of p-1. Thus
x is a primitive toot of p iff x^[(p-1)/q] is not congruent to 1 mod p,
for each prime factor q of p-1.
For instance when p = 71, p-1 = 70 = 2.5.7 and so x is a primitive root
modulo p iff none of x^35, x^14 and x^10 are = 1 (mod p).
Robin Chapman + "They did not have proper
SCHOOL OF MATHEMATICal Sciences - palms at home in Exeter."
University of Exeter, EX4 4QE, UK +
r...@maths.exeter.ac.uk - Peter Carey,
http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda, chapter 20
spam...@nil.nil
> >Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> >there a method (short of solving for all the powers of x) to determine
> >whether x is a primitive root mod p? In other words, is there a formula for
> >determining the order of x mod p? Many thanks for any assistance. --
> The order of every non-identity x will be p, if p is prime (and the order of
> the identity, will, of course, be 1).
> For more explanation, see an elementary text on group theory--arithmetic modulo
> any number p forms a group. The theory says, every x will have order dividing
> the modulus (and hence the result that if the modulus is prime, all elts
> without order 1 have order p).
But the order of the muliplicative group of Z_p is p-1.
(if you have all the prime factors of p-1, calculate:
x^{(p-1)/P} mod p for each prime factor P of p-1
If x is NOT a primitive root mod p, then x^j mod p must be 1 for some
j<p-1 where j divides p-1, so one of the values (p-1)/P will be a multiple
of j and one of the terms x^{(p-1)/P} mod p will be 1.
If and only if none of those are 1 mod p, x is a primitive root.
Of course, this does not give the order of x if x is not a primitive root,
just a multiple of its order)
bensc...@my-dejanews.com
tul...@my-dejanews.com wrote:
> Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> there a method (short of solving for all the powers of x) to determine
> whether x is a primitive root mod p? In other words, is there a formula
> for determining the order of x mod p? Many thanks for any assistance.
>
This is the well known "primitive root" problem, unsolved AFAIK.
The structure of Z(.) mod p is a p-1 cyclic group G, adjoined to '0' ,
essentially Fermat's Small Theorem (FST): n^p = n mod p (prime p, all n).
Short of checking x^d = 1 mod p, for proper divisors d= (p-1)/q [prime q],
(if true for some d then x is not primitive: it generates a subgroup x*
of units group G, with |x*| dividing p-1) there is no shorter way to tell
the primitivity of x.
Ciao, Nico Benschop. -- http://www.iae.nl/users/benschop
bensc...@my-dejanews.com
bensc...@my-dejanews.com wrote:
> In article <71trtj$4h4$1...@nnrp1.dejanews.com>,
> tul...@my-dejanews.com wrote:
> > Given a prime modulus p (e.g.,71) and a number x less than p (e.g.,7), is
> > there a method (short of solving for all the powers of x) to determine
> > whether x is a primitive root mod p? In other words, is there a formula
> > for determining the order of x mod p? Many thanks for any assistance.
> > -- M.Tullius
> >
>
> This is the well known "primitive root" problem, unsolved AFAIK
>
> essentially Fermat's Small Theorem (FST): n^p = n mod p (prime p, all n).
>
> Short of checking x^d = 1 mod p, for proper divisors d= (p-1)/q [prime q],
> (if true for some d then x is not primitive: it generates a subgroup x*
> of units group G, with |x*| dividing p-1) there is no shorter way to tell
> the primitivity of x.
>
> Ciao, Nico Benschop. -- http://www.iae.nl/users/benschop
>
Nota bene: the group of units G_k mod p^k (k>1) is _also_ cyclic,
and is of order (p-1)p^{k-1} --> hence is a product G_k = A_k.B_k.
with "core" subgroup |A_k|=p-1 (re: FST), and |B_k|= p^{k-1} = (p+1)*
A generator of G_2 will generate (if padded by msd zero's) also G_k
for every k>2. This is not always true for x* = G_1, where x may not
generate G_2.
Prime p=2 is the only prime for which G_k (k>1) is NOT cyclic,
but in fact a direct product: G_k = C2 x Cm, where m= 2^{k-2}
with 2-cycle C2={-1,1}
and Cm={3*}: so 3 is a semi-primitive root of 1 mod 2^k (k>2).
see http://www.iae.nl/users/benschop/nfb0.dvi (lem1.1)
"Triplets and symmetries of Arithmetic mod p^k"
(incl. proof of FLTcase1 via FST_extension)
So strangely: the only interesting prime, from a practical point
of view (computer hardware: binary code mod 2^k) is also the only
one for which the primitive root problem is solved (and simple;-)
Ciao, Nico benschop -- http://www.iae.nl/users/benschop