Counting and number theory for computing

Two branches of discrete mathematics are used constantly in computing. Combinatorics counts things: how many passwords of a given form exist, how many ways a test suite can be ordered, how many subsets an algorithm might examine. Number theory studies the integers, and its modular arithmetic underlies hashing, checksums, random number generators and public-key cryptography. This lesson introduces both, ending with a toy version of RSA. MATH-260 (Discrete Mathematics) and MATH-351 (Number Theory) go much further.

The sum and product rules

Two rules underlie nearly all counting. The sum rule: if a task can be done in one of \(m\) ways or in one of \(n\) other ways, with no overlap, there are \(m + n\) ways. The product rule: if a task consists of a first step with \(m\) choices followed by a second step with \(n\) choices, regardless of the first choice, there are \(mn\) ways. The product rule is the counting form of \(|A \times B| = |A||B|\) from lesson 7, and the sum rule is \(|A \cup B| = |A| + |B|\) for disjoint sets.

total = 62 ** 8
no_digit = 52 ** 8
print(f"total:            {total:,}")
print(f"at least 1 digit: {total - no_digit:,}")
rate = 10 ** 10                 # guesses per second, an illustrative offline attack rate
print(f"exhaustive search at 10^10 guesses/s: {total / rate / 3600:.1f} hours")
print(f"length 12 instead: {62 ** 12 / rate / (3600 * 24 * 365):,.0f} years")

total:            218,340,105,584,896
at least 1 digit: 164,880,377,053,440
exhaustive search at 10^10 guesses/s: 6.1 hours
length 12 instead: 10,230 years

Permutations

A permutation is an ordered arrangement. The number of ways to arrange \(n\) distinct objects in a row is \(n! = n(n-1)(n-2)\cdots 1\), by the product rule: \(n\) choices for the first position, \(n - 1\) for the second, and so on. The number of ways to choose and arrange \(r\) of \(n\) objects is

Factorials grow astonishingly fast. There are \(10! = 3,628,800\) orders for 10 tasks, and \(20! \approx 2.4 \times 10^{18}\) orders for 20. An algorithm that tries every ordering, such as a brute-force solution to the traveling salesperson problem, becomes useless beyond a few dozen items.

Combinations

A combination is an unordered selection. The number of ways to choose \(r\) objects from \(n\), read n choose r, is

The formula comes from dividing permutations by the \(r!\) orders in which each selection could be arranged. Choosing a 5-card hand from 52 cards gives \(\binom{52}{5} = 2,598,960\) hands. A useful identity is \(\binom{n}{r} = \binom{n}{n-r}\): choosing which \(r\) to take is the same as choosing which \(n - r\) to leave.

from math import comb, perm, factorial
from itertools import combinations, permutations
print("P(5,3) =", perm(5, 3), " = len(permutations):", len(list(permutations("abcde", 3))))
print("C(5,3) =", comb(5, 3), " = len(combinations):", len(list(combinations("abcde", 3))))
print("C(52,5) =", f"{comb(52, 5):,}")
print("20! =", f"{factorial(20):,}")
print("C(10,3) == C(10,7):", comb(10, 3) == comb(10, 7))

P(5,3) = 60  = len(permutations): 60
C(5,3) = 10  = len(combinations): 10
C(52,5) = 2,598,960
20! = 2,432,902,008,176,640,000
C(10,3) == C(10,7): True

The binomial theorem and Pascal's triangle

The numbers \(\binom{n}{r}\) are called binomial coefficients because they appear when \((x + y)^n\) is expanded. Each term of the expansion picks \(x\) or \(y\) from each of the \(n\) factors, and the number of ways to pick \(y\) exactly \(r\) times is \(\binom{n}{r}\).

Setting \(x = y = 1\) gives \(\sum_r \binom{n}{r} = 2^n\), which is the power set count of lesson 7 in another form: subsets of an \(n\)-element set, grouped by size. Pascal's identity, \(\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\), says that a subset of size \(r\) either contains a particular element (choose the other \(r - 1\) from the rest) or does not (choose all \(r\) from the rest). It generates Pascal's triangle, where each entry is the sum of the two above it.

row = [1]
for n in range(8):
    print(f"n={n}: " + " ".join(f"{x:3d}" for x in row).center(40), " sum =", sum(row))
    row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]

n=0:                     1                     sum = 1
n=1:                   1   1                   sum = 2
n=2:                 1   2   1                 sum = 4
n=3:               1   3   3   1               sum = 8
n=4:             1   4   6   4   1             sum = 16
n=5:           1   5  10  10   5   1           sum = 32
n=6:         1   6  15  20  15   6   1         sum = 64
n=7:       1   7  21  35  35  21   7   1       sum = 128

Divisibility, primes and the greatest common divisor

Number theory begins with the division algorithm: for integers \(a\) and \(d > 0\), there are unique integers \(q\) (the quotient) and \(r\) (the remainder) with \(a = dq + r\) and \(0 \le r < d\). In Python, q = a // d and r = a % d, and Python's % always returns a non-negative remainder for positive \(d\), even when \(a\) is negative: -7 % 3 is 2, because \(-7 = 3 \cdot (-3) + 2\). Some languages, including C, behave differently for negative numbers, a frequent source of bugs.

The greatest common divisor \(\gcd(a, b)\) is the largest integer dividing both \(a\) and \(b\). Euclid's algorithm computes it efficiently using the fact that \(\gcd(a, b) = \gcd(b, a \bmod b)\): any common divisor of \(a\) and \(b\) also divides \(a - qb = r\), and conversely. The algorithm repeats until the remainder is 0. It is one of the oldest algorithms still in daily use, and it runs in a number of steps proportional to the number of digits.

def gcd_trace(a, b):
    while b:
        print(f"gcd({a}, {b}): {a} = {b} * {a // b} + {a % b}")
        a, b = b, a % b
    return a

print("result:", gcd_trace(252, 198))
print("-7 % 3 =", -7 % 3, "   -7 // 3 =", -7 // 3)

gcd(252, 198): 252 = 198 * 1 + 54
gcd(198, 54): 198 = 54 * 3 + 36
gcd(54, 36): 54 = 36 * 1 + 18
gcd(36, 18): 36 = 18 * 2 + 0
result: 18
-7 % 3 = 2    -7 // 3 = -3

The extended Euclidean algorithm also finds integers \(s\) and \(t\) with \(sa + tb = \gcd(a, b)\), a fact known as Bézout's identity. Those coefficients are exactly what is needed to compute modular inverses, below.

Modular arithmetic

We write \(a \equiv b \pmod{n}\), read a is congruent to b modulo n, when \(n\) divides \(a - b\), that is, when \(a\) and \(b\) have the same remainder on division by \(n\). Lesson 9 showed that congruence modulo \(n\) is an equivalence relation with \(n\) classes. Its key property is that it respects addition and multiplication: if \(a \equiv b\) and \(c \equiv d \pmod{n}\), then \(a + c \equiv b + d\) and \(ac \equiv bd \pmod{n}\). So you can reduce modulo \(n\) at every step of a calculation and still get the right remainder at the end, which keeps numbers small.

This property justified the finite check in lesson 6: the remainder of \(n^2\) mod 8 depends only on the remainder of \(n\) mod 8. Clocks, days of the week, hash tables (key mod table size), checksums and the wraparound of fixed-width integers (arithmetic mod \(2^{32}\) or \(2^{64}\)) are all modular arithmetic.

A number \(b\) is a modular inverse of \(a\) modulo \(n\) if \(ab \equiv 1 \pmod{n}\). An inverse exists exactly when \(\gcd(a, n) = 1\). For example, 3 has inverse 7 modulo 10 because \(3 \cdot 7 = 21 \equiv 1\), but 4 has no inverse modulo 10. Python 3.8 and later compute inverses with pow(a, -1, n).

def egcd(a, b):
    """Return (g, s, t) with s*a + t*b == g == gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, s, t = egcd(b, a % b)
    return g, t, s - (a // b) * t

g, s, t = egcd(240, 46)
print(f"gcd = {g}, {s}*240 + {t}*46 = {s * 240 + t * 46}")
print("inverse of 3 mod 10:", pow(3, -1, 10), "  check:", 3 * pow(3, -1, 10) % 10)
try:
    pow(4, -1, 10)
except ValueError as e:
    print("4 mod 10:", e)

gcd = 2, -9*240 + 47*46 = 2
inverse of 3 mod 10: 7   check: 1
4 mod 10: base is not invertible for the given modulus

A toy RSA example

RSA, published in 1977 by Rivest, Shamir and Adleman, was the first widely used public-key cryptosystem. It lets anyone encrypt a message with a public key that only the holder of a private key can decrypt. Its mathematics uses everything in this lesson. The tiny numbers below make the arithmetic visible; real RSA uses primes hundreds of digits long, careful padding schemes and vetted libraries, and must never be implemented by hand for real use. CISSP-112 covers cryptography from a security perspective and CMPUT-331 from a computing one.

p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)
print(f"n = {n}, phi = {phi}, e = {e}, d = {d}, e*d mod phi = {e * d % phi}")
for m in [65, 1234, 3000]:
    c = pow(m, e, n)
    print(f"m = {m:4d} -> c = {c:4d} -> decrypted {pow(c, d, n)}")

n = 3233, phi = 3120, e = 17, d = 2753, e*d mod phi = 1
m =   65 -> c = 2790 -> decrypted 65
m = 1234 -> c = 2183 -> decrypted 1234
m = 3000 -> c = 1780 -> decrypted 3000

Why does decryption recover \(m\)? Because \(ed \equiv 1 \pmod{\varphi}\), so \(ed = 1 + k\varphi\) for some \(k\), and Euler's theorem from number theory says \(m^{\varphi} \equiv 1 \pmod{n}\) when \(\gcd(m, n) = 1\). Then \(c^d = m^{ed} = m \cdot (m^{\varphi})^k \equiv m \pmod{n}\). Security rests on the belief that factoring \(n\) into \(p\) and \(q\) is infeasible for large \(n\); anyone who could factor \(n\) could compute \(\varphi\) and then \(d\). Large quantum computers running Shor's algorithm could factor efficiently, which is why standards bodies are moving to post-quantum algorithms.