Difficulty: Intermediate | Prerequisites: Modular arithmetic basics, prime numbers, matrix multiplication, the Euclidean algorithm.
These topics sit at the intersection of number theory and algorithm design. The fingerprinting protocol uses modular arithmetic to compress large inputs (bit strings) into small "fingerprints" that can be compared cheaply. Matrix verification uses randomised spot-checking to avoid the cost of full multiplication. The Extended Euclidean Algorithm is the workhorse behind modular inverses, which underpin RSA and other cryptographic protocols. You should be comfortable with modular congruences, prime factorisation, and basic matrix operations before diving in.
Fingerprinting compresses bit strings using modular arithmetic so two parties can check equality by exchanging only a small fingerprint, not the whole string. Matrix multiplication can be verified in O(n²) time by multiplying both sides by a random vector and comparing. The Extended Euclidean Algorithm computes modular inverses, which exist exactly when the number and the modulus are coprime.
Fingerprinting protocol
A randomised method for comparing two large values (e.g. bit strings) by reducing them modulo a randomly chosen prime and comparing the residues. Think of it as hashing both strings down to a small number and checking whether the hashes match.
Bad prime
A prime p for which the fingerprinting protocol incorrectly accepts two distinct strings, i.e. x mod p = y mod p even though x ≠ y. In simple terms, a bad prime is one that divides the difference |x - y|.
Spot-checking (matrix multiplication)
A randomised algorithm that verifies whether AB = C by picking a random binary vector r and checking whether ABr = Cr. Think of it as testing the equation on a random "probe" instead of computing the full product.
Multiplicative inverse (modular inverse)
Given x and modulus y with gcd(x, y) = 1, the unique integer x' (mod y) such that x · x' ≡ 1 (mod y). In simple terms, it is the number you multiply x by to get 1 in modular arithmetic.
Extended Euclidean Algorithm
An algorithm that, given x and y, returns gcd(x, y) together with integers a, b satisfying ax + by = gcd(x, y). Think of it as the standard Euclidean algorithm, but it keeps track of the coefficients at each step so you get the linear combination for free.
Alice has bit string x, Bob has bit string y. Both are interpreted as integers in base 2 (most significant bit first).
The protocol picks a random prime p and compares x mod p with y mod p.
If x = y, the fingerprints always match (no false negatives).
If x ≠ y, the fingerprints match only when p divides |x - y|. Such primes are the "bad" primes.
Worked example from HW 11:
x = 1000001101₂ = 525, y = 0100111011₂ = 315
|x - y| = 210 = 2 × 3 × 5 × 7
The bad primes are exactly the prime factors of 210: 2, 3, 5, 7.
For any other prime p, x mod p ≠ y mod p, and the protocol correctly rejects.
Why the protocol works well in general:
The number of prime factors of |x - y| is at most log₂|x - y|, which for n-bit strings is at most n. By choosing p from a sufficiently large pool of primes, the probability of hitting a bad prime is small.
Given n×n matrices A, B, and a claimed product C, we want to verify AB = C without computing AB directly (which costs O(n³)).
The algorithm picks a random binary vector r ∈ {0,1}ⁿ, then checks whether A(Br) = Cr. This costs only O(n²).
If AB = C, the algorithm always accepts (ABr = Cr for every r).
If AB ≠ C, define D = AB - C ≠ 0. The algorithm rejects when Dr ≠ 0, and accepts (wrongly) when Dr = 0.
Finding a rejecting vector rN:
Pick any r such that (AB - C)r ≠ 0. Since AB - C ≠ 0, at least one row of D has a nonzero entry. Choose r to "activate" that entry. For instance, if column j of D has a nonzero entry, set rⱼ = 1 and the rest to 0 (or use trial and error with specific vectors).
Finding an accepting vector rY:
Find a nonzero r in the null space of D = AB - C, i.e. a nonzero r with Dr = 0. This is a system of linear equations; any nonzero solution works.
Key probability guarantee:
For a uniformly random binary vector r, Pr[Dr = 0] ≤ 1/2 when D ≠ 0. So the algorithm catches errors with probability at least 1/2 on each trial.
x has a multiplicative inverse modulo y if and only if gcd(x, y) = 1 (they are coprime).
The Extended Euclidean Algorithm finds integers a, b such that ax + by = gcd(x, y). When gcd(x, y) = 1, the coefficient a gives x⁻¹ mod y (reduced mod y).
Worked example: x = 11, y = 26
Apply ExtendedEuclid(26, 11):
26 = 2 × 11 + 4, so recurse on (11, 4)
11 = 2 × 4 + 3, so recurse on (4, 3)
4 = 1 × 3 + 1, so recurse on (3, 1)
3 = 3 × 1 + 0, so recurse on (1, 0)
Base case: returns (1, 1, 0)
Unwinding:
(1, 0) → g=1, a=1, b=0
(3, 1) → a=0, b=1-0×3=1, so g=1, a=0, b=1. Check: 0×3+1×1=1. ✓
(4, 3) → a=1, b=0-1×1= -1. Check: 1×4+(-1)×3=1. ✓
(11, 4) → a=-1, b=1-(-1)×2=3. Check: (-1)×11+3×4=1. ✓
(26, 11) → a=3, b=(-1)-3×2= -7. Check: 3×26+(-7)×11=78-77=1. ✓
So 11 × (-7) ≡ 1 (mod 26). Reducing: -7 mod 26 = 19.
Therefore 11⁻¹ mod 26 = 19. Verification: 11 × 19 = 209 = 8 × 26 + 1. ✓
\text{Bad primes for fingerprinting: } p \text{ is bad} \iff p \mid (x - y)\text{Spot-check rule: accept iff } A(Br) = Cr\text{Modular inverse: } x \cdot x' \equiv 1 \pmod{y}, \quad \text{exists iff } \gcd(x,y) = 1\text{Extended Euclidean: returns } (g, a, b) \text{ with } ax + by = g = \gcd(x,y)Fingerprinting is the idea behind hash-based integrity checks: when you download a file and compare its SHA-256 hash to the published one, you are running the same compare-via-small-summary logic. Matrix verification spot-checking appears in scientific computing, where verifying a GPU's matrix multiplication result is cheaper than recomputing it. Modular inverses are the backbone of RSA encryption, where decryption requires computing a modular inverse of the public exponent.
Students often think that if fingerprints match, the strings must be equal. They need not be: a matching fingerprint only means p does not divide x - y. The protocol has one-sided error.
Students sometimes confuse "bad primes" with all primes up to some bound. Bad primes are specifically the prime factors of |x - y|, regardless of size.
When computing modular inverses, students forget that the inverse exists only when gcd(x, y) = 1. If gcd > 1, there is no inverse.
In the matrix spot-check, students sometimes think the algorithm can give false negatives (reject when AB = C). It cannot: if AB = C, then ABr = Cr for every r, always.
⚠️ Know how to identify bad primes: factor |x - y| and list its prime divisors.
⚠️ Be able to run the Extended Euclidean Algorithm by hand and extract the modular inverse from the coefficients.
⚠️ Understand one-sided vs two-sided error: fingerprinting and matrix spot-checking both have one-sided error (no false negatives, possible false positives).
⚠️ Be ready to find specific vectors r that make the spot-check accept or reject for a given set of matrices.
True or False: If x mod p = y mod p for some prime p, then x = y. (False: p could be a bad prime.)
Fill in the blank: A prime p is "bad" for fingerprinting when p divides ______. (|x - y|)
True or False: The matrix spot-check algorithm can incorrectly reject a correct product AB = C. (False: it has no false negatives.)
Fill in the blank: x⁻¹ mod y exists if and only if gcd(x, y) = ______. (1)
True or False: Running the Extended Euclidean Algorithm on (26, 11) will return gcd = 1. (True: 26 and 11 are coprime.)
Q: Alice's string is x = 1000001101 and Bob's string is y = 0100111011. What are all the bad primes?
A: x = 525, y = 315. |x - y| = 210 = 2 × 3 × 5 × 7. The bad primes are 2, 3, 5, and 7.
Q: In the matrix spot-check, what does it mean for a vector r to make the algorithm "wrongly accept"?
A: It means AB ≠ C but (AB - C)r = 0, so the algorithm cannot distinguish C from the true product on that particular probe.
Q: Compute 11⁻¹ mod 26 using the Extended Euclidean Algorithm.
A: Run ExtendedEuclid(26, 11) to get coefficients satisfying a·26 + b·11 = 1. The coefficient b = -7 gives 11 × (-7) ≡ 1 (mod 26). Reducing, -7 mod 26 = 19. So 11⁻¹ mod 26 = 19.
Q: Why does the spot-check algorithm have no false negatives?
A: If AB = C, then D = AB - C = 0, so Dr = 0 for every vector r. The algorithm always computes ABr = Cr and accepts.
Q: How many bad primes can there be for two n-bit strings?
A: At most n, because |x - y| < 2ⁿ and any integer less than 2ⁿ has at most n prime factors (counted with multiplicity).
Fingerprinting connects directly to hashing and the birthday paradox: both rely on collisions being unlikely when the output space is large. The Extended Euclidean Algorithm reappears in RSA key generation (EECS 376 later material and EECS 478/578 cryptography courses). The spot-checking idea generalises to polynomial identity testing (see the Spot-Checking Polynomials notes), where the same "evaluate at a random point" strategy verifies polynomial identities.
Fingerprinting protocol, bad primes, modular arithmetic, mod, congruence, Freivalds' algorithm, matrix verification, spot-checking, random vector, multiplicative inverse, modular inverse, Extended Euclidean Algorithm, GCD, greatest common divisor, Bezout's identity, coprime, relatively prime, one-sided error, false positive, EECS 376, randomised algorithms