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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

// Copyright (C) 2020 Miklos Maroti
// Licensed under the MIT license (see LICENSE)

use crate::*;

/// The 2-element field represented as residue classes of integers modulo 2.
pub const GF2: QuotientField<CheckedInts<i8>> = QuotientField {
    base: I8,
    modulo: 2,
};

/// The 3-element field represented as residue classes of integers modulo 3.
pub const GF3: QuotientField<CheckedInts<i8>> = QuotientField {
    base: I8,
    modulo: 3,
};

/// A quotient field of an Euclidean domain by a principal ideal
/// generated by an irreducible (prime) element.
#[derive(Clone, Debug)]
pub struct QuotientField<A>
where
    A: EuclideanDomain,
{
    base: A,
    modulo: A::Elem,
}

impl<A> QuotientField<A>
where
    A: EuclideanDomain,
{
    /// Creates a field from the given Euclidean domain and one of
    /// its irreducible (prime) element. This method does not check
    /// that the modulo is indeed irreducible. If this fails, then
    /// calculating the multiplicative inverse of some elements
    /// may panic.
    pub fn new(base: A, modulo: A::Elem) -> Self {
        assert!(base.contains(&modulo));
        let one = base.one();
        assert!(base.is_zero(&base.rem(&one, &one)));
        QuotientField { base, modulo }
    }

    /// Returns the base ring from which this field was constructed.
    pub fn base(&self) -> &A {
        &self.base
    }

    /// Returns the modulo element from which this field was constructed.
    pub fn modulo(&self) -> &A::Elem {
        &self.modulo
    }
}

impl<A> Domain for QuotientField<A>
where
    A: EuclideanDomain,
{
    type Elem = A::Elem;

    fn contains(&self, elem: &Self::Elem) -> bool {
        self.base.reduced(elem, &self.modulo)
    }

    fn equals(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> bool {
        self.base.equals(elem1, elem2)
    }
}

impl<A> Semigroup for QuotientField<A>
where
    A: EuclideanDomain,
{
    fn mul(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> Self::Elem {
        self.base.rem(&self.base.mul(elem1, elem2), &self.modulo)
    }
}

impl<A> Monoid for QuotientField<A>
where
    A: EuclideanDomain,
{
    fn one(&self) -> Self::Elem {
        self.base.one()
    }

    fn is_one(&self, elem: &Self::Elem) -> bool {
        self.base.is_one(elem)
    }

    fn try_inv(&self, elem: &Self::Elem) -> Option<Self::Elem> {
        if self.is_zero(elem) {
            None
        } else {
            Some(self.inv(elem))
        }
    }

    fn invertible(&self, elem: &Self::Elem) -> bool {
        !self.is_zero(elem)
    }
}

impl<A> AbelianGroup for QuotientField<A>
where
    A: EuclideanDomain,
{
    fn zero(&self) -> Self::Elem {
        self.base.zero()
    }

    fn neg(&self, elem: &Self::Elem) -> Self::Elem {
        self.base.rem(&self.base.neg(elem), &self.modulo)
    }

    fn add(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> Self::Elem {
        self.base.rem(&self.base.add(elem1, elem2), &self.modulo)
    }
}

impl<A> UnitaryRing for QuotientField<A> where A: EuclideanDomain {}

impl<A> Field for QuotientField<A>
where
    A: EuclideanDomain,
{
    fn inv(&self, elem: &Self::Elem) -> Self::Elem {
        assert!(!self.is_zero(elem));
        let (g, _, r) = self.base.extended_gcd(&self.modulo, elem);
        let a = self.base.try_inv(&g).expect("modulo was not irreducible");
        self.mul(&a, &r)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn field_1721() {
        let field = QuotientField::new(I32, 1721);

        for a in 0..1720 {
            assert!(field.contains(&a));
            if a != 0 {
                let b = field.inv(&a);
                assert!(field.contains(&b));
                println!("{} {}", a, b);
                assert!(field.is_one(&field.mul(&a, &b)));
            }
        }
    }
}