class_groups/crypto_bigint/
c.rs

1use crypto_bigint::{Choice, Limb};
2
3/// The required view over a collection of limbs to calculate the `c` coefficient.
4///
5/// Implementations MUST implement all functions in time constant to the value of the inputs,
6/// except for the amount of limbs, unless otherwise stated. Implementations MUST NOT panic for any
7/// input which the caller MAY pass.
8pub(super) trait Limbs: Sized + Clone + AsRef<[Limb]> + AsMut<[Limb]> {
9  /// Square the value, returning the `(lo, hi)` terms.
10  ///
11  /// Implementations MUST ensure each part of the result has an amount of limbs equal to how many
12  /// limbs the input has.
13  fn widening_square(&self) -> (Self, Self);
14
15  /// Divide `num`  by `denom`, returning the low bits.
16  ///
17  /// Callers MUST ensure both parts of the numerator have an equivalent amount of limbs. Callers
18  /// MUST NOT request a division by `0`.
19  ///
20  /// Implementations MUST ensure the result has an amount of limbs equal to how many limbs each
21  /// part of the input has.
22  fn wrapping_div(num: (Self, Self), denom: &Self) -> Self;
23
24  /// Calculate the remainder of `num % denom`.
25  ///
26  /// Callers MUST NOT specify `denom = 0`.
27  fn rem(num: Self, denom: &Self) -> Self;
28}
29
30/// Calculate `c` such that `b^2 - 4ac = delta`.
31///
32/// The following bounds are present:
33/// - `delta < 0`
34/// - There is an integer solution for `c` in `b^2 - 4 a c = delta`.
35/// - `<_ as AsRef<[Limb]>>::as_ref(a).len() <= <_ as AsRef<[Limb]>>::as_ref(&b.1).len()`
36/// - `<_ as AsRef<[Limb]>>::as_ref(negative_discriminant_abs).len() <=
37///      2 * <_ as AsRef<[Limb]>>::as_ref(&b.1).len()`
38/// - `b < 2a`
39/// - $floor(log_2(|delta|)) + 1 < <_ as AsRef<[Limb]>>::as_ref(a).len() * Limb::BITS$
40/// - $floor(log_2(|a|)) + 1 < <_ as AsRef<[Limb]>>::as_ref(a).len() * Limb::BITS$
41///
42/// `delta` is specified via its absolute value in `negative_discriminant_abs`.
43pub(crate) fn c<L: Limbs>(a: &L, b: &(Choice, L), negative_discriminant_abs: &L) -> L {
44  let (mut b_lo, mut b_hi) = b.1.widening_square();
45
46  /*
47    `b^2 - 4ac = -|delta|`
48    `b^2 + |delta| = 4ac`
49
50    We simultaneously add `|delta|` and divide by four to obtain `ac`. Because `|delta|` is of size
51    at most the size of `b^2`, their sum is at most one bit bigger, while the simultaneous division
52    by `4` ensures the result is two bits smaller. Therefore, `(b^2 + |delta|) / 4` fits in the
53    container `b^2` fits in.
54  */
55  let mut carry = Limb::ZERO;
56  for i in 0 .. (b_lo.as_ref().len() + b_hi.as_ref().len()) {
57    let b_limb = if let Some(i) = i.checked_sub(b_lo.as_ref().len()) {
58      &mut b_hi.as_mut()[i]
59    } else {
60      &mut b_lo.as_mut()[i]
61    };
62
63    let new_limb;
64    (new_limb, carry) =
65      b_limb.carrying_add(*negative_discriminant_abs.as_ref().get(i).unwrap_or(&Limb::ZERO), carry);
66
67    // The lowest two bits should be assigned to the prior limb, as their highest two bits
68    let shift_down = new_limb << (Limb::BITS - 2);
69    *b_limb = new_limb >> 2;
70
71    if let Some(i) = i.checked_sub(1) {
72      let b_limb = if let Some(i) = i.checked_sub(b_lo.as_ref().len()) {
73        &mut b_hi.as_mut()[i]
74      } else {
75        &mut b_lo.as_mut()[i]
76      };
77      *b_limb |= shift_down;
78    }
79  }
80  // The `carry` becomes the highest two bits of the highest limb in `b`
81  *b_hi.as_mut().last_mut().unwrap() |= carry << (Limb::BITS - 2);
82  let ac = (b_lo, b_hi);
83
84  /*
85    As `b^2` is positive yet `delta < 0`, `4ac` must be non-zero. Therefore, `a` must be non-zero
86    if this is a valid form, making this division safe.
87
88    We also know `c < |delta|`, and will fit in the same container as `b_lo`  does, due to
89    requiring `b < 2a`. Substituting `b` for its bound `2a`, we have:
90    `(2a)^2 + |delta| = 4ac`
91    `(4a^2 + |delta|) / 4a = c`
92    `a + |delta| = c`
93    where the sum of `a + |delta|` is bound to fit in the container for `a`, which is of less than
94    or equal capacity to the container for `b.1` (itself of equal capacity to `b_lo, b_hi`).
95  */
96  L::wrapping_div(ac, a)
97}
class_groups/crypto_bigint/c.rs

class_groups/crypto_bigint/
c.rs
