CECCO::Polynomial< T > Class Template Reference

Univariate polynomial p(x) = a₀ + a₁x + … + aₙxⁿ over a CECCO::ComponentType. More...

#include <polynomials.hpp>

Inheritance diagram for CECCO::Polynomial< T >:

Public Types
enum	CacheIds { Weight = 0 }

Public Member Functions
template<FiniteFieldType S>
Polynomial< T > &	operator= (const Polynomial< S > &rhs)
template<typename U> requires std::convertible_to<std::decay_t<U>, T>
constexpr Polynomial< T > &	add_to_coefficient (size_t i, U &&c)
template<typename U> requires std::convertible_to<std::decay_t<U>, T>
constexpr Polynomial< T > &	set_coefficient (size_t i, U &&c)
Constructors
constexpr	Polynomial () noexcept=default
	Default constructor: empty polynomial (no coefficients; distinct from the zero polynomial).
constexpr	Polynomial (int e)
	Constant polynomial from an int (constructs T(e)).
constexpr	Polynomial (const T &e)
	Constant polynomial from a coefficient.
constexpr	Polynomial (const std::initializer_list< T > &l)
	From an initializer list of coefficients in ascending degree order.
constexpr	Polynomial (const Polynomial &other)
constexpr	Polynomial (Polynomial &&other) noexcept
template<FiniteFieldType S>
	Polynomial (const Polynomial< S > &other)
	Cross-field conversion between two finite fields of the same characteristic.
	Polynomial (const Vector< T > &v)
	From a coefficient vector: v[i] becomes the coefficient of x^i.
Assignment Operators
constexpr Polynomial &	operator= (const T &rhs)
	Assign a scalar: replace *this with the constant polynomial rhs.
constexpr Polynomial &	operator= (const Polynomial< T > &rhs)
constexpr Polynomial &	operator= (Polynomial &&rhs) noexcept
template<FiniteFieldType S>
Polynomial &	operator= (const Polynomial< S > &other)
	Cross-field assignment (same semantics as the cross-field constructor).
Unary Arithmetic Operations
constexpr Polynomial	operator+ () const &
	Unary + (lvalue): returns a copy.
constexpr Polynomial	operator+ () &&noexcept
	Unary + (rvalue): returns the rvalue itself.
constexpr Polynomial	operator- () const &
	Unary − (lvalue): returns a new polynomial with each coefficient negated.
constexpr Polynomial	operator- () &&
	Unary − (rvalue): negates coefficients in place.
T	operator() (const T &s) const
	Evaluate at s using Horner's method (O(n)).
Compound Assignment Operations
constexpr Polynomial &	operator+= (const Polynomial &rhs)
	Coefficient-wise addition; expands storage if rhs has higher degree, then prunes.
constexpr Polynomial &	operator-= (const Polynomial &rhs)
	Coefficient-wise subtraction; expands storage if rhs has higher degree, then prunes.
constexpr Polynomial &	operator*= (const Polynomial &rhs)
	Polynomial multiplication by convolution (O(n²)).
Polynomial &	operator/= (const Polynomial &rhs)
	Polynomial division: *this becomes the quotient of (*this) / rhs.
Polynomial &	operator%= (const Polynomial &rhs)
	Polynomial remainder: *this becomes (*this) mod rhs.
constexpr Polynomial &	operator*= (const T &s)
	Multiply every coefficient by the scalar s.
Polynomial &	operator/= (const T &s)
	Divide every coefficient by the scalar s.
constexpr Polynomial &	operator*= (size_t n)
	Multiply every coefficient by the integer n; reduces n modulo characteristic.
std::pair< Polynomial< T >, Polynomial< T > >	poly_long_div (const Polynomial< T > &rhs) const
	Long division: returns (q, r) with *this == q · rhs + r and r == 0 or deg(r) < deg(rhs).
Randomization
Polynomial &	randomize (size_t d)
	Replace *this with a random polynomial of degree exactly d.
Differentiation
Polynomial &	differentiate (size_t s)
	In-place classical s-th derivative.
Polynomial &	Hasse_differentiate (size_t s)
	In-place s-th Hasse derivative (= classical s-th derivative divided by s!).
Information and Properties
size_t	degree () const
	Degree max{i : aᵢ ≠ 0}.
Vector< T >	get_coefficients () const
	Coefficient vector (length = number of stored coefficients; 0 for an empty polynomial).
size_t	trailing_degree () const
	Trailing degree min{i : aᵢ ≠ 0}.
const T &	trailing_coefficient () const
	Coefficient of the lowest non-zero power.
const T &	leading_coefficient () const
	Coefficient of the highest non-zero power.
constexpr bool	is_empty () const noexcept
	True iff *this has no coefficients (distinct from the zero polynomial).
bool	is_zero () const
	True iff *this is the zero polynomial (one coefficient, equal to T(0)).
bool	is_one () const
	True iff *this is the constant polynomial 1.
bool	is_monic () const
	True iff the leading coefficient equals 1.
constexpr bool	is_irreducible () const
	Test irreducibility by trial division against every monic polynomial of degree ≤ deg/2.
size_t	wH () const
	Hamming weight: number of non-zero, non-erased coefficients; cached on first call.
Coefficient Access and Manipulation
template<typename U> requires std::convertible_to<std::decay_t<U>, T>
constexpr Polynomial &	add_to_coefficient (size_t i, U &&c)
	Add c to the coefficient of x^i; grows the polynomial if i > degree.
template<typename U> requires std::convertible_to<std::decay_t<U>, T>
constexpr Polynomial &	set_coefficient (size_t i, U &&c)
	Set the coefficient of x^i to c; grows the polynomial if i > degree.
constexpr Polynomial &	reciprocal ()
	Reciprocal: reverse coefficients, sending p(x) to xⁿ · p(1/x).
constexpr Polynomial &	normalize ()
	Make monic by dividing every coefficient by the leading one (no-op on zero or already-monic).
constexpr T	operator[] (size_t i) const
	Coefficient of x^i; returns T(0) for i > degree.

Friends
bool	operator== (const Polynomial &lhs, const Polynomial &rhs)
std::ostream &	operator<< (std::ostream &os, const Polynomial &rhs)

Detailed Description

template<ComponentType T>
class CECCO::Polynomial< T >

Univariate polynomial p(x) = a₀ + a₁x + … + aₙxⁿ over a CECCO::ComponentType.

Template Parameters

T	Coefficient type satisfying CECCO::ComponentType (finite field, double, std::complex<double>, or signed integer including InfInt)

Coefficients are stored low-to-high in a contiguous buffer; the leading-zero invariant is maintained by an internal prune() so data.size() - 1 is the degree (when non-empty and not the zero polynomial). The empty polynomial (no coefficients) is distinct from the zero polynomial — most queries throw std::invalid_argument on an empty polynomial.

Methods that need division are gated by requires FieldType<T>; methods that compare against zero (degree, Hamming weight, …) are gated by requires ReliablyComparableType<T>.

Usage_Example

using F7 = Fp<7>;
Polynomial<F7> p = {1, 2, 3};                    // 1 + 2x + 3x²
Polynomial<F7> q = {4, 5};                       // 4 + 5x
auto sum = p + q;
auto prod = p * q;
F7 v = p(F7(3));                                 // evaluation
auto [quot, rem] = p.poly_long_div(q);
size_t w = p.wH();                               // Hamming weight (cached)

Definition at line 121 of file polynomials.hpp.

Member Enumeration Documentation

CacheIds

template<ComponentType T>

enum CECCO::Polynomial::CacheIds

Enumerator
Weight

Definition at line 127 of file polynomials.hpp.

Constructor & Destructor Documentation

Polynomial() [1/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( )

constexprdefaultnoexcept

Default constructor: empty polynomial (no coefficients; distinct from the zero polynomial).

Polynomial() [2/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( int e )

inlineconstexpr

Constant polynomial from an int (constructs T(e)).

Definition at line 137 of file polynomials.hpp.

Polynomial() [3/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( const T & e )

inlineconstexpr

Constant polynomial from a coefficient.

Definition at line 140 of file polynomials.hpp.

Here is the caller graph for this function:

Polynomial() [4/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( const std::initializer_list< T > & l )

inlineconstexpr

From an initializer list of coefficients in ascending degree order.

l[i] becomes the coefficient of x^i. Trailing (high-degree) zeros are pruned to keep canonical form: Polynomial<int>{1, 2, 3} represents 1 + 2x + 3x².

Definition at line 148 of file polynomials.hpp.

Here is the call graph for this function:

Polynomial() [5/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( const Polynomial< T > & other )

inlineconstexpr

Definition at line 150 of file polynomials.hpp.

Polynomial() [6/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial ( Polynomial< T > && other )

inlineconstexprnoexcept

Definition at line 151 of file polynomials.hpp.

Polynomial() [7/8]

template<ComponentType T>

template<FiniteFieldType S>

CECCO::Polynomial< T >::Polynomial

(

const Polynomial< S > &

other

)

Cross-field conversion between two finite fields of the same characteristic.

Template Parameters

S	Source field type (Polynomial<S>); must share characteristic with T

Converts coefficient by coefficient via T's cross-field constructor, which routes through CECCO::details::largest_common_subfield_t and so handles disjoint construction towers. Propagates std::invalid_argument if any coefficient is not representable in T.

Definition at line 495 of file polynomials.hpp.

Polynomial() [8/8]

template<ComponentType T>

CECCO::Polynomial< T >::Polynomial

(

const Vector< T > &

v

)

From a coefficient vector: v[i] becomes the coefficient of x^i.

Resulting degree is v.get_n() - 1 (after pruning). For cross-field conversion, convert the vector first.

Definition at line 502 of file polynomials.hpp.

Member Function Documentation

add_to_coefficient() [1/2]

template<ComponentType T>

template<typename U>
requires std::convertible_to<std::decay_t<U>, T>

Polynomial< T > & CECCO::Polynomial< T >::add_to_coefficient ( size_t i, U && c )

constexpr

Definition at line 849 of file polynomials.hpp.

add_to_coefficient() [2/2]

template<ComponentType T>

template<typename U>
requires std::convertible_to<std::decay_t<U>, T>

Polynomial & CECCO::Polynomial< T >::add_to_coefficient ( size_t i, U && c )

constexpr

Add c to the coefficient of x^i; grows the polynomial if i > degree.

Parameters

i	Power of x
c	Value to add (perfect-forwarded)

degree()

template<ComponentType T>
requires ReliablyComparableType<T>

size_t CECCO::Polynomial< T >::degree

(

)

const

Degree max{i : aᵢ ≠ 0}.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 801 of file polynomials.hpp.

differentiate()

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::differentiate

(

size_t

s

)

In-place classical s-th derivative.

d^s/dx^s [∑ aᵢ xⁱ] = ∑_{i ≥ s} (i! / (i − s)!) aᵢ x^{i − s}. The s-th derivative of a polynomial of degree < s is the zero polynomial. s == 0 is the identity.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 748 of file polynomials.hpp.

get_coefficients()

template<ComponentType T>

Vector< T > CECCO::Polynomial< T >::get_coefficients

(

)

const

Coefficient vector (length = number of stored coefficients; 0 for an empty polynomial).

Definition at line 809 of file polynomials.hpp.

Hasse_differentiate()

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::Hasse_differentiate

(

size_t

s

)

In-place s-th Hasse derivative (= classical s-th derivative divided by s!).

D^{(s)}[∑ aᵢ xⁱ] = ∑_{i ≥ s} C(i, s) aᵢ x^{i − s}. Useful in characteristic p where the classical derivative loses information whenever s ≥ p.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 781 of file polynomials.hpp.

is_empty()

template<ComponentType T>

bool CECCO::Polynomial< T >::is_empty ( ) const

inlineconstexprnoexcept

True iff *this has no coefficients (distinct from the zero polynomial).

Definition at line 360 of file polynomials.hpp.

is_irreducible()

template<ComponentType T>

bool CECCO::Polynomial< T >::is_irreducible ( ) const

inlineconstexpr

Test irreducibility by trial division against every monic polynomial of degree ≤ deg/2.

Cost grows as q^{deg/2} in field size — practical only for small fields and small degrees.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 405 of file polynomials.hpp.

is_monic()

template<ComponentType T>

bool CECCO::Polynomial< T >::is_monic ( ) const

inline

True iff the leading coefficient equals 1.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 391 of file polynomials.hpp.

is_one()

template<ComponentType T>

bool CECCO::Polynomial< T >::is_one ( ) const

inline

True iff *this is the constant polynomial 1.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 379 of file polynomials.hpp.

is_zero()

template<ComponentType T>

bool CECCO::Polynomial< T >::is_zero ( ) const

inline

True iff *this is the zero polynomial (one coefficient, equal to T(0)).

Exceptions

std::invalid_argument

if *this is empty

Definition at line 367 of file polynomials.hpp.

leading_coefficient()

template<ComponentType T>

const T & CECCO::Polynomial< T >::leading_coefficient

(

)

const

Coefficient of the highest non-zero power.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 839 of file polynomials.hpp.

normalize()

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::normalize ( )

constexpr

Make monic by dividing every coefficient by the leading one (no-op on zero or already-monic).

Definition at line 899 of file polynomials.hpp.

operator%=()

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::operator%=

(

const Polynomial< T > &

rhs

)

Polynomial remainder: *this becomes (*this) mod rhs.

Specialised path when deg(this) == deg(rhs) (one subtraction); long division otherwise.

Exceptions

std::invalid_argument

if rhs is the zero polynomial

Definition at line 627 of file polynomials.hpp.

operator()()

template<ComponentType T>

T CECCO::Polynomial< T >::operator()

(

const T &

s

)

const

Evaluate at s using Horner's method (O(n)).

Returns

p(s) = a₀ + a₁s + a₂s² + … + aₙsⁿ

Exceptions

std::invalid_argument

if *this is empty

Definition at line 575 of file polynomials.hpp.

operator*=() [1/3]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator*= ( const Polynomial< T > & rhs )

constexpr

Polynomial multiplication by convolution (O(n²)).

Returns

Reference to *this with degree deg(this) + deg(rhs)

Exceptions

std::invalid_argument

if either operand is the empty polynomial

Definition at line 603 of file polynomials.hpp.

operator*=() [2/3]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator*= ( const T & s )

constexpr

Multiply every coefficient by the scalar s.

Definition at line 651 of file polynomials.hpp.

operator*=() [3/3]

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::operator*= ( size_t n )

constexpr

Multiply every coefficient by the integer n; reduces n modulo characteristic.

Definition at line 664 of file polynomials.hpp.

operator+() [1/2]

template<ComponentType T>

Polynomial CECCO::Polynomial< T >::operator+ ( ) &&

inlineconstexprnoexcept

Unary + (rvalue): returns the rvalue itself.

Definition at line 200 of file polynomials.hpp.

operator+() [2/2]

template<ComponentType T>

Polynomial CECCO::Polynomial< T >::operator+ ( ) const &

inlineconstexpr

Unary + (lvalue): returns a copy.

Definition at line 198 of file polynomials.hpp.

operator+=()

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator+= ( const Polynomial< T > & rhs )

constexpr

Coefficient-wise addition; expands storage if rhs has higher degree, then prunes.

Definition at line 585 of file polynomials.hpp.

operator-() [1/2]

template<ComponentType T>

Polynomial< T > CECCO::Polynomial< T >::operator- ( ) &&

constexpr

Unary − (rvalue): negates coefficients in place.

Definition at line 568 of file polynomials.hpp.

operator-() [2/2]

template<ComponentType T>

Polynomial< T > CECCO::Polynomial< T >::operator- ( ) const &

constexpr

Unary − (lvalue): returns a new polynomial with each coefficient negated.

Definition at line 561 of file polynomials.hpp.

operator-=()

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator-= ( const Polynomial< T > & rhs )

constexpr

Coefficient-wise subtraction; expands storage if rhs has higher degree, then prunes.

Definition at line 594 of file polynomials.hpp.

operator/=() [1/2]

template<ComponentType T>
requires FieldType<T>

Polynomial< T > & CECCO::Polynomial< T >::operator/=

(

const Polynomial< T > &

rhs

)

Polynomial division: *this becomes the quotient of (*this) / rhs.

Exceptions

std::invalid_argument

if rhs is the zero polynomial

Definition at line 617 of file polynomials.hpp.

operator/=() [2/2]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator/=

(

const T &

s

)

Divide every coefficient by the scalar s.

Exceptions

std::invalid_argument

if s == T(0)

Note

Round-trip (p / s) * s == p is only guaranteed when T satisfies CECCO::FieldType (otherwise integer rounding may corrupt coefficients).

Definition at line 682 of file polynomials.hpp.

operator=() [1/5]

template<ComponentType T>

template<FiniteFieldType S>

Polynomial & CECCO::Polynomial< T >::operator=

(

const Polynomial< S > &

other

)

Cross-field assignment (same semantics as the cross-field constructor).

operator=() [2/5]

template<ComponentType T>

template<FiniteFieldType S>

Polynomial< T > & CECCO::Polynomial< T >::operator=

(

const Polynomial< S > &

rhs

)

Definition at line 547 of file polynomials.hpp.

operator=() [3/5]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator= ( const Polynomial< T > & rhs )

constexpr

Definition at line 519 of file polynomials.hpp.

operator=() [4/5]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator= ( const T & rhs )

constexpr

Assign a scalar: replace *this with the constant polynomial rhs.

Definition at line 508 of file polynomials.hpp.

operator=() [5/5]

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::operator= ( Polynomial< T > && rhs )

constexprnoexcept

Definition at line 532 of file polynomials.hpp.

operator[]()

template<ComponentType T>

T CECCO::Polynomial< T >::operator[] ( size_t i ) const

constexpr

Coefficient of x^i; returns T(0) for i > degree.

Definition at line 908 of file polynomials.hpp.

poly_long_div()

template<ComponentType T>
requires FieldType<T>

std::pair< Polynomial< T >, Polynomial< T > > CECCO::Polynomial< T >::poly_long_div

(

const Polynomial< T > &

rhs

)

const

Long division: returns (q, r) with *this == q · rhs + r and r == 0 or deg(r) < deg(rhs).

Exceptions

std::invalid_argument

if rhs is the zero polynomial

Definition at line 690 of file polynomials.hpp.

randomize()

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::randomize

(

size_t

d

)

Replace *this with a random polynomial of degree exactly d.

The leading coefficient is resampled until non-zero, so the result really has degree d. Distribution per coefficient: finite-field types draw uniformly from the field; signed integers from [−100, 100]; double and the parts of std::complex<double> from [−1, 1].

Definition at line 716 of file polynomials.hpp.

reciprocal()

template<ComponentType T>

Polynomial< T > & CECCO::Polynomial< T >::reciprocal ( )

constexpr

Reciprocal: reverse coefficients, sending p(x) to xⁿ · p(1/x).

Definition at line 892 of file polynomials.hpp.

set_coefficient() [1/2]

template<ComponentType T>

template<typename U>
requires std::convertible_to<std::decay_t<U>, T>

Polynomial< T > & CECCO::Polynomial< T >::set_coefficient ( size_t i, U && c )

constexpr

Definition at line 873 of file polynomials.hpp.

set_coefficient() [2/2]

template<ComponentType T>

template<typename U>
requires std::convertible_to<std::decay_t<U>, T>

Polynomial & CECCO::Polynomial< T >::set_coefficient ( size_t i, U && c )

constexpr

Set the coefficient of x^i to c; grows the polynomial if i > degree.

Parameters

i	Power of x
c	New value (perfect-forwarded)

trailing_coefficient()

template<ComponentType T>
requires ReliablyComparableType<T>

const T & CECCO::Polynomial< T >::trailing_coefficient

(

)

const

Coefficient of the lowest non-zero power.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 828 of file polynomials.hpp.

trailing_degree()

template<ComponentType T>
requires ReliablyComparableType<T>

size_t CECCO::Polynomial< T >::trailing_degree

(

)

const

Trailing degree min{i : aᵢ ≠ 0}.

Exceptions

std::invalid_argument

if *this is empty

Definition at line 816 of file polynomials.hpp.

wH()

template<ComponentType T>

size_t CECCO::Polynomial< T >::wH ( ) const

inline

Hamming weight: number of non-zero, non-erased coefficients; cached on first call.

Definition at line 434 of file polynomials.hpp.

Friends And Related Symbol Documentation

operator<<

template<ComponentType T>

std::ostream & operator<< ( std::ostream & os, const Polynomial< T > & rhs )

friend

Definition at line 1216 of file polynomials.hpp.

operator==

template<ComponentType T>

bool operator== ( const Polynomial< T > & lhs, const Polynomial< T > & rhs )

friend

Definition at line 1206 of file polynomials.hpp.

---

The documentation for this class was generated from the following files:

• fields.hpp
• polynomials.hpp