# Simplified Lagrange interpolation formula inside Shamir's secret sharing scheme

I originally posted this question in the math stackexchange, but I then thought that it might be more appropriate in this section. I am currently studying Shamir's secret sharing scheme, which uses Lagrange's interpolation formula to reconstruct a key $$K$$ from a certain number of shares. In Shamir's scheme, during key reconstruction, there is no need to reconstruct the entire polynomial $$a(x)$$ since we only need the value $$a(0)$$, the secret. Therefore, we can use a simplification in the formula by substituting $$x=0$$ in the original Lagrange formula, which then becomes this:

$$K = \sum_{j=1}^t (y_j \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j}) \pmod p$$

where $$y_j$$ are the shares owned by the participants. If we now define

$$b_j = \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j} \pmod p$$

we can then reconstruct the key $$K$$ with this formula:

$$K = \sum_{j=1}^t b_jy_j \pmod p$$

And during the calculation of $$b_j$$ is where I hit a wall: in the book that I am using to study this (Cryptography Theory and Practice, by Stinson and Paterson), there is an example of how to compute $$b_j$$. We are given the following values:

$$x_1=1, x_2=2, x_3=3, x_4=4, x_5=5$$

And we want to get the value of $$b$$ for $$x_1$$, $$x_3$$ and $$x_5$$. The book shows this example for $$b_1$$:

\begin{align} b_1 &= \frac{x_3 x_5}{(x_3 - x_1)(x_5-x_1)} & & \pmod{17} \\ &= 3 * 5 * (2)^{-1} * (4)^{-1} & & \pmod{17}\\ &= 3 * 5 * 9 * 13 & & \pmod{17} \\ &= 4 & & \pmod{17} \end{align}

How did we get from $$(2)^{-1}$$ and $$(4)^{-1}$$ to $$9$$ and $$13$$ respectively?

• $2\cdot 9\bmod 17=18\bmod 17$ and $13\cdot 4\bmod 17=52\bmod 17=1$ as expected. – SEJPM Jun 9 '20 at 12:03

All these calculations are done $$\bmod{17}$$.
$$2^{-1}$$ means here the number, $$x$$, that satisfies the equation $$2x = 1 \pmod{17}$$. (Note that this is the same definition that we use for the reals). When you're working $$\bmod{17}$$ (or any prime number, in fact), every number except 0 has an inverse.