Shamir's Secret Sharing: Polynomial Math

Shamir's Secret Sharing (1979) encodes the secret as the y-intercept (f(0)) of a random degree-(k-1) polynomial over a finite field. Any k points uniquely determine the polynomial (Lagrange interpolation); fewer than k points reveal nothing.

To share secret S with threshold k among n parties: choose a prime p > S and n. Pick random coefficients a_1, ..., a_{k-1}. Define f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Party i receives share (i, f(i)).