qfb.h – binary quadratic forms¶
Authors:
William Hart
Håvard DammJohnsen (updated documentation)
Introduction¶
This module contains functionality for creating, listing and reducing binary quadratic forms. A qfb
struct consists of three fmpz_t
s, \(a\), \(b\) and \(c\), and basic algorithms for operations such as reduction, composition and enumerating are implemented and described below.
Currently the code only works for definite binary quadratic forms.
Memory management¶

void qfb_init(qfb_t q)¶
Initialise a
qfb_t
\(q\) for use.

void qfb_clear(qfb_t q)¶
Clear a
qfb_t
after use. This releases any memory allocated for \(q\) back to flint.
Hash table¶

void qfb_hash_clear(qfb_hash_t *qhash, slong depth)¶
Frees all memory used by a hash table of size \(2^{depth}\).

void qfb_hash_insert(qfb_hash_t *qhash, qfb_t q, qfb_t q2, slong iter, slong depth)¶
Insert the binary quadratic form
q
into the given hash table of size \(2^{depth}\) in the fieldq
of the hash structure. Also store the second binary quadratic formq2
(if notNULL
) in the similarly named field anditer
in the similarly named field of the hash structure.
Basic manipulation¶

void qfb_set(qfb_t f, qfb_t g)¶
Set the binary quadratic form \(f\) to be equal to \(g\).
Comparison¶

int qfb_equal(qfb_t f, qfb_t g)¶
Returns \(1\) if \(f\) and \(g\) are identical binary quadratic forms, otherwise returns \(0\).
Input/output¶

void qfb_print(qfb_t q)¶
Print a binary quadratic form \(q\) in the format \((a, b, c)\) where \(a\), \(b\), \(c\) are the entries of \(q\).
Computing with forms¶

void qfb_discriminant(fmpz_t D, qfb_t f)¶
Set \(D\) to the discriminant of the binary quadratic form \(f\), i.e. to \(b^2  4ac\), where \(f = (a, b, c)\).

void qfb_reduce(qfb_t r, qfb_t f, fmpz_t D)¶
Set \(r\) to a reduced form equivalent to the binary quadratic form \(f\) of discriminant \(D\).

int qfb_is_reduced(qfb_t r)¶
Returns \(1\) if \(q\) is a reduced binary quadratic form, otherwise returns \(0\). Note that this only tests for definite quadratic forms, so a form \(r = (a,b,c)\) is reduced if and only if \(b \le a \le c\) and if either inequality is an equality, then \(b \ge 0\).

slong qfb_reduced_forms(qfb **forms, slong d)¶
Given a discriminant \(d\) (negative for negative definite forms), compute all the reduced binary quadratic forms of that discriminant. The function allocates space for these and returns it in the variable
forms
(the user is responsible for cleaning this up by a single call toqfb_array_clear
onforms
, after use.) The function returns the number of forms generated (the form class number). The forms are stored in an array ofqfb
structs, which contain fieldsa, b, c
corresponding to forms \((a, b, c)\).

slong qfb_reduced_forms_large(qfb **forms, slong d)¶
As for
qfb_reduced_forms
. However, for small \(d\) it requires fewer primes to be computed at a small cost in speed. It is called automatically byqfb_reduced_forms
for large \(d\) so thatflint_primes
is not exhausted.

void qfb_nucomp(qfb_t r, const qfb_t f, const qfb_t g, fmpz_t D, fmpz_t L)¶
Shanks’ NUCOMP as described in [JvdP2002].
Computes the near reduced composition of forms \(f\) and \(g\) given \(L = \lfloor D^{1/4} \rfloor\) where \(D\) is the common discriminant of \(f\) and \(g\). The result is returned in \(r\).
We require that \(f\) is a primitive form.

void qfb_nudupl(qfb_t r, const qfb_t f, fmpz_t D, fmpz_t L)¶
As for
nucomp
except that the form \(f\) is composed with itself. We require that \(f\) is a primitive form.

void qfb_pow_ui(qfb_t r, qfb_t f, fmpz_t D, ulong exp)¶
Compute the near reduced form \(r\) which is the result of composing the principal form (identity) with \(f\)
exp
times.We require \(D\) to be set to the discriminant of \(f\) and that \(f\) is a primitive form.

void qfb_inverse(qfb_t r, qfb_t f)¶
Set \(r\) to the inverse of the binary quadratic form \(f\).

int qfb_is_principal_form(qfb_t f, fmpz_t D)¶
Return \(1\) if \(f\) is the reduced principal form of discriminant \(D\), i.e. the identity in the form class group, else \(0\).

void qfb_principal_form(qfb_t f, fmpz_t D)¶
Set \(f\) to the principal form of discriminant \(D\), i.e. the identity in the form class group.

int qfb_is_primitive(qfb_t f)¶
Return \(1\) if \(f\) is primitive, i.e. the greatest common divisor of its three coefficients is \(1\). Otherwise the function returns \(0\).

void qfb_prime_form(qfb_t r, fmpz_t D, fmpz_t p)¶
Sets \(r\) to the unique prime \((p, b, c)\) of discriminant \(D\), i.e. with \(0 < b \leq p\). We require that \(p\) is a prime.

int qfb_exponent_element(fmpz_t exponent, qfb_t f, fmpz_t n, ulong B1, ulong B2_sqrt)¶
Find the exponent of the element \(f\) in the form class group of forms of discriminant \(n\), doing a stage \(1\) with primes up to at least
B1
and a stage \(2\) for a single large prime up to at least the square ofB2_sqrt
. If the function fails to find the exponent it returns \(0\), otherwise the function returns \(1\) andexponent
is set to the exponent of \(f\), i.e. the minimum power of \(f\) which gives the identity.It is assumed that the form \(f\) is reduced. We require that
iters
is a power of \(2\) and thatiters
\(\ge 1024\).The function performs a stage \(2\) which stores up to \(4\times\)
iters
binary quadratic forms, and \(12\times\)iters
additional limbs of data in a hash table, whereiters
is the square root ofB2
.

int qfb_exponent(fmpz_t exponent, fmpz_t n, ulong B1, ulong B2_sqrt, slong c)¶
Compute the exponent of the class group of discriminant \(n\), doing a stage \(1\) with primes up to at least
B1
and a stage \(2\) for a single large prime up to at least the square ofB2_sqrt
, and with probability at least \(1  2^{c}\). If the prime limits are exhausted without finding the exponent, the function returns \(0\), otherwise it returns \(1\) andexponent
is set to the computed exponent, i.e. the minimum power to which every element of the class group has to be raised in order to get the identity.The function performs a stage \(2\) which stores up to \(4\times\)
iters
binary quadratic forms, and \(12\times\)iters
additional limbs of data in a hash table, whereiters
is the square root ofB2
.We use algorithm 8.1 of [Sut2007].

int qfb_exponent_grh(fmpz_t exponent, fmpz_t n, ulong B1, ulong B2_sqrt)¶
Similar to
qfb_exponent
except that the boundc
is automatically generated such that the exponent is guaranteed to be correct, if found, assuming the GRH, namely that the class group is generated by primes less than \(6\log^2(n)\) as described in [BD1992].