I'm trying to test my implementation of the Shamir Secret Sharing Scheme. I'm referring to an example of Lagrange Interpolation at: https://programmingpraxis.com/2011/06/17/adi-shamirs-threshold-scheme/
Going through the example the first line follows from the equation to computer S(0), but on line 2, in the last term, the 2 multiplier from line 1 becomes a 21. Similarly on line 3, in the middle term, the 21 multiplier from line 2 becomes a 23. Despite this the final answer is correct. Could someone please explain why these changes happen and how they get to the correct answer?
Please note x$^{−1}$ denotes ModInverse in 23.
S = [22 · 2(2−14)$^{−1}$ · 21(21−14)−1] + [8 · 14(14−2)$^{−1}$ · 21(21−2)$^{−1}$] + [5 · 14(14−21)$^{−1}$ · 2(2−21)$^{−1}$] (mod 23)
= [22 · 2 · 11$^{−1}$ · 21 · 7$^{−1}$] + [8 · 14 · 12$^{−1}$ · 21 · 19$^{−1}$] + [5 · 14 · 16$^{−1}$ · 21 · 4$^{−1}$] (mod 23)
= [22 · 2 · 21 · 21 · 10] + [8 · 14 · 2 · 23 · 17] + [5 · 14 · 13 · 21 · 6] (mod 23)
= 194040 + 87584 + 114660 (mod 23)
= 396284 (mod 23)
= 17
@moo
So Seth and I are working on this together and our issue is not with the mod inverse.
What we don’t understand is that the third term goes as follows:
[$5\cdot14\cdot$(14-21)$^{-1}$$\cdot$2$\cdot(2-21)$$^{-1}$]
[$5\cdot14\cdot(-7\equiv16mod23)$$^{-1}$$\cdot$21$\cdot(-19\equiv4mod23)$$^{-1}$]
Why does the bold faced 2 become the bold faced 21? The same is true in the second term between the following bold faced terms.
[8$\cdot$14$\cdot$12$^{-1}$$\cdot$21$\cdot$19$^{-1}$]
[8$\cdot$14$\cdot$2$\cdot$23$\cdot$17]
This sort of jump doesn't happen in the first term so we're not sure where it's coming from.
Thank you!