A primitive root modulo n is a concept from modular arithmetic in number theory. Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

If n≥1 is an integer, the numbers coprime to n form a group with multiplication modulo n as the operation; it is written as (Z/nZ)^× or Z_n^*. This group is cyclic if and only if n is equal to 1, 2, 4, p^k, or 2 p^k 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 Z_n^*. The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Coprime - Wikipedia /**/ @import /skins-1. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... In abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses. ...

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 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 and 3⁶ = 1 (mod 14). The only other primitive root modulo 14 is 5.

Here is a table containing the smallest primitive root for various values of n (sequence A046145 in OEIS): The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

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. In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with ak ≡ 1 (modulo n). ... In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. ...

First, compute φ(n). Then determine the different prime factors of φ(n), say p₁,...,p_k. Now, for every element m of (Z/nZ)^×, compute

using the fast exponentiation by squaring. A number m for which these k results are all different from 1 is a primitive root. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

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 p₀ such that, for every prime p ≥ p₀, there exists a primitive root modulo p that is less than

C p^1/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))².

In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... The Riemann hypothesis is one of the most important conjectures in mathematics. ... The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e, where e is equal to 2. ...

Uses

Primitive root modulo n is often used in cryptography, including the Diffie-Hellman Key Exchange Scheme. The German Lorenz cipher machine, used in World War II for encryption of high-level messages. ... Diffie-Hellman (D-H) key exchange is a cryptographic protocol which allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. ...

See also

• Dirichlet character
• Artin's conjecture on primitive roots