polynomials.hpp File Reference

Polynomial arithmetic library. More...

#include <initializer_list>
#include "matrices.hpp"

Include dependency graph for polynomials.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	CECCO::Polynomial< T >
	Univariate polynomial p(x) = a₀ + a₁x + … + aₙxⁿ over a CECCO::ComponentType. More...

Namespaces
namespace	CECCO
	Provides a framework for error correcting codes.

Functions
template<ComponentType T>
constexpr bool	CECCO::operator== (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
std::ostream &	CECCO::operator<< (std::ostream &os, const Polynomial< T > &rhs)
template<ComponentType T>
Polynomial< T >	CECCO::ZeroPolynomial ()
	Constant polynomial 0 (cached).
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator+ (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator+ (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator+ (const Polynomial< T > &lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator+ (Polynomial< T > &&lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator- (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator- (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator- (const Polynomial< T > &lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator- (Polynomial< T > &&lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const Polynomial< T > &lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (Polynomial< T > &&lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator/ (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator/ (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator% (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator% (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const Polynomial< T > &lhs, const T &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (Polynomial< T > &&lhs, const T &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const T &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const T &lhs, Polynomial< T > &&rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator/ (const Polynomial< T > &lhs, const T &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator/ (Polynomial< T > &&lhs, const T &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (const Polynomial< T > &lhs, size_t n)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (Polynomial< T > &&lhs, size_t n)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (size_t n, const Polynomial< T > &rhs)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator* (size_t n, Polynomial< T > &&rhs)
template<ComponentType T>
std::pair< Polynomial< T >, Polynomial< T > >	CECCO::poly_long_div (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T>
std::pair< Polynomial< T >, Polynomial< T > >	CECCO::poly_long_div (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::derivative (const Polynomial< T > &poly, size_t s)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::derivative (Polynomial< T > &&poly, size_t s)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::Hasse_derivative (const Polynomial< T > &poly, size_t s)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::Hasse_derivative (Polynomial< T > &&poly, size_t s)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::reciprocal (const Polynomial< T > &poly)
template<ComponentType T>
constexpr Polynomial< T >	CECCO::reciprocal (Polynomial< T > &&poly)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::normalize (const Polynomial< T > &poly)
template<ComponentType T> requires FieldType<T>
constexpr Polynomial< T >	CECCO::normalize (Polynomial< T > &&poly)
template<ComponentType T>
constexpr bool	CECCO::operator!= (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
template<ComponentType T> requires std::convertible_to<std::decay_t<decltype(a)>, T>
constexpr Polynomial< T >	CECCO::Monomial (size_t i, auto &&a=T(1))
	Monomial a · xⁱ
template<ComponentType T>
Polynomial< T >	CECCO::OnePolynomial ()
	Constant polynomial 1 (cached).
template<ComponentType T> requires FieldType<T>
Polynomial< T >	CECCO::GCD (Polynomial< T > a, Polynomial< T > b, Polynomial< T > *s=nullptr, Polynomial< T > *t=nullptr)
	Greatest common divisor of two polynomials via the (extended) Euclidean algorithm.
template<ComponentType T> requires FieldType<T>
Polynomial< T >	CECCO::GCD (const std::vector< Polynomial< T > > &polys)
	Greatest common divisor of a list of polynomials, computed iteratively.
template<ComponentType T> requires FieldType<T>
Polynomial< T >	CECCO::LCM (const Polynomial< T > &a, const Polynomial< T > &b)
	Least common multiple lcm(a, b) = (a · b) / gcd(a, b).
template<ComponentType T> requires FieldType<T>
Polynomial< T >	CECCO::LCM (const std::vector< Polynomial< T > > &polys)
	Least common multiple of a list of polynomials, computed iteratively.
template<ComponentType T>
constexpr Polynomial< T >	CECCO::operator^ (const Polynomial< T > &base, int exponent)
	Polynomial exponentiation by square-and-multiply.
template<uint16_t p, size_t m>
constexpr Vector< Fp< p > >	CECCO::ConwayCoefficients ()
	Coefficient vector [a₀, a₁, …, aₘ] of the Conway polynomial for 𝔽_{p^m}.
template<uint16_t p, size_t m>
constexpr Polynomial< Fp< p > >	CECCO::ConwayPolynomial ()
	Conway polynomial for 𝔽_{p^m} as a Polynomial<Fp<p>>.
template<FieldType T>
Polynomial< T >	CECCO::find_irreducible (size_t degree)
	Sample a random monic irreducible polynomial of degree degree over T.

Detailed Description

Polynomial arithmetic library.

Author

Christian Senger senge.nosp@m.r@in.nosp@m.ue.un.nosp@m.i-st.nosp@m.uttga.nosp@m.rt.d.nosp@m.e

Version

2.2.9

Date

2026

Copyright

Copyright (c) 2026, Christian Senger senge.nosp@m.r@in.nosp@m.ue.un.nosp@m.i-st.nosp@m.uttga.nosp@m.rt.d.nosp@m.e

Licensed for noncommercial use only, including academic teaching, research, and personal non-profit purposes. Commercial use is prohibited without a separate commercial license. See the LICENSE file in the repository root for full terms and how to request a commercial license.

Description

Univariate polynomials over any CECCO::ComponentType (finite fields, double, std::complex<double>, signed integers). Algorithms that need division — long division, GCD, LCM, derivatives, normalisation, irreducibility test — require CECCO::FieldType coefficients. Cross-field constructors between two finite fields of the same characteristic route through CECCO::details::largest_common_subfield_t. Polynomials are stored in canonical form (leading zero coefficients pruned automatically) and evaluated by Horner.

Usage_Example

using F7 = Fp<7>;
Polynomial<F7> p = {1, 2, 3};                        // 1 + 2x + 3x²
Polynomial<F7> q = {4, 5};                           // 4 + 5x
auto r = p * q;                                      // multiplication
F7 v = p(F7(2));                                     // Horner-method evaluation
auto [quot, rem] = p.poly_long_div(q);               // long division
auto g = GCD(p, q);                                  // gcd via extended Euclid
 
using F2 = Fp<2>;
using F4 = Ext<F2, MOD{1, 1, 1}>;
Polynomial<F2> a = {1, 0, 1};                        // x² + 1 over F₂
Polynomial<F4> b(a);                                 // upcast F₂ ⊆ F₄

Performance_Features

• Hamming weight is lazily computed and cached.
• Move-aware free arithmetic operators, so chained expressions don't copy intermediates.
• Horner's method gives O(n) polynomial evaluation.
• Canonical form (leading zeros pruned) is maintained by the mutating operations.

See also

fields.hpp, vectors.hpp, matrices.hpp, field_concepts_traits.hpp

Definition in file polynomials.hpp.