Skip to main content

reduce_to_upper_bound

Function reduce_to_upper_bound 

Source
pub(crate) fn reduce_to_upper_bound<L: Limbs>(
    log_2_bound: u32,
    a: L,
    b: (Choice, L),
    c: L,
    upper_bound: u32,
) -> (L, (Choice, L), L)
Expand description

Reduce an element until either its reduced or $|b| < 2^{upper_bound}$.

For a positive definite binary quadratic form (a, b, c) such that:

  • b^2 - 4ac = delta where delta < 0 (the form is well-defined for a negative discriminant)
  • $delta \cong 1 \mod 2$
  • 0 <= a, c (a, c aren’t negative, as enforced by the type system)
  • floor(log_2(a)) + 1 <= log_2_bound
  • floor(log_2(|b|)) + 1 <= log_2_bound
  • ceil(log_2_bound / Limb::BITS) <= <L as AsRef::<[Limb]>>::as_ref(&a).len()
  • <L as AsRef::<[Limb]>>::as_ref(&a).len() <= <L as AsRef::<[Limb]>>::as_ref(&b.1).len()
  • <L as AsRef::<[Limb]>>::as_ref(&a).len() == <L as AsRef::<[Limb]>>::as_ref(&c).len()

Yield an equivalent form (a', b', c') such that:

  • (a', b', c') is reduced or $|b| < 2^{upper_bound}$.
  • (a', b', c') is reduced or b' > a'

b.0, b'.0 are true if the value is positive.