I'm trying to find an interpolation polynomial degree $t$ less than the number of $n$ points for modulo prime $p$. Additionally, the results of this polynomial should be in small intervals (i.e. in $[0,3]$). I will give an example from Shamir Secret Sharing. Let secret is $23$, I have $6$ points ($p(1) = 2, p(2) = 0, p(3) = 1, p(4) = 3, p(5) = 0, p(6) = 1$). How can I find $a$ and $b$ from polynomial $p(x) = ax^2 + bx + 23$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ You are overloading the meaning of p and $p$. p is a prime number while $p$ denotes a polynomial. Please edit your question to clarify what you mean. $\endgroup$– Dilip SarwateCommented Oct 17 at 13:40
-
$\begingroup$ Your data are inconsistent. A quadratic polynomial with zeroes at $2$ and $5$ must satisfy symmetry requirements $p(3)=p(4)$ and $p(1)=p(6)$ which what you have written down fails to do. $\endgroup$– Dilip SarwateCommented Oct 17 at 16:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$p(2) = p(5) = 0$ implies that the OP's $p(x)$ is of the form $$c(x)(x-2)(x-5) = c(x)(x^2 -7x +10).$$ Since the OP insists that $p(x)$ is a quadratic polynomial, it must be that $c(x)$ is a constant, say $\alpha$. So, $$ax^2 + b(x) + 23 = \alpha(x^2-7x+10)$$ showing $10\alpha =23$, i.e., $$\alpha = \big((10^{-1} \bmod q)\times 23)\bmod q$$ where $q$ is the size of the prime field that is being used. Note that Shamir secret-sharing requires that $q>23$. Once the value of $\alpha$ has been determined, it can be used to find $a$ and $b$.
Note: While the $p(x)$ thus found satisfies $p(2) = p(5) = 0$, it does not satisfy the other constraints ($p(1) = 2$, etc) which appear to be written down at random. A quadratic polynomial with zeroes at $2$ and $5$ must satisfy symmetry requirements $p(3)=p(4)$ and $p(1)=p(6)$, and the data that the OP has chosen to provide does not meet these requirements.
$\begingroup$
$\endgroup$
1
In general you cannot. A polynomial of degree $d$ requires $d+1$ equations to uniquely determine it. On the flip side, unless there are dependencies in the $k$ values that are given (i.e., they lie in a subspace) the polynomial interpolating at those points will usually be degree $k-1.$
An example of this would be if your values were $$ p(i)=i^2+i+2 \pmod{29},\quad i=1,\ldots,6 $$ for example, i.e., they happened to be the values of a degree 2 polynomial, then Lagrange interpolation would recover this polynomial.
Note: For crypto applications points and values are randomly chosen for security and in general result in a full degree interpolating polynomial.
-
1$\begingroup$ Since $23$ is the secret, it should be smaller that the field size, no? $\endgroup$ Commented Oct 17 at 13:43