fields.hpp File Reference

Finite field arithmetic library. More...

#include <span>
#include "polynomials.hpp"

Include dependency graph for fields.hpp:

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

Go to the source code of this file.

Classes
class	CECCO::details::Base
	Tag base for the CRTP-protection idiom. More...
class	CECCO::details::Field< T >
	CRTP base documenting the interface every field type must provide. More...
class	CECCO::Rationals< T >
	Field of rational numbers ℚ = { p/q : p, q ∈ ℤ, q ≠ 0 } with selectable precision. More...
struct	CECCO::details::Lut1D< LabelType, FieldSize >
	1D lookup table for unary field operations (negation, inversion, order) More...
struct	CECCO::details::Lut2D< LabelType, FieldSize >
	2D lookup table for commutative binary operations, optionally compressed More...
struct	CECCO::details::Lut2Dcoeff< LabelType, ExtensionDegree, FieldSize >
	Lookup table mapping each extension-field label to its base-field coefficient vector. More...
struct	CECCO::details::LutHolderNoProvider< LutType, F, LutMode::CompileTime >
	CompileTime specialisation: table is a constexpr static member. More...
struct	CECCO::details::LutHolderNoProvider< LutType, F, LutMode::RunTime >
	RunTime specialisation: thread-safe lazy initialisation on first access. More...
struct	CECCO::details::LutHolder< LutType, ProviderLutType, P, F, LutMode::CompileTime >
	CompileTime specialisation: table baked into the binary. More...
struct	CECCO::details::LutHolder< LutType, ProviderLutType, P, F, LutMode::RunTime >
	RunTime specialisation: thread-safe lazy initialisation, dependency resolved on first access. More...
class	CECCO::Embedding< SUBFIELD, SUPERFIELD >
	Functor representing the field embedding φ: SUBFIELD → SUPERFIELD, with reverse lookup. More...
struct	CECCO::details::IsomorphismPair< A, B >
	Shared static storage of the forward and reverse maps for the isomorphism A ↔ B. More...
class	CECCO::Isomorphism< A, B >
	Functor representing the field isomorphism φ: A → B between two same-size finite fields. More...
class	CECCO::Fp< p >
	Prime field 𝔽_p ≅ ℤ/pℤ More...
class	CECCO::Ext< B, modulus, mode >
	Extension field 𝔽_{q^m} ≅ B[x]/(f(x)), constructed from a base field and an irreducible monic modulus polynomial. More...
class	CECCO::Iso< MAIN, OTHERS >
	Single logical field unifying several pairwise-isomorphic representations. More...

Namespaces
namespace	CECCO
	Provides a framework for error correcting codes.
namespace	CECCO::details
	Contains implementation details not to be exposed to the user. Functions and classes here may change without notice.

Macros
#define	CECCO_ERASURE_SUPPORT
	Enables erase() / unerase() / is_erased() on every field type.
#define	CECCO_USE_LUTS_FOR_FP
	Force prime fields to use lookup tables instead of modular arithmetic.
#define	CECCO_COMPRESS_LUTS_FROM_Q   256
	Compression threshold for 2D lookup tables in extension fields.

Typedefs
template<uint16_t p, uint8_t m = 1>
using	CECCO::label_t = typename std::conditional_t<sqm(p, m) < 255, uint8_t, uint16_t>

Functions
template<SignedIntType T>
std::ostream &	CECCO::operator<< (std::ostream &os, const Rationals< T > &e)
	Print as "numerator/denominator" (or just "numerator" when denominator is 1).
template<uint16_t q, uint8_t m, size_t SIZE>
static size_t constexpr	CECCO::details::integer_from_coeffs (const std::array< size_t, SIZE > &coeffs) noexcept
	Encode polynomial coefficients (low-to-high) as a base-q integer label.
template<typename LabelType, LabelType FieldSize>
constexpr auto	CECCO::details::compute_multiplicative_orders (const Lut2D< LabelType, FieldSize > &mul_lut)
	Build the table of multiplicative orders for all elements of 𝔽_Q.
template<typename LabelType, LabelType FieldSize> requires (is_prime<LabelType>(FieldSize))
constexpr auto	CECCO::details::compute_multiplicative_inverses_direct ()
	Build multiplicative-inverse table for 𝔽_p via extended Euclidean algorithm.
template<typename LabelType, LabelType FieldSize>
constexpr auto	CECCO::details::compute_multiplicative_inverses_search (const Lut2D< LabelType, FieldSize > &mul_lut)
	Build multiplicative-inverse table by searching the multiplication LUT.
template<typename LabelType, LabelType FieldSize> requires (is_prime<LabelType>(FieldSize))
constexpr auto	CECCO::details::compute_additive_inverses_direct ()
	Build additive-inverse (negation) table for 𝔽_p.
template<typename LabelType, LabelType FieldSize>
constexpr auto	CECCO::details::compute_additive_inverses_search (const Lut2D< LabelType, FieldSize > &add_lut)
	Build additive-inverse table by searching the addition LUT.
template<typename LabelType, LabelType FieldSize> requires (is_prime<LabelType>(FieldSize))
constexpr auto	CECCO::details::compute_modular_addition_table ()
	Build the addition table for 𝔽_p: lut_add(a, b) = (a + b) mod p.
template<typename F>
constexpr F::label_t	CECCO::details::compute_primitive_root ()
	Smallest primitive root of F* by direct power enumeration.
template<typename LabelType, LabelType FieldSize, typename LutCoeffType, uint8_t ExtensionDegree, typename BaseFieldType>
constexpr auto	CECCO::details::compute_polynomial_addition_table (const LutCoeffType &lut_coeff)
	Build the addition table for 𝔽_{q^m} via coefficient-wise base-field addition.
template<typename FieldType>
size_t	CECCO::details::calculate_multiplicative_order (const FieldType &element)
	Multiplicative order of element by repeated multiplication.
template<typename LabelType, LabelType FieldSize>
constexpr LabelType	CECCO::details::find_generator (const Lut1D< LabelType, FieldSize > &lut_mul_ord)
	First element with multiplicative order Q − 1 (a generator of 𝔽_Q*).
template<typename LabelType, LabelType FieldSize> requires (is_prime<LabelType>(FieldSize))
constexpr auto	CECCO::details::compute_modular_multiplication_table ()
	Build the multiplication table for 𝔽_p: lut_mul(a, b) = (a · b) mod p.
template<typename LabelType, LabelType FieldSize, typename LutCoeffType, uint8_t ExtensionDegree, typename BaseFieldType, auto Modulus>
constexpr auto	CECCO::details::compute_polynomial_multiplication_table (const LutCoeffType &lut_coeff)
	Build the multiplication table for 𝔽_{q^m}: polynomial multiply, then reduce mod f(x).
template<uint16_t p>
std::ostream &	CECCO::operator<< (std::ostream &os, const Fp< p > &e)
	Print as the integer label (or ERASURE_MARKER if erased).
template<FiniteFieldType B, MOD modulus, LutMode mode>
std::ostream &	CECCO::operator<< (std::ostream &os, const Ext< B, modulus, mode > &e)
	Print as the integer label (or ERASURE_MARKER if erased).
Field Arithmetic Operators
Free CRTP operators (+, −, *, /, ^) for any CECCO::FieldType Each operator constructs a result by calling T's compound assignment, with rvalue overloads that move from a temporary instead of copying. Scalar multiplication takes the integer on either side. Division throws std::invalid_argument if the right operand is zero. operator^ exponentiates by square-and-multiply via CECCO::sqm. Warning operator^ does not follow C++ precedence for ^: in b * a ^ p the parser evaluates (b * a) ^ p. Parenthesise as b * (a ^ p), or call CECCO::sqm directly.
template<FieldType T>
constexpr T	CECCO::operator+ (const T &lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator+ (T &&lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator+ (const T &lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator+ (T &&lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator- (const T &lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator- (T &&lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator- (const T &lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator- (T &&lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator* (const T &lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator* (T &&lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator* (const T &lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator* (T &&lhs, T &&rhs)
template<FieldType T>
constexpr T	CECCO::operator* (const T &lhs, uint16_t rhs)
template<FieldType T>
constexpr T	CECCO::operator* (uint16_t lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator* (T &&lhs, int rhs)
template<FieldType T>
constexpr T	CECCO::operator* (int lhs, T &&rhs)
template<FieldType T>
T	CECCO::operator/ (const T &lhs, const T &rhs)
template<FieldType T>
T	CECCO::operator/ (T &&lhs, const T &rhs)
template<FieldType T>
constexpr T	CECCO::operator^ (const T &base, int exponent)
template<FieldType T>
constexpr T	CECCO::operator^ (T &&base, int exponent)

Variables
constexpr std::string_view	CECCO::ERASURE_MARKER = "X"
template<typename LutType, LutType(*)() F>
constexpr LutType	CECCO::details::LutHolderNoProvider< LutType, F, LutMode::CompileTime >::lut
template<typename LutType, typename ProviderLutType, const ProviderLutType &(*)() P, LutType(*)(const ProviderLutType &(*)()) F>
constexpr LutType	CECCO::details::LutHolder< LutType, ProviderLutType, P, F, LutMode::CompileTime >::lut

Detailed Description

Finite field 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.3.12

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

Finite-field arithmetic. The library provides:

• prime fields 𝔽_p ≅ ℤ/pℤ via CECCO::Fp;
• extension fields 𝔽_{q^m} ≅ B[x]/(f(x)) over a base field B and an irreducible monic modulus f(x), via CECCO::Ext, with selectable LUT generation mode (runtime or compile-time);
• merged field towers via CECCO::Iso, which exposes one logical field from several isomorphic representations and connects otherwise-disjoint construction towers;
• cross-field constructors that pick the bridge field with CECCO::details::largest_common_subfield_t;
• rational numbers ℚ with selectable precision via CECCO::Rationals.

A field tower in this library is a sequence of constructed extensions. Mathematical intermediate fields that were never constructed are not part of the tower. Two towers ending at isomorphic fields can be glued together by wrapping the two endpoints in an Iso.

Usage_Example

using F2     = Fp<2>;
using F3     = Fp<3>;
using F4     = Ext<F2, {1, 1, 1}, LutMode::CompileTime>;  // 𝔽₂[x]/(x² + x + 1)
using F9     = Ext<F3, {2, 2, 1}, LutMode::CompileTime>;
using F16_a  = Ext<F2, {1, 0, 0, 1, 1}>;                  // RunTime LUTs (default)
using F16_b  = Ext<F4, {2, 1, 1}>;
using F16    = Iso<F16_a, F16_b>;                         // merge the two F16 towers
using F256_a = Ext<F2, {1, 1, 0, 1, 0, 0, 0, 1, 1}>;
using F256_b = Ext<F4, {2, 2, 2, 0, 1}>;
using F256_c = Ext<F16, {6, 13, 1}>;
using F256   = Iso<F256_a, F256_b, F256_c>;
 
F9 a(5), b(7);
auto c = a * b + F9(1);                       // arithmetic
size_t ord = a.get_multiplicative_order();
Vector<F3> v = a.as_vector<F3>();             // coordinate vector over F3
 
F16 d(1);
F256 e(d);                                    // upcast: F16 ⊆ F256

Performance_Features

• LUT modes per CECCO::Ext instantiation: LutMode::RunTime (default; faster compilation, lazy first-access initialisation) or LutMode::CompileTime (zero startup, tables baked into the binary). Mix freely within a tower.
• For extension fields with q ≥ CECCO_COMPRESS_LUTS_FROM_Q, the addition and multiplication tables are stored compressed (upper triangle only), saving ~50 % memory.
• Pure CRTP — no virtual dispatch; concepts (CECCO::FieldType, CECCO::FiniteFieldType) enforce the interface at compile time.

Note

CompileTime mode can exceed compiler recursion / step limits for larger fields. If needed, raise with -fconstexpr-depth=4294967295 -fconstexpr-steps=4294967295 (clang) or -fconstexpr-ops-limit=4294967295 (g++). Rule of thumb: CompileTime up to ~150 elements, RunTime above.

Irreducible_Polynomial_Construction

CECCO::Ext requires the modulus to be a monic irreducible polynomial of degree ≥ 2, coefficients given low-to-high (constant term first). To find one inside the library:

using B = Fp<3>;
auto p = find_irreducible<B>(4);  // monic, degree 4, irreducible over B
auto v = Vector(p);               // vector form, ready to paste as modulus into Ext<B, …>

Externally (Magma):

p := 2; m := 6; F := GaloisField(p);
P<x> := PolynomialRing(F);
px := IrreduciblePolynomial(F, m);
Reverse(Coefficients(px));

See also

field_concepts_traits.hpp for the concepts and traits (FieldType, SubfieldOf, …)

vectors.hpp, matrices.hpp, polynomials.hpp

Definition in file fields.hpp.

Macro Definition Documentation

CECCO_COMPRESS_LUTS_FROM_Q

#define CECCO_COMPRESS_LUTS_FROM_Q   256

Compression threshold for 2D lookup tables in extension fields.

For fields with at least this many elements, the addition and multiplication tables store only the upper triangle (exploiting commutativity), saving ~50 % memory. Optimal value depends on cache size.

Definition at line 125 of file fields.hpp.

CECCO_ERASURE_SUPPORT

#define CECCO_ERASURE_SUPPORT

Enables erase() / unerase() / is_erased() on every field type.

Define only if needed (error-correction with erasures); enabling it costs some performance.

Definition at line 104 of file fields.hpp.

CECCO_USE_LUTS_FOR_FP

#define CECCO_USE_LUTS_FOR_FP

Force prime fields to use lookup tables instead of modular arithmetic.

Almost always slower than direct mod-p arithmetic — leave undefined unless you have a reason.

Definition at line 114 of file fields.hpp.