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    /// The Montgomery-form element produced by transforming `self` into the ring.
63    type RingElement: 'a;
64    /// Transform `self` into Montgomery form within `ring`.
65    fn into_monty(self, ring: &'a Ring) -> Self::RingElement;
66}
67
68impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for UBig {
69    type RingElement = Montgomery<'a>;
70
71    #[inline]
72    fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
73        match ring.data() {
74            MontgomeryReprData::Single(r) => {
75                let modulus = r.0.modulus();
76                let residue = &self % &UBig::from_word(modulus);
77                Montgomery::from_single(r.0.transform(ubig_to_word(&residue)), r)
78            }
79            MontgomeryReprData::Double(r) => {
80                let modulus = r.0.modulus();
81                let residue = &self % &UBig::from_dword(modulus);
82                Montgomery::from_double(r.0.transform(ubig_to_dword(&residue)), r)
83            }
84            MontgomeryReprData::Large(r) => {
85                let s = r.modulus.len();
86                let modulus = UBig(Repr::from_buffer(Buffer::from(&r.modulus[..])));
87                let residue = &self % &modulus;
88                let residue_words = to_exact_words(&residue, s);
89                let memory_requirement = mul_memory_requirement(r);
90                let mut allocation = MemoryAllocation::new(memory_requirement);
91                let mut memory = allocation.memory();
92                let monty = mul_normalized_large(r, &residue_words, &r.r2_mod_m, &mut memory);
93                Montgomery::from_large(
94                    MontgomeryLargeVal(Buffer::from(monty).into_boxed_slice()),
95                    r,
96                )
97            }
98        }
99    }
100}
101
102impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for IBig {
103    type RingElement = Montgomery<'a>;
104
105    #[inline]
106    fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
107        let sign = self.sign();
108        let modulo = self.unsigned_abs().into_monty(ring);
109        match sign {
110            Sign::Positive => modulo,
111            Sign::Negative => -modulo,
112        }
113    }
114}
115
116/// Implement [`IntoMontgomeryRing`] for unsigned primitives.
117macro_rules! impl_into_monty_for_unsigned {
118    ($t:ty) => {
119        impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for $t {
120            type RingElement = Montgomery<'a>;
121            #[inline]
122            fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
123                UBig::from(self).into_monty(ring)
124            }
125        }
126    };
127}
128
129/// Implement [`IntoMontgomeryRing`] for signed primitives.
130macro_rules! impl_into_monty_for_signed {
131    ($t:ty) => {
132        impl<'a> IntoMontgomeryRing<'a, MontgomeryRepr> for $t {
133            type RingElement = Montgomery<'a>;
134            #[inline]
135            fn into_monty(self, ring: &'a MontgomeryRepr) -> Montgomery<'a> {
136                IBig::from(self).into_monty(ring)
137            }
138        }
139    };
140}
141
142impl_into_monty_for_unsigned!(bool);
143impl_into_monty_for_unsigned!(u8);
144impl_into_monty_for_unsigned!(u16);
145impl_into_monty_for_unsigned!(u32);
146impl_into_monty_for_unsigned!(u64);
147impl_into_monty_for_unsigned!(u128);
148impl_into_monty_for_unsigned!(usize);
149impl_into_monty_for_signed!(i8);
150impl_into_monty_for_signed!(i16);
151impl_into_monty_for_signed!(i32);
152impl_into_monty_for_signed!(i64);
153impl_into_monty_for_signed!(i128);
154impl_into_monty_for_signed!(isize);
155
156impl MontgomeryRepr {
157    /// Create an element of the Montgomery ring from another type.
158    ///
159    /// # Examples
160    ///
161    /// ```
162    /// # use dashu_int::{monty::MontgomeryRepr, UBig, IBig};
163    /// let ring = MontgomeryRepr::new(UBig::from(101u8));
164    /// let x = ring.reduce(-5);
165    /// let y = ring.reduce(IBig::from(96));
166    /// assert!(x == y);
167    /// ```
168    pub fn reduce<'a, T: IntoMontgomeryRing<'a, MontgomeryRepr, RingElement = Montgomery<'a>>>(
169        &'a self,
170        x: T,
171    ) -> Montgomery<'a> {
172        x.into_monty(self)
173    }
174}
175
176/// Extract a `Word` from a `UBig` known to fit in a single word.
177fn ubig_to_word(u: &UBig) -> Word {
178    match u.repr() {
179        TypedReprRef::RefSmall(d) => shrink_dword(d).expect("value fits in a word"),
180        TypedReprRef::RefLarge(_) => unreachable!("value is less than a single-word modulus"),
181    }
182}
183
184/// Extract a `DoubleWord` from a `UBig` known to fit in a double word.
185fn ubig_to_dword(u: &UBig) -> DoubleWord {
186    match u.repr() {
187        TypedReprRef::RefSmall(d) => d,
188        TypedReprRef::RefLarge(_) => unreachable!("value is less than a double-word modulus"),
189    }
190}
dashu_int/monty/convert.rs

dashu_int/monty/
convert.rs
