Solving a polynomial I've come across this page about partial passwords, and I am having difficulty trying to understand the polynomial equations in there. I can understand basic algebra but this page's explanation is just not clear for me.
The variables are:
p1,p2,p3...pk  : the letters of password P
K : unique secret key
N : number of letters to ask everytime
R1,R2, R3...R(N-1) : random numbers
x : the order of the character/letter

My questions are:


*

*How are $y_1, y_2, y_3,\ldots,y_{N-1}$ to be calculated if $y = K+R_1 x + R_2 x^2 + ... + R_{N-1}x^{N-1}$?

*How is $s_k=(y_k-p_k)$ to be calculated if $p_k$ is a letter or character?


For the polynomial equation given :  $K' = \sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)}$


*

*How is the value of j derived for each letter? 

*In the substitution, $\prod_j$ values seem different in the 1st and 2nd instances:
$$\sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)}K '= y_2\left(3 \frac{4}{(2-3)(2-4)} \right)
    +    y_3 \left(2 \frac{4}{(3-2)(3-4)} \right) 
    +    y_4 \left(2 \frac{3}{(4-2)(4-3)} \right)$$
Would greatly appreciate if someone with better mathematical understanding could explain to me those questions clearly.
 A: First, a bit of background. What they're doing here is based on Shamir's secret sharing. This is usually understood as a way of sharing a secret number between people so that none of them know it, but they can collaborate to find it out. E.g. suppose the nuclear launch code is to be shared between 5 generals in such a way that any 3 of them can launch the missiles. We rely on the basic property of polynomials that $n$ distinct points uniquely define an order $n-1$ polynomial. E.g. two points define a straight line, three points define a quadratic, 4 points define a cubic. So since we want 3 generals to collaborate and launch the missile, we choose a random quadratic $P$ such that $P(0)$ is our secret. Then we evaluate $P$ at 5 non-zero $x$-values and give a different $(x, P(x))$ pair to each general.
If you haven't understood that, read it again.
I've said that we rely on the fact that $n$ distinct points uniquely define an order $n-1$ polynomial, but I haven't said how to find that polynomial. If you're familiar with simultaneous equations then you should be able to see that one way of doing it is to treat each point as an equation in the coefficients (e.g. for the quadratic $y(x) = ax^2 + bx + c$, the point $(3, 7)$ is the equation $7 = 3^2a + 3b + c$) and solve them by any suitable method. However, it's quicker to use Lagrange interpolation, although less quick to understand why it works. I won't explain that in full in this answer - the link I gave in a comment should be a good starting point, and if you have specific questions about it then you can ask them separately.
Ok, onto the specific questions you asked above:


*

*$y_1$ is defined in point B4 as a shorthand notation for $y(1)$, and since $y = K+R_1 x + R_2 x^2 + \ldots + R_{N-1}x^{N-1}$ that means that $y_1 = K+R_1 + R_2 + \ldots + R_{N-1}$, $y_2 = K+2 R_1 + 4 R_2 + \ldots + 2^{N-1}R_{N-1}$, etc.

*We define a numeric value for each possible letter. If you're doing a worked example you might want to use $A=1, B=2, \ldots Z=26$. For "real world" implementations there are various standard character sets which are used for this; see e.g. UCS. For reasons going back to the (relatively) early days of computing, most of the character sets which are used for text in Western European languages languages have $A=65, B=66, \ldots$

*Your comment clarifies that you're familiar with the summation symbol $\sum$, but not with $\prod$. This upper-case Pi symbol is usually read as "product" and is like $\sum$ except that it multiplies rather than adding. So just as the $i$ in $\sum_i$ is a bound variable which runs over a range understood from context, the $j$ in $\prod_j$ is a bound variable which runs over a range understood from context. Here the explanation you're reading assumes familiarity with Lagrange interpolation, which supplies the context necessary to read it as "each $j$ from $1$ to $N$ which is not equal to $i$". Actually that's also spelt out as

where i and j run over i1, i2, ..., iN (step 1), and j skips the actual selected i.


*So with that context we can expand out a bit. In the worked example, $N=3$, and the values $i$ and $j$ can take are $2,3,4$ so $$\begin{eqnarray}
K^\prime & = & \sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)} \\
& = & y_2 \frac{\prod_{j \ne 2} (j)}{\prod_{j \ne 2} (2-j)} + y_3 \frac{\prod_{j \ne 3} (j)}{\prod_{j \ne 3} (3-j)} + y_4 \frac{\prod_{j \ne 4} (j)}{\prod_{j \ne 4} (4-j)} \\
& = & y_2 \frac{3\cdot 4}{(2-3)(2-4)} + y_3 \frac{2\cdot 4}{(3-2)(3-4)} + y_4 \frac{2\cdot 3}{(4-2)(4-3)}
\end{eqnarray}$$
I would prefer to write it instead as $$\begin{eqnarray}
K^\prime & = & \sum_i y_i \prod_{j \ne i} \frac{j}{i-j} \\
& = & \left( y_2 \cdot\frac{3}{2-3} \cdot\frac{4}{2-4} \right) + \left( y_3 \cdot\frac{2}{3-2}\cdot\frac{4}{3-4} \right) + \left( y_4 \cdot\frac{2}{4-2}\cdot\frac{3}{4-3} \right)
\end{eqnarray}$$
