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*}\]