Modular Arithmetic#
Modular arithmetic operates with the remainders of integers when they are divided by a fixed positive integer called the modulus. For the applications such as primality testing and cryptography it is necessary to deal with numbers which are much larger than 32 bits but whose range is nonetheless limited. Modular arithmetic is a system for dealing with restricted ranges of integers.
Ways to think about modular arithmetic:
Modular arithmetic limits numbers to a predefined range \(\{ 0, 1, \dotsc, m - 1 \}\) and wraps around whenever you try to leave this range.
Modular arithmetic deals with all the integers but partitions them into \(m\) equivalence classes each of the form \(\{ i + kN : k \in \mathbb{Z} \}\) for some \(i\) between \(0\) and \(N - 1\)
Congruence#
The congruence relation#
\(a = b \textbf{ mod } m\) versus \(a \equiv b \mod m\)#
Properties#
\( \begin{aligned} n \mid (a - b) \quad & \iff \quad nk = a - b \\ \quad & \iff \quad a \equiv b \mod n \\ n \mid (a - b) \quad & \iff \quad n \mid (a \pm c - (b \pm c)) \\ \quad & \iff \quad nk = a \pm c - (b \pm c) \\ \quad & \iff \quad a \pm c \equiv b \pm c \mod n \\ n \mid (a - b) \quad & \iff \quad n (k/c) = a - b \\ \quad & \iff \quad nk = ca - cb \\ \quad & \iff \quad ca \equiv cb \mod n \\ \end {aligned} \)
Factoring a scalar out of a congruence#
CLAIM
\(kx \equiv ka \mod n \iff x \equiv a \mod n/d\) where \(d = \gcd(n, k)\)
The modulus changes when dividing a congruence if you are dividing both sides of the congruence by a number that is not relatively prime to the modulus. In other words, if the number you’re dividing by shares a common factor with the modulus, you must also divide the modulus by that same common factor to maintain the congruence relation.
PROOF
\(kx \equiv ka \mod n \iff n \mid k(x - a) \iff n/d \mid (k/d)(x - a)\) where \(d = \gcd(n, k)\)
\( \begin{aligned} \frac{n}{\gcd(n, k)} \Biggm\vert\left( \frac{k}{\gcd(n, k)}(x - a) \right) \end {aligned} \)
By Euclid’s Lemma we know that
\(n/d \mid (k/d)(x - a) \implies\) either \(n/d \mid k/d\) or \(n/d \mid (x - a)\)
And we know that
\( \gcd(n/d, k/d) = \begin{aligned} \gcd\left( \frac{n}{\gcd(n, k)}, \frac{k}{\gcd(n, k)} \right) = 1 \end {aligned} \)
Thus it must be the case that
\(n/d \mid (x - a) \iff x \equiv a \mod n/d\)
\(\blacksquare\)
https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html
\( \begin{aligned} 65y & \equiv & 5 & \mod 10 \\ 5.13y & \equiv & 5.1 & \mod 10/\gcd(5, 10) \\ 13y & \equiv & 1 & \mod 2 \\ \end {aligned} \)
Congruences modulo \(m\) partition the integers into \(m\) equivalence or residue classes.
Multiplicative inverse modulo \(m\)#
import numpy as np
def euclidex (m : int,
n : int) -> int:
assert(n > 0)
assert(m >= n)
np.set_printoptions(formatter={'all': lambda x: f"{x:>{1+len(str(m))}}"})
print(f"{'r':>{2+len(str(m))}}{'x':>{2+len(str(m))}}{'y':>{2+len(str(m))}}")
u = np.array([m, 1, 0]) # u = [m, 1, 0] (as Python list)
v = np.array([n, 0, 1]) # v = [n, 0, 1] (as Python list)
while v[0] > 0:
print(f"{u}")
q = u[0] // v[0] # math: floor(u_0 / v_0)
w = u - q*v
u = v
v = w
# print (f"{u}")
return u
a = 1031
b = 71
print(euclidex(a, b))
r x y
[ 1031 1 0]
[ 71 0 1]
[ 37 1 -14]
[ 34 -1 15]
[ 3 2 -29]
[ 1 -23 334]
Modular Arithmetic#
Modular Addition#
To add two numbers \(x\) and \(y\) modulo \(N\) we start with regular addition. \(x\) and \(y\) are each in the range \(0\) to \(N - 1\) so their sum is in the range \(0\) to \(2(N - 1)\). When the sum exceeds \(N - 1\) we subtract \(N\) so that it falls back into the range \(0\) to \(N - 1\). The overall computations consists of an addition and a possible subtraction of numbers which never exceed \(2N\).
\(T(n) = O(n)\) where \(n = \lceil \log N \rceil\)
Modular Multiplication#
To multiply two numbers \(x\) and \(y\) modulo \(N\), we start with regular multiplication and then reduce the answer modulo \(N\). The product can be as large as \((N - 1)^2\) but this is still at most \(2n\) bits long since \(\log (N - 1)^2 = 2 \log (N - 1) \le 2n\). To reduce the answer modulo \(N\) we compute the remainder upon dividing it by \(N\) using the quadratic-time division algorithm. Multiplication thus remains a quadratic operation.
Complexity
\(T(n) = \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{multiplication}} + \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{reduction modulo \textit{N} via division}} = O(n^2)\)
Modular Division#
In ordinary arithmetic there is just one tricky case–division by zero. In modular arithmetic there are other tricky cases.
When division is legal, its running time is
\(T(n) = O(n^3)\)
Modular Exponentiation#
Can \(x^y \mod N\) be computed quickly for values of \(x\), \(y\), and \(N\) that are several hundred bits long? The result is some number modulo \(N\) and is therefore itself a few hundred bits long. The raw value \(x^y\) could be much longer. When \(x\) and \(y\) are just \(20\text{-b}\) numbers \(x^y\) is at least \((2^{19})^{2^{19}} = 2^{(19)(524,288)}\) which is about ten million bits long. Imagine what would happen if \(y\) is a \(500\text{-b}\) number. To make sure the numbers we are dealing with never grow too large, we need to perform all intermediate computations modulo \(N\).
Calculate \(x^y \mod N\) by repeatedly multiplying by \(x \mod N\). The resulting sequence of intermediate products \(x \mod N \to x^2 \mod N \to \dotsb \to x^y \mod N\) consists of numbers smaller than \(N\), so the individual multiplications do not take too long. But if \(y\) is \(500\) bits long we need to perform \(y - 1 \approx 2^{500}\) multiplications which is exponential in the size of \(y\).
It will be better to start with \(x\) and repeatedly square modulo \(N\): \(x \mod N \to x^2 \mod N \to x^4 \mod N \to x^8 \mod N \to \dotsb \to x^{2^{\lfloor \log y \rfloor}} \mod N\).
Each squaring takes \(O(\log^2 N)\) and there are \(\log y\) multiplications
To determine \(x^y \mod N\) multiply together the subset of these powers corresponding to \(1\) s in the binary representation of \(y\).
EXAMPLE
algorithm decomposition
\(x^{25} = x^{11001_2} = x^{10000_2} \cdot x^{1000_2} \cdot x^{1_2} = x^{16} \cdot x^8 \cdot x^1\)
For multiplication the terms \(x \cdot 2^i\) come from repeated doubling. For exponentiation the terms \(x^{2^i}\) come from repeated squaring
This algorithm implements the following recursive rule.
\( x^y = \begin{cases} (x^{\lfloor y/2 \rfloor})^2 & \text{if \textit{y} is even} \\ x \cdot (x^{\lfloor y/2 \rfloor})^2 & \text{if \textit{y} is odd} \\ \end {cases} \)
INPUT two n-bit integers x and N, and an integer exponent y
OUTPUT x^y mod N
MODEXP (x, y, N)
1 if y = 0
2 return 1
3
4 z = MODEXP(x, floor(y/2), N)
5
6 if even(y)
7 return z^2 mod N
8 else
9 return xz^2 mod N
Correctness
The recursive rule is transparently correct. Checking that the algorithm is correct is a matter of verifying that it mimics the rule and that it handles the base case \(y = 1\) properly.
Complexity
Let \(n\) be the size in bits of \(x\), \(y\), and \(N\) (whichever is the largest of the three). As with multiplication, the algorithm will halt after at most \(n\) recursive calls and during each call it multiplies \(n\)-bit numbers (doing computation modulo \(N\) saves us here) for a total running time of
\(T(n) = \underbrace{\quad\quad O(n) \quad\quad}_{\text{recursive calls}} \times \underbrace{\quad\quad O(n^2) \quad\quad}_{\text{multiplication}} = O(n^3)\)
Python#
\( \begin{aligned} s^d = \begin{cases} ss^{2(d-1)/2} & d \text{ odd} \\ s^{2d/2} & d \text{ even} \\ \end {cases} \end {aligned} \)
\( \begin{aligned} s^{10} &= (s^2)^{5} \\ s^{5} &= s(s^2)^2 \\ \end {aligned} \)
Multiplicative Inverse