Modular arithmetic is extremely important in modern cryptography, especially for asymmetric algorithms. Almost all crypto algorithms, both symmetric ciphers and asymmetric ciphers, are based on arithmetic within a finite number of elements. Most number sets we are used to, such as the set of natural numbers or the set of real numbers, are infinite. In the following we introduce modular arithmetic, which is a simple way of performing arithmetic in a finite set of integers.

Let’s look at an example of a finite set of integers from everyday life:
Example 1.4. Consider the hours on a clock. If you keep adding one hour, you obtain:
1h,2h,3h, . . . ,11h,12h,1h,2h,3h, . . . ,11h,12h,1h,2h,3h, . . .
Even though we keep adding one hour, we never leave the set.

Let’s look at a general way of dealing with arithmetic in such finite sets.
Example 1.5. We consider the set of the nine numbers:
{0,1,2,3,4,5,6,7,8}
We can do regular arithmetic as long as the results are smaller than 9. For instance:
2×3 = 6
4+4 = 8

But what about 8+4? Now we try the following rule: Perform regular integer arithmetic
and divide the result by 9. We then consider only the remainder rather than
the original result. Since 8+4 = 12, and 12/9 has a remainder of 3, we write:
8+4 ≡3 mod 9

Definition Modulo Operation
Let a, r,m ∈ Z (where Z is a set of all integers) and m > 0. We write
a ≡ r mod m
if m divides a−r.
m is called the modulus and r is called the remainder.

Computation of the Remainder

It is always possible to write a ∈ Z, such that a = q ·m+r for 0 ≤ r < m  Since a−r = q ·m (m divides a−r) we can now write: a ≡ r mod m. Note that
r ∈ {0,1,2, . . . ,m−1}.
Example

Let a = 42 and m = 9. Then 42 = 4 · 9+6 and therefore 42 ≡ 6 mod 9.