Modular Arithmetic#
Contents#
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, N - 1 \}\) and wraps around whenever you try to leave this range.
modular arithmetic deals with all the integers, but divides them into \(N\) equivalence classes each of the form \(\{ i + kN : k \in \mathbb{Z} \}\) for some \(i\) between \(0\) and \(N - 1\)
\(a \textbf{ mod } d\) is defined to be the remainder when \(a\) is divided by \(d\)
\(a \textbf{ mod } d := r\) when \(a = qd + r\) with \(0 \le r \lt d\)
If \(a\) and \(b\) are integers and \(m\) is a positive integer then \(a\) is congruent to \(b\) modulo \(m\) if \(m\) divides \(a - b\).
\( \begin{aligned} a \equiv b \mod m &\iff m | (a - b) &&\iff a = b + km \\ a \equiv 0 \mod m &\iff m | a &&\iff a = km \\ a \equiv 1 \mod m &\iff m | (a - 1) &&\iff a = 1 + km \\ \end {aligned} \)
We say that \(a \equiv b \mod m\) is a congruence and that \(m\) is its modulus.
\(253 \equiv 13 \,(\text{mod } 60)\) because \(253 - 13\) is a multiple of \(60\). (\(253\) minutes is \(4\) hours and \(13\) minutes.)
\(59 \equiv -1 \,(\text{mod } 60)\) because \(59 - (-1)\) is a multiple of \(60\). (When it’s \(59\) minutes past the hour it’s also one minute short of the next hour.)
\(a \equiv b \mod m\) represents a relation on the set of integers.
\(a \textbf{ mod } m = b\) represents a function.
Let \(a\) and \(b\) be integers and \(m\) be a positive integer. Then \(a \equiv b \mod m\) iff \(a \textbf{ mod } m = b \textbf{ mod } m\). (“a and b are congruent modulo m iff a and b have the same remainder when divided by m”)
Substitution Rule
If \(x \equiv x' \,(\text{mod } N)\) and \(y \equiv y' \,(\text{mod } N)\) then \(x + y \equiv x' + y' \,(\text{mod } N)\) and \(xy \equiv x'y' \,(\text{mod } N)\).
Associativity
\(x + (y + z) \equiv (x + y) + z \quad(\text{mod } N)\)
Commutativity
\(xy \equiv yz \quad(\text{mod } N)\)
Distributivity
\(x(y + z) \equiv xy + xz \quad(\text{mod } N)\)
The four rules imply that while performing a sequence of arithmetic operations it is legal to reduce intermediate results to their remainders modulo \(N\) at any stage:
\(2^{345} \equiv (2^5)^{69} \equiv 32^{69} \equiv 1^{69} \equiv 1 \quad(\text{mod } 31)\)
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)\)
Acknowledgements#
2006 Dasgupta, Sanjoy; Christos Papadimitriou; & Umesh Vazirani. Algorithms. Chapter 1. McGraw-Hill.
2018 Rosen, Kenneth. Discrete Mathematics and its Applications 8e. McGraw-Hill.