Split a secret into n shares so that any k of them rebuild it — and any k−1 reveal nothing at all. The trick: hide the secret as a polynomial’s constant term; k points fix a degree-(k−1) polynomial uniquely, fewer leave every secret equally likely. Pure algebra, information-theoretically secure.
THE TECHNIQUE a polynomial through the secret
To share secret S with threshold k: pick a random degree-(k−1) polynomial with f(0) = S, hand out points (i, f(i)) as shares. Any k shares reconstruct f (and so f(0) = S) by Lagrange interpolation; k−1 shares fit infinitely many polynomials, so S stays hidden. All arithmetic is mod a prime. Try it. live demo
HISTORY & CREDIT two schemes, one year
“Shamir alone invented secret sharing” — Blakley published a threshold scheme the next yearsame year, 1979, independently. cited
1979 · Adi Shamir (“How to Share a Secret,” CACM) — the polynomial scheme, elegant and exact: k points determine the polynomial, so k shares suffice and fewer reveal nothing. 1979 · George Blakley independently gives a geometric threshold scheme (the secret is a point where k hyperplanes meet) — same year, different mathematics. the security · it is information-theoretic: k−1 shares leave every possible secret equally likely, no computing power helps. Not merely hard — impossible to break under-threshold. the engine · reconstruction is Lagrange interpolation (dart 100) evaluated at x = 0, over a finite field.
Shamir is the S in RSA (dart 050); this is his other elegant one-pager. Shamir & Blakley, 1979
RECOMMEND FOR I-13 modular arithmetic + a modular inverse
Building shares and rebuilding by Lagrange at 0 is modular multiply and a modular inverse — both landed — and it round-trips on the compiler:
$ i13 run shamir.i13 # S=7, 2-of-3 over GF(13), shares (1,12)(2,4)(3,9)
rebuild from any 2 shares -> S = 7 modular inverse inv(2) = 7 (ext-Euclid)
Recommend: the tiny demo runs end-to-end — the merged %, and a modular inverse from extended Euclid (dart 084), rebuild S = 7 over a small prime field; no floating point. It is a real use of two landed features (modular arithmetic + the inverse) compounding. Note: real deployments use a 256-bit prime, so every share and Lagrange product needs bignum (dart 050’s addition) — the toy field runs in f64, the real field is a clean bignum job.