How Modular Arithmetic is the Building Block of Cryptography

Modular Arithmetic and Why It is the Building Block of Cryptography
Photo by Ocean Ng on Unsplash

Modular arithmetic is a branch of mathematics that deals with integers and their remainders when divided by a fixed integer. It involves operations such as addition, subtraction, multiplication, and division, but instead of working with the actual numbers, we work with their remainders modulo a fixed number, called the modulus.

For example, if we consider 7 modulo 3, we can write it as 71(mod3)7\equiv1\pmod{3} because 7 leaves a remainder of 1 when divided by 3. Similarly, 51(mod3)-5 \equiv 1\pmod{3} because -5 leaves the same remainder of 1 when divided by 3.

Modular arithmetic has many interesting properties that make it useful in various applications, including cryptography. In this article, we will explore some of these properties and their significance in cryptography.

Addition and Subtraction

In modular arithmetic, addition and subtraction work similarly to regular arithmetic but with one key difference. If the result of the operation exceeds the modulus, we take the remainder modulo the modulus as the final result.

For example, let's consider 6+4(mod7)6 + 4\pmod{7}. The sum is 10, which is greater than 7, so we need to take the remainder modulo 7, which is 3. Therefore, 6+43(mod7)6 + 4\equiv 3\pmod{7}.

Similarly, if we consider 25(mod7)2 - 5\pmod{7}, we get 25=32 - 5 = -3, which is less than 0. To obtain a positive remainder, we add the modulus to -3 until we get a positive number. In this case, we add 7 to -3, giving us 4. Therefore, 254(mod7)2 - 5\equiv 4\pmod{7}.


Multiplication in modular arithmetic is also similar to regular multiplication, but with the remainder of the product modulo the modulus as the final result. For example, let's consider 3×5(mod7)3\times5\pmod{7}. The product is 15, and the remainder of 15 when divided by 7 is 1. Therefore, 3×51(mod7)3\times5\equiv 1\pmod{7}.

One interesting property of modular multiplication is that it is distributive over addition. That is, (a+b)×ca×c+b×c(modm)(a+b)\times c\equiv a\times c+b\times c\pmod{m} for any integers aa, bb, and cc and modulus mm. This property is important in cryptography, as we will see later.


Division in modular arithmetic is more involved than the other operations, and it is not always possible. In general, we can only divide if the divisor is relatively prime to the modulus. That is, if gcd(c,m)=1gcd(c,m) = 1, where gcdgcd denotes the greatest common divisor.

Suppose we want to solve the equation axequivbpmodmaxequiv bpmod{m} for xx, where aa, bb, and mm are integers. If gcd(a,m)=1gcd(a,m) = 1, then there exists an integer solution xx. We can find this solution using the extended Euclidean algorithm, which is beyond the scope of this article.

Modular Exponentiation and Diffie Hellman

Modular exponentiation is an important mathematical operation used in various cryptographic protocols. It involves computing the remainder when a base number is raised to a power and divided by a modulus. This operation is particularly useful for encryption algorithms because it allows for fast computation of large powers modulo a prime number. One of the most common algorithms for modular exponentiation is the square and multiply algorithm, which utilizes the binary representation of the exponent to perform efficient exponentiation. This operation is widely used in public key cryptography, such as RSA, Diffie-Hellman key exchange, and ElGamal encryption.

The Diffie-Hellman key exchange protocol is a method for two parties to agree on a shared secret over an insecure communication channel. The protocol relies on the properties of modular exponentiation. Let's say Alice and Bob want to agree on a shared secret key KK. They first agree on a prime number pp and a generator gg modulo pp, which means that gg is relatively prime to pp and can generate all possible values modulo pp.

Then, each party chooses a secret number - Alice chooses aa and Bob chooses bb. They each compute their public value as follows:

A=gamodpA = g^a \bmod p

B=gbmodpB = g^b \bmod p

Alice and Bob then exchange their public values with each other over the insecure communication channel. They can now compute the shared secret key KK using the other party's public value and their own secret value:

K=Bamodp=gabmodpK = B^a \bmod p = g^{ab} \bmod p

K=Abmodp=gabmodpK = A^b \bmod p = g^{ab} \bmod p

Since both parties have computed the same value of KK, they now share a secret key which can be used for encryption and decryption. This protocol is secure because an eavesdropper cannot compute aa or bb from AA or BB alone without knowing the other party's secret value.


Modular arithmetic is a fundamental concept in cryptography and plays a crucial role in many cryptographic algorithms. It enables the secure computation of large numbers by reducing them to a smaller set of residue classes modulo a prime number, making it harder for attackers to decrypt sensitive information. Modular exponentiation, in particular, is widely used in public key cryptography algorithms such as Diffie-Hellman key exchange, RSA, and ElGamal encryption. These algorithms provide secure communication over unsecured networks by utilizing the properties of modular arithmetic to protect sensitive data from unauthorized access. Therefore, understanding and implementing modular arithmetic is critical to building strong cryptographic systems that can provide secure communication and data protection.