Primitive root modulo n

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

Example

The number 3 is a primitive root modulo 7 because they are subject

So for all elements of the reduced residue class group modulo 7 represented as powers of 3. The number 2 is not a primitive root modulo 7, there is, therefore, remains to be repeated in the sequence of powers of 2 modulo 7

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

Definition and existence conditions

An integer is a primitive root modulo if the residue class generates the residue class group. This is equivalent to saying 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:

This is Euler's φ function and the multiplicative order modulo m of the element, ie, the smallest positive exponent n for which (for the notation "mod" see modulo).

There are exactly then primitive roots modulo if the residue class group is a cyclic group. This is according to a set of CF Gauss exactly the case when the module

Applies. It denotes the set of odd primes.

If modulo primitive roots exist, then there are exactly modulo incongruent primitive roots. Each of these primitive roots modulo congruent to an element of the set:

With an arbitrary primitive root modulo.

Calculation of primitive roots

To determine if a number is a primitive root modulo, is first calculated, and then the order of. The order can be determined by sequentially adding the values ​​are calculated for example. The first applies to the, is the order of.

In the example from the introduction we can see that the 3 has order 6. As is also considered, 3 is a primitive root modulo 7

A number that is not a primitive root modulo 7 is the 4th applies here

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

Primitive roots modulo primes

The prime residue class groups of modules that are prime numbers have exactly elements. The numbers are the representatives of the different residue classes. Is a primitive root modulo, so does the expression for all values ​​of (in seemingly random order).

Examples

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

Primitive roots modulo prime powers

Is an odd prime, then a primitive root modulo also primitive root modulo small powers of. It is interesting to search for Primtivwurzeln modulo higher powers of that is a primitive root modulo ( with ) also primitive root to all higher powers of is .. Therefore, it is sufficient for higher powers of the prime,

• A primitive root modulo to find ( under the numbers)

• To test the numbers to determine whether they are primitive roots modulo - is necessary and already sufficient for that. Indeed, this already occurs for or that is, or is a primitive root modulo.

Then one has with any particular number in the second step is a primitive root modulo arbitrary.

Is the so- certain primitive root is odd, then it is also a primitive root modulo, otherwise this applies to.

Example of use

Primitive roots find an application in the Diffie -Hellman key exchange, one published in 1976 cryptographic method for public key exchange. Its security is based on the fact that

• It is easy to calculate for a given prime primitive root and integer with a,

But it

• Is consuming to find ( the so-called discrete logarithm ) for a known a corresponding.