Primitive root

As primitive roots are in number theory one branch of mathematics , certain elements of the reduced residue class groups designated. The defining property of a primitive root is that each element of the prime residue class group can be represented as a power of the primitive root.

example

The number 3 is a primitive root modulo 7, there applies

${\displaystyle 3^{1}\equiv 3\ {\pmod {7}}}$

${\displaystyle 3^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 3^{3}\equiv 6\ {\pmod {7}}}$

${\displaystyle 3^{4}\equiv 4\ {\pmod {7}}}$

${\displaystyle 3^{5}\equiv 5\ {\pmod {7}}}$

${\displaystyle 3^{6}\equiv 1\ {\pmod {7}}}$

All elements of the prime remainder class group can be represented modulo 7 as powers of 3, the exponent being the index assigned to the respective element ( discrete logarithm ). The number 2 is not a primitive root modulo 7, there is, so the remainders are repeated in the sequence of powers of 2 modulo 7 ${\displaystyle 1,2,\ldots ,6}$ ${\displaystyle 3^{i}}$ ${\displaystyle i}$ ${\displaystyle 2^{3}=8\equiv 1\ {\pmod {7}}}$

${\displaystyle (2^{k})_{k\in \mathbb {N} }=(2^{1},2^{2},2^{3}\equiv 1,2^{4}\equiv 2\,\ldots )}$

after 3 steps each, therefore not all 6 different prime residues modulo 7 are reached and 2 does not generate the prime residue class group .

Definition and conditions of existence

An integer is a primitive root modulo if the residue class generates the prime residue class group . This means that an integer is a primitive root modulo if and only if the order of modulo is equal to the group order of the prime residue class group: ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle a+m\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle m}$

${\displaystyle \operatorname {ord} _{m}(a)=\varphi (m)}$.

Here, the Euler's φ function and the multiplicative order modulo m of the member , d. H. the smallest positive exponent for which is (for the notation “mod” see modulo ). ${\displaystyle \varphi }$ ${\displaystyle \operatorname {ord} _{m}(a)}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a^{n}\equiv 1\;({\bmod {\;}}m)}$

By the way, exactly then is also

${\displaystyle \operatorname {ord} _{m}(a)=\lambda (m)}$,

where is the Carmichael function . ${\displaystyle \lambda }$

There are primitive roots modulo if and only if the prime residue class group is a cyclic group . According to CF Gauss's theorem, this is the case if and only for the module ${\displaystyle m}$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$

${\displaystyle m\in \{2,4,p^{\alpha },2p^{\alpha }\;\;|\;\;2<p\in \mathbb {P} ;\;\alpha \in \mathbb {N} \}}$

applies. It denotes the set of prime numbers. ${\displaystyle \mathbb {P} }$

If there are modulo primitive roots , then there are exactly modulo incongruent primitive roots . Each of these primitive roots is modulo congruent to an element of the set: ${\displaystyle m}$ ${\displaystyle \varphi (\varphi (m))}$ ${\displaystyle m}$ ${\displaystyle m}$

${\displaystyle \{a^{n}\mid 1\leq n\leq \varphi (m),\ \operatorname {ggT} (n,\varphi (m))=1\}}$

where any primitive root is modulo . ${\displaystyle a}$ ${\displaystyle m}$

Calculation of primitive roots

Trying out (brute force)

To determine whether a number is primitive root modulo , first and then the order of is calculated. The order can be determined, for example, by successively calculating the values for . The first thing to be true is the order of . ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle \varphi (m)}$ ${\displaystyle a}$ ${\displaystyle a^{t}{\bmod {m}}}$ ${\displaystyle t\in \{1,2,\ldots ,m-1\}}$ ${\displaystyle t}$ ${\displaystyle a^{t}{\bmod {m}}=1}$ ${\displaystyle a}$

In the example from the introduction you can see that the 3 has the order 6. Since, in addition , 3 is a primitive root modulo 7. ${\displaystyle \varphi (7)=6}$

A number that is not a primitive root modulo 7 is 4. Here applies

${\displaystyle 4^{1}\equiv 4\ {\pmod {7}}}$

${\displaystyle 4^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 4^{3}\equiv 1\ {\pmod {7}}}$

The order of 4 is therefore 3 and 4 is not a primitive root modulo 7.

One can save many trials by using the fact that the order divides according to Lagrange's theorem , since every number for which holds is divisible by the order. Therefore, one only has to check for all factors of whether exponentiation with them maps the number to 1, and the smallest such factor is the order. ${\displaystyle \varphi (m)}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle a^{k}\equiv 1{\bmod {m}}}$ ${\displaystyle \varphi (m)}$

Primitive roots modulo prime numbers

The prime residue class groups for modules that are prime numbers consist of exactly elements. The numbers are the representatives of the different remainder classes. If a primitive root is modulo , the expression assumes for all values (in apparently random order). ${\displaystyle m}$ ${\displaystyle m-1}$ ${\displaystyle 1,2,\ldots ,m-1}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle a^{t}{\bmod {m}}}$ ${\displaystyle t\in \{0,1,2,\ldots ,m-2\}}$ ${\displaystyle \{1,\ldots ,m-1\}}$

Examples

The following table shows the primitive roots modulo of the prime numbers up to 29.

${\displaystyle m}$	${\displaystyle \varphi (\varphi (m))}$	Primitive roots modulo ${\displaystyle m}$
2	1	1
3	1	2
5	2	2, 3
7th	2	3, 5
11	4th	2, 6, 7, 8
13	4th	2, 6, 7, 11
17th	8th	3, 5, 6, 7, 10, 11, 12, 14
19th	6th	2, 3, 10, 13, 14, 15
23	10	5, 7, 10, 11, 14, 15, 17, 19, 20, 21
29	12	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27

Primitive roots modulo prime powers

If an odd prime number, then a primitive root is modulo with also primitive root modulo smaller powers of . What is interesting for the search for primitive roots modulo higher powers of is that a primitive root is modulo (with ) also a primitive root to all higher powers of . Therefore, for higher powers of the prime number , it is sufficient ${\displaystyle p}$ ${\displaystyle p^{\alpha }}$ ${\displaystyle \alpha >1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \gamma }$ ${\displaystyle p^{2}}$ ${\displaystyle 2\leq \gamma \leq p^{2}-1}$ ${\displaystyle p}$ ${\displaystyle p}$

• to find a primitive root modulo (among the numbers ), ${\displaystyle \gamma _{1}}$ ${\displaystyle p}$ ${\displaystyle 2,3,\ldots ,p-1}$

• to test the numbers to see if they are primitive roots modulo . What is necessary and already sufficient for this is that it is. In fact, this already occurs for or , i.e. H. or is a primitive root modulo . ${\displaystyle \gamma _{1}+k\cdot p,\;(0\leq k\leq p-1)}$ ${\displaystyle p^{2}}$ ${\displaystyle (\gamma _{1}+k\cdot p)^{p-1}\not \equiv 1\mod p^{2}}$ ${\displaystyle k=0}$ ${\displaystyle k=1}$ ${\displaystyle \gamma _{1}}$ ${\displaystyle \gamma _{1}+p}$ ${\displaystyle p^{2}}$

Then with every number determined in the second step one has a primitive root modulo for any number . ${\displaystyle \gamma _{2}}$ ${\displaystyle p^{\alpha }}$ ${\displaystyle \alpha \in \mathbb {N} }$

If the primitive root determined in this way is odd, then it is also primitive root modulo , otherwise this applies to . ${\displaystyle \gamma _{2}}$ ${\displaystyle 2\cdot p^{\alpha }}$ ${\displaystyle \gamma _{2}+p^{\alpha }}$

Application example

Primitive roots are used in Diffie-Hellman key exchange , a cryptographic method for public key exchange published in 1976 . Its security is based on the fact that

• it is easy to a given prime , primitive root and integer one calculate with , ${\displaystyle p}$ ${\displaystyle g}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle A=g^{a}{\bmod {p}}}$

it but

• It is laborious to find a corresponding one (the so-called discrete logarithm ) for a known one . ${\displaystyle A}$ ${\displaystyle a}$

Web links

• Calculation of primitive roots

literature

The Disquisitiones Arithmeticae were published in Latin by Carl Friedrich Gauß . The contemporary German translation includes all of his writings on number theory:

• Carl Friedrich Gauß : Investigations into higher arithmetic (German translation), Original: Leipzig 1801.
• Peter Bundschuh : Introduction to Number Theory . 5th edition. Springer Verlag, 2002, ISBN 3-540-43579-4 , pp. 109-120
• Armin Leutbecher: Number Theory - An Introduction to Algebra . 1st edition. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8 .

Individual evidence

1. ↑ The latter is generally closer to the element order, because it applies to everyone ${\displaystyle a,m}$

   ${\displaystyle \operatorname {ord} _{m}(a)\;|\;\lambda (m)\;|\;\varphi (m)}$.

2. ↑ ^{a b c} A. Leutbecher: Number Theory - An Introduction to Algebra. Pp. 53-54.
3. ↑ Carl Friedrich Gauss: Investigations on higher arithmetic. H. Maser, 1889, p. Art. 92 , accessed January 30, 2017 .