1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  quadratic_ideal.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the class quadratic_ideal
6%%
7%%  Copyright   (c)   1996   by  LiDIA-Group
8%%
9%%  Author:  Michael J. Jacobson, Jr., Markus Maurer
10%%
11
12%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13
14\NAME
15
16\CLASS{quadratic_ideal} \dotfill fractional ideals of quadratic orders
17
18
19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20
21\ABSTRACT
22
23\code{quadratic_ideal} is a class for representing and computing with fractional ideals of
24quadratic orders.  It supports basic operations like ideal multiplication as well as more
25complex operations such as computing the order of an equivalence class in the class group.
26
27%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
28
29\DESCRIPTION
30
31A \code{quadratic_ideal} is represented as an ordered triple $(q,a,b)$ ($a$ and $b$ are
32\code{bigint}, $q$ is \code{bigrational}) representing the $\bbfZ$-module $q [a\bbfZ + (b +
33\sqrt{\D})/ 2\, \bbfZ ]$.  In addition to $a$, $b$, and $q$, a pointer to the
34\code{quadratic_order} to which the ideal belongs is stored with each instance of
35\code{quadratic_ideal}.
36
37Let $I$ be a real quadratic ideal and $a\in I$.  We call $\alpha$ a minimum of $I$, if $\alpha >
380$ and there is no non-zero number $\beta\in I$ such that $|\beta| < |\alpha|$ and $|\sigma
39\beta| < |\sigma \alpha|$, where $\sigma$ denotes the conjugate map.  We call $I$ reduced, if
40$1$ is a minimum in $I$, which is equivalent to the fact that $\bigl|\sqrt{\D} - 2 |a|\bigr| < b
41< \sqrt{\D}$, i.e., the corresponding form $a,b,c$ is reduced, and $q = 1/a$.  Similarly, a
42imaginary quadratic ideal $I$ is called reduced, if $a \leq c$ and $b \geq 0$ if $a = c$ and $q
43= 1/a$.  Here, $c = (b^{2} - \D)/(4a)$.
44
45This class is meant to be used for general computations with quadratic ideals.  The classes
46\code{qi_class} and \code{qi_class_real} should be used for computations specific to quadratic
47ideal equivalence classes.
48
49
50%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
51
52\CONS
53
54\begin{fcode}{ct}{quadratic_ideal}{}
55  initializes with the zero ideal.
56\end{fcode}
57
58\begin{fcode}{ct}{quadratic_ideal}{const bigint & $a_2$, const bigint &
59    $b_2$, bigrational & $q_2$, quadratic_order & $\Or_2$ = last_order}%
60  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it,
61  otherwise $A$ is set to the zero ideal.  If $\Or_2$ is omitted, the most-recently accessed
62  \code{quadratic_order} will be used.
63\end{fcode}
64
65\begin{fcode}{ct}{quadratic_ideal}{const long $a_2$, const long $b_2$, bigrational & $q_2$,
66    quadratic_order & $\Or_2$ = last_order}%
67  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it,
68  otherwise $A$ is set to the zero ideal.  If $\Or_2$ is omitted, the most-recently accessed
69  \code{quadratic_order} will be used.
70\end{fcode}
71
72\begin{fcode}{ct}{quadratic_ideal}{const quadratic_form & $f$}
73  initializes with the positively oriented ideal associated with $f$.  If $f$ is not regular,
74  the \code{quadratic_ideal} will be initialized to zero.
75\end{fcode}
76
77\begin{fcode}{ct}{quadratic_ideal}{const qi_class & $A$}
78  initializes with the reduced ideal $A$.
79\end{fcode}
80
81\begin{fcode}{ct}{quadratic_ideal}{const qi_class_real & $A$}
82  initializes with the reduced ideal $A$.
83\end{fcode}
84
85\begin{fcode}{ct}{quadratic_ideal}{const quadratic_ideal & $A$}
86  initializes a copy of $A$.
87\end{fcode}
88
89\begin{fcode}{ct}{quadratic_ideal}{const quadratic_order & $O$}
90  initializes with the ideal $O$.
91\end{fcode}
92
93\begin{fcode}{dt}{~quadratic_ideal}{}
94\end{fcode}
95
96
97%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
98
99\ASGN
100
101Let $A$ be of type \code{quadratic_ideal}.  The operator \code{=} is overloaded.  For efficiency
102reasons, the following functions are also implemented.  Note that the parameter $\Or_2$ is
103optional.  If it is omitted, the new ideal will belong to the most recently accessed quadratic
104order.
105
106\begin{fcode}{void}{$A$.assign_zero}{quadratic_order & $\Or_2$ = last_order}
107  $A = (0)$, the zero ideal.
108\end{fcode}
109
110\begin{fcode}{void}{$A$.assign_one}{quadratic_order & $\Or_2$ = last_order}
111  $A = (1)$, the whole order.
112\end{fcode}
113
114\begin{fcode}{void}{$A$.assign_principal}{const bigint & $x$, const bigint & $y$,
115    quadratic_order & $\Or_2$ = last_order}%
116  sets $A$ to the principal ideal generated by $x + y (\D + \sqrt{\D}) / 2$, where $\D$ is the
117  discriminant of $\Or_2$.
118\end{fcode}
119
120\begin{fcode}{bool}{$A$.assign}{const bigint & $a_2$, const bigint & $b_2$,
121    const bigrational & $q_2$, quadratic_order & $\Or_2$ = last_order}%
122  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it
123  and \TRUE is returned.  Otherwise, $A$ will be set to zero and \FALSE is returned.
124\end{fcode}
125
126\begin{fcode}{bool}{$A$.assign}{const long $a_2$, const long $b_2$, const bigrational & $q_2$,
127    quadratic_order & $\Or_2$ = last_order}%
128  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it
129  and \TRUE is returned.  Otherwise, $A$ will be set to zero and \FALSE is returned.
130\end{fcode}
131
132\begin{fcode}{void}{$A$.assign}{const quadratic_form & $f$}
133  sets $A$ to the positively oriented ideal associated with $f$.  If $f$ is not regular, the
134  \LEH will be evoked.
135\end{fcode}
136
137\begin{fcode}{void}{$A$.assign}{const qi_class & $B$}
138  sets $A$ to the reduced ideal $B$.
139\end{fcode}
140
141\begin{fcode}{void}{$A$.assign}{const qi_class_real & $B$}
142  sets $A$ to the reduced ideal $B$.
143\end{fcode}
144
145\begin{fcode}{void}{$A$.assign}{const quadratic_ideal & $B$}
146  $A \assign B$.
147\end{fcode}
148
149\begin{fcode}{bool}{$A$.assign_order}{quadratic_order & $\Or_2$}
150  changes the quadratic order to which $A$ belongs.  If $A$ is not an ideal in $\Or_2$, nothing
151  is changed and false is returned.  Otherwise, true is returned.
152\end{fcode}
153
154\begin{fcode}{bool}{$A$.set_order}{quadratic_order & $\Or_2$}
155  changes the quadratic order to which $A$ belongs.  If $A$ is not an ideal in $\Or_2$, nothing
156  is changed and false is returned.  Otherwise, true is returned.
157\end{fcode}
158
159\begin{Tfcode}{void}{$A$.assign_module_of}{const bigrational & $nq$,
160    quadratic_number_standard $q_1$, quadratic_number_standard $q_2$}%
161    Initializes the coefficients of $A$ such that $q (\bbfZ a + \bbfZ
162    (b + \sqrt{\D})/2) = n q (\bbfZ q_1 + \bbfZ q_2)$ without assigning an order to $A$.
163\end{Tfcode}
164
165\begin{fcode}{bool}{$A$.assign}{const bigrational & $nq$,
166    const quadratic_number_standard & $q_1$,const quadratic_number_standard & $q_2$}%
167  If $q (\bbfZ q_1 + \bbfZ q_2)$ is a quadratic ideal, i.e., a $\bbfZ$ module of rank $2$, the
168  function returns true, and assigns the standard representation of the module to $A$.
169  Otherwise the function returns false, and initializes the ideal with the order.
170\end{fcode}
171
172
173%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
174
175\ACCS
176
177Let $A$ be of type \code{quadratic_ideal}.
178
179\begin{cfcode}{bigint}{$A$.get_a}{}
180  returns the coefficient $a$ in the representation $(q,a,b)$ of $A$.
181\end{cfcode}
182
183\begin{cfcode}{bigint}{$A$.get_b}{}
184  returns the coefficient $b$ in the representation $(q,a,b)$ of $A$.
185\end{cfcode}
186
187\begin{cfcode}{bigrational}{$A$.get_q}{}
188  returns the coefficient $q$ in the representation $(q,a,b)$ of $A$.
189\end{cfcode}
190
191\begin{cfcode}{bigint}{$A$.get_c}{}
192  returns the value $c = (b^2 - \D ) / (4a)$ corresponding to the representation $(q,a,b)$ of
193  $A$, where $\D$ is the discriminant of the quadratic order to which $A$ belongs.
194\end{cfcode}
195
196\begin{cfcode}{const quadratic_order &}{$A$.which_order}{}
197  returns a reference to the \code{quadratic_order} of which $A$ belongs.
198\end{cfcode}
199
200\begin{cfcode}{const quadratic_order &}{$A$.get_order}{}
201  returns a reference to the \code{quadratic_order} of which $A$ belongs.
202\end{cfcode}
203
204\begin{fcode}{const quadratic_order &}{which_order}{const quadratic_ideal & $A$}
205  returns a reference to the \code{quadratic_order} of which $A$ belongs.
206\end{fcode}
207
208\begin{cfcode}{bigint}{$A$.discriminant}{}
209  returns the discriminant of the quadratic order to which $A$ belongs.
210\end{cfcode}
211
212
213%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
214
215\ARTH
216
217Let $A$ be of type \code{quadratic_ideal}.  The following operators are overloaded and can be
218used in exactly the same way as in the programming language C++.
219\begin{center}
220  \code{(unary) -}\\
221  \code{(binary) +, *, /}\\
222  \code{(binary with assignment) *=,  /=}\\
223\end{center}
224\textbf{Note:} By $-A$ and $A^{-1}$ we denote the inverse of $A$ if it exists, by $A / B$ we
225denote $A \cdot B^{-1}$, and by $A + B$ the set $\{ a+b | a\in A, b\in B\}$.
226
227To avoid copying, these operations can also be performed by the following functions:
228
229\begin{fcode}{void}{add}{quadratic_ideal & $C$, const quadratic_ideal & $A$,
230    const quadratic_ideal & $B$}%
231  $C \assign A + B$ if $A$ and $B$ are of the same quadratic order; otherwise the \LEH will be evoked.
232\end{fcode}
233
234%\begin{fcode}{void}{intersect}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const quadratic_ideal & $B$}
235%       $C$ is set to the intersection of $A$ and $B$ if they
236%       are of the same quadratic order;
237%       otherwise the \LEH will be evoked.
238%\end{fcode}
239
240\begin{fcode}{void}{multiply}{quadratic_ideal & $C$, const quadratic_ideal & $A$,
241    const quadratic_ideal & $B$}%
242  $C \assign A \cdot B$.  If $A$ and $B$ do not belong to the same quadratic order, the \LEH will be
243  evoked.
244\end{fcode}
245
246\begin{fcode}{void}{multiply}{quadratic_ideal & $J$, const quadratic_ideal & $I$,
247    const quadratic_number_standard & $g$}%
248  $J \assign I \cdot (g \cdot O)$, where $O$ is the order of $I$ and $g$.
249\end{fcode}
250
251\begin{fcode}{void}{$A$.conjugate}{}
252  $A$ is set to the conjugate of $A$.
253\end{fcode}
254
255\begin{fcode}{void}{get_conjugate}{quadratic_ideal & $A$, const quadratic_ideal & $B$}
256  $A$ is set to the conjugate of $B$.
257\end{fcode}
258
259\begin{fcode}{quadratic_ideal}{get_conjugate}{quadratic_ideal & $A$}
260  returns the conjugate of $A$.
261\end{fcode}
262
263\begin{fcode}{void}{$A$.invert}{}
264  If $A$ is invertible, $A \assign A^{-1}$, otherwise $A$ is set to its conjugate.
265\end{fcode}
266
267\begin{fcode}{void}{inverse}{quadratic_ideal & $A$, const quadratic_ideal & $B$}
268  If $B$ is invertible, $A \assign B^{-1}$, otherwise $A$ is set to the conjugate of $B$.
269\end{fcode}
270
271\begin{fcode}{quadratic_ideal}{inverse}{quadratic_ideal & $A$}
272  If $A$ is invertible, $A^{-1}$ is returned, otherwise the conjugate of $A$ is returned.
273\end{fcode}
274
275\begin{fcode}{void}{divide}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const quadratic_ideal & $B$}
276  $C = A \cdot B^{-1}$.  If $A$ and $B$ are not of the same quadratic order or $B = (0)$, the
277  \LEH will be evoked.  If $B$ is not invertible, $C$ is set to the product of $A$ and the
278  conjugate of $B$.
279\end{fcode}
280
281\begin{fcode}{void}{divide}{quadratic_ideal & $J$, const quadratic_ideal & $I$,
282    const quadratic_number_standard & $g$}%
283  $J \assign I / (g \cdot O)$, where $O$ is the order of $I$ and $g$.
284\end{fcode}
285
286\begin{fcode}{void}{square}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
287  $C \assign A^2$.
288\end{fcode}
289
290\begin{fcode}{void}{power}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const bigint & $i$}
291  $C \assign A^i$.  If $i < 0$, $B^i$ is computed where $B = A^{-1}$ or the conjugate of $A$ if $A$ is
292  not invertible.
293\end{fcode}
294
295\begin{fcode}{void}{power}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const long $i$}
296  $C \assign A^i$.  If $i < 0$, $B^i$ is computed where $B = A^{-1}$ or the conjugate of $A$ if
297  $A$ is not invertible.
298\end{fcode}
299
300
301
302%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
303
304\COMP
305
306The binary operators \code{==}, \code{!=}, \code{<=}, \code{<} (true subset), \code{>=},
307\code{>} and the unary operator \code{!} (comparison with $(0)$) are overloaded and can be used
308in exactly the same way as in the programming language C++.  Let $A$ be an instance of type
309\code{quadratic_ideal}.
310
311\begin{cfcode}{bool}{$A$.is_zero}{}
312  returns \TRUE if $A = (0)$, \FALSE otherwise.
313\end{cfcode}
314
315\begin{cfcode}{bool}{$A$.is_one}{}
316  returns \TRUE if $A = (1)$, \FALSE otherwise.
317\end{cfcode}
318
319\begin{cfcode}{bool}{$A$.is_equal}{const quadratic_ideal & $B$}
320  returns \TRUE if $A$ and $B$ are equal, \FALSE otherwise.
321\end{cfcode}
322
323\begin{cfcode}{bool}{$A$.is_subset}{const quadratic_ideal & $B$}
324  returns \TRUE if $A$ is a subset of $B$, \FALSE otherwise.
325\end{cfcode}
326
327\begin{cfcode}{bool}{$A$.is_proper_subset}{const quadratic_ideal & $B$}
328  returns \TRUE if $A$ is a proper subset of $B$, \FALSE otherwise.
329\end{cfcode}
330
331
332%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
333
334\BASIC
335
336\begin{cfcode}{operator}{quadratic_form}{}
337  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{quadratic_form}.
338\end{cfcode}
339
340\begin{cfcode}{operator}{qi_class}{}
341  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{qi_class}.  The
342  current order of \code{qi_class} will be set to the order of the ideal.
343\end{cfcode}
344
345\begin{cfcode}{operator}{qi_class_real}{}
346  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{qi_class_real}.
347  The current order of \code{qi_class} and \code{qi_class_real} will be set to the order of the
348  ideal.
349\end{cfcode}
350
351\begin{fcode}{void}{swap}{quadratic_ideal & $A$, quadratic_ideal & $B$}
352  exchanges the values of $A$ and $B$.
353\end{fcode}
354
355
356%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
357
358\HIGH
359
360Let $A$ be of type \code{quadratic_ideal}.
361
362\begin{cfcode}{bigrational}{$A$.smallest_rational}{}
363  returns the smallest rational number in $A$.  This is simply the value of $qa$, where $q$ and
364  $a$ are coefficients in the representation of $A$.
365\end{cfcode}
366
367\begin{cfcode}{bigint}{$A$.denominator}{}
368  returns the smallest positive integer $d$ such that $d \cdot A$ is integral. This is simply
369  the denominator of $q$, where $q$ is the coefficient of the representation of $A$.
370\end{cfcode}
371
372\begin{cfcode}{bigint}{$A$.multiply_by_denominator}{}
373  multiplies $A$ by its denominator $d$, where $d$ is the smallest positive integer $d$ such
374  that $d \cdot A$ is integral.
375\end{cfcode}
376
377\begin{cfcode}{bool}{$A$.is_integral}{}
378  returns \TRUE if $A$ is an integral ideal, \FALSE otherwise.
379\end{cfcode}
380
381\begin{cfcode}{bigint}{$A$.conductor}{}
382  returns the conductor of $A$.
383\end{cfcode}
384
385\begin{cfcode}{bool}{$A$.is_invertible}{}
386  returns \TRUE if $A$ is invertible, \FALSE otherwise.
387\end{cfcode}
388
389\begin{cfcode}{bigrational}{$A$.norm}{}
390  returns the norm of $A$.
391\end{cfcode}
392
393\begin{fcode}{quadratic_order}{$A$.ring_of_multipliers}{}
394  returns the ring of multipliers of $A$.
395\end{fcode}
396
397\begin{fcode}{bool}{generate_prime_ideal}{quadratic_ideal A, const bigint & $p$,
398    quadratic_order & $\Or_2$ = last_order}%
399  attempts to set $A$ to the prime ideal lying over the prime $p$.  If successful (the Kronecker
400  symbol $\kronecker{\D}{p} \neq -1$), \TRUE is returned, otherwise \FALSE is returned.  Note
401  that the parameter $\Or_2$ is optional.  If it is omitted, the new ideal will belong to the
402  most recently accessed quadratic order.
403\end{fcode}
404
405
406%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
407
408\SSTITLE{Reduction}
409
410For the reduction operator functions, if $A$ is reduced and belongs to an imaginary quadratic
411order, it will not be modified.
412
413\begin{cfcode}{bool}{$A$.is_reduced}{}
414  returns \TRUE if $A$ is reduced, \FALSE otherwise.
415\end{cfcode}
416
417\begin{fcode}{void}{$A$.reduce}{}
418  reduces $A$.
419\end{fcode}
420
421\begin{fcode}{void}{$A$.reduce}{quadratic_number_standard & $g$}
422  computes $g$ such that $A / g$ is reduced and assigns $A \assign A/g$.
423\end{fcode}
424
425\begin{fcode}{void}{$A$.rho}{}
426  applies the reduction operator $\rho$ once to $A$.
427\end{fcode}
428
429\begin{fcode}{void}{$A$.rho}{quadratic_number_standard & $g$}
430  computes $g$ sucht that $\rho(A) = A / g$ and assigns $A \assign A / g$.
431\end{fcode}
432
433\begin{fcode}{void}{apply_rho}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
434  sets $C$ to the result of the reduction operator $\rho$ being applied once to $A$.
435\end{fcode}
436
437\begin{fcode}{qi_class}{apply_rho}{quadratic_ideal & $A$}
438  returns a \code{qi_class} corresponding to the result of the reduction operator $\rho$ being
439  applied once to $A$.
440\end{fcode}
441
442\begin{fcode}{void}{$A$.inverse_rho}{}
443  applies the inverse reduction operator once to $A$.
444\end{fcode}
445
446\begin{fcode}{void}{$A$.inverse_rho}{quadratic_number_standard & $g$}
447  computes $g$ sucht that $\rho^{-1}(A) = A / g$ and assigns $A \assign A / g$.
448\end{fcode}
449
450\begin{fcode}{void}{apply_inverse_rho}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
451  sets $C$ to the result of the inverse reduction operator $\rho^{-1}$ being applied once to $A$.
452\end{fcode}
453
454\begin{fcode}{qi_class}{apply_inverse_rho}{quadratic_ideal & $A$}
455  returns a \code{qi_class} corresponding to the result of the inverse reduction operator
456  $\rho^{-1}$ being applied once to $A$.
457\end{fcode}
458
459
460
461%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
462
463\SSTITLE{Prescribed logarithm}
464
465Let $\Ln$ denote the Lenstra logarithm: $\Ln(x) = 1/2 \ln|x / \sigma(x)|$.
466
467\begin{fcode}{void}{$A$.local_close}{quadratic_number_standard & $\alpha$, xbigfloat & $a$,
468    xbigfloat $t$, long $k$}%
469  The function transforms $A$ into a reduced ideal $B = A / \alpha$, where $\alpha$ is a minimum
470  in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| + 2^{-k+1}$ for any minimum $\beta$ in $A$.
471  It also computes an absolute $k$-approximation $a$ to $\Ln(\alpha)$.  The function uses
472  reduction, $\rho$, and inverse $\rho$ operations to determine $B$.  If $A$ is not a real
473  quadratic ideal, the \LEH is called.
474\end{fcode}
475
476\begin{fcode}{void}{$A$.order_close}{quadratic_number_power_product & $\alpha$, xbigfloat & $a$,
477    xbigfloat $t$, long $k$}%
478  If $A$ is a real quadratic order, the function transforms $A$ into a reduced ideal $B = A /
479  \alpha$, where $\alpha$ is a minimum in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| +
480  2^{-k+1}$ for any minimum $\beta$ in $A$.  It also computes an absolute $k$-approximation $a$
481  to $\Ln(\alpha)$.  The function uses repeated squaring to determine $B$.  If $A$ is not a real
482  quadratic order, the \LEH is called.
483\end{fcode}
484
485\begin{fcode}{void}{$A$.close}{quadratic_number_power_product & $\alpha$ xbigfloat & $a$,
486    xbigfloat $t$, long $k$}%
487  The function transforms $A$ into a reduced ideal $B = A / \alpha$, where $\alpha$ is a minimum
488  in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| + 2^{-k+1}$ for any minimum $\beta$ in $A$.
489  It also computes an absolute $k$-approximation $a$ to $\Ln(\alpha)$.  The function uses
490  \code{order_close} and \code{local_close} to determine $B$.  If $A$ is not a real quadratic
491  ideal, the \LEH is called.
492\end{fcode}
493
494
495%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
496
497\SSTITLE{Equivalence and principality testing}
498
499\begin{cfcode}{bool}{$A$.is_equivalent}{const quadratic_ideal & $B$}
500  returns \TRUE if $A$ and $B$ are in the same ideal equivalence class, \FALSE otherwise.
501\end{cfcode}
502
503\begin{cfcode}{bool}{$A$.is_principal}{}
504  returns \TRUE if $A$ is principal, \FALSE otherwise.
505\end{cfcode}
506
507
508%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
509
510\SSTITLE{Orders, discrete logarithms, and subgroup structures}
511
512\begin{fcode}{bigint}{$A$.order_in_CL}{}
513  returns the order of $A$ in the ideal class group of its quadratic order, i.e. the least
514  positive integer $x$ such that $A^x$ is equivalent to $(1)$.  It uses the \code{qi_class}
515  function of the same name.  If $A$ is not invertible, $0$ is returned.
516\end{fcode}
517
518\begin{cfcode}{bool}{$A$.DL}{const quadratic_ideal & $G$, bigint & $x$}
519  returns \TRUE if $A$ belongs to the cyclic subgroup generated by $G$, \FALSE otherwise.  If
520  so, $x$ is set to the discrete logarithm of $A$ to the base $G$, i.e., the least non-negative
521  integer $x$ such that $G^x$ is equivalent to $A$.  If not, $x$ is set to the order of $G$.
522  The function uses the \code{qi_class} function of the same name.  If either $A$ or $G$ is not
523  invertible, \FALSE is returned and $x$ is set to $0$.
524\end{cfcode}
525
526\begin{fcode}{base_vector< bigint >}{subgroup}{base_vector< quadratic_ideal > & $G$}
527  returns the vector of elementary divisors representing the structure of the subgroup generated
528  by the classes corresponding to the invertible ideals contained in $G$.  The function uses the
529  \code{qi_class} function of the same name.
530\end{fcode}
531
532\begin{fcode}{bigfloat}{$A$.regulator}{}
533  returns an approximation of the regulator of the quadratic order to which $A$ belongs.  If $A$
534  belongs to an imaginary quadratic order, $1$ is returned.
535\end{fcode}
536
537\begin{fcode}{bigint}{$A$.class_number}{}
538  returns the order of the ideal class group of the quadratic order to which $A$ belongs.
539\end{fcode}
540
541\begin{fcode}{base_vector< bigint >}{$A$.class_group}{}
542  returns the vector of elementary divisors representing the structure of the ideal class group
543  of the quadratic order to which $A$ belongs.
544\end{fcode}
545
546
547%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
548
549\IO
550
551Let $A$ be of type \code{quadratic_ideal}.  The \code{istream} operator \code{>>} and the
552\code{ostream} operator \code{<<} are overloaded.  The input of a \code{quadratic_ideal}
553consists of \code{(q a b)}, where $q$ is a \code{bigrational} and $a$ and $b$ are integers
554corresponding to the representation $A = q [ a \bbfZ + (b + \sqrt{\D})/2 \, \bbfZ ]$.  The ideal
555is assumed to belong to the most recently accessed quadratic order.  The output has the format
556$((q),a,b)$.
557
558
559%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
560
561\SEEALSO
562
563\SEE{quadratic_order},
564\SEE{qi_class},
565\SEE{qi_class_real},
566\SEE{quadratic_form}
567
568
569%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
570
571%\NOTES
572
573
574%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
575
576\EXAMPLES
577
578\begin{quote}
579\begin{verbatim}
580#include <LiDIA/quadratic_order.h>
581#include <LiDIA/quadratic_ideal.h>
582
583int main()
584{
585    quadratic_order QO;
586    quadratic_ideal A, B, C;
587    bigint D, p, x;
588
589    do {
590        cout << "Please enter a quadratic discriminant: "; cin >> D;
591    } while (!QO.assign(D));
592    cout << endl;
593
594    /* compute 2 prime ideals */
595    p = 3;
596    while (!generate_prime_ideal(A,p,QO))
597        p = next_prime(p);
598    p = next_prime(p);
599    while (!generate_prime_ideal(B,p,QO))
600        p = next_prime(p);
601
602    cout << "A = " << A << endl;
603    cout << "B = " << B << endl;
604
605    power(C,B,3);
606    C *= -A;
607    square(C, C);
608    cout << "C = (A^-1*B^3)^2 = " << C << endl;
609
610    cout << "|<C>| = " << C.order_in_CL() << endl;
611
612    C.reduce();
613    cout << "C reduced = " << C << endl;
614
615    cout << "ring of multipliers of C:\n";
616    cout << C.ring_of_multipliers() << endl;
617
618    if (A.DL(B, x))
619        cout << "log_B A = " << x << endl << flush;
620    else
621        cout << "no discrete log:  |<B>| = " << x << endl << flush;
622
623    return 0
624}
625\end{verbatim}
626\end{quote}
627
628Example:
629\begin{quote}
630\begin{verbatim}
631Please enter a quadratic discriminant: -82636319
632
633A = ((1), 3, 1)
634B = ((1), 5, 1)
635C = (A^-1*B^3)^2 = ((1/9), 140625, 103541)
636|<C>| = 20299
637C reduced = ((1), 2856, -271)
638ring of multipliers of C:
639Quadratic Order:
640   Delta = -82636319 (8)
641
642log_B A = 17219
643\end{verbatim}
644\end{quote}
645
646For further examples please refer to
647\path{LiDIA/src/packages/quadratic_order/quadratic_ideal_appl.cc}.
648
649
650%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
651
652\AUTHOR
653
654Michael J.~Jacobson, Jr.
655