.. _qfb: **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 inplemented and described below. Currently the code only works for definite binary quadratic forms. Memory management ---------------------------------------------------------------------------------------- .. function:: void qfb_init(qfb_t q) Initialise a ``qfb_t`` `q` for use. .. function:: void qfb_clear(qfb_t q) Clear a ``qfb_t`` after use. This releases any memory allocated for `q` back to flint. .. function:: 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 ---------------------------------------------------------------------------------------- .. function:: qfb_hash_t * qfb_hash_init(slong depth) Initialises a hash table of size `2^{depth}`. .. function:: void qfb_hash_clear(qfb_hash_t * qhash, slong depth) Frees all memory used by a hash table of size `2^{depth}`. .. function:: 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. .. function:: 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 ---------------------------------------------------------------------------------------- .. function:: void qfb_set(qfb_t f, qfb_t g) Set the binary quadratic form `f` to be equal to `g`. Comparison ---------------------------------------------------------------------------------------- .. function:: 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 ---------------------------------------------------------------------------------------- .. function:: 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 ---------------------------------------------------------------------------------------- .. function:: 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)`. .. function:: 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`. .. function:: 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`. .. function:: 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)`. .. function:: 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. .. function:: 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. .. function:: 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. .. function:: 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. .. function:: void qfb_pow(qfb_t r, qfb_t f, fmpz_t D, fmpz_t exp) As per ``qfb_pow_ui``. .. function:: void qfb_inverse(qfb_t r, qfb_t f) Set `r` to the inverse of the binary quadratic form `f`. .. function:: 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`. .. function:: 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. .. function:: 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`. .. function:: 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. .. function:: 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``. .. function:: 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]_. .. function:: 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]_.