Introduction to Cryptography with Coding Theory, 3rd Edition

A.10 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{,}853)\text{,}(4421\text{,}4387)\text{,}(6543\text{,}1234)\text{,}(93293\text{,}78428)\text{,}(12398\text{,}7563)\text{.}$$

Find the secret.

SOLUTION

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

In[1]:= InterpolatingPolynomial[ { {9853, 853 }, {4421, 4387 }, {6543, 1234 }, {93293, 78428 }, {12398, 7563 } }, x]

Out[1]= $853+(-{\displaystyle \frac{1767}{2716}}+(+{\displaystyle \frac{2406987}{9538347560}}+(-{\displaystyle \frac{8464915920541}{3130587195363428640000}})$ $-{\displaystyle \frac{49590037201346405337547(-93293+\text{x})}{133788641510994876594882226797600000}})(-6543+\text{x}))(-4421+\text{x}))$ $(-9853+\text{x})$

Now evaluate at $x=0$ to find the constant term (use $/\text{.}x->0$ to evaluate at $x=0$):

In[2]:= %/. x - > 0

Out[2]= ${\displaystyle \frac{\mathrm{204484326154044983230114592433944282591\; ...}}{}}$