# qfb.h – binary quadratic forms

Authors:

- William Hart

- Håvard Damm-Johnsen (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.

void qfb_array_clear(qfb **forms, slong num)

  Clean up an array of `qfb` structs allocated by a qfb function. The parameter `num` must be set to the length of the array.

## Hash table

qfb_hash_t *qfb_hash_init(slong depth)

  Initialises a hash table of size \(2^{depth}\).

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 field `q` of the hash structure. Also store the second binary quadratic form `q2` (if not `NULL`) in the similarly named field and `iter` in the similarly named field of the hash structure.

slong qfb_hash_find(qfb_hash_t *qhash, qfb_t q, slong depth)

  Search for the given binary quadratic form or its inverse in the given hash table of size \(2^{depth}\). If it is found, return the index in the table (which is an array of `qfb_hash_t` structs), otherwise return `-1`.

## 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 to `qfb_array_clear` on `forms`, after use.) The function returns the number of forms generated (the form class number). The forms are stored in an array of `qfb` structs, which contain fields `a, 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 by `qfb_reduced_forms` for large \(|d|\) so that `flint_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_pow(qfb_t r, qfb_t f, fmpz_t D, fmpz_t exp)

  As per `qfb_pow_ui`.

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 of `B2_sqrt`. If the function fails to find the exponent it returns \(0\), otherwise the function returns \(1\) and `exponent` 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 that `iters` \(\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, where `iters` is the square root of `B2`.

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 of `B2_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\) and `exponent` 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, where `iters` is the square root of `B2`.

  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 bound `c` 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].