1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
.. _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 implemented 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]_.
|
