Reed-Solomon codes, RSA cryptography, and algebraic curves
Scratched CDs that still play, secure websites, and elliptic-curve cryptography all run on rings and fields. Here are three places the algebra does real work.
Enter a three-symbol message, press Introduce Error, and choose which symbol to corrupt. Watch the decoder recover the original message.
A 3-symbol message is encoded as a degree-2 polynomial over GF(7), evaluated at 5 points for redundancy. With 5 evaluation points, we can detect and correct a single-symbol error.
Rings and fields are not just abstract constructions -- they are the foundation of technologies we use every day. Error-correcting codes rely on finite field arithmetic, public-key cryptography exploits the structure of Z/nZ, and algebraic geometry studies the zero sets of polynomial rings.
Reed-Solomon codes encode messages as polynomials over a finite field and evaluate them at multiple points. The redundancy allows recovering the original message even when some symbols are corrupted. Enter a message, introduce an error, and watch the correction algorithm recover the original.
Key insight: A degree-k polynomial is uniquely determined by k+1 points. With more evaluation points than necessary, corrupted points can be detected and corrected by finding the polynomial that fits the majority.
Pick a pair of primes and a message, then press Next Step to walk through key generation, encryption, and decryption. Decryption returns your message.
RSA security relies on the difficulty of factoring n = p·q. With small primes this is trivial, but with 2048-bit primes it is computationally infeasible.
The RSA algorithm relies on the ring Z/nZ where n = pq is a product of two large primes. The multiplicative structure of this ring -- described by Euler's theorem -- allows encryption with a public key and decryption with a private key. Security depends on the difficulty of factoring n.
Key insight: RSA works because computing e-th powers mod n is easy, but finding the e-th root without knowing the factorization of n is hard. The ring structure of Z/nZ makes encryption and decryption inverse operations.
Switch between curves to see the shapes that single polynomial equations draw. Compare the smooth elliptic curve with the singular one.
Algebraic geometry studies the zero sets of polynomials. Green curves show where f(x,y) = 0. Blue/red shading indicates positive/negative regions. These objects connect ring theory to geometry.
Algebraic geometry studies the zero sets of polynomials -- the solutions to equations like x² + y² = 1 or y² = x³ - x. These curves are geometric objects defined purely by polynomial algebra. The interplay between the ring R[x, y] and the geometry of the curve is one of the deepest themes in modern mathematics.
Key insight: Elliptic curves (like y² = x³ - x) have a group structure: you can "add" points on the curve. This group law over finite fields is the basis of elliptic curve cryptography, currently the most efficient form of public-key encryption.
Spot a mistake or have an idea?