class_groups/crypto_bigint/
boxed_uint.rs

1#![expect(clippy::inline_always)]
2
3use alloc::boxed::Box;
4
5use crypto_bigint::{
6  CtEq as _, CtAssign as _, Resize as _, Zero, One as _, ConcatenatingSquare as _,
7  ConcatenatingMul as _, Gcd as _, Choice, NonZero, BoxedUint,
8};
9
10impl super::c::Limbs for BoxedUint {
11  #[inline(always)]
12  fn widening_square(&self) -> (Self, Self) {
13    let size = self.bits_precision();
14    let square = self.concatenating_square().clone();
15    let hi = (&square >> size).resize_unchecked(size);
16    let lo = square.resize_unchecked(size);
17    (lo, hi)
18  }
19  #[inline(always)]
20  fn wrapping_div(num: (Self, Self), denom: &Self) -> Self {
21    let denom_bits = denom.bits_precision();
22    let num =
23      num.1.resize_unchecked(2 * denom_bits).overflowing_shl_vartime(denom_bits).unwrap() | num.0;
24    // The caller is bound to not pass `0` as the denominator
25    let (quotient, remainder) = num.div_rem(&denom.to_nz().unwrap());
26    debug_assert!(bool::from(remainder.is_zero()));
27    quotient.resize_unchecked(denom_bits)
28  }
29  #[inline(always)]
30  fn rem(num: Self, denom: &Self) -> Self {
31    num.div_rem(&NonZero::new(denom.clone()).unwrap()).1
32  }
33}
34
35impl super::reduction::Limbs for BoxedUint {
36  #[inline(always)]
37  fn like_zero(&self) -> Self {
38    Zero::zero_like(self)
39  }
40}
41
42impl super::composition::Limbs for BoxedUint {
43  type Wide = BoxedUint;
44  #[expect(private_interfaces)]
45  fn xgcd(self, other: Self) -> super::composition::Xgcd<Self> {
46    // The documentation on the `trait` allows us to make these bounds
47    debug_assert!(bool::from(!self.is_zero()));
48    debug_assert!(bool::from(!other.is_zero()));
49
50    // `BoxedUint` has a `gcd` method but not an `xgcd` method, so we calculate `u, v` ourselves
51    // We know the `gcd` is non-zero as the inputs are non-zero
52    let gcd = NonZero::new(self.gcd(&other)).unwrap();
53
54    // Calculate `u` as the modular inverse of `self % other`
55    let u = {
56      let self_div_gcd = &self / &gcd;
57      let other_div_gcd = &other / &gcd;
58      /*
59        This has a modular inverse as these are coprime, which will be true UNLESS `self` is itself
60        a factor (or multiple) of `other`. In this case, the coefficients are `0, 1` or `1, 0`.
61      */
62      let u = self_div_gcd.invert_mod(&NonZero::new(other_div_gcd).unwrap());
63      let u_if_divisible =
64        BoxedUint::from(u8::from(self_div_gcd.is_one())).resize_unchecked(other.bits_precision());
65      u.unwrap_or(u_if_divisible)
66    };
67
68    /*
69      Calculate `v` as `(ua - d) / b`.
70
71      We explicitly use a `wrapping_sub` as `ua = 0` occurs when `b | a`. This causes an invalid
72      value to be assigned to `v`, but we then correct it to `1` if so.
73    */
74    /*
75      TODO: The composition algorithm doesn't need this coefficient for one of its two calls to
76      `xgcd`. If we split the `xgcd` function into one which returns the `u` coefficient and one
77      which returns the `u` and `v` coefficients, we can optimize this out.
78    */
79    let v =
80      ((u.concatenating_mul(&self)).wrapping_sub(&*gcd)) / NonZero::new(other.clone()).unwrap();
81    let mut v = v.resize_unchecked(self.bits_precision());
82    // If `u = 0` because `b` is a factor of `a`, correct the `v` coefficient to `1`
83    v.ct_assign(&BoxedUint::one_like(&v), u.is_zero());
84
85    /*
86      Return `u` as the positive coefficient, `v` as the negative coefficient, as it's our choice
87      when we know the inputs are non-zero EXCEPT when one is a factor of the other. In this case,
88      both are positive as one coefficient will be zero.
89    */
90    let v_sign = u.is_zero();
91
92    #[cfg(debug_assertions)]
93    {
94      use crypto_bigint::CtSelect as _;
95      let eq1 = u.concatenating_mul(&self);
96      let eq2 = v.concatenating_mul(&other);
97      let lhs = <_>::ct_select(
98        &(eq1.wrapping_sub(&eq2).concatenating_add(BoxedUint::zero())),
99        &eq1.concatenating_add(&eq2),
100        v_sign,
101      );
102      debug_assert!(bool::from(lhs.ct_eq(&*gcd)));
103    }
104
105    super::composition::Xgcd { d: gcd.get(), u: (Choice::TRUE, u), v: (v_sign, v) }
106  }
107  #[inline(always)]
108  fn div(self, denom: &Self) -> Self {
109    self.div_rem(&NonZero::new(denom.clone()).unwrap()).0
110  }
111  #[inline(always)]
112  fn mul_mod(&self, other: &Self, modulus: &Self) -> Self {
113    let product = self.mul_mod(other, &NonZero::new(modulus.clone()).unwrap());
114    product.resize_unchecked(modulus.bits_precision())
115  }
116  #[inline(always)]
117  fn mul(&self, other: &Self) -> Self::Wide {
118    self.concatenating_mul(other)
119  }
120  #[inline(always)]
121  fn square(&self) -> Self::Wide {
122    self.concatenating_square()
123  }
124}
125
126impl super::composition::WideLimbs<BoxedUint> for BoxedUint {
127  #[inline(always)]
128  fn rem(self, denom: &BoxedUint) -> Self {
129    let remainder = self.div_rem(&NonZero::new(denom.clone()).unwrap()).1;
130    remainder.resize_unchecked(denom.bits_precision())
131  }
132}
133
134impl super::encoding::Limbs for BoxedUint {
135  fn wide_div_rem_thin(wide: Self::Wide, thin: &NonZero<Self>) -> (Self::Wide, Self) {
136    wide.div_rem(thin)
137  }
138
139  fn coprime(a: Self, b_abs: Self, c: Self::Wide) -> Choice {
140    a.gcd(&b_abs).gcd(&c).is_one()
141  }
142}
143
144impl super::element::Limbs for BoxedUint {
145  type Bytes = Box<[u8]>;
146
147  #[inline(always)]
148  fn max_bits() -> Option<u32> {
149    None
150  }
151
152  #[inline(always)]
153  fn truncate(wide: Self::Wide, bits: u32) -> Self {
154    wide.resize_unchecked(bits)
155  }
156  #[inline(always)]
157  fn widen(thin: Self, wide_bits: u32) -> Self::Wide {
158    thin.resize_unchecked(wide_bits)
159  }
160
161  #[inline(always)]
162  fn to_le_bytes(self) -> Self::Bytes {
163    BoxedUint::to_le_bytes(&self)
164  }
165  #[inline(always)]
166  fn wide_to_le_bytes(wide: Self::Wide) -> impl AsRef<[u8]> {
167    BoxedUint::to_le_bytes(&wide)
168  }
169
170  #[inline(always)]
171  fn from_le_slice(mut bytes: &[u8], max_bits: u32) -> Self {
172    while ((8 * u32::try_from(bytes.len().saturating_sub(1)).unwrap()) >= max_bits) &&
173      bytes.last().map(|byte| bool::from(byte.ct_eq(&0))).unwrap_or(false)
174    {
175      bytes = &bytes[.. (bytes.len() - 1)];
176    }
177    Self::from_le_slice(bytes, max_bits).unwrap()
178  }
179  #[inline(always)]
180  fn wide_from_le_slice(mut bytes: &[u8], max_bits: u32) -> Self::Wide {
181    while ((8 * u32::try_from(bytes.len().saturating_sub(1)).unwrap()) >= max_bits) &&
182      bytes.last().map(|byte| bool::from(byte.ct_eq(&0))).unwrap_or(false)
183    {
184      bytes = &bytes[.. (bytes.len() - 1)];
185    }
186    Self::from_le_slice(bytes, max_bits).unwrap()
187  }
188
189  fn stitch(first: Self::Bytes, second: Self::Bytes, bytes_per_element: usize) -> impl AsRef<[u8]> {
190    [&first[.. bytes_per_element], &second[.. bytes_per_element]].concat()
191  }
192}
class_groups/crypto_bigint/boxed_uint.rs

class_groups/crypto_bigint/
boxed_uint.rs
