Primitive root modulo n
From Free net encyclopedia
A primitive root modulo n is a concept from modular arithmetic in number theory.
If n≥1 is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)× or Zn*. This group is cyclic if and only if n is equal to 1 or 2 or 4 or pk or 2 pk for a prime number p ≥ 3 and k ≥ 1. A generator of this cyclic group is called a primitive root modulo n, or a primitive element of Zn*.
A primitive root modulo n, in other words, is an integer g such that, modulo n, every integer not having a common factor with n is congruent to a power of g.
Take for example n = 14. The elements of
- (Z/14Z)×
are the congruence classes of
- 1, 3, 5, 9, 11 and 13.
Then 3 is a primitive root modulo 14, as we have 32 = 9, 33 = 13, 34 = 11, 35 = 5 and 36 = 1 (modulo 14). The only other primitive root modulo 14 is 5.
Here is a table containing the smallest primitive root for various values of n Template:OEIS:
| n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| primitive root mod n | 1 | 2 | 3 | 2 | 5 | 3 | - | 2 | 3 | 2 | - | 2 | 3 |
No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order of a number m modulo n is equal to φ(n) (the order of (Z/nZ)×), then it is a primitive root. We can use this to test for primitive roots:
- first compute φ(n). Then determine the different prime factors of φ(n), say p1,...,pk. Now, for every element m of (Z/nZ)×, compute
- <math>m^{\phi(n)/p_i}\mod n \qquad\mbox{ for } i=1,\ldots,k</math>
using the fast exponentiating by squaring. As soon as you find a number m for which these k results are all different from 1, you stop: m is a primitive root.
The number of primitive roots modulo n, if there are any, is equal to
- φ(φ(n))
since, in general, a cyclic group with r elements has φ(r) generators.
Sometimes one is interested in small primitive roots. We have the following results. For every ε>0 there exist positive constants C and p0 such that, for every prime p ≥ p0, there exists a primitive root modulo p that is less than
- C p1/4+ε.
If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p that is less than
- 70 (ln(p))2.
Uses
Primitive root modulo n is often used in cryptography, including the Diffie-Hellman Key Exchange Scheme.
See also
fr:Racine primitive modulo n it:Generatore (teoria dei numeri) hu:Primitív gyök zh:原根