Struct Polynomial

Source

pub struct Polynomial<C> { /* private fields */ }

Available on crate feature alloc only.

Expand description

Polynomial $f(x) = \sum_i a_i x^i$ defined as a list of coefficients $[a_0, \dots, a_{\text{degree}}]$

Polynomial is generic over type of coefficients C, it can be Scalar<E>, NonZero<Scalar<E>>, SecretScalar<E>, Point<E>, or any other type that implements necessary traits.

Implementations§

Source §

impl<C: IsZero> Polynomial<C>

Source

pub fn from_coefs(coefs: Vec<C>) -> Self

Constructs a polynomial from its coefficients

coefs[i] is coefficient of x^i term. Resulting polynomial will be $f(x) = \sum_i \text{coefs}_i \cdot x^i$

§Example

use generic_ec::{Scalar, curves::Secp256k1};
use generic_ec_zkp::polynomial::Polynomial;

let coefs: [Scalar<Secp256k1>; 3] = [
    Scalar::random(&mut OsRng),
    Scalar::random(&mut OsRng),
    Scalar::random(&mut OsRng),    
];
let polynomial = Polynomial::from_coefs(coefs.to_vec());

let x = Scalar::random(&mut OsRng);
assert_eq!(
    coefs[0] + x * coefs[1] + x * x * coefs[2],
    polynomial.value::<_, Scalar<_>>(&x),
);

Source §

impl<C> Polynomial<C>

Source

pub fn degree(&self) -> usize

Returns polynomial degree

Polynomial degree is index of most significant non-zero coefficient. Polynomial $f(x) = 0$ considered to have degree $deg(f) = 0$.

$$ \begin{dcases} deg(f(x) = \sum_i a_i \cdot x^i) &= n \text{, where } a_n \ne 0 \land n \to max \\ deg(f(x) = 0) &= 0 \end{dcases} $$

Source

pub fn coefs(&self) -> &[C]

Returns polynomial coefficients

Source

pub fn into_coefs(self) -> Vec<C>

Destructs polynomial, returns its coefficients

Source §

impl<C: Samplable> Polynomial<C>

Source

pub fn sample(rng: &mut impl RngCore, degree: usize) -> Self

Samples a random polynomial with specified degree

Source

pub fn sample_with_const_term( rng: &mut impl RngCore, degree: usize, const_term: C, ) -> Self

Samples a random polynomial with specified degree and constant term

Constant term determines value of polynomial at point zero: $f(0) = \text{const\_term}$

§Example

use generic_ec::{Scalar, curves::Secp256k1};
use generic_ec_zkp::polynomial::Polynomial;

let const_term = Scalar::<Secp256k1>::from(1234);
let polynomial = Polynomial::sample_with_const_term(&mut OsRng, 3, const_term);
assert_eq!(const_term, polynomial.value::<_, Scalar<_>>(&Scalar::zero()));

Source §

impl<C> Polynomial<C>

Source

pub fn value<P, O>(&self, point: &P) -> O
where for<'a> O: Zero + Mul<&'a P, Output = O> + Add<&'a C, Output = O>,

Evaluates polynomial value at given point: $f(\text{point})$

Polynomial coefficients, point, and output can all be differently typed.

§Example: polynomial with coefficients typed as non-zero scalars vs elliptic points

Let $f(x) = a_1 \cdot x + a_0$ and $F(x) = G \cdot f(x)$. Coefficients of $f(x)$ are typed as NonZero<Scalar<E>>, and $F(x)$ has coefficients typed as NonZero<Point<E>>.

When we evaluate $f(x)$, we have coefficients C of type NonZero<Scalar<E>>, and both point P and output O of type Scalar<E>.

On other hand, when $F(x)$ is evaluated, coefficients C have type NonZero<Point<E>>, point P has type Scalar<E>, and output O is of type Point<E>.

use generic_ec::{Point, Scalar, NonZero, curves::Secp256k1};
use generic_ec_zkp::polynomial::Polynomial;

let f: Polynomial<NonZero<Scalar<Secp256k1>>> = Polynomial::sample(&mut OsRng, 1);
let F: Polynomial<NonZero<Point<_>>> = &f * &Point::generator();

let x = Scalar::random(&mut OsRng);
assert_eq!(
    f.value::<_, Scalar<_>>(&x) * Point::generator(),    
    F.value::<_, Point<_>>(&x)
);