use gf256::Gf256;
use std::io;
use std::io::prelude::*;

/// evaluates a polynomial at x=1, 2, 3, ... n (inclusive)
pub(crate) fn encode_secret_byte<W: Write>(src: &[u8], n: u8, w: &mut W) -> io::Result<()> {
    for raw_x in 1..(u16::from(n) + 1) {
        let x = Gf256::from_byte(raw_x as u8);
        let mut fac = Gf256::one();
        let mut acc = Gf256::zero();
        for &coeff in src.iter() {
            acc += fac * Gf256::from_byte(coeff);
            fac *= x;
        }
        w.write_all(&[acc.to_byte()])?;
    }
    Ok(())
}

use gf256::Gf256;
use std::io;
use std::io::prelude::*;

/// evaluates a polynomial at x=1, 2, 3, ... n (inclusive)
pub(crate) fn encode_secret_byte<W: Write>(src: &[u8], n: u8, w: &mut W) -> io::Result<()> {
    for raw_x in 1..(u16::from(n) + 1) {
        let x = Gf256::from_byte(raw_x as u8);
        let sum = src.iter().rev().fold(Gf256::zero(), |acc, &coeff| {
            Gf256::from_byte(coeff) + acc * x
        });
        w.write_all(&[sum.to_byte()])?;
    }
    Ok(())
}

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)
