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,657,012 ns/iter (+/- 26,998)
test sss::generate_1kb_3_5 ... bench: 885,919 ns/iter (+/- 51,110)
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,657,012 ns/iter (+/- 26,998) test sss::generate_1kb_3_5 ... bench: 885,919 ns/iter (+/- 51,110)