Module reduction 

A constant-time reduction algorithm.

This is derived from Algorithm 1 of https://eprint.iacr.org/2022-466. Some typos have been accounted for. Algorithm 2 is a restatement of Algorithm 1 in an iterative fashion and accordingly may of more approximate structure to the following, yet this work was independently derived from Algorithm 1.

In order to be efficient, this does not always operate over the full amount of limbs of each number. Instead, as the reduction occurs (and as the numbers shrink), the amount of limbs operated over also reduce. This requires extensively arguing the bounds for inputs and the outputs of each function. This is done via brief proofs written in comments within each function.

Traits

Limbs 🔒

A collection of limbs and associated helper methods.

Functions

a_lte_c 🔒

Obtain the equivalent form (a', b', c') for which a' <= c'.

approximate_a_lte_c 🔒

Obtain the equivalent form (a', b', c') for which floor(log_2(a')) <= floor(log_2(c')).

negate_b 🔒

Conditionally negate the b coefficient for a binary quadratic form of odd discriminant.

normalize 🔒

Normalize an almost-reduced element.

partial_reduce 🔒

Partially reduce a positive definite binary quadratic form.

reduce 🔒

Reduce an element.

reduce_to_next_bit 🔒

Reduce the b coefficient by at least one bit or until reduced.

reduce_to_upper_bound 🔒

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

should_reduce_to_next_bit_except_final 🔒

If reduce_to_next_bit should actually apply, except possibly incorrect.

should_reduce_to_next_bit_final 🔒

If reduce_to_next_bit should actually apply.