# How do we solve Shammir 2,3 sharring scheme where arithmetic is modulo?

I am trying to get secret S and I have 3 values (2,2)(6,3)(4,9) and know that modulo is 13.

I tried using Lagrange basis polynomial and got 8 but I am not sure if that is right and also I cannot find way to derive the equation of the line in form of ax+by= c mod 13.

• 8 is correct... Oct 27 '15 at 19:25
• I cannot find way to derive the equation of the line in form of ax+by= c mod 13. Oct 29 '15 at 12:53

You should choose two points. (for example (2,2) and (6,3)). Then you can compute the Lagrange interpolation polynomial as below:

$$f(x)=2.(\dfrac{x-6}{2-6})+3.(\dfrac{x-2}{6-2})=-(\dfrac{2x-12}{4})+(\dfrac{3x-6}{4})$$

$$\ \ \ \ \ \ \ \ =(\dfrac{x+6}{4})=(\dfrac{x}{4})+(\dfrac{6}{4})\ mod(13)=10x+60\ mod(13)=10x+8$$

Because $$4^{-1}=10 \ mod(13)$$.

• Latex has \mod \bmod and \pmod{}. Also \cdot instead of *. Nov 14 '20 at 19:16

The form of equation you expect is not usually applied to Shamir's Sharing Scheme. Instead the equation is usually represented as polynomial: $$f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}\,\! \mod p,$$ where $k$ is number of pieces needed to restore the secret; $a_i$ are random coefficients (modulo p) and $p$ is 13 (in your case).

According to this your "equation of the line" (after recovering it with Lagrange interpolation polynomial) should look like: $$f\left(x\right)=10x+8\mod 13.$$ As you can see $a_0$ coefficient here is $8$ so that your guess is right (since $a_0$ is the secret itself).

• n0unc3 did say it saw a (2,3) system; that means that 2 shares were sufficient to recover the secret. Hence, it's not at all surprising that one of the shares are superfluous... Nov 12 '15 at 19:08
• @poncho, that's right, thank you. I have removed needless caveat. Nov 13 '15 at 1:47