qfb_reduced_forms, qfb_reduced_forms_large
#include <flint/qfb.h>Compute all reduced primitive positive definite forms of discriminant d < 0, allocate an array for them, store it in *forms and return their number, the class number 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 \not\equiv 0, 1 \pmod 4, and throws for d \ge 0.
qfb_reduced_forms loops over b and sieves the factorisations of (b^2 - d)/4 with the square roots of d modulo small primes; the forms are the factorisations into ac with |b| \le a \le c. It needs the primes up to about \sqrt{|d|} and calls qfb_reduced_forms_large when that would require too large a table. qfb_reduced_forms_large loops over a \le \sqrt{|d|/3} instead, with the square roots of d modulo 4a, and needs only the primes up to |d|^{1/4}. Both take O(|d|^{1/2 + o(1)}) time and memory.
Guides#
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-10-20).
@misc{flint-doc-qfb-qfb-reduced-forms,
author = {{The FLINT team}},
title = {{qfb\_reduced\_forms, qfb\_reduced\_forms\_large (qfb.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/qfb/qfb_reduced_forms.html},
note = {Generated 2026-10-20}
}