Training Computer Engineering Modular Arithmetic & Cryptography Math
4 / 5

Modular Arithmetic & Cryptography Math

24 min Computer Engineering

Modular Arithmetic & Cryptography Math

Modular arithmetic underpins computer science topics from hashing to cryptography. It works with remainders after division.

Modular Arithmetic

$$a \equiv b \pmod{m} \iff m \mid (a - b)$$

"$a$ is congruent to $b$ mod $m$" means $a$ and $b$ have the same remainder when divided by $m$.

Properties

If $a \equiv b$ and $c \equiv d$ (mod $m$), then:

  • $(a + c) \equiv (b + d) \pmod{m}$
  • $(a \cdot c) \equiv (b \cdot d) \pmod{m}$
  • $a^n \equiv b^n \pmod{m}$
GCD & Euclidean Algorithm

$$\gcd(a, b) = \gcd(b, a \bmod b)$$

Repeat until remainder is 0. The last non-zero remainder is the GCD.

Example 1

Find $17 \bmod 5$.

$17 = 3 \times 5 + 2$, so $17 \bmod 5 = 2$.

Example 2

Find $\gcd(252, 198)$ using the Euclidean algorithm.

$252 = 1 \times 198 + 54$
$198 = 3 \times 54 + 36$
$54 = 1 \times 36 + 18$
$36 = 2 \times 18 + 0$

$\gcd(252, 198) = 18$

Example 3

Compute $7^{100} \bmod 10$ (find the last digit of $7^{100}$).

Powers of 7 mod 10 cycle: $7, 9, 3, 1, 7, 9, 3, 1, \ldots$ (period 4).

$100 \bmod 4 = 0$, so $7^{100} \equiv 7^0 \equiv 1 \pmod{10}$. Last digit is $1$.

Practice Problems

1. Find $29 \bmod 7$.
2. Is $45 \equiv 15 \pmod{10}$?
3. Find $\gcd(84, 36)$.
4. Find $(13 + 19) \bmod 7$.
5. Find $(8 \times 7) \bmod 5$.
6. Find the last digit of $3^{50}$.
7. Find $\gcd(1071, 462)$.
8. RSA key: if $p = 5$, $q = 11$, find $n = pq$ and $\phi(n) = (p-1)(q-1)$.
9. Find $e$ such that $\gcd(e, \phi(n)) = 1$ for $\phi = 40$ from #8. Choose the smallest $e > 1$.
10. What is $2^{10} \bmod 1000$?
11. Find the multiplicative inverse of 3 mod 11 (find $x$ such that $3x \equiv 1 \pmod{11}$).
12. A hash function: $h(k) = k \bmod m$ where $m = 13$. Find $h(47)$, $h(26)$, $h(13)$.
Show Answer Key

1. $29 = 4 \times 7 + 1$; answer: $1$

2. $45 - 15 = 30$; $10 \mid 30$ ✓ — yes, $45 \equiv 15 \pmod{10}$

3. $84 = 2 \times 36 + 12$; $36 = 3 \times 12 + 0$; $\gcd = 12$

4. $32 \bmod 7 = 4$

5. $56 \bmod 5 = 1$

6. $3^1=3, 3^2=9, 3^3=7, 3^4=1$ (mod 10, period 4); $50 \bmod 4 = 2$; last digit is $9$

7. $1071 = 2(462) + 147$; $462 = 3(147) + 21$; $147 = 7(21) + 0$; $\gcd = 21$

8. $n = 55$, $\phi = 40$

9. $\gcd(3, 40) = 1$; $e = 3$

10. $2^{10} = 1{,}024$; $1{,}024 \bmod 1000 = 24$

11. $3 \times 4 = 12 \equiv 1 \pmod{11}$; inverse is $4$

12. $h(47) = 47 \bmod 13 = 8$; $h(26) = 0$; $h(13) = 0$ (collision with 26)

Algorithm Complexity — Big-O Notation Placement Test Practice — Computer Engineering