Expand description
Composition of binary quadratic forms in constant time.
This is generic to the underlying container representing the numbers, allowing usage with both
allocating and non-allocating backends. However, the module as a whole is in a weird place.
Specifically, it optimizes some functions, and leverages incompleteness elsewhere (tailored to
the specific special cases encountered during reduction), but the optimized functions are not
a majority of the runtime (or even a notable part). Instead, the GCD, divisions are, and those
are completely deferred. Additionally, despite being generic to the underlying containers and
not explicitly allocating, this code does make frequent use of clone (presumably copies for
elements represented on the stack) due to requiring a non-trivial amount of scratch variables.
The important aspect of this code is that it’s clearly bounded as necessary to verify the correctness of the implemented algortithm. Despite this, the implemented algorithm is not itself proven here, it being Algorithm 5.4.7 Composition of Positive Definite Forms from A Course in Computational Algebraic Number Theory by Henri Cohen (as commonly implemented in its optimized variant as “NUCOMP”). Per a remark, and also Chapter 5, Exercise 9, the composite of two primitive forms is itself primitive.
Structs§
- Xgcd 🔒
- The result of an extended GCD algorithm.
Traits§
- Limb
Helpers 🔒 - Limbs 🔒
- The required view over a collection of limbs to calculate the
ccoefficient. - Wide
Limbs 🔒
Functions§
- add 🔒
- Compose two positive definite binary quadratic forms.
- diff_
assign 🔒 - Calculate the difference of two signed integers.
- double 🔒
- Compose a positive definite binary quadratic form with itself.
- sum_
assign_ 🔒half_ of_ two_ numbers_ congruent_ mod_ two - Calculate half the sum of two signed integers which are congruent modulo two.