feanor_math/rings/zn/
zn_pow2.rs

1use smallvec::SmallVec;
2
3use crate::delegate::DelegateRing;
4use crate::divisibility::DivisibilityRing;
5use crate::homomorphism::*;
6use crate::integer::*;
7use crate::pid::*;
8use crate::primitive_int::{StaticRing, StaticRingBase};
9use crate::ring::*;
10use crate::rings::rust_bigint::{RustBigintRing, RustBigintRingBase};
11use crate::rings::zn::*;
12use crate::specialization::*;
13use crate::{
14    impl_field_wrap_unwrap_homs, impl_field_wrap_unwrap_isos, impl_localpir_wrap_unwrap_homs,
15    impl_localpir_wrap_unwrap_isos,
16};
17
18const DEFAULT_SMALLVEC_SIZE: usize = 4;
19
20/// Ring representing `Z/nZ`, where `n = 2^k` for some `k`, computing the modular reductions
21/// via standard bit masking.
22///
23/// # Performance
24///
25/// This implementation uses schoolbook multiplication.  As such, it is only optimized for a
26/// small enough `k`.
27/// Elements are internally stored using `SmallVec<[u64; N]>`, where `N` is a compile-time
28/// constant, and is the threshold for when dynamic allocation is used.
29/// It is recommended to set N to be exactly div_ceil(k, 64).
30///
31///
32/// # Example
33/// ```rust
34/// # use feanor_math::ring::*;
35/// # use feanor_math::homomorphism::*;
36/// # use feanor_math::rings::zn::*;
37/// # use feanor_math::rings::zn::zn_pow2::*;
38/// # use feanor_math::primitive_int::*;
39/// # use feanor_math::assert_el_eq;
40/// let R = Z2k::<3>::new(130);
41/// let a = R
42///     .get_ring()
43///     .from_base_u64_repr([u64::MAX, u64::MAX, 3].into_iter());
44/// assert_el_eq!(R, R.int_hom().map(-1), a);
45/// ```
46#[derive(Clone)]
47pub struct Z2kBase<const N: usize = DEFAULT_SMALLVEC_SIZE> {
48    k: usize,
49    n_limbs: usize,
50    last_limb_mask: u64,
51    modulus: El<RustBigintRing>,
52}
53impl<const N: usize> Z2kBase<N>
54where
55    [u64; N]: smallvec::Array<Item = u64>,
56{
57    pub fn new(k: usize) -> Self {
58        assert!(k >= 1);
59        let n_limbs = k.div_ceil(64);
60        assert!(
61            n_limbs <= 16,
62            "This implementation is not optimized for such a large modulus."
63        );
64        let modulus = RustBigintRing::RING.power_of_two(k);
65
66        let last_limb_mask = if k % 64 == 0 {
67            0xFFFFFFFFFFFFFFFF
68        } else {
69            0xFFFFFFFFFFFFFFFF >> (64 - (k % 64))
70        };
71        Self {
72            k,
73            n_limbs,
74            last_limb_mask,
75            modulus,
76        }
77    }
78
79    fn mask_el(&self, el: &mut Z2kEl<N>) {
80        el.0[self.n_limbs - 1] &= self.last_limb_mask;
81        el.0.truncate(self.n_limbs);
82    }
83
84    fn bigint_to_el(&self, ZZ: &RustBigintRing, x: &El<RustBigintRing>) -> Z2kEl<N> {
85        let mut rem = ZZ.euclidean_rem(ZZ.clone_el(x), self.modulus());
86
87        // normalize to `[0, 2^k)`.
88        if ZZ.is_neg(&rem) {
89            ZZ.add_assign_ref(&mut rem, self.modulus());
90        }
91
92        let mut limbs = SmallVec::from_elem(0, self.n_limbs);
93        for (i, d) in ZZ.get_ring().abs_base_u64_repr(&rem).take(self.n_limbs).enumerate() {
94            limbs[i] = d;
95        }
96        Z2kEl(limbs)
97    }
98
99    fn el_to_bigint(&self, ZZ: &RustBigintRing, mut el: Z2kEl<N>) -> El<RustBigintRing> {
100        self.mask_el(&mut el);
101        let mut acc = ZZ.zero();
102        let i128_ring = StaticRing::<i128>::RING;
103        for i in 0..self.n_limbs {
104            let limb = int_cast(el.0[i] as i128, ZZ, &i128_ring);
105            if !ZZ.is_zero(&limb) {
106                let shifted = ZZ.mul(limb, ZZ.power_of_two(64 * i));
107                ZZ.add_assign(&mut acc, shifted);
108            }
109        }
110        acc
111    }
112
113    /// Returns an iterator over the digits of the `2^64`-adic digit
114    /// representation of the absolute value of the given element.
115    pub fn abs_base_u64_repr(&self, el: &Z2kEl<N>) -> impl Iterator<Item = u64> {
116        el.0.iter().take(self.n_limbs).enumerate().map(|(i, &x)| {
117            if i == self.n_limbs - 1 {
118                x & self.last_limb_mask
119            } else {
120                x
121            }
122        })
123    }
124
125    /// Interprets the elements of the iterator as digits in a `2^64`-adic
126    /// digit representation, and returns the big integer represented by it.
127    pub fn from_base_u64_repr<I>(&self, data: I) -> Z2kEl<N>
128    where
129        I: Iterator<Item = u64>,
130    {
131        let data = data.take(self.n_limbs).enumerate().map(|(i, x)| {
132            if i == self.n_limbs - 1 {
133                x & self.last_limb_mask
134            } else {
135                x
136            }
137        });
138        Z2kEl(SmallVec::from_iter(data))
139    }
140}
141
142impl<const N: usize> PartialEq for Z2kBase<N>
143where
144    [u64; N]: smallvec::Array<Item = u64>,
145{
146    fn eq(&self, other: &Self) -> bool { self.k == other.k }
147}
148
149impl<const N: usize> Eq for Z2kBase<N> where [u64; N]: smallvec::Array<Item = u64> {}
150
151pub type Z2k<const N: usize = DEFAULT_SMALLVEC_SIZE> = RingValue<Z2kBase<N>>;
152impl<const N: usize> Z2k<N>
153where
154    [u64; N]: smallvec::Array<Item = u64>,
155{
156    pub fn new(log_modulus: usize) -> Self { RingValue::from(Z2kBase::<N>::new(log_modulus)) }
157}
158
159#[derive(Clone)]
160pub struct Z2kEl<const N: usize>(SmallVec<[u64; N]>)
161where
162    [u64; N]: smallvec::Array<Item = u64>;
163impl<const N: usize> RingBase for Z2kBase<N>
164where
165    [u64; N]: smallvec::Array<Item = u64>,
166{
167    type Element = Z2kEl<N>;
168
169    fn clone_el(&self, val: &Self::Element) -> Self::Element { val.clone() }
170
171    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
172        let mut carry = 0u64;
173        for i in 0..self.n_limbs {
174            let (sum, o0) = lhs.0[i].overflowing_add(rhs.0[i]);
175            let (sum, o1) = sum.overflowing_add(carry);
176            lhs.0[i] = sum;
177            carry = (o0 || o1) as u64;
178        }
179    }
180
181    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { self.add_assign_ref(lhs, &rhs); }
182
183    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
184        let mut borrow = 0u64;
185        for i in 0..self.n_limbs {
186            let (diff, o0) = lhs.0[i].overflowing_sub(rhs.0[i]);
187            let (diff, o1) = diff.overflowing_sub(borrow);
188            lhs.0[i] = diff;
189            borrow = (o0 || o1) as u64;
190        }
191    }
192
193    fn negate_inplace(&self, lhs: &mut Self::Element) {
194        let mut z = self.zero();
195        self.sub_assign_ref(&mut z, lhs);
196        *lhs = z;
197    }
198
199    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { self.mul_assign_ref(lhs, &rhs); }
200
201    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { *lhs = mul_z2k(lhs, rhs, self.n_limbs); }
202
203    fn from_int(&self, value: i32) -> Self::Element {
204        let ZZ = &RustBigintRing::RING;
205        let x = ZZ.int_hom().map(value);
206        self.bigint_to_el(ZZ, &x)
207    }
208
209    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
210        let mut a = lhs.clone();
211        let mut b = rhs.clone();
212        self.mask_el(&mut a);
213        self.mask_el(&mut b);
214        a.0 == b.0
215    }
216
217    fn is_zero(&self, value: &Self::Element) -> bool {
218        let mut v = value.clone();
219        self.mask_el(&mut v);
220        v.0.iter().all(|x| *x == 0)
221    }
222
223    fn is_one(&self, value: &Self::Element) -> bool { self.eq_el(value, &self.one()) }
224
225    fn is_commutative(&self) -> bool { true }
226    fn is_noetherian(&self) -> bool { true }
227
228    fn dbg_within<'a>(
229        &self,
230        value: &Self::Element,
231        out: &mut std::fmt::Formatter<'a>,
232        _: EnvBindingStrength,
233    ) -> std::fmt::Result {
234        let ZZ = RustBigintRing::RING;
235        write!(out, "{}", ZZ.format(&self.el_to_bigint(&ZZ, value.clone())))
236    }
237
238    fn characteristic<J: RingStore + Copy>(&self, ZZ: J) -> Option<El<J>>
239    where
240        J::Type: IntegerRing,
241    {
242        self.size(ZZ)
243    }
244
245    fn is_approximate(&self) -> bool { false }
246}
247
248// Schoolbook multiplication, only keeps the first `n_limbs` limbs.
249fn mul_z2k<const N: usize>(Z2kEl(a): &Z2kEl<N>, Z2kEl(b): &Z2kEl<N>, n_limbs: usize) -> Z2kEl<N>
250where
251    [u64; N]: smallvec::Array<Item = u64>,
252{
253    let mut res = SmallVec::from_elem(0, n_limbs);
254    for i in 0..n_limbs {
255        let mut carry = 0u128;
256        for j in 0..n_limbs - i {
257            let idx = i + j;
258            let sum = a[i] as u128 * b[j] as u128 + res[idx] as u128 + carry;
259            res[idx] = sum as u64;
260            carry = sum >> 64;
261        }
262    }
263    Z2kEl(res)
264}
265
266impl<const N: usize> DivisibilityRing for Z2kBase<N>
267where
268    [u64; N]: smallvec::Array<Item = u64>,
269{
270    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
271        super::generic_impls::checked_left_div(RingRef::new(self), lhs, rhs)
272    }
273}
274
275impl<const N: usize> CanHomFrom<Z2kBase<N>> for Z2kBase<N>
276where
277    [u64; N]: smallvec::Array<Item = u64>,
278{
279    type Homomorphism = ();
280
281    fn has_canonical_hom(&self, from: &Z2kBase<N>) -> Option<Self::Homomorphism> {
282        // Canonical homomorphism is expected to be unital. As such, characteristics must match.
283        (from.k == self.k).then_some(())
284    }
285
286    fn map_in(
287        &self,
288        _from: &Z2kBase<N>,
289        el: <Z2kBase<N> as RingBase>::Element,
290        _: &Self::Homomorphism,
291    ) -> Self::Element {
292        el
293    }
294}
295
296impl<const N: usize> CanIsoFromTo<Z2kBase<N>> for Z2kBase<N>
297where
298    [u64; N]: smallvec::Array<Item = u64>,
299{
300    type Isomorphism = ();
301
302    fn has_canonical_iso(&self, from: &Z2kBase<N>) -> Option<Self::Isomorphism> { (self.k == from.k).then_some(()) }
303
304    fn map_out(
305        &self,
306        _from: &Z2kBase<N>,
307        el: Self::Element,
308        _: &Self::Isomorphism,
309    ) -> <Z2kBase<N> as RingBase>::Element {
310        el
311    }
312}
313
314#[derive(Clone)]
315pub struct Z2KBaseElementsIter<'a, const N: usize>
316where
317    [u64; N]: smallvec::Array<Item = u64>,
318{
319    ring: &'a Z2kBase<N>,
320    next_index: Z2kEl<N>,
321    wrap_around: bool,
322}
323
324impl<'a, const N: usize> Iterator for Z2KBaseElementsIter<'a, N>
325where
326    [u64; N]: smallvec::Array<Item = u64>,
327{
328    type Item = Z2kEl<N>;
329
330    fn next(&mut self) -> Option<Self::Item> {
331        if self.wrap_around {
332            return None;
333        }
334
335        let out = self.next_index.clone();
336        self.ring.add_assign(&mut self.next_index, self.ring.one());
337        if self.ring.is_zero(&self.next_index) {
338            self.wrap_around = true;
339        }
340        Some(out)
341    }
342}
343
344impl<const N: usize> FiniteRingSpecializable for Z2kBase<N>
345where
346    [u64; N]: smallvec::Array<Item = u64>,
347{
348    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.execute() }
349}
350
351impl<const N: usize> FiniteRing for Z2kBase<N>
352where
353    [u64; N]: smallvec::Array<Item = u64>,
354{
355    type ElementsIter<'a>
356        = Z2KBaseElementsIter<'a, N>
357    where
358        Self: 'a;
359
360    fn elements<'a>(&'a self) -> Self::ElementsIter<'a> {
361        Z2KBaseElementsIter {
362            ring: self,
363            next_index: self.zero(),
364            wrap_around: false,
365        }
366    }
367
368    fn random_element<G: FnMut() -> u64>(&self, rng: G) -> <Self as RingBase>::Element {
369        super::generic_impls::random_element(self, rng)
370    }
371
372    fn size<I: RingStore + Copy>(&self, other_ZZ: I) -> Option<El<I>>
373    where
374        I::Type: IntegerRing,
375    {
376        {
377            if other_ZZ.get_ring().representable_bits().is_none()
378                || self.k < other_ZZ.get_ring().representable_bits().unwrap()
379            {
380                Some(int_cast(
381                    RustBigintRing::RING.clone_el(&self.modulus),
382                    other_ZZ,
383                    &RustBigintRing::RING,
384                ))
385            } else {
386                None
387            }
388        }
389    }
390}
391
392impl<const N: usize> PrincipalIdealRing for Z2kBase<N>
393where
394    [u64; N]: smallvec::Array<Item = u64>,
395{
396    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
397        super::generic_impls::checked_div_min(RingRef::new(self), lhs, rhs)
398    }
399
400    fn extended_ideal_gen(
401        &self,
402        lhs: &Self::Element,
403        rhs: &Self::Element,
404    ) -> (Self::Element, Self::Element, Self::Element) {
405        let ZZ = RustBigintRing::RING;
406        let l = self.el_to_bigint(&ZZ, lhs.clone());
407        let r = self.el_to_bigint(&ZZ, rhs.clone());
408        let (s, t, d) = ZZ.extended_ideal_gen(&l, &r);
409        let [s, t, d] = [s, t, d].map(|x| self.bigint_to_el(&ZZ, &x));
410        (s, t, d)
411    }
412}
413
414impl<const N: usize, I: ?Sized + IntegerRing> CanHomFrom<I> for Z2kBase<N>
415where
416    [u64; N]: smallvec::Array<Item = u64>,
417{
418    type Homomorphism = super::generic_impls::BigIntToZnHom<I, RustBigintRingBase, Self>;
419
420    fn has_canonical_hom(&self, from: &I) -> Option<Self::Homomorphism> {
421        super::generic_impls::has_canonical_hom_from_bigint(from, self, RustBigintRing::RING.get_ring(), None)
422    }
423
424    default fn map_in(&self, from: &I, el: I::Element, hom: &Self::Homomorphism) -> Self::Element {
425        let ZZ = &RustBigintRing::RING;
426        super::generic_impls::map_in_from_bigint(
427            from,
428            self,
429            ZZ.get_ring(),
430            el,
431            hom,
432            |n| self.bigint_to_el(ZZ, &n),
433            |n| self.bigint_to_el(ZZ, &n),
434        )
435    }
436}
437
438impl<const N: usize> CanHomFrom<RustBigintRingBase> for Z2kBase<N>
439where
440    [u64; N]: smallvec::Array<Item = u64>,
441{
442    fn map_in(
443        &self,
444        _from: &RustBigintRingBase,
445        el: <RustBigintRingBase as RingBase>::Element,
446        _: &Self::Homomorphism,
447    ) -> Self::Element {
448        self.bigint_to_el(&RustBigintRing::RING, &el)
449    }
450}
451
452macro_rules! impl_static_int_to_z2k {
453    ($($int:ident),*) => {
454        $(
455            impl<const N: usize> CanHomFrom<StaticRingBase<$int>> for Z2kBase<N>
456            where
457                [u64; N]: smallvec::Array<Item = u64>,
458            {
459                fn map_in(
460                    &self,
461                    from: &StaticRingBase<$int>,
462                    el: $int,
463                    _: &Self::Homomorphism,
464                ) -> Self::Element {
465                    let ZZ = &RustBigintRing::RING;
466                    let x = int_cast(el, ZZ, RingRef::new(from));
467                    self.bigint_to_el(ZZ, &x)
468                }
469            }
470        )*
471    };
472}
473
474impl_static_int_to_z2k! { i8, i16, i32, i64, i128 }
475
476impl<const N: usize> ZnRing for Z2kBase<N>
477where
478    [u64; N]: smallvec::Array<Item = u64>,
479{
480    type IntegerRingBase = RustBigintRingBase;
481    type IntegerRing = RustBigintRing;
482
483    fn integer_ring(&self) -> &Self::IntegerRing { &RustBigintRing::RING }
484
485    fn smallest_positive_lift(&self, el: Self::Element) -> El<Self::IntegerRing> {
486        let ZZ = RustBigintRing::RING;
487        self.el_to_bigint(&ZZ, el)
488    }
489
490    fn smallest_lift(&self, el: Self::Element) -> El<Self::IntegerRing> {
491        let result = self.smallest_positive_lift(el);
492        let mut mod_half = self.integer_ring().clone_el(self.modulus());
493        self.integer_ring().euclidean_div_pow_2(&mut mod_half, 1);
494        if self.integer_ring().is_gt(&result, &mod_half) {
495            self.integer_ring().sub_ref_snd(result, self.modulus())
496        } else {
497            result
498        }
499    }
500
501    fn modulus(&self) -> &El<Self::IntegerRing> { &self.modulus }
502
503    fn any_lift(&self, el: Self::Element) -> El<Self::IntegerRing> { self.smallest_positive_lift(el) }
504
505    fn from_int_promise_reduced(&self, x: El<Self::IntegerRing>) -> Self::Element {
506        debug_assert!({
507            let ZZ = RustBigintRing::RING;
508            !ZZ.is_neg(&x) && ZZ.is_lt(&x, &self.modulus)
509        });
510        self.bigint_to_el(&RustBigintRing::RING, &x)
511    }
512}
513
514impl_field_wrap_unwrap_homs! { Z2kBase, Z2kBase }
515impl_field_wrap_unwrap_isos! { Z2kBase, Z2kBase }
516impl_localpir_wrap_unwrap_homs! { Z2kBase, Z2kBase }
517impl_localpir_wrap_unwrap_isos! { Z2kBase, Z2kBase }
518
519#[cfg(test)]
520mod tests {
521    use super::*;
522    use crate::primitive_int::StaticRing;
523    use crate::ring::generic_tests as ring_generic_tests;
524    use crate::rings::zn::generic_tests as zn_generic_tests;
525
526    const SMALL_Ks: [usize; 2] = [3, 8];
527    const ZZ: BigIntRing = BigIntRing::RING;
528
529    #[test]
530    fn test_z2k_can_hom_map_in_large_power() {
531        let r: Z2k = Z2k::new(256);
532        zn_generic_tests::test_map_in_large_int(r);
533    }
534
535    #[test]
536    fn test_z2k_can_hom_axioms_static_i32() {
537        let to: Z2k = Z2k::new(14);
538        ring_generic_tests::test_hom_axioms(StaticRing::<i32>::RING, to, -12i32..=12);
539    }
540
541    #[test]
542    fn test_z2k_can_hom_axioms_bigint_ring() {
543        let to: Z2k = Z2k::new(20);
544        let edge = [
545            ZZ.zero(),
546            ZZ.one(),
547            ZZ.negate(ZZ.one()),
548            ZZ.int_hom().map(17),
549            ZZ.int_hom().map(-42),
550            ZZ.pow(ZZ.int_hom().map(2), 200),
551        ];
552        ring_generic_tests::test_hom_axioms(&ZZ, to, edge.into_iter());
553    }
554
555    #[test]
556    fn test_z2k_pow2_64_add_mul_edge_cases() {
557        let r: Z2k = Z2k::new(64);
558
559        let almost_mod = ZZ.sub(ZZ.power_of_two(64), ZZ.int_hom().map(5));
560        let a = r.coerce(&ZZ, almost_mod);
561        let b = r.int_hom().map(5);
562        assert_el_eq!(r, r.zero(), r.add_ref(&a, &b));
563
564        // `2^32 * 2^32` = 0 mod `2^64`.
565        let pow32 = ZZ.power_of_two(32);
566        let u = r.coerce(&ZZ, pow32);
567        assert_el_eq!(r, r.zero(), r.mul_ref(&u, &u));
568    }
569
570    #[test]
571    fn test_z2k_pow2_130_add_mul_edge_cases() {
572        let r: Z2k = Z2k::new(130);
573
574        // `k` is not a multiple of 64, so the last limb is partially masked.
575        let almost_mod = ZZ.sub(ZZ.power_of_two(130), ZZ.int_hom().map(11));
576        let a = r.coerce(&ZZ, almost_mod);
577        let b = r.int_hom().map(11);
578        assert_el_eq!(r, r.zero(), r.add_ref(&a, &b));
579
580        // `2^100 + 2^129` = 0 mod `2^130`.
581        let hi = ZZ.add(ZZ.power_of_two(100), ZZ.power_of_two(129));
582        let expected = ZZ.euclidean_rem(ZZ.mul_ref(&hi, &hi), &r.modulus());
583        let x = r.coerce(&ZZ, hi);
584        let y = r.mul_ref(&x, &x);
585        assert!(ZZ.eq_el(&expected, &r.smallest_positive_lift(y)));
586    }
587
588    #[test]
589    fn test_ring_axioms_z2kbase() {
590        for k in SMALL_Ks {
591            let ring: Z2k = Z2k::new(k);
592            crate::ring::generic_tests::test_ring_axioms(&ring, ring.elements())
593        }
594    }
595
596    #[test]
597    fn test_zn_ring_axioms_znbase() {
598        for k in SMALL_Ks {
599            let ring: Z2k = Z2k::new(k);
600            crate::rings::zn::generic_tests::test_zn_axioms(ring);
601        }
602    }
603
604    #[test]
605    fn test_divisibility_axioms() {
606        for k in SMALL_Ks {
607            let R: Z2k = Z2k::new(k);
608            crate::divisibility::generic_tests::test_divisibility_axioms(&R, R.elements());
609        }
610    }
611
612    #[test]
613    fn test_principal_ideal_ring_axioms() {
614        for k in SMALL_Ks {
615            let R: Z2k = Z2k::new(k);
616            crate::pid::generic_tests::test_principal_ideal_ring_axioms(&R, R.elements());
617        }
618    }
619
620    #[test]
621    fn test_finite_field_axioms() {
622        for k in SMALL_Ks {
623            let R: Z2k = Z2k::new(k);
624            crate::rings::finite::generic_tests::test_finite_ring_axioms(&R);
625        }
626    }
627}
feanor_math/rings/zn/zn_pow2.rs

feanor_math/rings/zn/
zn_pow2.rs
