feanor_math/rings/zn/
zn_static.rs

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

feanor_math/rings/zn/
zn_static.rs
