Use Horner's method for evaluating polynomials
Use Horner's method for evaluating polynomials

Horner's method is an algorithm for calculating polynomials, which consists of
transforming the monomial form into a computationally efficient form. It is
pretty easy to understand:
https://en.wikipedia.org/wiki/Horner%27s_method#Description_of_the_algorithm

This implementation has resulted in a noticeable secret share generation speedup
as the RustySecrets benchmarks show, especially when calculating larger
polynomials:

Before:
test sss::generate_1kb_10_25 ... bench: 3,104,391 ns/iter (+/- 113,824)
test sss::generate_1kb_3_5 ... bench: 951,807 ns/iter (+/- 41,067)

After:
test sss::generate_1kb_10_25        ... bench:   2,071,655 ns/iter (+/- 46,445)
test sss::generate_1kb_3_5          ... bench:     869,875 ns/iter (+/- 40,246)

SpinResearch/RustySecrets