# Is there supposed to be a unique polynomial when given t shares for (t,n) Shamir Secret Sharing scheme?

I always thought that part of the idea behind SSS was that there is only a single $$t-1$$ degree polynomial through $$t$$ unique points; that this holds when the polynomial coefficients are over the reals and also in particular for SSS when the elements are chosen from a finite field. However I'm running into (what I think is) a counterexample -- so I must be doing something wrong :)

Consider SSS with modulus is $$4$$, so we are working in $$\text{GF}(4)$$. Assume the secret to be shared is $$S = 3$$, and the polynomial chosen ends up being $$f(x) = x^2 + 2x + 3 \mod 4$$. We pick three points $$(0,3), (1,2), (3,2)$$ on $$f(x)$$ as the shares (I'm aware the y-intercept should not be chosen as a share in this type of SSS scheme, but it's not super relevant to the question at hand). When I attempt to reconstruct the secret by solving the system of equations for the polynomial coefficients defined by the shares, I get two possible polynomials for $$f(x) = a_2 x^2 + a_1 x + S \mod 4$$.

$$S = 3 \mod 4$$

$$a_2 + a_1 + S = 2 \mod 4$$

$$9a_2 + 3a_1 + S = 2 \mod 4$$

Solving this system for the coefficients yields $$a_1 = 0, a_2 = 3$$ and $$a_1 = 2, a_2 = 1$$ as solutions, implying that two degree $$2$$ polynomials go through the $$3$$ points $$(0,3), (1,2), (3,2)$$. Namely $$g(x) = 3x^2 + 3 \mod 4$$ and $$h(x) = x^2 + 2x + 3 \mod 4$$. I thought there should only be one degree $$2$$ polynomial through $$3$$ distinct points?

I think my understanding is wrong somewhere, and would appreciate anyone pointing it out!

• Rereading this closely, maybe the mistake is that the integers $\mod 4$ are not a field, since $2$ doesn't have an inverse $\mod 4$.. so the integers $\mod 4$ are not isomorphic to $\text{GF}(4)$. Then, the error in my thinking is that the integers $\mod p^k$ for prime $p$ and $k \geq 1$ are isomomorphic to $\text{GF}(p^k)$. In this case, can someone clarify when the integers modulo $p^k$ are isomorphic to $\text{GF}(p^k)$? Commented Mar 24 at 16:20
• For $k>1$, the integers modulo $p^k$ are not isomorphic to GF$(p^k)$; for $k=1$, they are. That's all there is to it. Commented Mar 25 at 16:25

You are operating in integers modulo $$4$$ which is not a field, it is $$\mathbb{Z}_4.$$ This means that there are zero divisors (for example $$2\times2=0 \pmod 4$$) and thus polynomial representation of functions is not unique.