Namespaces
	detail

	expressions

	polynomial

Classes
class	arithmetic_sequence_domain

class	basic_radix2_domain

class	evaluation_domain

class	extended_radix2_domain

class	geometric_sequence_domain

class	polynomial

class	step_radix2_domain

Functions
template<typename Range >
void	addition (Range &c, const Range &a, const Range &b)

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

template<typename Range >
void	condense (Range &a)

template<typename Range >
void	division (Range &q, Range &r, const Range &a, const Range &b)

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 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 Range >
void	fft_multiplication (Range &c, const Range &a, const Range &b)

template<typename Range >
bool	is_zero (const Range &a)

template<typename InputRange , typename FieldValueType = typename std::iterator_traits<typename InputRange::iterator>::value_type::first_type>
std::enable_if< std::is_same< std::pair< FieldValueType, FieldValueType >, typename std::iterator_traits< typename InputRange::iterator >::value_type >::value, polynomial< FieldValueType > >::type	lagrange_interpolation (const InputRange &points)

template<typename FieldType >
std::shared_ptr< evaluation_domain< FieldType > >	make_evaluation_domain (std::size_t m)
	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. More...

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 >
void	multiplication (Range &c, const Range &a, const Range &b)

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)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator* (const FieldValueType &A, const polynomial< FieldValueType, Allocator > &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator* (const polynomial< FieldValueType, Allocator > &A, const FieldValueType &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator+ (const FieldValueType &A, const polynomial< FieldValueType, Allocator > &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator+ (const polynomial< FieldValueType, Allocator > &A, const FieldValueType &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator- (const FieldValueType &A, const polynomial< FieldValueType, Allocator > &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator- (const polynomial< FieldValueType, Allocator > &A, const FieldValueType &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator/ (const FieldValueType &A, const polynomial< FieldValueType, Allocator > &B)

template<typename FieldValueType , typename Allocator = std::allocator<FieldValueType>, typename = typename std::enable_if<detail::is_field_element<FieldValueType>::value>::type>
polynomial< FieldValueType, Allocator >	operator/ (const polynomial< FieldValueType, Allocator > &A, const FieldValueType &B)

template<typename Range >
void	reverse (Range &a, std::size_t n)

template<typename Range >
void	subtraction (Range &c, const Range &a, const Range &b)

template<typename Range >
Range	transpose_multiplication (const std::size_t &n, const Range &a, const Range &c)

template<typename FieldType >
constexpr std::enable_if< std::is_same< typename FieldType::value_type, std::complex< double > >::value, typename FieldType::value_type >::type	unity_root (const std::size_t n)

template<typename FieldType >
constexpr std::enable_if<!std::is_same< typename FieldType::value_type, std::complex< double > >::value, typename FieldType::value_type >::type	unity_root (const std::size_t n)

Function Documentation

◆ addition()

template<typename Range >

void nil::crypto3::math::addition	(	Range &	c,
		const Range &	a,
		const Range &	b
	)

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

◆ 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.

◆ 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]

◆ division()

template<typename Range >

void nil::crypto3::math::division	(	Range &	q,
		Range &	r,
		const Range &	a,
		const Range &	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.

◆ 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 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).

◆ fft_multiplication()

template<typename Range >

void nil::crypto3::math::fft_multiplication	(	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.

◆ is_zero()

template<typename Range >

bool nil::crypto3::math::is_zero ( const Range & a )

Returns true if polynomial A is a zero polynomial.

◆ lagrange_interpolation()

template<typename InputRange , typename FieldValueType = typename std::iterator_traits<typename InputRange::iterator>::value_type::first_type>

std::enable_if< std::is_same<std::pair<FieldValueType, FieldValueType>, typename std::iterator_traits<typename InputRange::iterator>::value_type>::value, polynomial<FieldValueType> >::type nil::crypto3::math::lagrange_interpolation ( const InputRange & points )

◆ make_evaluation_domain()

template<typename FieldType >

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

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.

◆ 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.

◆ multiplication()

template<typename Range >

void nil::crypto3::math::multiplication	(	Range &	c,
		const Range &	a,
		const Range &	b
	)

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

◆ 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.