Skip to content

Appendix A: Mathematical Reference

This appendix provides a quick-reference for mathematical notation, identities, and algorithms used throughout the text.

A.1 Number Theory Quick Reference

Identity / Property Statement
Euler’s Theorem \(a^{\phi(n)} \equiv 1 \pmod{n}\) if \(\gcd(a,n) = 1\)
Fermat’s Little Theorem \(a^{p-1} \equiv 1 \pmod{p}\) if prime \(p \nmid a\)
Wilson’s Theorem \((p-1)! \equiv -1 \pmod{p}\) for prime \(p\)
Euler Totient \(\phi(pq) = (p-1)(q-1)\); \(\phi(p^k) = p^{k-1}(p-1)\)
Carmichael Function \(\lambda(n) = \text{lcm}(p_1^{a_1-1}(p_1-1), …)\)
CRT Unique \(x \bmod \prod n_i\) from \(x \equiv a_i \pmod{n_i}\)

A.2 Modular Arithmetic Operations

Extended Euclidean Algorithm:

def xgcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = xgcd(b, a
    return g, y, x - (a // b) * y

# Modular inverse: a^{-1} mod n
def modinv(a, n):
    g, x, _ = xgcd(a
    if g != 1: raise ValueError("No inverse")
    return x

Square-and-multiply exponentiation:

def powmod(base, exp, mod):
    result = 1
    base
    while exp > 0:
        if exp & 1:
            result = result * base
        base = base * base
        exp >>= 1
    return result

Miller-Rabin primality test:

def is_prime(n, k=10):
    """Probabilistic primality test, k rounds."""
    if n < 2: return False
    if n in (2, 3): return True
    if n
    # Write n-1 = 2^r * d
    r, d = 0, n - 1
    while d
        r += 1; d //= 2
    import random
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = x * x
            if x == n - 1: break
        else:
            return False
    return True

A.3 Group Theory Reference

Group Operation Order
\(\mathbb{Z}_n\) Addition mod \(n\) \(n\)
\(\mathbb{Z}_n^*\) Multiplication mod \(n\) \(\phi(n)\)
\(\mathbb{Z}_p^*\) (prime \(p\)) Multiplication \(p-1\)
\(E(\mathbb{F}_p)\) Point addition \(\approx p\) (Hasse’s theorem)
\((\{0,1\}^n, \oplus)\) XOR \(2^n\)

A.4 Information Theory

\[\begin{align*} H(X) &= -\sum_x p(x) \log_2 p(x) \quad \text{(Shannon entropy, bits)} \\ H_\infty(X) &= -\log_2 \max_x p(x) \quad \text{(min-entropy)} \\ H(X|Y) &= H(X,Y) - H(Y) \quad \text{(conditional entropy)} \\ I(X;Y) &= H(X) - H(X|Y) \quad \text{(mutual information)} \end{align*}\]

Entropy of common password policies:

Character Set Length Entropy
Digits \(\{0\)-\(9\}\) 4 \(4 \log_2 10 \approx 13.3\) bits
Lowercase 8 \(8 \log_2 26 \approx 37.6\) bits
Alphanumeric 12 \(12 \log_2 62 \approx 71.4\) bits
All printable ASCII (95) 16 \(16 \log_2 95 \approx 105.1\) bits
BIP-39 word list (\(2^{11}\)) 12 words 132 bits

A.5 Complexity Classes

Class Description Example
P Polynomial time (classical) AES encryption
NP Non-deterministic polynomial SAT, Graph Coloring
BQP Bounded-error quantum polynomial Factoring (Shor)
NP-hard At least as hard as NP RSA factoring (believed)
\(\mathsf{negl}(\lambda)\) Negligible function PRF advantage

A.6 Elliptic Curve Standard Parameters

Curve25519 (RFC 7748):

\[\begin{align*} p &= 2^{255} - 19 \\ A &= 486662 \quad \text{(Montgomery form: } y^2 = x^3 + Ax^2 + x\text{)} \\ \text{Order } n &= 2^{252} + 27742317777372353535851937790883648493 \\ h &= 8 \quad \text{(cofactor)} \end{align*}\]

P-256 (secp256r1, NIST FIPS 186-5):

\[\begin{align*} p &= 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 \\ a &= p - 3 \\ n &= \texttt{0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551} \\ h &= 1 \end{align*}\]