Simplified Lagrange interpolation formula inside Shamir's secret sharing scheme

Question

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?

Answer 1

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.

To calculate inverses efficiently, you should use the extended Euclidean algorithm. But with a small number like 17, it might be worthwhile to just construct a multiplication table to get practice with modular arithmetic.