Galois fields (finite fields). More...
#include <concepts>#include <cstddef>#include <cstdint>#include <functional>#include <ranges>#include <stdexcept>#include <type_traits>import dedekind.algebra:universal;import dedekind.sequences;import dedekind.sets;import dedekind.category;
Namespaces | |
| namespace | dedekind::category |
Concepts | |
| concept | dedekind::algebra::IsGaloisField |
A finite field, as an algebraic set: an ETCS set X whose carrier X::Domain is an axiomatic field with the carrier-author finite-cardinality opt-in. | |
Functions | |
| constexpr π½64 | dedekind::algebra::operator* (bool s, π½64 v) noexcept |
Scalar action of \(\mathbb{F}_2\) (witnessed on bool) on π½64, via the natural embedding \(\mathbb{F}_2 \hookrightarrow \mathbb{F}_{64}\) ( \(0 \mapsto 0\), \(1 \mapsto 1\)). | |
| constexpr π½64 | dedekind::algebra::inverse (π½64 a, std::plus< π½64 >) noexcept |
The additive (group) inverse of π½64, spelled as the computable inverse(a, std::plus) free function that category::inverse_v routes through by ADL. | |
| auto | dedekind::algebra::f64_primitive_powers () |
| Enumerate \(\mathbb{F}_{64}^{\times}\) as the cyclic walk \(\alpha^0, \alpha^1, \ldots, \alpha^{62}\). | |
Variables | |
| template<typename T, typename Add = std::plus<T>, typename Mult = std::multiplies<T>> | |
| constexpr bool | dedekind::algebra::is_galois_field_v = is_galois_field<T, Add, Mult>::value |
| template<typename T, typename Add = std::plus<T>, typename Mult = std::multiplies<T>> | |
| constexpr std::size_t | dedekind::algebra::galois_order_v = galois_order<T, Add, Mult>::value |
| constexpr π½64 | dedekind::algebra::f64_primitive_Ξ± = π½64{static_cast<std::uint8_t>(2)} |
Detailed Description
Galois fields (finite fields).
@partition :galois
- Copyright
- 2026 The Dedekind Authors Licensed under the Apache License, Version 2.0.
galois__Scope
A \emph{Galois field} (or finite field) is a field of finite cardinality. Every such field has order \(q = p^n\) for some prime \(p\) and positive integer \(n\); the prime \(p\) is the field's characteristic, and the field is a \(n\)-dimensional vector space over its prime subfield \(\mathbb{F}_p\). The canonical examples are \(\mathbb{F}_p\) (prime-order, $n = 1$) and \(\mathrm{GF}(p^n)\) (prime-power order, realised as \(\mathbb{F}_p[x] / (f(x))\) for an irreducible \(f\) of degree \(n\)).
This partition hosts:
IsGaloisField— the concept (field + finite-cardinality opt-in);is_galois_field_v,galois_order_v— the carrier- authored opt-in traits;- concrete Galois-field carriers:
boolunder(std::bit_xor, std::bit_and) as \(\mathbb{F}_2\), andπ½64as \(\mathrm{GF}(2^6) = \mathbb{F}_2[x]/(x^6 + x + 1)\).
The generic (possibly-infinite) IsField concept lives in algebra:field; vector-space structure of Galois fields over their prime subfield (e.g. IsVectorSpace<π½64, bool>) is witnessed in algebra:vectorspace, which imports this partition to reach the carriers.
- Note
- "Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country." β David Hilbert, address to the ZΓΌrich ICM (1932).
Function Documentation
◆ f64_primitive_powers()
|
inlineexport |
Enumerate \(\mathbb{F}_{64}^{\times}\) as the cyclic walk \(\alpha^0, \alpha^1, \ldots, \alpha^{62}\).
Returns a FinitePath <π½64> of size 63 whose i-th element is \(\alpha^i\). Built via sequences::iterate, which pre-materialises the orbit into a shared vector at construction time — so at(n) is O(1) and a full enumeration is O(n) rather than the naive O(n^2) of a per-call exponent walk. The walk is the bidirectional anchor between category::IsCyclicGroup<π½64, std::multiplies<π½64>> (axiomatic: π½64^Γ is cyclic of order 63) and the standard-library std::ranges::input_range surface — the same path that morphologies:archimedean :: IsCyclic carriers walk via successor / generator, here realised as an explicit sequence over \(\mathbb{N}_{<63}\).
◆ inverse()
The additive (group) inverse of π½64, spelled as the computable inverse(a, std::plus) free function that category::inverse_v routes through by ADL.
In characteristic two every element is its own additive inverse ( \(-x = x\), since \(2x = 0\)), so this returns -a via the carrier's unary negation. The is_invertible_v marker for (π½64, std::plus) is supplied separately by the GaloisFieldRegistration atlas (see SpeciesTraits above); that marker asserts invertibility but does not by itself make the inverse computable. This free function is the matching computable operation, without which inverse_v<π½64, std::plus> is not callable even though the marker holds. Downstream, the translation-graph inverse (:algebra:halfspace_transport) takes the converse shift from inverse_v, so it needs this hook to fire over π½64.
◆ operator*()
|
constexprexportnoexcept |
Scalar action of \(\mathbb{F}_2\) (witnessed on bool) on π½64, via the natural embedding \(\mathbb{F}_2 \hookrightarrow \mathbb{F}_{64}\) ( \(0 \mapsto 0\), \(1 \mapsto 1\)).
Required by IsVectorSpace<π½64, bool> (witnessed in algebra:vectorspace): the scalar side is the prime subfield \(\mathbb{F}_2\); its action on the ambient field is "multiply
every coordinate of @c v by the scalar bit", i.e.\ falseΒ·v = 0 and trueΒ·v = v. The one-operand std::multiplies functor dispatches here via ADL.
Variable Documentation
◆ f64_primitive_Ξ±
|
inlineconstexprexport |
galois__Formal_Verification
#388
The multiplicative group \(\mathbb{F}_{64}^{\times}\) is cyclic of order 63 (as witnessed above); a primitive element is \(\alpha = x\) under the chosen polynomial \(f(x) = x^6 + x + 1\), which has bit-representation 0b000010 = 2. Thus the enumeration \(\{\alpha^0, \alpha^1, \ldots, \alpha^{62}\}\) visits every element of \(\mathbb{F}_{64}^{\times}\) exactly once and is the canonical worked example of an IsFiniteSequence over a finite cyclic group — the example sketched in the sequences:net IsSequence_vs_stdlib_388 doc block.
