qfb.h

Initialise q (to (0, 0, 0)) and free its memory.

Clears the first num forms of the array *forms and frees the array, as allocated by qfb_reduced_forms.

Sets f to a copy of g.

Returns 1 if f and g have the same coefficients, otherwise 0. For reduced forms this tests equivalence.

Prints q as (a, b, c).

Sets D to the discriminant b^2 - 4ac of f = (a, b, c).

Returns 1 if \gcd(a, b, c) = 1, otherwise 0.

Sets r to the reduced form equivalent to the positive definite form f, whose discriminant must be D (used to recompute c). Aliasing is allowed.

Returns 1 if the positive definite form r is reduced, otherwise 0.

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.

Sets f to the principal form of discriminant D, (1, 0, -D/4) for D \equiv 0 \pmod 4 and (1, 1, (1 - D)/4) for D \equiv 1 \pmod 4.

Returns 1 if f is the reduced principal form of discriminant D (the identity of the class group, for reduced f), otherwise 0.

Sets r to the reduced inverse of the reduced form f: (a, -b, c), or f itself if a = b or a = c (such forms have order at most 2).

Sets r to a form (p, b, c) of discriminant D with 0 \le b \le p, for a prime p such that D is a square modulo 4p (that is, p splits or ramifies). The result is not specified otherwise. If p^2 \mid D the form may be imprimitive.

Sets r to a form in the class of the composition of f and g, both of discriminant D, by Shanks' NUCOMP algorithm in the version of Jacobson and van der Poorten [JvdP2002], with a partial Lehmer extended GCD (fmpz_xgcd_partial). The parameter must be L = \lfloor |D|^{1/4} \rfloor. The result is nearly reduced (its coefficients are of the size of \sqrt{|D|}) but must be passed to qfb_reduce to obtain the reduced form. f must be primitive.

As qfb_nucomp for the composition of f with itself (NUDUPL), which needs fewer operations. f must be primitive.

Set r to the reduced form in the class of f^{\mathit{exp}}, by binary powering with NUDUPL and NUCOMP and a reduction after each step. D must be the discriminant of f, which must be primitive. For exponent 0 the result is the principal form and for exponent 1 a copy of f (not reduced if f is not). qfb_pow_with_root takes L = \lfloor |D|^{1/4} \rfloor as an argument instead of computing it. A negative fmpz_t exponent is allowed: the result is then the power -\mathit{exp} of the inverse form (qfb_inverse).

Tries to find the order of the class of the reduced primitive form f in the class group of discriminant n. Returns 1 and sets exponent to the order on success, and returns 0 if the order is not of the form s \cdot q with s a product of prime powers below about B1 and q a prime below about B2_sqrt squared.

Tries to compute the exponent of the class group of discriminant n < 0, the least common multiple of the orders of its elements, as the least common multiple of the orders of prime forms for small primes. Returns 1 and sets exponent on success, and 0 if qfb_exponent_element fails. The parameter c controls the number of prime forms tried; the result is the exponent with high probability (heuristically, at least 1 - 2^{-c}), but it is not proved. The bounds B1 and B2_sqrt are as for qfb_exponent_element.

As qfb_exponent, but uses the prime forms of all primes p < 6 \log^2 |n| that split or ramify. Assuming the generalised Riemann hypothesis, these generate the class group [Bach1990], [BD1992], so the result is the exponent of the class group if the function returns 1.

Allocate a table of 2^{\mathit{depth}} empty entries (with q->a zero) and free it.

Stores q, q2 (unless it is NULL) and iter in the first free entry at or after the position given by the hash of q. An exception is raised if the table is full.

Returns the index of an entry containing q or its inverse (the same a and |b|), or -1 if there is none (also when the table is full and does not contain it).