nil::crypto3::math Namespace Reference

Namespaces

 detail
 A convenience method for choosing an evaluation domain Returns an evaluation domain object in which the domain S has size |S| >= MinSize. The function get_evaluation_domain is chosen from different supported domains, depending on MinSize.
 

Classes

class  arithmetic_sequence_domain
 
class  basic_radix2_domain
 
class  evaluation_domain
 
class  extended_radix2_domain
 
class  geometric_sequence_domain
 
class  step_radix2_domain
 

Functions

template<typename Range >
void _condense (Range &a)
 
template<typename Range >
bool _is_zero (const Range &a)
 
template<typename Range >
void _polynomial_addition (Range &c, const Range &a, const Range &b)
 
template<typename FieldType >
void _polynomial_division (std::vector< typename FieldType::value_type > &q, std::vector< typename FieldType::value_type > &r, const std::vector< typename FieldType::value_type > &a, const std::vector< typename FieldType::value_type > &b)
 
template<typename FieldType >
void _polynomial_multiplication (std::vector< typename FieldType::value_type > &c, const std::vector< typename FieldType::value_type > &a, const std::vector< typename FieldType::value_type > &b)
 
template<typename FieldType , typename Range >
void _polynomial_multiplication_on_fft (Range &c, const Range &a, const Range &b)
 
template<typename FieldType >
void _polynomial_multiplication_on_kronecker (std::vector< typename FieldType::value_type > &c, const std::vector< typename FieldType::value_type > &a, const std::vector< typename FieldType::value_type > &b)
 
template<typename FieldType >
std::vector< typename FieldType::value_type > _polynomial_multiplication_transpose (const std::size_t &n, const std::vector< typename FieldType::value_type > &a, const std::vector< typename FieldType::value_type > &c)
 
template<typename Range >
void _polynomial_subtraction (Range &c, const Range &a, const Range &b)
 
template<typename Range >
void _reverse (Range &a, std::size_t n)
 
template<typename FieldType >
void compute_subproduct_tree (std::vector< std::vector< std::vector< typename FieldType::value_type >>> &T, std::size_t m)
 
template<typename FieldValueType , typename Range >
FieldValueType evaluate_lagrange_polynomial (const Range &domain, const FieldValueType &t, std::size_t m, std::size_t idx)
 
template<typename FieldValueType , typename InputIterator >
FieldValueType evaluate_lagrange_polynomial (InputIterator first, InputIterator last, const FieldValueType &t, std::size_t m, std::size_t idx)
 Naive evaluation of a single Lagrange polynomial, used for testing purposes. More...
 
template<typename FieldValueType , typename ContiguousContainer >
FieldValueType evaluate_polynomial (const ContiguousContainer &coeff, const FieldValueType &t, std::size_t m)
 
template<typename FieldValueType , typename ContiguousIterator >
FieldValueType evaluate_polynomial (ContiguousIterator first, ContiguousIterator last, const FieldValueType &t, std::size_t m)
 Naive evaluation of a single polynomial, used for testing purposes. More...
 
template<typename FieldType , typename Range1 , typename Range2 , typename Range3 , typename Range4 , typename Range5 >
void extended_euclidean (const Range1 &a, const Range2 &b, Range3 &g, Range4 &u, Range5 &v)
 Perform the standard Extended Euclidean Division algorithm. Input: Polynomial A, Polynomial B. Output: Polynomial G, Polynomial U, Polynomial V, such that G = (A * U) + (B * V). More...
 
template<typename FieldType >
void kronecker_substitution (std::vector< typename FieldType::value_type > &v3, const std::vector< typename FieldType::value_type > &v1, const std::vector< typename FieldType::value_type > &v2)
 Given two polynomial vectors, A and B, the function performs polynomial multiplication and returns the resulting polynomial vector. The implementation makes use of [Harvey 07, Multipoint Kronecker Substitution, Section 2.1] and [Gathen and Gerhard, Modern Computer Algebra 3rd Ed., Section 8.4]. More...
 
template<typename FieldType >
std::shared_ptr< evaluation_domain< FieldType > > make_evaluation_domain (std::size_t m)
 
template<typename FieldType >
void monomial_to_newton_basis (std::vector< typename FieldType::value_type > &a, const std::vector< std::vector< std::vector< typename FieldType::value_type >>> &T, size_t n)
 
template<typename FieldType , typename Range1 , typename Range2 , typename Range3 >
void monomial_to_newton_basis_geometric (Range1 &a, const Range2 &geometric_sequence, const Range3 &geometric_triangular_sequence, const std::size_t &n)
 
template<typename Range , typename FieldValueType >
void multiply_by_coset (Range &a, const FieldValueType &g)
 
template<typename FieldType >
void newton_to_monomial_basis (std::vector< typename FieldType::value_type > &a, const std::vector< std::vector< std::vector< typename FieldType::value_type >>> &T, size_t n)
 
template<typename FieldType , typename Range1 , typename Range2 , typename Range3 >
void newton_to_monomial_basis_geometric (Range1 &a, const Range2 &geometric_sequence, const Range3 &geometric_triangular_sequence, std::size_t n)
 

Function Documentation

◆ _condense()

template<typename Range >
void nil::crypto3::math::_condense ( Range &  a)

Removes extraneous zero entries from in vector representation of polynomial. Example - Degree-4 Polynomial: [0, 1, 2, 3, 4, 0, 0, 0, 0] -> [0, 1, 2, 3, 4] Note: Simplest condensed form is a zero polynomial of vector form: [0]

◆ _is_zero()

template<typename Range >
bool nil::crypto3::math::_is_zero ( const Range &  a)

Returns true if polynomial A is a zero polynomial.

◆ _polynomial_addition()

template<typename Range >
void nil::crypto3::math::_polynomial_addition ( Range &  c,
const Range &  a,
const Range &  b 
)

Computes the standard polynomial addition, polynomial A + polynomial B, and stores result in polynomial C.

◆ _polynomial_division()

template<typename FieldType >
void nil::crypto3::math::_polynomial_division ( std::vector< typename FieldType::value_type > &  q,
std::vector< typename FieldType::value_type > &  r,
const std::vector< typename FieldType::value_type > &  a,
const std::vector< typename FieldType::value_type > &  b 
)

Perform the standard Euclidean Division algorithm. Input: Polynomial A, Polynomial B, where A / B Output: Polynomial Q, Polynomial R, such that A = (Q * B) + R.

◆ _polynomial_multiplication()

template<typename FieldType >
void nil::crypto3::math::_polynomial_multiplication ( std::vector< typename FieldType::value_type > &  c,
const std::vector< typename FieldType::value_type > &  a,
const std::vector< typename FieldType::value_type > &  b 
)

Perform the multiplication of two polynomials, polynomial A * polynomial B, and stores result in polynomial C.

◆ _polynomial_multiplication_on_fft()

template<typename FieldType , typename Range >
void nil::crypto3::math::_polynomial_multiplication_on_fft ( Range &  c,
const Range &  a,
const Range &  b 
)

Perform the multiplication of two polynomials, polynomial A * polynomial B, using FFT, and stores result in polynomial C.

◆ _polynomial_multiplication_on_kronecker()

template<typename FieldType >
void nil::crypto3::math::_polynomial_multiplication_on_kronecker ( std::vector< typename FieldType::value_type > &  c,
const std::vector< typename FieldType::value_type > &  a,
const std::vector< typename FieldType::value_type > &  b 
)

Perform the multiplication of two polynomials, polynomial A * polynomial B, using Kronecker Substitution, and stores result in polynomial C.

◆ _polynomial_multiplication_transpose()

template<typename FieldType >
std::vector<typename FieldType::value_type> nil::crypto3::math::_polynomial_multiplication_transpose ( const std::size_t &  n,
const std::vector< typename FieldType::value_type > &  a,
const std::vector< typename FieldType::value_type > &  c 
)

Compute the transposed, polynomial multiplication of vector a and vector b. Below we make use of the transposed multiplication definition from [Bostan, Lecerf, & Schost, 2003. Tellegen's Principle in Practice, on page 39].

◆ _polynomial_subtraction()

template<typename Range >
void nil::crypto3::math::_polynomial_subtraction ( Range &  c,
const Range &  a,
const Range &  b 
)

Computes the standard polynomial subtraction, polynomial A - polynomial B, and stores result in polynomial C.

◆ _reverse()

template<typename Range >
void nil::crypto3::math::_reverse ( Range &  a,
std::size_t  n 
)

Compute the reverse polynomial up to vector size n (degree n-1). Below we make use of the reversal endomorphism definition from [Bostan, Lecerf, & Schost, 2003. Tellegen's Principle in Practice, on page 38].

◆ compute_subproduct_tree()

template<typename FieldType >
void nil::crypto3::math::compute_subproduct_tree ( std::vector< std::vector< std::vector< typename FieldType::value_type >>> &  T,
std::size_t  m 
)

Compute the Subproduct Tree of degree 2^M and store it in Tree T. Below we make use of the Subproduct Tree description from [Bostan and Schost 2005. Polynomial Evaluation and Interpolation on Special Sets of Points], on page 7.

◆ evaluate_lagrange_polynomial() [1/2]

template<typename FieldValueType , typename Range >
FieldValueType nil::crypto3::math::evaluate_lagrange_polynomial ( const Range &  domain,
const FieldValueType &  t,
std::size_t  m,
std::size_t  idx 
)
inline

◆ evaluate_lagrange_polynomial() [2/2]

template<typename FieldValueType , typename InputIterator >
FieldValueType nil::crypto3::math::evaluate_lagrange_polynomial ( InputIterator  first,
InputIterator  last,
const FieldValueType &  t,
std::size_t  m,
std::size_t  idx 
)
inline

Naive evaluation of a single Lagrange polynomial, used for testing purposes.

The inputs are:

  • an integer m
  • a domain S = (a_{0},...,a_{m-1}) of size m
  • a field element element t
  • an index idx in {0,...,m-1} The output is the polynomial L_{idx,S}(z) evaluated at z = t.

◆ evaluate_polynomial() [1/2]

template<typename FieldValueType , typename ContiguousContainer >
FieldValueType nil::crypto3::math::evaluate_polynomial ( const ContiguousContainer &  coeff,
const FieldValueType &  t,
std::size_t  m 
)
inline

◆ evaluate_polynomial() [2/2]

template<typename FieldValueType , typename ContiguousIterator >
FieldValueType nil::crypto3::math::evaluate_polynomial ( ContiguousIterator  first,
ContiguousIterator  last,
const FieldValueType &  t,
std::size_t  m 
)
inline

Naive evaluation of a single polynomial, used for testing purposes.

The inputs are:

  • an integer m
  • a vector coeff representing monomial P of size m
  • a field element element t The output is the polynomial P(x) evaluated at x = t.

◆ extended_euclidean()

template<typename FieldType , typename Range1 , typename Range2 , typename Range3 , typename Range4 , typename Range5 >
void nil::crypto3::math::extended_euclidean ( const Range1 &  a,
const Range2 &  b,
Range3 &  g,
Range4 &  u,
Range5 &  v 
)

Perform the standard Extended Euclidean Division algorithm. Input: Polynomial A, Polynomial B. Output: Polynomial G, Polynomial U, Polynomial V, such that G = (A * U) + (B * V).

◆ kronecker_substitution()

template<typename FieldType >
void nil::crypto3::math::kronecker_substitution ( std::vector< typename FieldType::value_type > &  v3,
const std::vector< typename FieldType::value_type > &  v1,
const std::vector< typename FieldType::value_type > &  v2 
)

Given two polynomial vectors, A and B, the function performs polynomial multiplication and returns the resulting polynomial vector. The implementation makes use of [Harvey 07, Multipoint Kronecker Substitution, Section 2.1] and [Gathen and Gerhard, Modern Computer Algebra 3rd Ed., Section 8.4].

◆ make_evaluation_domain()

template<typename FieldType >
std::shared_ptr<evaluation_domain<FieldType> > nil::crypto3::math::make_evaluation_domain ( std::size_t  m)

◆ monomial_to_newton_basis()

template<typename FieldType >
void nil::crypto3::math::monomial_to_newton_basis ( std::vector< typename FieldType::value_type > &  a,
const std::vector< std::vector< std::vector< typename FieldType::value_type >>> &  T,
size_t  n 
)

Perform the general change of basis from Monomial to Newton Basis with Subproduct Tree T. Below we make use of the MonomialToNewton and TNewtonToMonomial pseudocode from [Bostan and Schost 2005. Polynomial Evaluation and Interpolation on Special Sets of Points], on page 12 and 14.

◆ monomial_to_newton_basis_geometric()

template<typename FieldType , typename Range1 , typename Range2 , typename Range3 >
void nil::crypto3::math::monomial_to_newton_basis_geometric ( Range1 &  a,
const Range2 &  geometric_sequence,
const Range3 &  geometric_triangular_sequence,
const std::size_t &  n 
)

Perform the change of basis from Monomial to Newton Basis for geometric sequence. Below we make use of the psuedocode from [Bostan & Schost 2005. Polynomial Evaluation and Interpolation on Special Sets of Points] on page 26.

◆ multiply_by_coset()

template<typename Range , typename FieldValueType >
void nil::crypto3::math::multiply_by_coset ( Range &  a,
const FieldValueType &  g 
)

Translate the vector a to a coset defined by g.

◆ newton_to_monomial_basis()

template<typename FieldType >
void nil::crypto3::math::newton_to_monomial_basis ( std::vector< typename FieldType::value_type > &  a,
const std::vector< std::vector< std::vector< typename FieldType::value_type >>> &  T,
size_t  n 
)

Perform the general change of basis from Newton to Monomial Basis with Subproduct Tree T. Below we make use of the NewtonToMonomial pseudocode from [Bostan and Schost 2005. Polynomial Evaluation and Interpolation on Special Sets of Points], on page 11.

◆ newton_to_monomial_basis_geometric()

template<typename FieldType , typename Range1 , typename Range2 , typename Range3 >
void nil::crypto3::math::newton_to_monomial_basis_geometric ( Range1 &  a,
const Range2 &  geometric_sequence,
const Range3 &  geometric_triangular_sequence,
std::size_t  n 
)

Perform the change of basis from Newton to Monomial Basis for geometric sequence Below we make use of the psuedocode from [Bostan & Schost 2005. Polynomial Evaluation and Interpolation on Special Sets of Points] on page 26.