The group of units-Primitive Roots-Discrete logarithm

The group $U_n$ ( Group of units)

It is noted that the set all numbers relatively prime to $n$ ( gcd(a,n)=1 ) (units $U_n$ )forms a group in $\mathbb{Z}_n$ under multiplication.

We say that a group $G$ is abelian if its elements commute, that is $gh=hg$ for all $g,h \in G$.The group $U_n$ is an abelian group under multiplication $\pmod{n}$.

If $G$ is a finite group with an identity element $e$, the order of an element $g \in G$ is the least integer $k>0$ such that $g^k=e$, then the integers $l$ such that $g^l=e$ are the multiples of $k$.

Example:

In $U_5$ the element 2 have order 4.ie; $2^1 \equiv 2,2^2 \equiv 4,2^3 \equiv 3,2^4 \equiv 1 \pmod{5}$, so $k=4$ is the least positive exponent such that $2^k=1$( the identity element) in $U_5$.Similarly the element 1 has order 1, while the elements 3 and 4 have orders 4 and 2 respectively.

In $U_8$ the elements 1,3,5,7 have orders 1,2,2,2 respectively.

Our aim is to describe the structure of the group $U_n$ for all $n$.To do this, it is not sufficient simply to know its order $\phi(n)$.For example since $\phi(5)=4=\phi(8)$, the groups $U_5$ and $U_8$ bot have order 4.However these two groups are not isomorphic, since $U_5$ has elements order 4 ,namely 2 and 3, where as $U_8$ has none.In group theoretic terminology and notation, $U_5$ is a cyclic group of order 4.$(U_5 \cong C_4)$, generated by 2 or 3, where as $U_8$ is a Klein Four Group $(U_8 \cong V_4 = C_2 \times C_2)$

Primitive Root and  cyclic group : Definition

If $U_n$ is cyclic then any generator $g$ for $U_n$ is called a primitive root $\pmod{n}$. This means that $g$ has order equal to the order $\phi(n)$ of $U_n$, so that the powers of $g$ yield all the elements of $U_n$.For instance, 2 and 3 are primitive roots $\pmod{5}$.But there are no primitive roots $\pmod{8}$, since $U_8$ is not cyclic.

Finding primitive roots in $U_n$ (if they exist) is a non-trivial problem. and there is no simple solution. One obvious but tedious method is to try each of the $\phi(n)$ units $a \in U_n$ in turn each time computing the powers $a^i \pmod{n}$ to find the order of $a$ in $U_n$;if we find an element $a$ of order $\phi(n)$ then we know that this must be primitive root.

The following lemma helps in finding the primitive root efficiently

An element $a \in U_n$ is a  primitive root if and only if  $a^{\phi(n)/q} \ne 1 $ in $U_n$  for each prime $q$ dividing $\phi(n)$.

Example: Let $n=11, \phi(11)=10$, So the prime factors of 10 are 2 and 5.Lets see whether $a=2$ is a primitive root.

$2^5 =32 \equiv 10 \pmod{11}$
$2^2=4 \equiv 4 \pmod{11}$

So both are $\not \equiv 1$, and hence we can conclude that 2 is a primitive root.We can verify this

$2^1=2,2^2=4,2^3=8,2^4=5,2^5=10,2^6=9,2^7=7,2^8=3,2^9=6,2^{10}=1$

Thus 2 has order 10 and its power gives all the elements of $U_{11}$

If we apply lemma with $a=3$, we can find that $3^{5}=343=1 \pmod{11}.$ So 3 is not a primitive root in $\pmod{11}$; its powers are 3,9,5,4,and 1

Example: Lets find a primitive root $\pmod{17}$.We have $\phi(17)=16$, which has only $q=2$ as a prime factor. The lemma implies that an element $a \in U_17 $ is primitive root if and only if $a^8 \ne 1$ in $U_{17}$.Trying $a=2$ first , we have $2^8=256 \equiv 1 \pmod{17}$, so 2 is not a primitive root.How ever $3^8 \equiv 16 \pmod{17}$, so 3 is a primitive root.

Example: Lets take another example where $n$ is composite say 9.The group has $\phi(9)=6$ elements.2 and 3 are the factors of $\phi(6)$.Thus an element $a \in U_9$ is a primitive root if and only if $a^2,a^3 \ne 1$ in $U_9$.Since $2^2,2^3 \not \equiv 1 \pmod{9}$ , we see that 2 is a primitive root.

Note: If $U_n$ has a primitive root then it has $\phi (\phi(n))$ of them.If $p$ is prime then the group $U_p$ is cyclic.

If $p$ is prime then $U_p$ has $\phi(d)$ elements of order $d$ for each $d$ dividing $p-1$.

Example: The table below shows the powers of integers modulo 19.The primitive roots are 2,3,10,13,14,15.

It has $\phi(\phi(19))=\phi(18)=6$ primitive roots.

The factors of 18 are 1,2,3,6,9,18

$\phi(1)=1$- There is 1 element of order 1 which is 1

$\phi(2)=1$- There is 1 element of order 2 which is 18

$\phi(3)=2$- There are 2 elements of order 3 which are 7 and 11

$\phi(6)=2$- There are 2 elements of order 6 which are 8 and 12

$\phi(9)=6$- There are 6 elements of order 9 which are 4,5,6,9,16,17

$\phi(18)=6$- There are 6 elements of order 18 which are 2,3,10,13,14,15 ( primitive roots)

Note: 

If $p$ is an odd prime then $U_{p^e}$ is cyclic for all $e \ge 1$.

If $g$ is a primitive root $\pmod{p}$, where $p$ is an odd prime, then $g$ is usually a primitive root $\pmod{p^2}$, in which case $g$ is always a primitive root $\pmod{p^e}$ for all $e$.For instance $g=2$ is a primitive root in $U_5$ and also a primitive root in $U_{5^2}$ and hence for all $e$.

The group $U_{2^e}$ is cyclic only for $e=1$ or $e=2$.

Python code

Finding order of an element

from sympy.ntheory import n_order 

print(n_order(2, 19))

18

print(n_order(6, 19))

9

print(n_order(7, 19))

3

Checking primitive roots

from sympy.ntheory import is_primitive_root

print(is_primitive_root(2,19))

True

print(is_primitive_root(6,19))

False

Return Smallest Primitive Root

from sympy.ntheory.residue_ntheory import primitive_root

primitive_root(19)

2

Existence of Primitive Roots

How can we determine all integers  $n$ for which there exist primitive root $\pmod{n}$

Theorem: The group $U_n$ is cyclic if and only if $n=1,2,4,p^e,2p^e$, where $p$ is an odd prime.

This can be verified for various values of $n$,

Lemma: if $n=r.s$, where  $r$ and $s$ are co prime and are both greater than 2, then $U_n$ is not cyclic.

Examples:

$U_8$ is not cyclic because 8  is not of the form $1,2,4,p^e,2p^e$, where $p$ is an odd prime.

$U_{15}$ is not cyclic because $15=3 \times 5$ and $gcd(3,5)=1$

Application of Primitive Roots

Discrete Logarithm Problem

With ordinary positive real numbers, the logarithm function is the inverse of exponentiation. An analogous function exists for modular arithmetic. Let us briefly review the properties of ordinary logarithms.The logarithm of a number is defined to be the power to which some positive base (except 1) must be raised in order to equal the number.That is, for base $x$ and for a value $y$,

$$y=x^{log_x(y)}$$

Consider a primitive root $a$ for some prime number $p$(the argument can be developed for nonprimes as well). Then we know that the powers of $a$ from 1 through $(p-1)$ produce each integer from 1 through $(p-1)$ exactly once.We also know that any integer $b$ satisfies

$$b \equiv r \pmod{p} \quad \text{for some}\: r \: \text{where} , 0 \le r \le (p-1)$$

by the definition of modular arithmetic. It follows that for any integer $b$ and a primitive root $a$ of prime number $p$ , we can find a unique exponent $i$ such that

$$b \equiv a^i \pmod{p} \quad \text{where} , 0 \le i \le (p-1)$$

This exponent $i$ is referred to as the discrete logarithm of the number $b$ for the base $a \pmod{p}$.We denote this value as $dlog_{a,p}(b)$

Note the following:

$dlog_{a,p}(1) = 0$ because $a^0 \pmod{p }= 1 \pmod{ p} = 1$

$dlog_{a,p}(a) = 1$  because $a^1 \pmod{p} = a $

Note: Keep in mind that unique discrete logarithms $\pmod{m}$ to some base exist only if $a$ is a primitive root of $m$.

Consider $U_{19}$. The primitive root and discrete logarithm are shown in table below.

Calculation of Discrete Logarithms

Consider the equation

$$y=g^x \pmod{p}$$

Given $g,x$ and $p$, it is a straightforward matter to calculate $y$. At the worst, we must perform $x$ repeated multiplications, and algorithms exist for achieving greater efficiency.

However, given $y, g$, and $p$, it is, in general, very difficult to calculate $x$(take the discrete logarithm). The difficulty seems to be on the same order of magnitude as that of factoring primes required for RSA. There is no asymptotically fastest known algorithm for taking discrete logarithms modulo a prime number.

Python Code

from sympy.ntheory import discrete_log
print(discrete_log(19, 8, 2))
3
print(discrete_log(19, 10,15))
13

Solving Congruence

Consider solving the congruence(find $x$)  given $m,c$ and $n$

$x^m \equiv c \pmod{n}$

Example:

Consider the congruence $x^4 \equiv 13 \pmod{17}$.

First note that any solution $x$ must be a unit $\pmod{17}$. This group is cyclic, so both $x$ and $13$ can be expressed as a power of a primitive root $g \pmod{17}$.3 is a primitive root of this group $U_{17}$ and $3^4 \equiv 13 \pmod{17}$.So we can write the congruence $3^{4i} \equiv 3^4 \pmod{17}$.It is noted that $3^{4i} \equiv 3^4 \pmod{17}$ only if  $4i = 4 \pmod{16}$ or equivalently $i \equiv 1 \pmod{4}$

The relevant values of $i$ (between 0 and 15) are therefore 1,5,9,13. So the solutions of the original congruence are $x \equiv 3,3^5,3^9\: \text{and} \: 3^{13}$ 

Note:if there exist a primitive root $g \pmod{n}$, writing $x=g^i$ and $c=g^b$, we convert the original non linear congruence $x^m \equiv c \pmod{n}$ into linear congruence $mi \equiv b \pmod{\phi(n)}$

Application- Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange algorithm is a method for securely exchanging cryptographic keys over a public channel. This method allows two parties to jointly establish a shared secret key, which can then be used for secure communications. The algorithm is based on the difficulty of solving the discrete logarithm problem in finite fields.

Steps of the Diffie-Hellman Key Exchange Algorithm:

1. Agree on Parameters:

   • Both parties agree on a large prime number $�$ and a base $�$, which is known as a generator of a cyclic group. These parameters can be public and are not considered secret.

2. Generate Private Keys:

   • Each party generates a private key randomly. Let's denote the private key of Alice as
     $�$ and the private key of Bob as $�$. These private keys remain secret and are not ransmitted over the network.

3. Compute Public Keys:

   • Each party computes their public key by raising the base $�$ to the power of their private key and taking the modulus $�$.
     • Alice computes her public key $�$ as follows: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�$.
     • Bob computes his public key $�$ as follows: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�$.
   • Alice and Bob then exchange their public keys over the public channel.

4. Compute the Shared Secret:

   • Each party computes the shared secret key using the public key received from the other party and their own private key. This computation will result in the same shared secret for both parties.
     • Alice computes the shared secret $�$ using Bob's public key: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�$.
     • Bob computes the shared secret $�$ using Alice's public key: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�$.

Due to the properties of exponentiation in modular arithmetic, both computations for the shared secret will result in the same value:

$�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�=({�}^{�}{)}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�={�}^{��}\mathrm{m}\mathrm{o}\mathrm{d}�$ $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�=({�}^{�}{)}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�={�}^{��}\mathrm{m}\mathrm{o}\mathrm{d}�$

Example:

Let's use a toy example to illustrate this:

• Let the prime $�=23$ and the base $�=5$.
• Alice selects a private key $�=6$.
• Bob selects a private key $�=15$.

1. Compute Public Keys:

   • Alice computes her public key: $�=5^6\mathrm{m}\mathrm{o}\mathrm{d}23=8$.
   • Bob computes his public key: $�=5^{15}\mathrm{m}\mathrm{o}\mathrm{d}23=2$.

2. Exchange Public Keys:

   • Alice sends $�=8$ to Bob, and Bob sends $�=2$ to Alice.

3. Compute the Shared Secret:

   • Alice computes the shared secret: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�=2^6\mathrm{m}\mathrm{o}\mathrm{d}23=9$.
   • Bob computes the shared secret: $�={�}^{�}\mathrm{m}\mathrm{o}\mathrm{d}�=8^{15}\mathrm{m}\mathrm{o}\mathrm{d}23=9$.
Both Alice and Bob now share the secret key
$=9$

This example simplifies the actual calculations to make it easy to follow. In real-world applications, the numbers involved are typically very large to ensure security against attacks, such as trying all possible keys (brute-force attack).