crypto_bigint/
odd.rs

1//! Wrapper type for non-zero integers.
2
3use crate::{
4    Bounded, Choice, ConstOne, CtAssign, CtEq, CtOption, CtSelect, Int, Integer, Limb, Mul,
5    NonZero, One, Uint, UintRef,
6};
7use core::{cmp::Ordering, fmt, ops::Deref};
8use ctutils::{CtAssignSlice, CtEqSlice};
9
10#[cfg(feature = "alloc")]
11use crate::{BoxedUint, Resize};
12
13#[cfg(feature = "rand_core")]
14use crate::{Random, rand_core::TryRng};
15
16#[cfg(all(feature = "alloc", feature = "rand_core"))]
17use crate::RandomBits;
18
19#[cfg(feature = "serde")]
20use crate::Zero;
21#[cfg(feature = "serde")]
22use serdect::serde::{
23    Deserialize, Deserializer, Serialize, Serializer,
24    de::{Error, Unexpected},
25};
26
27/// Odd unsigned integer.
28pub type OddUint<const LIMBS: usize> = Odd<Uint<LIMBS>>;
29
30/// Odd unsigned integer reference.
31pub type OddUintRef = Odd<UintRef>;
32
33/// Odd signed integer.
34pub type OddInt<const LIMBS: usize> = Odd<Int<LIMBS>>;
35
36/// Odd boxed unsigned integer.
37#[cfg(feature = "alloc")]
38pub type OddBoxedUint = Odd<BoxedUint>;
39
40/// Wrapper type for odd integers.
41///
42/// These are frequently used in cryptography, e.g. as a modulus.
43#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, PartialOrd, Ord)]
44#[repr(transparent)]
45pub struct Odd<T: ?Sized>(pub(crate) T);
46
47impl<T> Odd<T> {
48    /// Create a new odd integer.
49    #[inline]
50    pub fn new(mut n: T) -> CtOption<Self>
51    where
52        T: Integer,
53    {
54        let is_odd = n.is_odd();
55
56        // Use one as a placeholder in the event an even number is provided, so functions that
57        // operate on `NonZero` values really can expect the value to never be zero, even in the
58        // case `CtOption::is_some` is false.
59        n.ct_assign(&T::one_like(&n), !is_odd);
60        CtOption::new(Self(n), is_odd)
61    }
62
63    /// Returns the inner value.
64    #[inline]
65    pub fn get(self) -> T {
66        self.0
67    }
68
69    /// Returns a copy of the inner value for `Copy` types.
70    ///
71    /// This allows the function to be `const fn`, since `Copy` is implicitly `!Drop`, which avoids
72    /// problems around `const fn` destructors.
73    #[inline]
74    pub const fn get_copy(self) -> T
75    where
76        T: Copy,
77    {
78        self.0
79    }
80}
81
82impl<T: ?Sized> Odd<T> {
83    /// Provides access to the contents of [`Odd`] in a `const` context.
84    pub const fn as_ref(&self) -> &T {
85        &self.0
86    }
87
88    /// All odd integers are definitionally non-zero, so we can also obtain a reference to
89    /// the equivalent [`NonZero`] type.
90    pub const fn as_nz_ref(&self) -> &NonZero<T> {
91        // SAFETY: `NonZero` and `Odd` are both `repr(transparent)` newtypes of `T` and therefore
92        // have the same layout. All `Odd` numbers are definitionally non-zero because zero is an
93        // even number
94        #[allow(unsafe_code)]
95        unsafe {
96            &*(&raw const self.0 as *const NonZero<T>)
97        }
98    }
99}
100
101impl<T> Odd<T>
102where
103    T: Bounded + ?Sized,
104{
105    /// Total size of the represented integer in bits.
106    pub const BITS: u32 = T::BITS;
107
108    /// Total size of the represented integer in bytes.
109    pub const BYTES: usize = T::BYTES;
110}
111
112impl<const LIMBS: usize> OddUint<LIMBS> {
113    /// Create a new [`OddUint`] from the provided big endian hex string.
114    ///
115    /// # Panics
116    /// - if the hex is malformed or not zero-padded accordingly for the size.
117    /// - if the value is even.
118    #[must_use]
119    #[track_caller]
120    pub const fn from_be_hex(hex: &str) -> Self {
121        let uint = Uint::<LIMBS>::from_be_hex(hex);
122        assert!(uint.is_odd().to_bool_vartime(), "number must be odd");
123        Odd(uint)
124    }
125
126    /// Create a new [`Odd<Uint<LIMBS>>`] from the provided little endian hex string.
127    ///
128    /// # Panics
129    /// - if the hex is malformed or not zero-padded accordingly for the size.
130    /// - if the value is even.
131    #[must_use]
132    #[track_caller]
133    pub const fn from_le_hex(hex: &str) -> Self {
134        let uint = Uint::<LIMBS>::from_le_hex(hex);
135        assert!(uint.is_odd().to_bool_vartime(), "number must be odd");
136        Odd(uint)
137    }
138
139    /// Borrow this `OddUint` as a `&OddUintRef`.
140    #[inline]
141    #[must_use]
142    pub const fn as_uint_ref(&self) -> &OddUintRef {
143        self.0.as_uint_ref().as_odd_unchecked()
144    }
145
146    /// Construct an [`Odd<Uint<T>>`] from the unsigned integer value,
147    /// truncating the upper bits if the value is too large to be
148    /// represented.
149    #[must_use]
150    pub const fn resize<const T: usize>(&self) -> Odd<Uint<T>> {
151        Odd(self.0.resize())
152    }
153}
154
155impl<const LIMBS: usize> AsRef<OddUintRef> for OddUint<LIMBS> {
156    fn as_ref(&self) -> &OddUintRef {
157        self.as_uint_ref()
158    }
159}
160
161impl<const LIMBS: usize> Odd<Int<LIMBS>> {
162    /// The sign and magnitude of this [`Odd<Int<{LIMBS}>>`].
163    #[must_use]
164    pub const fn abs_sign(&self) -> (Odd<Uint<LIMBS>>, Choice) {
165        // Absolute value of an odd value is odd
166        let (abs, sgn) = Int::abs_sign(self.as_ref());
167        (Odd(abs), sgn)
168    }
169
170    /// The magnitude of this [`Odd<Int<{LIMBS}>>`].
171    #[must_use]
172    pub const fn abs(&self) -> Odd<Uint<LIMBS>> {
173        self.abs_sign().0
174    }
175}
176
177impl<T: ?Sized> AsRef<T> for Odd<T> {
178    fn as_ref(&self) -> &T {
179        &self.0
180    }
181}
182
183impl<T> AsRef<[Limb]> for Odd<T>
184where
185    T: AsRef<[Limb]>,
186{
187    fn as_ref(&self) -> &[Limb] {
188        self.0.as_ref()
189    }
190}
191
192impl<T: ?Sized> AsRef<NonZero<T>> for Odd<T> {
193    fn as_ref(&self) -> &NonZero<T> {
194        self.as_nz_ref()
195    }
196}
197
198impl<T> CtAssign for Odd<T>
199where
200    T: CtAssign,
201{
202    #[inline]
203    fn ct_assign(&mut self, other: &Self, choice: Choice) {
204        self.0.ct_assign(&other.0, choice);
205    }
206}
207impl<T> CtAssignSlice for Odd<T> where T: CtAssignSlice {}
208
209impl<T> CtEq for Odd<T>
210where
211    T: CtEq + ?Sized,
212{
213    #[inline]
214    fn ct_eq(&self, other: &Self) -> Choice {
215        CtEq::ct_eq(&self.0, &other.0)
216    }
217}
218impl<T> CtEqSlice for Odd<T> where T: CtEq {}
219
220impl<T> CtSelect for Odd<T>
221where
222    T: CtSelect,
223{
224    #[inline]
225    fn ct_select(&self, other: &Self, choice: Choice) -> Self {
226        Self(self.0.ct_select(&other.0, choice))
227    }
228}
229
230impl<T> Default for Odd<T>
231where
232    T: One,
233{
234    #[inline]
235    fn default() -> Self {
236        Odd(T::one())
237    }
238}
239
240impl<T: ?Sized> Deref for Odd<T> {
241    type Target = T;
242
243    fn deref(&self) -> &T {
244        &self.0
245    }
246}
247
248impl<T> ConstOne for Odd<T>
249where
250    T: ConstOne + One,
251{
252    const ONE: Self = Self(T::ONE);
253}
254
255impl<T> One for Odd<T>
256where
257    T: One,
258{
259    #[inline]
260    fn one() -> Self {
261        Self(T::one())
262    }
263}
264
265impl<T> num_traits::One for Odd<T>
266where
267    T: One + Mul<T, Output = T>,
268{
269    #[inline]
270    fn one() -> Self {
271        Self(T::one())
272    }
273
274    fn is_one(&self) -> bool {
275        self.0.is_one().into()
276    }
277}
278
279/// Any odd integer multiplied by another odd integer is definitionally odd.
280impl<T> Mul<Self> for Odd<T>
281where
282    T: Mul<T, Output = T>,
283{
284    type Output = Self;
285
286    fn mul(self, rhs: Self) -> Self {
287        Self(self.0 * rhs.0)
288    }
289}
290
291impl<const LIMBS: usize> PartialEq<Odd<Uint<LIMBS>>> for Uint<LIMBS> {
292    fn eq(&self, other: &Odd<Uint<LIMBS>>) -> bool {
293        self.eq(&other.0)
294    }
295}
296
297impl<const LIMBS: usize> PartialOrd<Odd<Uint<LIMBS>>> for Uint<LIMBS> {
298    fn partial_cmp(&self, other: &Odd<Uint<LIMBS>>) -> Option<Ordering> {
299        Some(self.cmp(&other.0))
300    }
301}
302
303impl OddUintRef {
304    /// Construct an [`Odd<Uint<T>>`] from the unsigned integer value,
305    /// truncating the upper bits if the value is too large to be
306    /// represented.
307    #[must_use]
308    pub const fn to_uint_resize<const T: usize>(&self) -> Odd<Uint<T>> {
309        Odd(self.0.to_uint_resize())
310    }
311}
312
313#[cfg(feature = "alloc")]
314impl OddBoxedUint {
315    /// Borrow this `OddBoxedUint` as a `&OddUintRef`.
316    #[inline]
317    #[must_use]
318    pub const fn as_uint_ref(&self) -> &OddUintRef {
319        self.0.as_uint_ref().as_odd_unchecked()
320    }
321
322    /// Generate a random `Odd<Uint<T>>`.
323    #[cfg(feature = "rand_core")]
324    pub fn random<R: TryRng + ?Sized>(rng: &mut R, bit_length: u32) -> Self {
325        let mut ret = BoxedUint::random_bits(rng, bit_length);
326        ret.limbs[0] |= Limb::ONE;
327        Odd(ret)
328    }
329}
330
331#[cfg(feature = "alloc")]
332impl AsRef<OddUintRef> for OddBoxedUint {
333    fn as_ref(&self) -> &OddUintRef {
334        self.as_uint_ref()
335    }
336}
337
338#[cfg(feature = "alloc")]
339impl PartialEq<OddBoxedUint> for BoxedUint {
340    fn eq(&self, other: &OddBoxedUint) -> bool {
341        self.eq(&other.0)
342    }
343}
344
345#[cfg(feature = "alloc")]
346impl PartialOrd<OddBoxedUint> for BoxedUint {
347    fn partial_cmp(&self, other: &OddBoxedUint) -> Option<Ordering> {
348        Some(self.cmp(&other.0))
349    }
350}
351
352#[cfg(feature = "alloc")]
353impl Resize for OddBoxedUint {
354    type Output = Self;
355
356    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
357        Odd(self.0.resize_unchecked(at_least_bits_precision))
358    }
359
360    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
361        self.0.try_resize(at_least_bits_precision).map(Odd)
362    }
363}
364
365#[cfg(feature = "alloc")]
366impl Resize for &OddBoxedUint {
367    type Output = OddBoxedUint;
368
369    fn resize_unchecked(self, at_least_bits_precision: u32) -> Self::Output {
370        Odd((&self.0).resize_unchecked(at_least_bits_precision))
371    }
372
373    fn try_resize(self, at_least_bits_precision: u32) -> Option<Self::Output> {
374        (&self.0).try_resize(at_least_bits_precision).map(Odd)
375    }
376}
377
378#[cfg(feature = "rand_core")]
379impl<const LIMBS: usize> Random for Odd<Uint<LIMBS>> {
380    /// Generate a random `Odd<Uint<T>>`.
381    fn try_random_from_rng<R: TryRng + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
382        let mut ret = Uint::try_random_from_rng(rng)?;
383        ret.limbs[0] |= Limb::ONE;
384        Ok(Odd(ret))
385    }
386}
387
388impl<T> fmt::Display for Odd<T>
389where
390    T: fmt::Display + ?Sized,
391{
392    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
393        fmt::Display::fmt(&self.0, f)
394    }
395}
396
397impl<T> fmt::Binary for Odd<T>
398where
399    T: fmt::Binary + ?Sized,
400{
401    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
402        fmt::Binary::fmt(&self.0, f)
403    }
404}
405
406impl<T> fmt::Octal for Odd<T>
407where
408    T: fmt::Octal + ?Sized,
409{
410    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
411        fmt::Octal::fmt(&self.0, f)
412    }
413}
414
415impl<T> fmt::LowerHex for Odd<T>
416where
417    T: fmt::LowerHex + ?Sized,
418{
419    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
420        fmt::LowerHex::fmt(&self.0, f)
421    }
422}
423
424impl<T> fmt::UpperHex for Odd<T>
425where
426    T: fmt::UpperHex + ?Sized,
427{
428    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
429        fmt::UpperHex::fmt(&self.0, f)
430    }
431}
432
433#[cfg(feature = "serde")]
434impl<'de, T: Deserialize<'de> + Integer + Zero> Deserialize<'de> for Odd<T> {
435    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
436    where
437        D: Deserializer<'de>,
438    {
439        let value: T = T::deserialize(deserializer)?;
440        Option::<Self>::from(Self::new(value)).ok_or(D::Error::invalid_value(
441            Unexpected::Other("even"),
442            &"a non-zero odd value",
443        ))
444    }
445}
446
447#[cfg(feature = "serde")]
448impl<T: Serialize + Zero> Serialize for Odd<T> {
449    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
450    where
451        S: Serializer,
452    {
453        self.0.serialize(serializer)
454    }
455}
456
457#[cfg(feature = "subtle")]
458impl<T> subtle::ConditionallySelectable for Odd<T>
459where
460    T: Copy,
461    Self: CtSelect,
462{
463    fn conditional_select(a: &Self, b: &Self, choice: subtle::Choice) -> Self {
464        a.ct_select(b, choice.into())
465    }
466}
467
468#[cfg(feature = "subtle")]
469impl<T> subtle::ConstantTimeEq for Odd<T>
470where
471    T: ?Sized,
472    Self: CtEq,
473{
474    fn ct_eq(&self, other: &Self) -> subtle::Choice {
475        CtEq::ct_eq(self, other).into()
476    }
477}
478
479#[cfg(feature = "zeroize")]
480impl<T: zeroize::Zeroize> zeroize::Zeroize for Odd<T> {
481    fn zeroize(&mut self) {
482        self.0.zeroize();
483    }
484}
485
486#[cfg(test)]
487mod tests {
488    use super::Odd;
489    use crate::{ConstOne, U128, Uint};
490
491    #[cfg(feature = "alloc")]
492    use crate::BoxedUint;
493
494    #[test]
495    fn default() {
496        assert!(Odd::<U128>::default().is_odd().to_bool());
497    }
498
499    #[test]
500    fn from_be_hex_when_odd() {
501        assert_eq!(
502            Odd::<U128>::from_be_hex("00000000000000000000000000000001"),
503            Odd::<U128>::ONE
504        );
505    }
506
507    #[test]
508    #[should_panic]
509    fn from_be_hex_when_even() {
510        let _ = Odd::<U128>::from_be_hex("00000000000000000000000000000002");
511    }
512
513    #[test]
514    fn from_le_hex_when_odd() {
515        assert_eq!(
516            Odd::<U128>::from_le_hex("01000000000000000000000000000000"),
517            Odd::<U128>::ONE
518        );
519    }
520
521    #[test]
522    #[should_panic]
523    fn from_le_hex_when_even() {
524        let _ = Odd::<U128>::from_le_hex("20000000000000000000000000000000");
525    }
526
527    #[test]
528    fn not_odd_numbers() {
529        let zero = Odd::new(Uint::<4>::ZERO);
530        assert!(bool::from(zero.is_none()));
531        let two = Odd::new(Uint::<4>::from(2u8));
532        assert!(bool::from(two.is_none()));
533    }
534
535    #[cfg(feature = "alloc")]
536    #[test]
537    fn not_odd_numbers_boxed() {
538        let zero = Odd::new(BoxedUint::zero());
539        assert!(bool::from(zero.is_none()));
540        let two = Odd::new(BoxedUint::from(2u8));
541        assert!(bool::from(two.is_none()));
542    }
543}
crypto_bigint/odd.rs

crypto_bigint/
odd.rs
