pub(crate) fn partial_reduce<L: Limbs + Limbs>(
log_2_bound: u32,
a: L,
b: (Choice, L),
negative_discriminant_abs: &L,
) -> (L, (Choice, L), L)Expand description
Partially reduce a positive definite binary quadratic form.
For a positive definite binary quadratic form (a, b, c) such that:
b^2 - 4ac = deltawheredelta < 0(the form is well-defined for a negative discriminant)- $delta \cong 1 \mod 2$
0 <= a(aisn’t negative, as enforced by the type system)floor(log_2(a)) + 1 <= log_2_boundfloor(log_2(|b|)) + 1 <= log_2_bound- There is an integer solution for
cinb^2 - 4 a c = delta. 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(&negative_discriminant_abs).len() <= 2 * <L as AsRef::<[Limb]>>::as_ref(&b.1).len()- $floor(log_2(|delta|)) + 1 < <_ as AsRef<Limb>>::as_ref(a).len() * Limb::BITS$
- $floor(log_2(a)) + 1 < <_ as AsRef<Limb>>::as_ref(a).len() * Limb::BITS$
Yield an equivalent form (a', b', c') such that:
b'^2 <= |delta|(a', b', c')is reduced orb' > a'gcd(a, b, c) = gcd(a', b', c')
As composition is presumably programmed to compose b-bit-length numbers, where composition
outputs 2 * b-bit-length numbers, this function intends to solely perform the necessary
reduction such that the numbers are once again of b-bit-length (and able to be composed
again). While these forms are not reduced, they may still usable for composition without
performing a full reduction (which would take roughly twice as long). This allows deferring a
full reduction until one needs a reduced form.
This second bound on the output, (a', b', c') is reduced or b' > a', is critical as it
enables the following corollary: a'^2 < |delta|.
b.0, b'.0 are true if the value is positive.
delta is bound to be negative and specified via its absolute value in
negative_discriminant_abs.