How to compute $\prod_{i=1}^ny'{_i}^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$with modular arithmetic for Lagrange

106 Views Asked by At

What I would like to do is an exponentiation with a public constant $(c=9)$ to the power of a secret number $(s=4)$ without revealing it and everything with modular arithmetic.

$$c^s= 5 \pmod{11} \tag 1$$

To do it, I splitted the secret number $s$ with a secret polynomial $(y(x) = 3x^2 + 2x + s)$ using Shamir's secret sharing and get three points from it.

$$(x_i,y_i) = [(1, 9), (2, 9), (3, 4)] \pmod{11}$$

Now, I want to perform the same as in $(1)$ but with the $y_i$ part of the points

$$ y'_i = c^{y_i}$$ $$(x_i,y'_i) = [(1, 5), (2, 1), (3, 4)] \pmod{11}$$

To obtain the same result as in $(1)$ secretly, it is necessary to interpolate all points $(x_i, y_i)$ using Lagrange $(L=\sum_{i=1}^n\;y_i\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i})$ where $x=0$ but, since I'm not going to use $y_i$ instead I'm going to use $y'_i$, it is necessary to change the function raising $c$ to the power of $L$:

$$c^L=\prod_{i=1}^n\;c^\left(y_i\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$$ $$c^L=\prod_{i=1}^n (c^{y_i})^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right)$$ $$c^L=\prod_{i=1}^ny'{_i}^\left(\prod_{\genfrac{}{}{0}{1}{j\not=i}{j=1}}^n\frac{x_j}{x_j-x_i}\right) \tag 2$$

With all of that said, what is the step-by-step process of calculating the above equation $(2)$ using modular arithmetic with the points $(x_i,y'_i)$?

I tried to solve what is in the exponent with $\pmod{11-1}$ but when I did the inverse of $(x_j-x_i)$ it just didn’t work, the multiplication is fine, but the division is simply giving an incorrect number or it is not possible.

1

There are 1 best solutions below

0
On

Modulo $11$ we have that $$1^{-1} =1, 2^{-1}=6, 3^{-1}=4, 4^{-1} =3, 5^{-1}=9, 6^{-1} = 2, 7^{-1} = 8, 8^{-1} = 7, 9^{-1} = 5, 10^{-1} = 10$$

In every expression like $\frac{a}{b}$ write it as $a\cdot b^{-1}$ and reduce modulo $11$ again.

So your product terms of quotients become a lot multiplications modulo $11$.