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

Find the secret.

SOLUTION

The function interppoly(x,f,m) calculates the interpolating polynomial that passes through the points $(x_j\text{,}{f}_j)$. The arithmetic is done mod $m$.

In order to use this function, we need to make a vector that contains the $x$ values, and another vector that contains the share values. This can be done using the following two commands:

>> x=[9853 4421 6543 93293 12398];

>> s=[853 4387 1234 78428 7563];

Now we calculate the coefficients for the interpolating polynomial.

>> y=interppoly(x,s,987541)

y =
    678987   14728   1651   574413   456741

The first value corresponds to the constant term in the interpolating polynomial and is the secret value. Therefore, 678987 is the secret.