Suppose we have a (5, 8) Shamir secret sharing scheme. Everything is mod the prime $p=987541\text{.}$ Five of the shares are

Find the secret.

SOLUTION

One way: First, find the Lagrange interpolating polynomial through the five points:

> interp([9853,4421,6543,93293,12398],
[853,4387,1234,78428,7563],x)

$$\begin{array}{c}-{\displaystyle \frac{\text{49590037201346405337547}}{\text{133788641510994876594882226797600000}}}{\text{X}}^{\text{4}}\\ +{\displaystyle \frac{\text{353130857169192557779073307}}{\text{8919242767399658439658815119840000}}}{\text{X}}^{\text{3}}\\ -{\displaystyle \frac{\text{8829628978321139771076837361481}}{\text{19112663072999268084983175256800000}}}{\text{X}}^{\text{2}}\\ +{\displaystyle \frac{\text{9749049230474450716950803519811081}}{\text{44596213836998292198294075599200000}}}\text{X}\\ +{\displaystyle \frac{\text{204484326154044983230114592433944282591}}{\text{22298106918499146099147037799600000}}}\end{array}$$

Now evaluate at $x=0$ to find the constant term:

> eval(%,x=0)

$${\displaystyle \frac{\text{204484326154044983230114592433944282591}}{\text{22298106918499146099147037799600000}}}$$

We need to change this to an integer mod 987541:

> % mod 987541

                   678987

Therefore, 678987 is the secret.

Here is another way. Set up the matrix equations as in the text and then solve for the coefficients of the polynomial mod 987541:

> map(x->x mod 987541,evalm(inverse(matrix(5,5,
[1,9853,$9853\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2,$9853\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$3,$9853\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$4,
1,4421,$4421\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2,$4421\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$3,$4421\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$4,
1,6543,$6543\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2,$6543\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$3, $6543\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$4,
1, 93293, $93293\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2,$93293\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$3, $93293\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$4,
1, 12398, $12398\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$2,$12398\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$3,$12398\stackrel{\mathbf{ˆ}}{\phantom{\mathbf{a}}}$4]))
&*matrix(5,1,[853,4387,1234,78428,7563])))

$$\left[\begin{array}{c}678987\\ 14728\\ 1651\\ 574413\\ 456741\end{array}\right]$$

The constant term is $678987\text{,}$ which is the secret.