FLINT3.7.0-dev
/

qfb_reduced_forms, qfb_reduced_forms_large

Synopsis#include <flint/qfb.h>
slong qfb_reduced_forms(qfb ** forms, slong d)source
slong qfb_reduced_forms_large(qfb ** forms, slong d)source

Compute all reduced primitive positive definite forms of discriminant d<0d < 0, allocate an array for them, store it in *forms and return their number, the class number h(d)h(d). The forms are in no particular order. The array must be freed with qfb_array_clear(forms, num). Returns 0 (with *forms set to NULL) if d≢0,1(mod4)d \not\equiv 0, 1 \pmod 4, and throws for d≥0d \ge 0.

qfb_reduced_forms loops over bb and sieves the factorisations of (b2−d)/4(b^2 - d)/4 with the square roots of dd modulo small primes; the forms are the factorisations into acac with ∣b∣≤a≤c|b| \le a \le c. It needs the primes up to about ∣d∣\sqrt{|d|} and calls qfb_reduced_forms_large when that would require too large a table. qfb_reduced_forms_large loops over a≤∣d∣/3a \le \sqrt{|d|/3} instead, with the square roots of dd modulo 4a4a, and needs only the primes up to ∣d∣1/4|d|^{1/4}. Both take O(∣d∣1/2+o(1))O(|d|^{1/2 + o(1)}) time and memory.

Guides#

Cite this page

The FLINT team, “qfb_reduced_forms, qfb_reduced_forms_large (qfb.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/qfb/qfb_reduced_forms.html (generated 2026-11-02).