Prime field 𝔽_p ≅ ℤ/pℤ More...

#include <fields.hpp>

Inheritance diagram for CECCO::Fp:

Public Types
using	label_t = ::CECCO::label_t<p>

Public Member Functions
constexpr	Fp () noexcept
	Default constructor: 0.
constexpr	Fp (int l)
	Construct from int, reducing modulo p (handles negative values).
constexpr	Fp (const Fp &other) noexcept=default
constexpr	Fp (Fp &&other) noexcept=default
template<FiniteFieldType S, MOD ext_modulus, LutMode mode>
	Fp (const Ext< S, ext_modulus, mode > &other)
	Extract a prime-field element from an extension field (downcast).
template<FiniteFieldType MAIN, FiniteFieldType... OTHERS> requires SubfieldOf<Iso<MAIN, OTHERS...>, Fp<p>>
	Fp (const Iso< MAIN, OTHERS... > &other)
	Extract a prime-field element from an Iso containing this prime subfield.
	~Fp () noexcept=default
constexpr Fp &	operator= (int l) noexcept
	Assign int, reducing modulo p.
constexpr Fp &	operator= (const Fp &rhs) noexcept=default
constexpr Fp &	operator= (Fp &&rhs) noexcept=default
template<FiniteFieldType S, MOD ext_modulus, LutMode mode>
Fp &	operator= (const Ext< S, ext_modulus, mode > &other)
	Project an extension-field element to 𝔽_p (copy-and-swap; same semantics as the constructor).
template<FiniteFieldType MAIN, FiniteFieldType... OTHERS>
Fp &	operator= (const Iso< MAIN, OTHERS... > &other)
	Project an Iso element to 𝔽_p (copy-and-swap; same semantics as the constructor).
constexpr bool	operator== (const Fp &rhs) const noexcept
constexpr Fp	operator- () const &noexcept
	Additive inverse (lvalue): returns a new element with -label mod p.
constexpr Fp &	operator- () &&noexcept
	Additive inverse (rvalue): in place.
constexpr Fp &	operator+= (const Fp &rhs) noexcept
	*this = (label + rhs.label) mod p
constexpr Fp &	operator-= (const Fp &rhs) noexcept
	*this = (label − rhs.label) mod p
constexpr Fp &	operator*= (const Fp &rhs) noexcept
	*this = (label · rhs.label) mod p
constexpr Fp &	operator*= (int s) noexcept
	*this = (label · s) mod p (repeated addition)
Fp &	operator/= (const Fp &rhs)
	*this = (label · rhs.label⁻¹) mod p; throws std::invalid_argument if rhs is zero
Fp &	randomize ()
	Uniform random element in {0, …, p − 1}.
Fp &	randomize_force_change ()
	Like randomize but guaranteed to differ from the current value.
size_t	get_multiplicative_order () const
	Multiplicative order in 𝔽_p*.
size_t	get_additive_order () const
	Additive order: 1 for zero, p otherwise.
constexpr size_t	get_label () const noexcept
	Underlying integer label in {0, …, p − 1}.
constexpr bool	has_positive_sign () const noexcept
	Always true (finite fields are unordered).
constexpr bool	is_zero () const noexcept
	True iff this is the additive identity.
constexpr Fp &	erase () noexcept
	Mark this element as erased (encoded as label == max(label_t)).
constexpr Fp &	unerase () noexcept
	Clear the erasure flag, resetting to the additive identity.
constexpr bool	is_erased () const noexcept
	Test whether this element is currently erased.
template<FiniteFieldType S, MOD ext_modulus, LutMode mode>
Fp< p > &	operator= (const Ext< S, ext_modulus, mode > &rhs)
template<FiniteFieldType MAIN, FiniteFieldType... OTHERS>
Fp< p > &	operator= (const Iso< MAIN, OTHERS... > &rhs)
Public Member Functions inherited from CECCO::details::Field< Fp< p > >
Fp< p > &	operator= (int l)=delete
	Assign from int — derived must implement.
constexpr bool	operator!= (const Fp< p > &rhs) const
	Inequality, defined as !(*this == rhs).
constexpr Fp< p >	operator+ () const &
	Unary + on an lvalue: returns a copy.
Fp< p >	operator- () const &noexcept=delete
	Additive inverse on an lvalue — derived must implement.
Fp< p > &	operator+= (const Fp< p > &rhs) noexcept=delete
	*this += rhs — derived must implement
Fp< p > &	operator-= (const Fp< p > &rhs) noexcept=delete
	*this -= rhs — derived must implement
Fp< p > &	operator*= (const Fp< p > &rhs) noexcept=delete
	this = rhs — derived must implement
Fp< p > &	operator/= (const Fp< p > &rhs)=delete
	*this /= rhs; throws std::invalid_argument if rhs is zero — derived must implement
Field &	randomize ()=delete
	Uniform random element of the field — derived must implement; may return the same value.
Field &	randomize_force_change ()=delete
	Like randomize but guaranteed to differ from the current value — derived must implement.
size_t	get_multiplicative_order () const=delete
	Smallest k > 0 with this^k == 1; throws std::invalid_argument if *this is zero.
size_t	get_additive_order () const=delete
	Smallest k > 0 with k * *this == 0; for finite fields of characteristic p this is p (or 1 for zero); for ℚ it is 1 for zero and 0 (infinite) otherwise.
bool	has_positive_sign () const noexcept=delete
	True if the element is "positive" (always true for finite fields; sign of numerator for ℚ).
bool	is_zero () const noexcept=delete
	True if *this is the additive identity.
Field &	erase () noexcept=delete
	Mark this element as erased (out-of-field marker for erasure decoding).
Field &	unerase () noexcept=delete
	Clear the erasure flag, resetting to additive identity.
bool	is_erased () const noexcept=delete
	Test whether this element is currently erased.

Static Public Member Functions
static std::string	get_info ()
	Human-readable description: "prime field with p elements".
static constexpr size_t	get_characteristic () noexcept
static constexpr Fp	get_generator () noexcept
	Generator (primitive root) of 𝔽_p*; precomputed label is Gen.
static constexpr size_t	get_p () noexcept
static constexpr size_t	get_m () noexcept
static constexpr size_t	get_q () noexcept
static constexpr size_t	get_size () noexcept
static constexpr bool	is_constexpr_ready () noexcept
	Always true for prime fields.
static void	show_tables ()
	Print all lookup tables to std::cout (debugging aid).
static constexpr bool	ready ()
	Compile-time signal that all LUTs are constructed.

Static Public Attributes
static constexpr label_t	Gen = details::compute_primitive_root<Fp>()
	Primitive element (generator) of F_p*.
Precomputed Lookup Tables
Compile-time generated tables for field operations
static constexpr Lut2D	lut_add = details::compute_modular_addition_table<label_t, p>()
	Addition lookup table: lut_add(a,b) = (a + b) mod p.
static constexpr Lut2D	lut_mul = details::compute_modular_multiplication_table<label_t, p>()
	Multiplication lookup table: lut_mul(a,b) = (a * b) mod p.
static constexpr Lut1D	lut_neg = details::compute_additive_inverses_direct<label_t, p>()
	Additive inverse lookup table: lut_neg[a] = (-a) mod p.
static constexpr Lut1D	lut_inv = details::compute_multiplicative_inverses_direct<label_t, p>()
	Multiplicative inverse lookup table: lut_inv[a] = a^(-1) mod p.
static constexpr Lut1D	lut_mul_ord = details::compute_multiplicative_orders<label_t, p>(lut_mul)
	Multiplicative order lookup table: lut_mul_ord[a] = multiplicative order of a in 𝔽_p \{0}.
static constexpr bool	luts_ready

Additional Inherited Members
Protected Member Functions inherited from CECCO::details::Field< Fp< p > >
	~Field () noexcept=default
Protected Member Functions inherited from CECCO::details::Base
	Base ()=default

Detailed Description

template<uint16_t p>
class CECCO::Fp

Prime field 𝔽_p ≅ ℤ/pℤ

Template Parameters

p	Prime modulus, 2 ≤ p ≤ 65521 (largest prime fitting in uint16_t)

Elements are stored as label_t integers in {0, 1, …, p − 1} (width is the smallest unsigned type that fits p). Arithmetic is direct mod-p by default; define CECCO_USE_LUTS_FOR_FP to switch to LUTs (rarely advisable). The primality of p is enforced by static_assert.

Usage_Example

using F5 = Fp<5>;
F5 a(3), b(4);
auto c = a + b;                               // 2 (7 mod 5)
auto d = a / b;                               // 3 · 4⁻¹ = 3 · 4 = 2 in 𝔽₅
size_t ord = a.get_multiplicative_order();    // order of 3 in 𝔽₅*

Definition at line 1647 of file fields.hpp.

Member Typedef Documentation

◆ label_t

template<uint16_t p>

using CECCO::Fp::label_t = ::CECCO::label_t

Definition at line 1651 of file fields.hpp.

Constructor & Destructor Documentation

◆ Fp() [1/6]

template<uint16_t p>

CECCO::Fp::Fp ( )

inlineconstexprnoexcept

Default constructor: 0.

Definition at line 1654 of file fields.hpp.

Here is the caller graph for this function:

◆ Fp() [2/6]

template<uint16_t p>

CECCO::Fp::Fp ( int l )

constexpr

Construct from int, reducing modulo p (handles negative values).

Definition at line 1879 of file fields.hpp.

◆ Fp() [3/6]

template<uint16_t p>

CECCO::Fp::Fp ( const Fp & other )

constexprdefaultnoexcept

◆ Fp() [4/6]

template<uint16_t p>

CECCO::Fp::Fp ( Fp && other )

constexprdefaultnoexcept

◆ Fp() [5/6]

template<uint16_t p>

template<FiniteFieldType S, MOD ext_modulus, LutMode mode>

CECCO::Fp::Fp ( const Ext< S, ext_modulus, mode > & other )

Extract a prime-field element from an extension field (downcast).

Template Parameters

S	Base of the source extension field
ext_modulus	Modulus of the source extension field

Exceptions

std::invalid_argument if other is not in the prime subfield

Uses a cached CECCO::Embedding from Fp to Ext<S, ext_modulus, mode>; since 𝔽_p is the minimal subfield of any extension over it, this is the canonical reverse lookup. Source and target must share the characteristic (enforced by static_assert).

Definition at line 1887 of file fields.hpp.

◆ Fp() [6/6]

template<uint16_t p>
requires SubfieldOf<Iso<MAIN, OTHERS...>, Fp>

template<FiniteFieldType MAIN, FiniteFieldType... OTHERS>
requires SubfieldOf<Iso<MAIN, OTHERS...>, Fp>

CECCO::Fp::Fp ( const Iso< MAIN, OTHERS... > & other )

Extract a prime-field element from an Iso containing this prime subfield.

Exceptions

std::invalid_argument if no Iso component contains an element in 𝔽_p

Tries the MAIN representation first, then each of OTHERS, until one yields a successful downcast to Fp.

Definition at line 1908 of file fields.hpp.

◆ ~Fp()

template<uint16_t p>

CECCO::Fp::~Fp ( )

defaultnoexcept

Member Function Documentation

◆ erase()

template<uint16_t p>

Fp & CECCO::Fp::erase ( )

constexprnoexcept

Mark this element as erased (encoded as label == max(label_t)).

Warning: Erased elements must not participate in field arithmetic — see CECCO_ERASURE_SUPPORT.

Definition at line 2160 of file fields.hpp.

◆ get_additive_order()

template<uint16_t p>

size_t CECCO::Fp::get_additive_order ( ) const

Additive order: 1 for zero, p otherwise.

Definition at line 2125 of file fields.hpp.

◆ get_characteristic()

template<uint16_t p>

constexpr size_t CECCO::Fp::get_characteristic ( )

inlinestaticconstexprnoexcept

Definition at line 1744 of file fields.hpp.

◆ get_generator()

template<uint16_t p>

constexpr Fp CECCO::Fp::get_generator ( )

inlinestaticconstexprnoexcept

Generator (primitive root) of 𝔽_p*; precomputed label is Gen.

Definition at line 1750 of file fields.hpp.

◆ get_info()

template<uint16_t p>

std::string CECCO::Fp::get_info ( )

inlinestatic

Human-readable description: "prime field with p elements".

Definition at line 1739 of file fields.hpp.

◆ get_label()

template<uint16_t p>

size_t CECCO::Fp::get_label ( ) const

inlineconstexprnoexcept

Underlying integer label in {0, …, p − 1}.

Definition at line 1747 of file fields.hpp.

◆ get_m()

template<uint16_t p>

constexpr size_t CECCO::Fp::get_m ( )

inlinestaticconstexprnoexcept

Definition at line 1753 of file fields.hpp.

◆ get_multiplicative_order()

template<uint16_t p>

size_t CECCO::Fp::get_multiplicative_order ( ) const

Multiplicative order in 𝔽_p*.

Exceptions

std::invalid_argument if *this is zero

Definition at line 2112 of file fields.hpp.

◆ get_p()

template<uint16_t p>

constexpr size_t CECCO::Fp::get_p ( )

inlinestaticconstexprnoexcept

Definition at line 1752 of file fields.hpp.

◆ get_q()

template<uint16_t p>

constexpr size_t CECCO::Fp::get_q ( )

inlinestaticconstexprnoexcept

Definition at line 1754 of file fields.hpp.

◆ get_size()

template<uint16_t p>

constexpr size_t CECCO::Fp::get_size ( )

inlinestaticconstexprnoexcept

Definition at line 1755 of file fields.hpp.

◆ has_positive_sign()

template<uint16_t p>

bool CECCO::Fp::has_positive_sign ( ) const

inlineconstexprnoexcept

Always true (finite fields are unordered).

Definition at line 1769 of file fields.hpp.

◆ is_constexpr_ready()

template<uint16_t p>

constexpr bool CECCO::Fp::is_constexpr_ready ( )

inlinestaticconstexprnoexcept

Always true for prime fields.

Prime fields' arithmetic interface is constexpr regardless of CECCO_USE_LUTS_FOR_FP, so a CompileTime CECCO::Ext can always be built on top.

Definition at line 1763 of file fields.hpp.

◆ is_erased()

template<uint16_t p>

bool CECCO::Fp::is_erased ( ) const

inlineconstexprnoexcept

Test whether this element is currently erased.

Definition at line 1784 of file fields.hpp.

◆ is_zero()

template<uint16_t p>

bool CECCO::Fp::is_zero ( ) const

inlineconstexprnoexcept

True iff this is the additive identity.

Definition at line 1771 of file fields.hpp.

◆ operator*=() [1/2]

template<uint16_t p>

Fp & CECCO::Fp::operator*= ( const Fp & rhs )

constexprnoexcept

*this = (label · rhs.label) mod p

Definition at line 2032 of file fields.hpp.

◆ operator*=() [2/2]

template<uint16_t p>

Fp & CECCO::Fp::operator*= ( int s )

constexprnoexcept

*this = (label · s) mod p (repeated addition)

Definition at line 2051 of file fields.hpp.

◆ operator+=()

template<uint16_t p>

Fp & CECCO::Fp::operator+= ( const Fp & rhs )

constexprnoexcept

*this = (label + rhs.label) mod p

Definition at line 1998 of file fields.hpp.

◆ operator-() [1/2]

template<uint16_t p>

Fp & CECCO::Fp::operator- ( ) &&

constexprnoexcept

Additive inverse (rvalue): in place.

Definition at line 1983 of file fields.hpp.

◆ operator-() [2/2]

template<uint16_t p>

Fp CECCO::Fp::operator- ( ) const &

constexprnoexcept

Additive inverse (lvalue): returns a new element with -label mod p.

Definition at line 1966 of file fields.hpp.

◆ operator-=()

template<uint16_t p>

Fp & CECCO::Fp::operator-= ( const Fp & rhs )

constexprnoexcept

*this = (label − rhs.label) mod p

Definition at line 2015 of file fields.hpp.

◆ operator/=()

template<uint16_t p>

Fp & CECCO::Fp::operator/= ( const Fp & rhs )

*this = (label · rhs.label⁻¹) mod p; throws std::invalid_argument if rhs is zero

Definition at line 2062 of file fields.hpp.

◆ operator=() [1/7]

template<uint16_t p>

template<FiniteFieldType S, MOD ext_modulus, LutMode mode>

Fp & CECCO::Fp::operator= ( const Ext< S, ext_modulus, mode > & other )

Project an extension-field element to 𝔽_p (copy-and-swap; same semantics as the constructor).

◆ operator=() [2/7]

template<uint16_t p>

template<FiniteFieldType S, MOD ext_modulus, LutMode mode>

Fp & CECCO::Fp::operator= ( const Ext< S, ext_modulus, mode > & rhs )

Definition at line 1950 of file fields.hpp.

◆ operator=() [3/7]

template<uint16_t p>

Fp & CECCO::Fp::operator= ( const Fp & rhs )

constexprdefaultnoexcept

◆ operator=() [4/7]

template<uint16_t p>

template<FiniteFieldType MAIN, FiniteFieldType... OTHERS>

Fp & CECCO::Fp::operator= ( const Iso< MAIN, OTHERS... > & other )

Project an Iso element to 𝔽_p (copy-and-swap; same semantics as the constructor).

◆ operator=() [5/7]

template<uint16_t p>

template<FiniteFieldType MAIN, FiniteFieldType... OTHERS>

Fp & CECCO::Fp::operator= ( const Iso< MAIN, OTHERS... > & rhs )

Definition at line 1959 of file fields.hpp.

◆ operator=() [6/7]

template<uint16_t p>

Fp & CECCO::Fp::operator= ( Fp && rhs )

constexprdefaultnoexcept

◆ operator=() [7/7]

template<uint16_t p>

Fp & CECCO::Fp::operator= ( int l )

constexprnoexcept

Assign int, reducing modulo p.

Definition at line 1941 of file fields.hpp.

◆ operator==()

template<uint16_t p>

bool CECCO::Fp::operator== ( const Fp & rhs ) const

inlineconstexprnoexcept

Definition at line 1705 of file fields.hpp.

◆ randomize()

template<uint16_t p>

Fp & CECCO::Fp::randomize ( )

Uniform random element in {0, …, p − 1}.

Definition at line 2076 of file fields.hpp.

◆ randomize_force_change()

template<uint16_t p>

Fp & CECCO::Fp::randomize_force_change ( )

Like randomize but guaranteed to differ from the current value.

Definition at line 2094 of file fields.hpp.

◆ ready()

template<uint16_t p>

constexpr bool CECCO::Fp::ready ( )

inlinestaticconstexpr

Compile-time signal that all LUTs are constructed.

Used by extension fields built on top of 𝔽_p to defer their own LUT computation until the base field is fully instantiated, avoiding compiler recursion-depth issues.

Definition at line 1793 of file fields.hpp.

◆ show_tables()

template<uint16_t p>

void CECCO::Fp::show_tables ( )

static

Print all lookup tables to std::cout (debugging aid).

Definition at line 2134 of file fields.hpp.

◆ unerase()

template<uint16_t p>

Fp & CECCO::Fp::unerase ( )

constexprnoexcept

Clear the erasure flag, resetting to the additive identity.

Definition at line 2166 of file fields.hpp.

Member Data Documentation

◆ Gen

template<uint16_t p>

label_t CECCO::Fp::Gen = details::compute_primitive_root<Fp>()

staticconstexpr

Primitive element (generator) of F_p*.

Smallest primitive root mod p, computed at compile time via constexpr power enumeration using Fp's own multiplication.

Definition at line 1831 of file fields.hpp.

◆ lut_add

template<uint16_t p>

Lut2D CECCO::Fp::lut_add = details::compute_modular_addition_table<label_t, p>()

staticconstexpr

Addition lookup table: lut_add(a,b) = (a + b) mod p.

Definition at line 1850 of file fields.hpp.

◆ lut_inv

template<uint16_t p>

Lut1D CECCO::Fp::lut_inv = details::compute_multiplicative_inverses_direct<label_t, p>()

staticconstexpr

Multiplicative inverse lookup table: lut_inv[a] = a^(-1) mod p.

Definition at line 1859 of file fields.hpp.

◆ lut_mul

template<uint16_t p>

Lut2D CECCO::Fp::lut_mul = details::compute_modular_multiplication_table<label_t, p>()

staticconstexpr

Multiplication lookup table: lut_mul(a,b) = (a * b) mod p.

Definition at line 1853 of file fields.hpp.

◆ lut_mul_ord

template<uint16_t p>

Lut1D CECCO::Fp::lut_mul_ord = details::compute_multiplicative_orders<label_t, p>(lut_mul)

staticconstexpr

Multiplicative order lookup table: lut_mul_ord[a] = multiplicative order of a in 𝔽_p \{0}.

Definition at line 1862 of file fields.hpp.

◆ lut_neg

template<uint16_t p>

Lut1D CECCO::Fp::lut_neg = details::compute_additive_inverses_direct<label_t, p>()

staticconstexpr

Additive inverse lookup table: lut_neg[a] = (-a) mod p.

Definition at line 1856 of file fields.hpp.

◆ luts_ready

template<uint16_t p>

bool CECCO::Fp::luts_ready

staticconstexpr

Initial value:

                                 = []() constexpr {
    static_assert(lut_add(0, 0) == 0);  
    static_assert(lut_neg(0) == 0);     
    static_assert(lut_mul(0, 1) == 0);  
    return true;
}()

Definition at line 1864 of file fields.hpp.

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Additional Inherited Members

Detailed Description

Usage_Example

Member Typedef Documentation

◆ label_t

Constructor & Destructor Documentation

◆ Fp() [1/6]

◆ Fp() [2/6]

◆ Fp() [3/6]

◆ Fp() [4/6]

◆ Fp() [5/6]

◆ Fp() [6/6]

◆ ~Fp()

Member Function Documentation

◆ erase()

◆ get_additive_order()

◆ get_characteristic()

◆ get_generator()

◆ get_info()

◆ get_label()

◆ get_m()

◆ get_multiplicative_order()

◆ get_p()

◆ get_q()

◆ get_size()

◆ has_positive_sign()

◆ is_constexpr_ready()

◆ is_erased()

◆ is_zero()

◆ operator*=() [1/2]

◆ operator*=() [2/2]

◆ operator+=()

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ operator-=()

◆ operator/=()

◆ operator=() [1/7]

◆ operator=() [2/7]

◆ operator=() [3/7]

◆ operator=() [4/7]

◆ operator=() [5/7]

◆ operator=() [6/7]

◆ operator=() [7/7]

◆ operator==()

◆ randomize()

◆ randomize_force_change()

◆ ready()

◆ show_tables()

◆ unerase()

Member Data Documentation

◆ Gen

◆ lut_add

◆ lut_inv

◆ lut_mul

◆ lut_mul_ord

◆ lut_neg

◆ luts_ready