dashu_int/monty/
convert.rs

1//! Conversion between Montgomery form, UBig and IBig.
2
3use crate::{
4    arch::word::{DoubleWord, Word},
5    buffer::Buffer,
6    ibig::IBig,
7    memory::MemoryAllocation,
8    primitive::shrink_dword,
9    repr::{Repr, TypedReprRef},
10    ubig::UBig,
11    Sign,
12};
13use dashu_base::UnsignedAbs;
14use num_modular::Reducer;
15
16use super::mul::{mul_memory_requirement, mul_normalized_large, residue_normalized_large};
17use super::repr::{
18    to_exact_words, Montgomery, MontgomeryInner, MontgomeryLargeVal, MontgomeryRepr,
19    MontgomeryReprData,
20};
21
22impl Montgomery<'_> {
23    /// Get the residue in range `0..m`.
24    ///
25    /// # Examples
26    ///
27    /// ```
28    /// # use dashu_int::{monty::MontgomeryRepr, UBig};
29    /// let ring = MontgomeryRepr::new(UBig::from(101u8));
30    /// let x = ring.reduce(UBig::from(234u8));
31    /// assert_eq!(x.residue(), UBig::from(32u8));
32    /// ```
33    #[inline]
34    pub fn residue(&self) -> UBig {
35        match self.repr() {
36            MontgomeryInner::Single(raw, ring) => UBig::from_word(ring.0.residue(*raw)),
37            MontgomeryInner::Double(raw, ring) => UBig::from_dword(ring.0.residue(*raw)),
38            MontgomeryInner::Large(raw, ring) => {
39                let memory_requirement = mul_memory_requirement(ring);
40                let mut allocation = MemoryAllocation::new(memory_requirement);
41                let mut memory = allocation.memory();
42                let res = residue_normalized_large(ring, &raw.0, &mut memory);
43                UBig(Repr::from_buffer(Buffer::from(res)))
44            }
45        }
46    }
47
48    /// Get the modulus of the ring that this element belongs to.
49    pub fn modulus(&self) -> UBig {
50        match self.repr() {
51            MontgomeryInner::Single(_, ring) => UBig::from_word(ring.0.modulus()),
52            MontgomeryInner::Double(_, ring) => UBig::from_dword(ring.0.modulus()),
53            MontgomeryInner::Large(_, ring) => {
54                UBig(Repr::from_buffer(Buffer::from(&ring.modulus[..])))
55            }
56        }
57    }
58}
59
60/// Trait for types that can be converted into a [`Montgomery`] value by a [`MontgomeryRepr`].
61pub trait IntoMontgomeryRing<'a, Ring> {
62    type RingElement: 'a;
63    fn into_monty(self, ring: &'a Ring) -> Self::RingElement;
64}
65
66impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for UBig {
67    type RingElement = Montgomery<'a>;
68
69    #[inline]
70    fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
71        match ring.data() {
72            MontgomeryReprData::Single(r) => {
73                let modulus = r.0.modulus();
74                let residue = &self % &UBig::from_word(modulus);
75                Montgomery::from_single(r.0.transform(ubig_to_word(&residue)), r)
76            }
77            MontgomeryReprData::Double(r) => {
78                let modulus = r.0.modulus();
79                let residue = &self % &UBig::from_dword(modulus);
80                Montgomery::from_double(r.0.transform(ubig_to_dword(&residue)), r)
81            }
82            MontgomeryReprData::Large(r) => {
83                let s = r.modulus.len();
84                let modulus = UBig(Repr::from_buffer(Buffer::from(&r.modulus[..])));
85                let residue = &self % &modulus;
86                let residue_words = to_exact_words(&residue, s);
87                let memory_requirement = mul_memory_requirement(r);
88                let mut allocation = MemoryAllocation::new(memory_requirement);
89                let mut memory = allocation.memory();
90                let monty = mul_normalized_large(r, &residue_words, &r.r2_mod_m, &mut memory);
91                Montgomery::from_large(
92                    MontgomeryLargeVal(Buffer::from(monty).into_boxed_slice()),
93                    r,
94                )
95            }
96        }
97    }
98}
99
100impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for IBig {
101    type RingElement = Montgomery<'a>;
102
103    #[inline]
104    fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
105        let sign = self.sign();
106        let modulo = self.unsigned_abs().into_monty(ring);
107        match sign {
108            Sign::Positive => modulo,
109            Sign::Negative => -modulo,
110        }
111    }
112}
113
114/// Implement [`IntoMontgomeryRing`] for unsigned primitives.
115macro_rules! impl_into_monty_for_unsigned {
116    ($t:ty) => {
117        impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for $t {
118            type RingElement = Montgomery<'a>;
119            #[inline]
120            fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
121                UBig::from(self).into_monty(ring)
122            }
123        }
124    };
125}
126
127/// Implement [`IntoMontgomeryRing`] for signed primitives.
128macro_rules! impl_into_monty_for_signed {
129    ($t:ty) => {
130        impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for $t {
131            type RingElement = Montgomery<'a>;
132            #[inline]
133            fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
134                IBig::from(self).into_monty(ring)
135            }
136        }
137    };
138}
139
140impl_into_monty_for_unsigned!(bool);
141impl_into_monty_for_unsigned!(u8);
142impl_into_monty_for_unsigned!(u16);
143impl_into_monty_for_unsigned!(u32);
144impl_into_monty_for_unsigned!(u64);
145impl_into_monty_for_unsigned!(u128);
146impl_into_monty_for_unsigned!(usize);
147impl_into_monty_for_signed!(i8);
148impl_into_monty_for_signed!(i16);
149impl_into_monty_for_signed!(i32);
150impl_into_monty_for_signed!(i64);
151impl_into_monty_for_signed!(i128);
152impl_into_monty_for_signed!(isize);
153
154impl MontgomeryRepr {
155    /// Create an element of the Montgomery ring from another type.
156    ///
157    /// # Examples
158    ///
159    /// ```
160    /// # use dashu_int::{monty::MontgomeryRepr, UBig, IBig};
161    /// let ring = MontgomeryRepr::new(UBig::from(101u8));
162    /// let x = ring.reduce(-5);
163    /// let y = ring.reduce(IBig::from(96));
164    /// assert!(x == y);
165    /// ```
166    pub fn reduce<'a, T: IntoMontgomeryRing<'a, MontgomeryRepr, RingElement = Montgomery<'a>>>(
167        &'a self,
168        x: T,
169    ) -> Montgomery<'a> {
170        x.into_monty(self)
171    }
172}
173
174/// Extract a `Word` from a `UBig` known to fit in a single word.
175fn ubig_to_word(u: &UBig) -> Word {
176    match u.repr() {
177        TypedReprRef::RefSmall(d) => shrink_dword(d).expect("value fits in a word"),
178        TypedReprRef::RefLarge(_) => unreachable!("value is less than a single-word modulus"),
179    }
180}
181
182/// Extract a `DoubleWord` from a `UBig` known to fit in a double word.
183fn ubig_to_dword(u: &UBig) -> DoubleWord {
184    match u.repr() {
185        TypedReprRef::RefSmall(d) => d,
186        TypedReprRef::RefLarge(_) => unreachable!("value is less than a double-word modulus"),
187    }
188}
dashu_int/monty/convert.rs

dashu_int/monty/
convert.rs
