alga2 0.1.0

A modern abstract-algebra hierarchy for Rust — the successor to alga, powered by batch-impl
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

//! The multiplicative ladder: Semiring → Ring → CommutativeRing → Field.
//!
//! These traits combine both operators: the additive part is the abelian
//! ladder from the parent module, the multiplicative part is the monoid
//! under [`Multiplicative`], and the two are tied
//! together by distributivity — a law, tested in `crate::laws`. `Field`
//! additionally requires `0 != 1` (a law).

use crate::op::{Additive, Multiplicative, Operator};

use super::{AbelianGroup, Monoid, VectorSpace};

/// A semiring: additive [`Monoid`] + multiplicative [`Monoid`] + distributivity.
pub trait Semiring<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Monoid<Oa> + Monoid<Om>
{
}

/// A ring: a [`Semiring`] whose additive part is an abelian group
/// (the additively-commutative law is part of the definition).
pub trait Ring<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Semiring<Oa, Om> + AbelianGroup<Oa>
{
}

/// A commutative ring: a [`Ring`] whose multiplicative part commutes.
pub trait CommutativeRing<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Ring<Oa, Om>
{
}

/// A division ring: a [`Ring`] where every nonzero element has a
/// multiplicative inverse (not necessarily commutative). Every field is a
/// division ring; the quaternions are the classic non-commutative example.
pub trait DivisionRing<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Ring<Oa, Om>
{
    /// The multiplicative inverse of `self`.
    fn inv(&self) -> Self;
}

/// A field: a commutative division ring with `0 != 1` (a law).
pub trait Field<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    DivisionRing<Oa, Om> + CommutativeRing<Oa, Om>
{
}

/// An integral domain: a commutative ring with no zero divisors — `a·b = 0`
/// implies `a = 0` or `b = 0` (a law) — and `0 != 1`.
///
/// Note: the crate's integer numerics are `Z/2^N` (wrapping), which has zero
/// divisors (e.g. `16 * 16 ≡ 0 (mod 256)`), so they are deliberately *not*
/// integral domains; the canonical inhabitant is the prime-modulus `ModN<P>`
/// (a finite field, hence a domain).
pub trait IntegralDomain<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    CommutativeRing<Oa, Om>
{
}

/// A unique factorization domain: an integral domain where every nonzero
/// non-unit element factors uniquely (up to order and units) into
/// irreducibles.
pub trait UniqueFactorizationDomain<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    IntegralDomain<Oa, Om>
{
}

/// A principal ideal domain: an integral domain whose ideals are all
/// principal (every ideal is generated by a single element).
pub trait PrincipalIdealDomain<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    UniqueFactorizationDomain<Oa, Om>
{
}

/// An ordered field: a field with a total order compatible with its
/// operations (the order laws are in `crate::laws`).
pub trait OrderedField<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Field<Oa, Om> + PartialOrd
{
}

/// A finite field: a field with finitely many elements.
pub trait FiniteField<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Field<Oa, Om>
{
    /// The characteristic — the additive order of the multiplicative
    /// identity (a prime).
    fn characteristic() -> u64;

    /// The number of elements (a prime power).
    fn order() -> u64;
}

/// A field extension: a field that is a finite-dimensional vector space over
/// a base field.
pub trait FieldExtension<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    Field<Oa, Om> + VectorSpace<Oa, Om, Scalar = <Self as FieldExtension<Oa, Om>>::BaseField>
{
    /// The base field.
    type BaseField: Field<Oa, Om>;

    /// The degree of the extension `[K : F]`.
    fn degree() -> usize;

    /// The field trace `Tr(x)`.
    fn trace(&self) -> Self::BaseField;

    /// The field norm `N(x)`.
    fn norm(&self) -> Self::BaseField;
}

/// A tower of field extensions: `K = K₀ ⊃ K₁ ⊃ ... ⊃ K_h = F`.
pub trait FieldExtensionTower<Oa: Operator = Additive, Om: Operator = Multiplicative>:
    FieldExtension<Oa, Om>
{
    /// The height of the tower.
    fn tower_height() -> usize;

    /// The degree of the `i`-th step.
    fn extension_degree(i: usize) -> usize;
}