<p>Yes. If you choose the evaluation poitns for the polynomial carefully, this problem is the same as correcting erasures in the Reed-Solomon encoding of a message, and there are faster algorithms for that problem. </p>

<p><a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction" rel="nofollow">http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction</a></p>

CC BY-SA 3.0
2015-02-06T19:25:49.427Z
2015-02-06T19:25:49.427Z
Adam Smith
<p><a href="https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing" rel="nofollow">Shamir's secret sharing scheme</a> is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the original polynomial and subsequently the secret.</p>

<p>The regrouping process can be summarized as finding $p(0)$ in a polynomial knowing only the degree and pairs $(x_i, y_i)$ such that $p(x_i) = y_i$.</p>

<p>My question is: how do I do this efficiently? All implementations I've seen so far are $O(n^2)$ because they recompute the polynomial using <a href="https://en.wikipedia.org/wiki/Lagrange_polynomial" rel="nofollow">Lagrange</a>, with a few optimizations. Are there known faster ways?</p>

CC BY-SA 3.0
2014-07-22T09:10:32.763Z
It's certainly possible in some cases to get $O(n \lg n)$ using the FFT. You might want to explore the possibilities there when the available points aren't a full set of roots of unity.
Peter Taylor
<cr.crypto-security><time-complexity><polynomials>
Efficient Shamir secret sharing reconstruction
BoppreH
# Efficient Shamir secret sharing reconstruction

(Asked by: username_0 on 2014-07-21)

[Shamir's secret sharing scheme](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing) is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the original polynomial and subsequently the secret.

The regrouping process can be summarized as finding $p(0)$ in a polynomial knowing only the degree and pairs $(x\_i, y\_i)$ such that $p(x\_i) = y\_i$.

My question is: how do I do this efficiently? All implementations I've seen so far are $O(n^2)$ because they recompute the polynomial using [Lagrange](https://en.wikipedia.org/wiki/Lagrange_polynomial), with a few optimizations. Are there known faster ways?

**Tags:** cr.crypto-security, time-complexity, polynomials
> **Comments:**
> **username_1**: It's certainly possible in some cases to get $O(n \lg n)$ using the FFT. You might want to explore the possibilities there when the available points aren't a full set of roots of unity.  

---

## 1 answers

### Answer by username_2 on 2015-02-06. Score: 2

Yes. If you choose the evaluation poitns for the polynomial carefully, this problem is the same as correcting erasures in the Reed-Solomon encoding of a message, and there are faster algorithms for that problem.

<http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction>


---

