Shamir's secret sharing scheme 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, with a few optimizations. Are there known faster ways?
Efficient Shamir secret sharing reconstruction
cr.crypto security;time complexity;polynomials