feanor_math/rings/zn/
zn_static.rs

1use serde::{Deserialize, Deserializer, Serialize, Serializer, de};
2
3use crate::algorithms::eea::*;
4use crate::divisibility::*;
5use crate::field::*;
6use crate::homomorphism::*;
7use crate::local::PrincipalLocalRing;
8use crate::pid::{EuclideanRing, PrincipalIdealRing, PrincipalIdealRingStore};
9use crate::primitive_int::{StaticRing, StaticRingBase};
10use crate::reduce_lift::poly_eval::InterpolationBaseRing;
11use crate::ring::*;
12use crate::rings::extension::FreeAlgebraStore;
13use crate::rings::extension::galois_field::*;
14use crate::rings::zn::*;
15use crate::seq::*;
16use crate::serialization::SerializableElementRing;
17use crate::specialization::*;
18
19/// Ring that implements arithmetic in `Z/nZ` for a small `n` known
20/// at compile time.
21#[stability::unstable(feature = "enable")]
22#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
23pub struct ZnBase<const N: u64, const IS_FIELD: bool>;
24
25#[stability::unstable(feature = "enable")]
26pub const fn is_prime(n: u64) -> bool {
27    assert!(n >= 2);
28    let mut d = 2;
29    while d < n {
30        if n.is_multiple_of(d) {
31            return false;
32        }
33        d += 1;
34    }
35    return true;
36}
37
38impl<const N: u64, const IS_FIELD: bool> ZnBase<N, IS_FIELD> {
39    #[stability::unstable(feature = "enable")]
40    pub const fn new() -> Self {
41        assert!(!IS_FIELD || is_prime(N));
42        ZnBase
43    }
44}
45
46impl<const N: u64, const IS_FIELD: bool> RingBase for ZnBase<N, IS_FIELD> {
47    type Element = u64;
48
49    fn clone_el(&self, val: &Self::Element) -> Self::Element { *val }
50
51    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
52        *lhs += rhs;
53        if *lhs >= N {
54            *lhs -= N;
55        }
56    }
57
58    fn negate_inplace(&self, lhs: &mut Self::Element) {
59        if *lhs != 0 {
60            *lhs = N - *lhs;
61        }
62    }
63
64    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
65        *lhs = ((*lhs as u128 * rhs as u128) % (N as u128)) as u64
66    }
67
68    fn from_int(&self, value: i32) -> Self::Element {
69        RingRef::new(self).coerce(&StaticRing::<i64>::RING, value.into())
70    }
71
72    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { *lhs == *rhs }
73
74    fn is_commutative(&self) -> bool { true }
75
76    fn is_noetherian(&self) -> bool { true }
77
78    fn dbg_within<'a>(
79        &self,
80        value: &Self::Element,
81        out: &mut std::fmt::Formatter<'a>,
82        _: EnvBindingStrength,
83    ) -> std::fmt::Result {
84        write!(out, "{}", *value)
85    }
86
87    fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
88    where
89        I::Type: IntegerRing,
90    {
91        self.size(ZZ)
92    }
93
94    fn is_approximate(&self) -> bool { false }
95}
96
97impl<const N: u64, const IS_FIELD: bool> CanHomFrom<StaticRingBase<i64>> for ZnBase<N, IS_FIELD> {
98    type Homomorphism = ();
99
100    fn has_canonical_hom(&self, _: &StaticRingBase<i64>) -> Option<()> { Some(()) }
101
102    fn map_in(&self, _: &StaticRingBase<i64>, el: i64, _: &()) -> Self::Element {
103        let result = ((el % (N as i64)) + (N as i64)) as u64;
104        if result >= N { result - N } else { result }
105    }
106}
107
108impl<const N: u64, const IS_FIELD: bool> CanHomFrom<ZnBase<N, IS_FIELD>> for ZnBase<N, IS_FIELD> {
109    type Homomorphism = ();
110    fn has_canonical_hom(&self, _: &Self) -> Option<()> { Some(()) }
111    fn map_in(&self, _: &Self, el: Self::Element, _: &()) -> Self::Element { el }
112}
113
114impl<const N: u64, const IS_FIELD: bool> CanIsoFromTo<ZnBase<N, IS_FIELD>> for ZnBase<N, IS_FIELD> {
115    type Isomorphism = ();
116    fn has_canonical_iso(&self, _: &Self) -> Option<()> { Some(()) }
117    fn map_out(&self, _: &Self, el: Self::Element, _: &()) -> Self::Element { el }
118}
119
120impl<const N: u64, const IS_FIELD: bool> DivisibilityRing for ZnBase<N, IS_FIELD> {
121    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
122        let (s, _, d) = signed_eea((*rhs).try_into().unwrap(), N as i64, StaticRing::<i64>::RING);
123        let mut rhs_inv = ((s % (N as i64)) + (N as i64)) as u64;
124        if rhs_inv >= N {
125            rhs_inv -= N;
126        }
127        if *lhs % d as u64 == 0 {
128            Some(self.mul(*lhs / d as u64, rhs_inv))
129        } else {
130            None
131        }
132    }
133}
134
135impl<const N: u64, const IS_FIELD: bool> PrincipalIdealRing for ZnBase<N, IS_FIELD> {
136    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
137        generic_impls::checked_div_min(RingRef::new(self), lhs, rhs)
138    }
139
140    fn extended_ideal_gen(
141        &self,
142        lhs: &Self::Element,
143        rhs: &Self::Element,
144    ) -> (Self::Element, Self::Element, Self::Element) {
145        let (s, t, d) =
146            StaticRing::<i64>::RING.extended_ideal_gen(&(*lhs).try_into().unwrap(), &(*rhs).try_into().unwrap());
147        let quo = RingRef::new(self).into_can_hom(StaticRing::<i64>::RING).ok().unwrap();
148        (quo.map(s), quo.map(t), quo.map(d))
149    }
150}
151
152impl<const N: u64> EuclideanRing for ZnBase<N, true> {
153    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
154        assert!(!self.is_zero(rhs));
155        (self.checked_left_div(&lhs, rhs).unwrap(), self.zero())
156    }
157
158    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> { if self.is_zero(val) { Some(0) } else { Some(1) } }
159}
160
161#[stability::unstable(feature = "enable")]
162#[derive(Clone, Copy)]
163pub struct ZnBaseElementsIter<const N: u64> {
164    current: u64,
165}
166
167impl<const N: u64> Iterator for ZnBaseElementsIter<N> {
168    type Item = u64;
169
170    fn next(&mut self) -> Option<Self::Item> {
171        if self.current < N {
172            self.current += 1;
173            return Some(self.current - 1);
174        } else {
175            return None;
176        }
177    }
178}
179
180impl<const N: u64, const IS_FIELD: bool> HashableElRing for ZnBase<N, IS_FIELD> {
181    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) { h.write_u64(*el); }
182}
183
184impl<const N: u64, const IS_FIELD: bool> SerializableElementRing for ZnBase<N, IS_FIELD> {
185    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
186    where
187        D: Deserializer<'de>,
188    {
189        <i64 as Deserialize>::deserialize(deserializer)
190            .and_then(|x| {
191                if x < 0 || x >= *self.modulus() {
192                    Err(de::Error::custom("ring element value out of bounds for ring Z/nZ"))
193                } else {
194                    Ok(x)
195                }
196            })
197            .map(|x| self.from_int_promise_reduced(x))
198    }
199
200    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
201    where
202        S: Serializer,
203    {
204        <i64 as Serialize>::serialize(&self.smallest_positive_lift(*el), serializer)
205    }
206}
207
208impl<const N: u64, const IS_FIELD: bool> FiniteRing for ZnBase<N, IS_FIELD> {
209    type ElementsIter<'a> = ZnBaseElementsIter<N>;
210
211    fn elements(&self) -> ZnBaseElementsIter<N> { ZnBaseElementsIter { current: 0 } }
212
213    fn random_element<G: FnMut() -> u64>(&self, rng: G) -> <Self as RingBase>::Element {
214        generic_impls::random_element(self, rng)
215    }
216
217    fn size<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
218    where
219        I::Type: IntegerRing,
220    {
221        if ZZ.get_ring().representable_bits().is_none()
222            || self.integer_ring().abs_log2_ceil(self.modulus()) < ZZ.get_ring().representable_bits()
223        {
224            Some(int_cast(*self.modulus(), ZZ, self.integer_ring()))
225        } else {
226            None
227        }
228    }
229}
230
231impl<const N: u64> InterpolationBaseRing for ZnBase<N, true> {
232    type ExtendedRingBase<'a>
233        = GaloisFieldBaseOver<RingRef<'a, Self>>
234    where
235        Self: 'a;
236
237    type ExtendedRing<'a>
238        = GaloisFieldOver<RingRef<'a, Self>>
239    where
240        Self: 'a;
241
242    fn in_base<'a, S>(&self, ext_ring: S, el: El<S>) -> Option<Self::Element>
243    where
244        Self: 'a,
245        S: RingStore<Type = Self::ExtendedRingBase<'a>>,
246    {
247        let wrt_basis = ext_ring.wrt_canonical_basis(&el);
248        if wrt_basis.iter().skip(1).all(|x| self.is_zero(&x)) {
249            return Some(wrt_basis.at(0));
250        } else {
251            return None;
252        }
253    }
254
255    fn in_extension<'a, S>(&self, ext_ring: S, el: Self::Element) -> El<S>
256    where
257        Self: 'a,
258        S: RingStore<Type = Self::ExtendedRingBase<'a>>,
259    {
260        ext_ring.inclusion().map(el)
261    }
262
263    fn interpolation_points<'a>(&'a self, count: usize) -> (Self::ExtendedRing<'a>, Vec<El<Self::ExtendedRing<'a>>>) {
264        let ring = generic_impls::interpolation_ring(RingRef::new(self), count);
265        let points = ring.elements().take(count).collect();
266        return (ring, points);
267    }
268}
269
270impl<const N: u64, const IS_FIELD: bool> FiniteRingSpecializable for ZnBase<N, IS_FIELD> {
271    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.execute() }
272}
273
274impl<const N: u64, const IS_FIELD: bool> ZnRing for ZnBase<N, IS_FIELD> {
275    type IntegerRingBase = StaticRingBase<i64>;
276    type IntegerRing = RingValue<StaticRingBase<i64>>;
277
278    fn integer_ring(&self) -> &Self::IntegerRing { &StaticRing::<i64>::RING }
279
280    fn smallest_positive_lift(&self, el: Self::Element) -> El<Self::IntegerRing> { el as i64 }
281
282    fn modulus(&self) -> &El<Self::IntegerRing> { &(N as i64) }
283
284    fn is_field(&self) -> bool { is_prime(N) }
285
286    fn from_int_promise_reduced(&self, x: El<Self::IntegerRing>) -> Self::Element {
287        debug_assert!(x >= 0);
288        debug_assert!((x as u64) < N);
289        x as u64
290    }
291}
292
293impl<const N: u64> Domain for ZnBase<N, true> {}
294
295impl<const N: u64> PerfectField for ZnBase<N, true> {}
296
297impl<const N: u64> Field for ZnBase<N, true> {}
298
299impl<const N: u64> PrincipalLocalRing for ZnBase<N, true> {
300    fn max_ideal_gen(&self) -> &Self::Element { &0 }
301
302    fn nilpotent_power(&self) -> Option<usize> { Some(1) }
303}
304
305impl<const N: u64, const IS_FIELD: bool> RingValue<ZnBase<N, IS_FIELD>> {
306    #[stability::unstable(feature = "enable")]
307    pub const RING: Self = Self::from(ZnBase::new());
308}
309
310/// Ring that implements arithmetic in `Z/nZ` for a small `n` known
311/// at compile time. For details, see [`ZnBase`].
312#[stability::unstable(feature = "enable")]
313pub type Zn<const N: u64> = RingValue<ZnBase<N, false>>;
314
315/// Ring that implements arithmetic in `Z/nZ` for a small `n` known
316/// at compile time. For details, see [`ZnBase`].
317#[stability::unstable(feature = "enable")]
318pub type Fp<const P: u64> = RingValue<ZnBase<P, true>>;
319
320#[test]
321fn test_is_prime() {
322    assert_eq!(true, is_prime(17));
323    assert_eq!(false, is_prime(49));
324}
325
326#[stability::unstable(feature = "enable")]
327pub const F17: Fp<17> = Fp::<17>::RING;
328
329#[test]
330fn test_finite_field_axioms() {
331    crate::rings::finite::generic_tests::test_finite_ring_axioms(&F17);
332    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Zn::<128>::RING);
333    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Fp::<257>::RING);
334    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Zn::<256>::RING);
335}
336
337#[test]
338fn test_zn_el_add() {
339    let a = F17.int_hom().map(6);
340    let b = F17.int_hom().map(12);
341    assert_eq!(F17.int_hom().map(1), F17.add(a, b));
342}
343
344#[test]
345fn test_zn_el_sub() {
346    let a = F17.int_hom().map(6);
347    let b = F17.int_hom().map(12);
348    assert_eq!(F17.int_hom().map(11), F17.sub(a, b));
349}
350
351#[test]
352fn test_zn_el_mul() {
353    let a = F17.int_hom().map(6);
354    let b = F17.int_hom().map(12);
355    assert_eq!(F17.int_hom().map(4), F17.mul(a, b));
356}
357
358#[test]
359fn test_zn_el_div() {
360    let a = F17.int_hom().map(6);
361    let b = F17.int_hom().map(12);
362    assert_eq!(F17.int_hom().map(9), F17.checked_div(&a, &b).unwrap());
363}
364
365#[test]
366fn fn_test_div_impossible() {
367    let _a = Zn::<22>::RING.int_hom().map(4);
368    // the following line should give a compiler error
369    // Zn::<22>::RING.div(_a, _a);
370}
371
372#[test]
373fn test_zn_ring_axioms_znbase() {
374    super::generic_tests::test_zn_axioms(Zn::<17>::RING);
375    super::generic_tests::test_zn_axioms(Zn::<63>::RING);
376}
377
378#[test]
379fn test_divisibility_axioms() {
380    crate::divisibility::generic_tests::test_divisibility_axioms(Zn::<17>::RING, Zn::<17>::RING.elements());
381    crate::divisibility::generic_tests::test_divisibility_axioms(Zn::<9>::RING, Zn::<9>::RING.elements());
382    crate::divisibility::generic_tests::test_divisibility_axioms(Zn::<12>::RING, Zn::<12>::RING.elements());
383}
384
385#[test]
386fn test_principal_ideal_ring_axioms() {
387    let R = Zn::<17>::RING;
388    crate::pid::generic_tests::test_principal_ideal_ring_axioms(R, R.elements());
389    let R = Zn::<63>::RING;
390    crate::pid::generic_tests::test_principal_ideal_ring_axioms(R, R.elements());
391}
feanor_math/rings/zn/zn_static.rs

feanor_math/rings/zn/
zn_static.rs
