Modular Arithmetic

In basic cryptology we become very comfortable with arithmetic carried out mod 26, but it rapidly becomes necessary to consider other possible moduli as well. Here we provide the basics of modular arithmetic.

First we have to pick a modulus which is a positive whole number m. We say two numbers a, b are equal modulo m (or congruent modulo m; that is the proper term) if m divides a-b. In that case, we write $a\equiv b \pmod m$ (an equals sign with three bars).

Examples:
$$\begin{align*}31 \equiv 5 \pmod{26} \quad &\text{because $31-5 = 26 =1\cdot 26$ ... ...\equiv -7 \pmod{16} \quad &\text{because $89--7 = 96 =6\cdot 16$ } \end{align*}$$

The neat things about modular arithmetic is that all the basic operations, addition, subtraction, multiplication and division, all preserve congruences to the same modulus. Thus, given $26\equiv 4 \pmod{11}$ and $47\equiv 3\pmod{11}$, we can conclude that
$$\begin{align*}26+47 &=\equiv 4+3 \pmod{11} \\ 26-47 &=\equiv 4-3 \pmod{11} \\ 26\cdot47 &=\equiv 4\cdot 3 \pmod{11} \end{align*}$$
We have to be a little careful about division, because we do not want to divide by 0, of course, and in modular arithmetic other numbers (such as 11 or 22 in this example) could be equivalent to 0.

Arithmetic modulo 2 is especially simple, because we have a very small addition table.

+	0	1
0	0	1
1	1	0

That's right: we have to define 1+1=0, since $1+1=2\equiv 0 \pmod 2$. This is sometimes called bit arithmetic, because it deals only with 0's and 1's, which are the fundamental building blocks of computer science, or bits.

Here is a more indepth look at modular arithmetic. Suppose we have a modulus m, and pairs of congruent integers modulo m:

$$a\equiv c \pmod m \qquad\text{and}\qquad b\equiv d \pmod m$$

The properties we were talking about before are
$$\begin{align*}a+b &\equiv c+d \pmod m\\ ab \equiv cd \pmod m \end{align*}$$
Here is why they are always true. The congruences mean that a-c = kmand b-d = lm for some integers k and l. Congruence means that the numbers differ by a multiple of m. All right, just add those two equations up, and we have

a-c+b-d = km+lm= (k+l)m

The right side is still a multiple of m, and the left side is (a+b)-(c+d). That proves the addition formula.

Multiplication is a little harder:
$$\begin{align*}ab-cd &= ab -cb +cb-cd \\ &= (a-c)b +c(b-d) \\ &= kmb + clm \\ &= (kb+cl)m \end{align*}$$
The first step is known as ``adding-and-subtracting.'' If you add and subtract the same quantity, you don't change the expression. Theoretically, though, that allows us to see that ab-cd is still a multiple of m. That proves the multiplication property.

These are very powerful properties. For instance, we can use them to compute congruences with extremely large numbers. As an example, suppose we would like to know the last decimal digit of 7¹00. That number is far too large for our calculator, but all we are asking for is $7^100 \pmod{10}$ (the last decimal digit). Then we might compute a few powers and see that $7^2 =49 \equiv -1 \pmod{10}$. Aha! That means

$$7^{100} = (7^2)^{50} \equiv (-1)^{50} = 1 \pmod{10}$$

Thus, the last decimal digit of 7¹⁰⁰ is 1. We will be very much concerned with computing powers in modular arithmetic when we discuss some of the state-of-the-art cryptosystems and authentication schemes.

As a final note here, you should be careful of the difference between modular arithmetic and word arithmetic. Words are strings of bits, such as 10111001, which is a word of length 8 bits. We have seen in [Beutelspacher, 1994] the use of arithmetic of words in cipher systems such as the one-time pad and the Data Encryption System. This not quite the same as modular arithmetic. Addition of words is carried out bit by bit. One common notation is

$$11010111 \oplus 01010101 = 10000010$$

where the corresponding bits have been added according to mod 2 arithmetic.