# C.9 Examples for Chapter 17

# Example 38

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

$$(9853\text{,}\text{}853)\text{,}\text{}(4421\text{,}\text{}4387)\text{,}\text{}(6543\text{,}\text{}1234)\text{,}\text{}(93293\text{,}\text{}78428)\text{,}\text{}(12398\text{,}\text{}7563)\text{.}$$

Find the secret.

SOLUTION

The function *interppoly(x,f,m)* calculates the interpolating polynomial that passes through the points $({x}_{j}\text{,}\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.