The exponent of a number says how many times to multiply the number by it self. Ex:

\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)

where 3 is the exponent (or power) and 4 is the base. In words we say 4 to the power 3.

Here are the laws of exponents:

You already use modulo computation when you look at the clock and e.g. needs to figure out what time it's 3 hours after 11 o'clock, which is 2 o'clock. In math we write that as:

\( (11 + 3) \: mod \: 12 = 2 \)

where 12 is the modulus because we want the time as an integer between 0 and 11 (12 o'clock is in this case denoted by 0). In words we say 11 plus 3 modulo 12 is equal 2. The result of a modulo computation is an integer between 0 and the modulus minus 1. E.g. with the modulus 3 we have that:

• \( 1 \: mod \: 3 = 1 \)
• \( 2 \: mod \: 3 = 2 \)
• \( 3 \: mod \: 3 = 0 \)
• \( 4 \: mod \: 3 = 1 \)
• \( 5 \: mod \: 3 = 2 \)
• \( 6 \: mod \: 3 = 0 \)
• etc.

If we e.g. look at \( 27 \: mod \: 5 \) then modulo computes the number of times 5 divides 27 and then returns the remainder of the result which is 2 in this case, i.e. \( 27 \: mod \: 5 = 2 \). But how did we get this result?

First we compute the number of times it's possible to multiply 5 with the number \( x \) such that we get an integer as close as possible to 27 without exceeding it, i.e. we have to find the maximun value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case we have that \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then by subtracting 27 with 25 we get the answer \( 27 - 25 = 2\).

If the integer is negative e.g. \( -27 \: mod \: 5 \) we have to do it slightly different and the answer is \( -27 \: mod \: 5 = 3 \). In this case the integer \( x \) is negative and should be the closest integer that exceed -27, i.e. we have to find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Now we have that \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then by subtracting -27 with -30 we get the answer \( -27 - (-30) = -27 + 30 = 3\).

It's important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \) etc. and NOT a fraction or float such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \) etc.

If two integers \( a \) and \( b \) modulo the same modulus \( c \) returns the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). I.e. if \( a \: mod \: c = r \) and \( b \: mod \: c = r \) then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e. \( c > a \), the result will always be equal \( a \: mod \: c = a \).

A prime number is an integer greater than 1, which only can be divided evenly by 1 and itself. Divided evenly means that the result must not be a float. E.g. if you try to divide 13 with 3 it returns the float \( \frac{13}{3} = 4.333 \). We have that 13 is a prime number because it can only be divided evenly by 1 and itself, i.e. \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).

If an integer is not a prime number it's called a composite number. E.g. the integer 6 is a composite number because it can be divided evenly by 1, 2, 3 and 6:

\( \frac{6}{1} = 6 \), \( \frac{6}{2} = 3 \), \( \frac{6}{3} = 2 \) and \( \frac{6}{6} = 1 \)

The term composite means "something made by combining things". So, a composite number is an integer made by multiplying prime numbers:

• 2 is a prime
• 3 is a prime
• 4 is a composite: \( 2 \cdot 2 = 4 \)
• 5 is a prime
• 6 is a composite: \( 2 \cdot 3 = 6 \)
• 7 is a prime
• 8 is a composite: \( 2 \cdot 2 \cdot 2 = 8 \)
• 9 is a composite: \( 3 \cdot 3 = 9 \)
• etc.

Therefore, an integer is either a prime number or a product of prime numbers (a composite number).

The famous Greek mathematician Euclid proved that there are infinite many prime numbers.

Michael Rabin and Gary Miller have developed an algorithm that decides whether an integer is a prime or composite number by testing the integer with multiple bases denoted by \( a \). The algorithm is called the Rabin-Miller primality test.

Before we describe what the greatest common divisor of two integers are, we first define what we mean by a divisor. In this context is a divisor of an integer \( x \) some integer that divides \( x \) evenly, i.e. the result must not be a float. E.g. if you try to divide \( x=12 \) with 5 it returns the float \( \frac{12}{5} = 2.4 \) and 5 is therefore not a divisor of \( x=12 \). For \( x=12 \) we have the divisors 1, 2, 3, 4, 6 and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \) and \( \frac{12}{12} = 1 \).

Likewise the divisors of 16 is 1, 2, 4, 8 and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \) and \( \frac{16}{16}=1 \).

The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer of the common divisors. In math we write that as \( \gcd(12, 16) = 4 \).

Two integers with greatest common divisor 1 are called relatively prime numbers or co-primes. E.g. 15 and 28 are relatively prime numbers because \( \gcd(15, 28) = 1 \) (notice that 28 is not a prime number).

If one of the two integers is a prime number the greatest common divisor will always be 1, i.e. \( \gcd(a, p) = 1 \) where \( a \) is an integer (either a prime number or a composite number) and \( p \) is a prime number.

One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integer.

The extended Euclidean algorithm is an extended version of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \) the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \) and \( \mu \) such that:

\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)

where \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime numbers, i.e. \( \gcd(a, b) = 1 \), then:

\( a \cdot \lambda + b \cdot \mu = 1 \)

and \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).

You can easily compute \( \gcd(a, b) \), \( \lambda \) and \( \mu \) for e.g. \( a=5 \) and \( b=39 \) with a simple table. So, let us first create a table with 3 columns (we do not yet know how many rows there will be in the table). Let us denote the entry in the first row and first column for [1,1], the entry in the first row and second column for [1,2], the entry in the second row and first column for [2,1] and so on.

Next we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the biggest integer \( q_{1} \), such that \( q_{1} \cdot a \leq b \). We have that \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \) and a remainder of \( r_{1}=4 \), which we write in entry [3,1].

Again we try to find the biggest integer \( q_{2} \), such that \( q_{2} \cdot r_{1} \leq a \). We have that \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \) and a remainder of \( r_{2}=1 \) that we write in entry [4,1]. Notice that we just computed the same as before, just with integers in a lower row.

The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). And because 5 and 39 are relatively prime numbers, we know that \( \lambda \) and \( \mu \) exists and we can then start using the last column.

First we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3] we compute the same as before, just with integers from the row above, i.e. \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).

Finally we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1\) and \( 40 \geq 39 \) we have that \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)) and the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\) where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).

The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:

The set of integers \( \{ \dots, -2, -1, 0, 1, 2, \dots \} \) is denoted by the symbol \( \mathbb{Z} \), i.e. \( \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} \), and is called a ring of integers or a group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by the symbol \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand version \( \mathbb{Z}_{n} \). This subset contains the following elements (because we compute modulo \( n \)):

\( \mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n - 1 \}\)

Notice that whenever we make an addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the addition or multiplication modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this we look at \( n = 5 \):

\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)

When adding \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (3 \cdot 4) \: mod \: 5 = 12 \: mod \: 5 = 2 \).

An integer \( a \) in \( \mathbb{Z}_{n} \) has an inverse if the greatest common divisor of \( a \) and \( n \) is 1, i.e. \( \gcd(a, n) = 1 \) (see "The extended Euclidean algorithm" for more information). The integer \( a \) is then called an unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by the symbol \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we will use the shorthand version \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units then is the multiplication \( (a_{1} \cdot a_{2}) \: mod \: n \) also always an unit (i.e. \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the addition \( (a_{1} + a_{2}) \: mod \: n \) may NOT be an unit (i.e. \( a_{1} + a_{2} \) is in the group \( \mathbb{Z}_{n} \) but may not be in the group \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):

• \( \mathbb{Z}_{8} = \{ 0, 1, 2, 3, 4, 5, 6, 7 \}\)
• \( \mathbb{Z}_{8}^{*} = \{ 1, 3, 5, 7 \} \)

If we chose \( n \) to be a prime number \( p \) then for all integers \( a \) excluding 0 in \( \mathbb{Z}_{p} \) we have that \( \gcd(a, p) = 1 \), which result in that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) excluding 0, i.e.:

\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)

E.g. for \( p=7 \) we see that the only difference in the two sets \( \mathbb{Z}_{7} \) and \( \mathbb{Z}_{7}^{*} \) is the integer 0:

• \( \mathbb{Z}_{7} = \{ 0, 1, 2, 3, 4, 5, 6 \}\)
• \( \mathbb{Z}_{7}^{*} = \{ 1, 2, 3, 4, 5, 6 \} \)

The number of elements in \( \mathbb{Z}_{n}^{*} \) is denoted by the symbol \( \phi(n) \) after a famous Swiss mathematician called Euler and is called Euler's phi function. As we saw previously, then if \( n \) is a prime number \( p \) then \( \phi(p) = p-1 \). The number of elements in a group \( G \) is also called the order of \( G \) and is written as \( \left| G \right| \). The order of:

• \( \mathbb{Z}_{n} \) is \( \left| \mathbb{Z}_{n} \right| = n \) where \( n \) is a composite number
• \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) \) where \( n \) is a composite number
• \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) = (p-1) \cdot (q-1) \) where \( n = p \cdot q \) and \( p \) and \( q \) are prime numbers
• \( \mathbb{Z}_{p}^{*} \) is \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \) where \( p \) is a prime number

If we e.g. chose the elements \( x \), \( a \) and \( b \) from the group \( \mathbb{Z}_{p}^{*} \) and want to compute \( x^{a + b} \: mod \: p \), then in the exponent we actually compute \( a + b \) modulo the order of the group, i.e. \( a + b \: mod \: (p-1) \) because \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \). So, what we actually compute is \( x^{a + b \: mod \: (p-1)} \: mod \: p \). The same is true if we had chosen one of the other groups; We always compute modulo the order of the group in the exponent. Therefore, next time you look at an equation from a cryptosystem and wonder why they suddenly compute e.g. modulo \( p-1 \) instead of modulo \( p \), then it's because the equation is used in the exponent of some integer.

In the following we use the group \( \mathbb{Z}_{p} \) as an example for simplicity, but we could have chosen any group.

There exist an element \( g \) in the group of integers \( \mathbb{Z}_{p} \) (see "The group of integers and units" for more information), where \( p \) is a prime number, whose powers gives every elements in the set of units \( \mathbb{Z}_{p}^{*} \), i.e. there exists an integer \( g \) in \( \mathbb{Z}_{p} \) such that:

\( \mathbb{Z}_{p}^{*} = \{ g^{1} \: mod \: p, g^{2} \: mod \: p, g^{3} \: mod \: p, \dots, g^{p-1} \: mod \: p \} \)

where \( g^{p-1} \: mod \: p = 1 \) because \( p-1 \: mod \: (p-1) = 0 \) (remember that the order of \( \mathbb{Z}_{p}^{*} \) is \( p-1 \) and we compute modulo the order of the group in the exponent of \( g \) because \( g \) belongs to the group \( \mathbb{Z}_{p}^{*} \)) and \( g^{0} = 1 \). Such a \( g \) is called a generator or a primitive root of the group and it's denoted as \( \left< g \right> = \mathbb{Z}_{p}^{*} \). We also say that the order of \( g \) is \( ord(g) = p-1 \) because \( g \) generates the group \( \mathbb{Z}_{p}^{*} \) with \( p-1 \) elements.

To make it clear we look at an example with the prime number 5. We remember that \( \mathbb{Z}_{5}^{*} = \{ 1, 2, 3, 4 \} \) (see "The group of integers and units" for the example). The group \( \mathbb{Z}_{5}^{*} \) has 2 as a generator because the powers of 2 generates every elements in the group, i.e. \( \left< 2 \right> = \mathbb{Z}_{5}^{*} \):

• \( 2^{1} \: mod \: 5 = 2 \)
• \( 2^{2} \: mod \: 5 = 4 \)
• \( 2^{3} \: mod \: 5 = 3 \)
• \( 2^{4} \: mod \: 5 = 1 \)

The last power is 4 because \( p - 1 = 5 - 1 = 4\). On the other hand, 4 is NOT a generator of \( \mathbb{Z}_{5}^{*} \) because the powers of 4 only generates the integers 1 and 4:

• \( 4^{1} \: mod \: 5 = 4 \)
• \( 4^{2} \: mod \: 5 = 1 \)
• \( 4^{3} \: mod \: 5 = 4 \)
• \( 4^{4} \: mod \: 5 = 1 \)

If you don't know the factorization of the integer \( p-1 \), then the only way to find a generator is to make the above computation, i.e. check that it generates every element in the group \( \mathbb{Z}_{p}^{*} \). Otherwise, if you know the factorization of the integer \( p-1 \), then for every prime number \( q \) that evenly divides the integer \( p-1 \) we check that \( g^{(p-1)/q} \: mod \: p \neq 1 \) for a random integer \( g \) in the group \( \mathbb{Z}_{p} \). If this is the case, then \( g \) is a generator of \( \mathbb{Z}_{p}^{*} \).

Because the prime factorication problem is hard (the problem of computing the factorization of the integer \( p-1 \)), we use a so called safe prime \( p \). A safe prime \( p \) is on the form \( p = 2 \cdot q + 1 \) where \( q \) is a prime number. Now the factorization of \( p-1 \) is always only \( 2 \) and \( q \). E.g. if we compute the safe prime \( p = 2 \cdot 5 + 1 = 11 \) with the prime number \( q = 5 \) we see that \( g = 7 \) is a generator of the group \( \mathbb{Z}_{11}^{*} \) because:

• \( 7^{(11-1)/2} \: mod \: 11 = 10 \neq 1 \)
• \( 7^{(11-1)/5} \: mod \: 11 = 5 \neq 1 \)

where 2 and \( q=5 \) are the only prime numbers that divides \( p-1=11-1=10 \) evenly. For the same reason is \( g = 5 \) not a generator of \( \mathbb{Z}_{11}^{*} \) because:

• \( 5^{(11-1)/2} \: mod \: 11 = 1 \)
• \( 5^{(11-1)/5} \: mod \: 11 = 3 \neq 1 \)

The group \( \mathbb{Z}_{n}^{*} \) where \( n \) is a composite number may not have a generator, but if \( n \) is a prime number \( p \) then the group \( \mathbb{Z}_{p}^{*} \) has minimum one generator.

Let \( g \) be a generator of the group \( G \). Given the values \( g \) and \( H \), the discrete logarithm (DL) problem is about computing the exponent \( a \) in the following equation, which is a hard problem:

\( g^{a} = H \)

The exponent \( a \) is also called the discrete logarithm of \( H \) to the base \( g \).

E.g. if we use the group \( \mathbb{Z}_{p}^{*} \) where \( p \) is a large prime number and \( g \) is a generator of the group, then if you are given \( g \), \( p \) and \( H \) it's a hard to compute \( a \), such that it satisfies the following equation:

\( g^{a} \: mod \: p = H \)

Besides the DL problem we have two similar problems; the Diffie-Hellman (DH) problem and the decisional Diffie-Hellman (DDH) problem. Given the values \( g \), \( g^{a} \) and \( g^{b} \) the DH problem is about computing the exponent \( a \cdot b \) in \( g^{a \cdot b} \).

Similar, given the values \( g \), \( g^{a} \), \( g^{b} \) and \( g^{c} \) the DDH problem is about deciding whether \( c = a \cdot b \) or \( c \) is a random integer.

You may have noticed that if we can solve the DL problem, i.e. computing \( a \) in \( g^{a} = H \), then we also can solve the DH problem: first we compute \( a \) in \( g^{a} \), then \( b \) in \( g^{b} \) and finally \( a \cdot b \). Now this also implies that we can solve the DDH problem: first we compute \( a \cdot b \) as described above, then \( c \) in \( g^{c} \) and finally we check whether \( c = a \cdot b \).