Shamir's secret sharing
= Shamir's secret sharing
{c}
{wiki}
Shamir's secret sharing places a secret $N$ at the constant term of a random polynomial $f\in\mathbb F_p[X]$ of degree at most $r-1$ and issues distinct nonzero evaluation pairs $(x_i,f(x_i))$. Any $r$ shares recover $f$ by <polynomial interpolation>. Given fewer than $r$ shares, every candidate constant term has the same number of compatible coefficient tuples, which gives perfect secrecy.