What is Modular Arithmetic?

Usually, when you want to perform division, you do something like:

$$ \frac{3}{5} = 1,(6) \Rightarrow 1\frac{2}{3} $$

But there are some cases when you only need the remainder.

$$ \frac{\text{Dividend}}{\text{Divisor}} = \text{Quotient} + \text{Remainder} $$

Where \(\text{Quotient} = k \times \text{Divisor}\) for some integer \(k\).

This is called modular arithmetic:

$$ A \mod{B} = R $$

Examples:

$$ \frac{0}{3} \text{ remainder } = 0 $$ $$ \frac{1}{3} \text{ remainder } = 1 $$ $$ \frac{2}{3} \text{ remainder } = 2 $$ $$ \frac{3}{3} \text{ remainder } = 0 $$ $$ \frac{4}{3} \text{ remainder } = 1 $$ $$ \frac{5}{3} \text{ remainder } = 2 $$ $$ \frac{6}{3} \text{ remainder } = 0 $$

As you may notice, there are two important things to observe here:

Note:

• The remainder is always less than the divisor, so \(R \in <0, \text{divisor})\).
• The remainders are sequential.

Modulo Congruence

$$ A \equiv B \pmod{C} $$

This means:

$$ A \mod{C} = B \mod{C} $$

And

$$ A - B = k \times C, \text{ where } k \in \mathbb{Z} $$

Mathematical Operations

For addition:

$$ (A + B) \mod{C} = ((A \mod{C}) + (B \mod{C})) \mod{C} $$

And for multiplication:

$$ (A \times B) \mod{C} = ((A \mod{C}) \times (B \mod{C})) \mod{C} $$

But wait, why would you choose \(((A \mod{C}) \times (B \mod{C})) \mod{C}\) over \((A \times B) \mod{C}\)?

It may seem unnecessary for small values of \(A\) and \(B\), but let's say we want to calculate \(7^{256} \mod{13}\). Instead of calculating \(7 \times 7 \times \ldots \times 7\) (256 times), we can simplify the process:

$$ 7^1 \mod{13} = 7 $$ $$ 7^2 \mod{13} = 10 $$ $$ 7^4 \mod{13} = (7^2 \times 7^2) \mod{13} \Rightarrow (10 \times 10) \mod{13} = 9 $$ $$ 7^8 \mod{13} = (7^4 \times 7^4) \mod{13} \Rightarrow (9 \times 9) \mod{13} = 3 $$ $$ \vdots $$ $$ 7^{256} \mod{13} = (7^{128} \times 7^{128}) \mod{13} = 9 $$

You can calculate this in a finite number of operations. It was easier because 256 is a power of 2, so all you had to do was square the previous result.

You can apply the same method even with other numbers like \(5^{117} \mod{19}\).

$$ 5^{117} \mod{19} = 5^{(1+4+16+32+64)} \mod{19} $$

Since \(1, 4, 16, 32, 64\) are all powers of 2, you can continue:

$$ 5^{117} \mod{19} = (5^1 \times 5^4 \times 5^{16} \times 5^{32} \times 5^{64}) \mod{19} $$

$$ 5^{117} \mod{19} = ((5^1 \mod{19}) \times (5^4 \mod{19}) \times (5^{16} \mod{19}) \times (5^{32} \mod{19}) \times (5^{64} \mod{19})) \mod{19} $$

$$ 5^{117} \mod{19} = (5 \times 17 \times 16 \times 9 \times 5) \mod{19} $$

$$ 5^{117} \mod{19} = 61200 \mod{19} = 1 $$

So:

$$ 5^{117} \mod{19} = 1 $$

Now that you know how to perform these essential operations, we can move on to some definitions.

Fermat's Little Theorem

Fermat's Little Theorem states that if \(p\) is a prime number and \(a\) is an integer such that \(a\) is not divisible by \(p\) (i.e., \(p\) does not divide \(a\)), then:

$$ a^{p-1} \equiv 1 \pmod{p} $$

This can also be written as:

$$ a^{p} \equiv a \pmod{p} $$

where \(a\) is any integer, and \(p\) is a prime number.

Example 1: Simple Application

Let's consider \(a = 2\) and \(p = 7\). Since 7 is a prime number, we can apply Fermat's Little Theorem:

According to the theorem:

$$ 2^{7-1} = 2^{6} \equiv 1 \pmod{7} $$

Let's calculate:

$$ 2^6 = 64 $$

Now, divide 64 by 7 and find the remainder:

$$ 64 \div 7 = 9 \text{ remainder } 1 $$

So:

$$ 64 \equiv 1 \pmod{7} $$

This confirms that:

$$ 2^{6} \equiv 1 \pmod{7} $$

This example shows that \(2^{6}\) modulo 7 gives a remainder of 1, as predicted by Fermat's Little Theorem.

Example 2: Larger Exponent

Now let's consider a larger example with \(a = 5\) and \(p = 11\):

According to Fermat's Little Theorem:

$$ 5^{11-1} = 5^{10} \equiv 1 \pmod{11} $$

Let's calculate \(5^{10} \mod{11}\). To make it easier, we'll use the properties of exponents and modular arithmetic:

First, calculate:

$$ 5^2 = 25 $$

Then:

$$ 25 \mod{11} = 3 $$

So:

$$ 5^2 \equiv 3 \pmod{11} $$

Now, calculate:

$$ 5^{10} = (5^2)^5 \equiv 3^5 \pmod{11} $$

We can break this down further:

$$ 3^2 = 9 $$

$$ 3^4 = 9^2 = 81 $$

And:

$$ 81 \mod{11} = 4 $$

So:

$$ 3^4 \equiv 4 \pmod{11} $$

Finally:

$$ 3^5 \equiv 4 \times 3 = 12 \equiv 1 \pmod{11} $$

This confirms that:

$$ 5^{10} \equiv 1 \pmod{11} $$

In this example, even with a larger exponent, Fermat's Little Theorem accurately predicts the result of \(5^{10} \mod{11}\), showing that it is indeed congruent to 1.

Modular Multiplicative Inverse

According to Wikipedia, a modular multiplicative inverse is an integer \(x\) such that the product \(ax\) is congruent to 1 with respect to the modulus \(m\). This can be written as:

$$ ax \equiv 1 \pmod{m} $$

A modular multiplicative inverse \(x\) exists if and only if \(\text{GCD}(a, m) = 1\).

Example:

$$ 3 \times x \equiv 1 \pmod{13} $$ $$ \text{GCD}(3,13) = 1 $$ $$ x = 9 $$

Why 9?

Because:

$$ (3 \times 9) \mod{13} = 27 \mod{13} = 1 $$

But wait, how did you find out it's 9?

To find such numbers, the Extended Euclidean Algorithm can be used. Understanding and calculating modular multiplicative inverses is the first step to learning cryptographic algorithms.

Quadratic Residue

A quadratic residue is a number that is congruent to \(a^2\) modulo \(p\). Let's say \(a = 11\) and \(p = 29\).

$$ a^2 \equiv 5 \pmod{29} $$

because:

$$ 121 \mod{29} = 5 $$

Since \(a = 11\) and \(a^2 \equiv 5\), we can say that 11 is a square root of 5 modulo 29. And since we know it's squared, there should be a second root as well, right? Yes, there is. But how do we find it?

If \(x_1\) is one square root, then:

$$ x_1^2 \equiv q \pmod{p} $$

The second root \(x_2\) is given by:

$$ x_2 = p - x_1 $$

And:

$$ x_1^2 \equiv x_2^2 \equiv q \pmod{p} $$

In the above example, 5 is called a quadratic residue modulo 29.

Now, let's calculate \(a\) such that \(a^2 \equiv 18 \pmod{29}\).

You can write a loop in code to check all numbers from 1 to \(p-1\), and since \(q\) isn't a large number, you can quickly verify all possibilities to see that there is no integer that satisfies this equation. This means 18 is a Quadratic Non-Residue modulo 29.

For small values of \(p\) like 29, it's easy to iterate through all the possibilities to find the square root. But as \(p\) gets larger, it becomes nearly impossible to calculate it in a reasonable time.

So, is there any trick that could make this faster? Of course, there is, and it's called the Legendre Symbol.

Legendre Symbol

The Legendre symbol is a notation that helps determine whether a given number is a quadratic residue modulo a prime number \(p\). It is denoted as:

$$ \left(\frac{a}{p}\right) $$

Where:

• \(a\) is an integer.
• \(p\) is an odd prime.

The Legendre symbol \(\left(\frac{a}{p}\right)\) is defined as:

$$ \left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } a \equiv 0 \pmod{p}, \ 1 & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0 \pmod{p}, \ -1 & \text{if } a \text{ is a quadratic non-residue modulo } p. \end{cases} $$

Example:

Let's calculate the Legendre symbol \(\left(\frac{5}{29}\right)\).

Step 1: Verify that \(29\) is a prime number.

Step 2: Calculate \(5^{(p-1)/2} \mod{p}\), where \(p = 29\).

Here, we compute:

$$ 5^{(29-1)/2} = 5^{14} $$

Now, calculate \(5^{14} \mod{29}\) by repeatedly squaring and reducing modulo 29:

$$ 5^1 \equiv 5 \pmod{29} $$ $$ 5^2 \equiv 25 \pmod{29} $$ $$ 5^4 \equiv 25^2 \equiv 625 \equiv 16 \pmod{29} $$ $$ 5^8 \equiv 16^2 \equiv 256 \equiv 24 \pmod{29} $$ $$ 5^{14} \equiv 5^8 \times 5^4 \times 5^2 \equiv 24 \times 16 \times 25 \equiv 9600 \equiv 1 \pmod{29} $$

Step 3: Interpret the result:

• Since the result is \(1\), this means \(5\) is a quadratic residue modulo \(29\), and:

$$ \left(\frac{5}{29}\right) = 1 $$

Another Example:

Let's try another example with \(a = 18\) and \(p = 29\).

Step 1: Calculate \(18^{14} \mod{29}\):

$$ 18^2 \equiv 324 \equiv 5 \pmod{29} $$ $$ 18^4 \equiv 5^2 \equiv 25 \pmod{29} $$ $$ 18^8 \equiv 25^2 \equiv 625 \equiv 16 \pmod{29} $$ $$ 18^{14} \equiv 18^8 \times 18^4 \times 18^2 \equiv 16 \times 25 \times 5 \equiv 2000 \equiv -1 \pmod{29} $$

Step 2: Interpret the result:

• Since the result is \(-1\), this means \(18\) is a quadratic non-residue modulo \(29\), and:

$$ \left(\frac{18}{29}\right) = -1 $$

The Legendre symbol is a powerful tool in number theory, especially in the context of solving quadratic congruences and understanding properties of quadratic residues modulo a prime.

Finding Square Roots Modulo a Prime when \( p \equiv 3 \pmod{4} \)

Now that you know how to check whether a number is a quadratic residue, it's time to find its square roots.

If \( p \equiv 3 \pmod{4} \), then \( p + 1 \) is divisible by 4. If we want to find the square root of \( a \) modulo \( p \), then:

$$ \left( \pm a^{\frac{p+1}{4}} \right)^2 \equiv a^{\frac{p+1}{2}} \equiv a^{\frac{p-1}{2} + 1} = a^{\frac{p-1}{2}} \times a \equiv 1 \times a = a \pmod{p} $$

But since \( a \) was chosen to be a quadratic residue (otherwise, it has no square roots), it follows that:

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod{p} $$

Thus, the two square roots of \( a \) modulo \( p \) can be very easily computed as:

$$ \pm a^{\frac{p+1}{4}} $$

Example 1: When the Rule Applies

Let's take \( p = 7 \) and \( a = 2 \). First, we check whether \( p \equiv 3 \pmod{4} \):

$$ 7 \equiv 3 \pmod{4} $$

Now, to check if \( 2 \) is a quadratic residue modulo 7, we can use the Legendre symbol:

$$ \left(\frac{2}{7}\right) $$

Since \( 2^{\frac{7-1}{2}} \equiv 2^3 \equiv 8 \equiv 1 \pmod{7} \), it follows that:

$$ \left(\frac{2}{7}\right) = 1 $$

This indicates that \( 2 \) is a quadratic residue modulo 7. We can now find the square roots using the formula:

$$ x \equiv \pm 2^{\frac{7+1}{4}} \equiv \pm 2^2 \equiv \pm 4 \pmod{7} $$

So, the square roots of 2 modulo 7 are 4 and 3 (since \(-4 \equiv 3 \pmod{7}\)).

Example 2: When the Rule Does Not Apply

Now consider \( p = 7 \) and \( a = 3 \). Again, \( p = 7 \) satisfies \( p \equiv 3 \pmod{4} \), so we proceed to check if \( 3 \) is a quadratic residue modulo 7 using the Legendre symbol:

$$ \left(\frac{3}{7}\right) $$

Calculate:

$$ 3^{\frac{7-1}{2}} = 3^3 = 27 \equiv 6 \pmod{7} $$

Since \(6 \not\equiv 1 \pmod{7}\), it follows that:

$$ \left(\frac{3}{7}\right) = -1 $$

This indicates that \( 3 \) is not a quadratic residue modulo 7, meaning it has no square roots modulo 7, and thus the formula does not apply.

Finding Square Roots with the Tonelli-Shanks Algorithm

For primes \( p \) where \( p \equiv 1 \pmod{4} \), or when more general cases are needed, the Tonelli-Shanks algorithm is typically used to find square roots modulo a prime. This algorithm works for any odd prime \( p \) and is capable of finding the square roots when they exist, even when the simple formula for \( p \equiv 3 \pmod{4} \) does not apply. Luckily, this algorithm has a lot of implementations in various established libraries, making it easier for you to apply without having to implement it from scratch.

Chinese Remainder Theorem

The last thing I want to introduce is the Chinese Remainder Theorem, which allows us to find an integer \(x\) that satisfies a system of simultaneous congruences like:

$$ x \equiv 2 \pmod{5} $$ $$ x \equiv 3 \pmod{11} $$ $$ x \equiv 5 \pmod{17} $$

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem states that if you have a system of simultaneous congruences:

$$ x \equiv a_1 \pmod{m_1} $$ $$ x \equiv a_2 \pmod{m_2} $$ $$ \vdots $$ $$ x \equiv a_k \pmod{m_k} $$

where the moduli \(m_1, m_2, \dots, m_k\) are pairwise coprime (i.e., \(\gcd(m_i, m_j) = 1\) for all \(i \neq j\)), then there exists a unique solution modulo \(M\), where \(M = m_1 \times m_2 \times \cdots \times m_k\).

Finding the Solution

To find the solution \(x\) that satisfies the system of congruences, we can follow these steps:

1. Compute the product \(M\):

$$ M = m_1 \times m_2 \times \cdots \times m_k $$

For our example:

$$ M = 5 \times 11 \times 17 = 935 $$

1. For each congruence, calculate the partial product \(M_i\):

$$ M_i = \frac{M}{m_i} $$

For the first congruence:

$$ M_1 = \frac{935}{5} = 187 $$

For the second congruence:

$$ M_2 = \frac{935}{11} = 85 $$

For the third congruence:

$$ M_3 = \frac{935}{17} = 55 $$

1. Find the modular inverses \(N_i\) of each \(M_i\) modulo \(m_i\):

The modular inverse \(N_i\) is a number such that:

$$ N_i \times M_i \equiv 1 \pmod{m_i} $$

For \(M_1 = 187\) modulo 5:

$$ N_1 = 3 $$ (because \(187 \times 3 \equiv 1 \pmod{5}\))

For \(M_2 = 85\) modulo 11:

$$ N_2 = 6 $$ (because \(85 \times 6 \equiv 1 \pmod{11}\))

For \(M_3 = 55\) modulo 17:

$$ N_3 = 9 $$ (because \(55 \times 9 \equiv 1 \pmod{17}\))

1. Compute the solution \(x\) as the sum of products:

$$ x = \sum_{i=1}^{k} a_i \times M_i \times N_i $$

Substituting the values:

$$ x = (2 \times 187 \times 3) + (3 \times 85 \times 6) + (5 \times 55 \times 9) $$

$$ x = 1122 + 1530 + 2475 $$

$$ x = 5127 $$

1. Reduce \(x\) modulo \(M\):

$$ x \equiv 5127 \pmod{935} $$

$$ x = 5127 \mod 935 = 572 $$

So the solution to the system of congruences is:

$$ x \equiv 572 \pmod{935} $$

Summary

The Chinese Remainder Theorem is a powerful tool in number theory and modular arithmetic, allowing us to solve systems of congruences with different moduli that are pairwise coprime. The theorem guarantees a unique solution modulo the product of the moduli, and the steps outlined above provide a systematic way to find that solution. Luckily, there are also many libraries and tools that have implemented this algorithm, making it easy to apply in practice.

In this post, I have covered all the necessary theory and information to move forward with cryptography algorithms and attacks in future posts. Understanding these foundational concepts is crucial for delving into more advanced topics in cryptography, and I hope this serves as a solid base for what's to come.