1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  quadratic_number_power_product.tex        LiDIA documentation
4%%
5%%  This file contains the documentation of the class
6%%  quadratic_number_power_product.
7%%
8%%  Copyright (c) 1999 by the LiDIA Group
9%%
10%%  Author: Markus Maurer
11%%
12
13\newcommand{\num}{\mathit{num}}
14\newcommand{\den}{\mathit{den}}
15
16
17%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
18
19\NAME
20
21\CLASS{quadratic_number_power_product} \dotfill power products of quadratic numbers.
22
23
24%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25
26\ABSTRACT
27
28\code{quadratic_number_power_product} is a class that represents power products of quadratic
29numbers.  It uses the class \SEE{quadratic_number_power_product_basis} to represent the basis of
30the power product and a vector of \SEE{bigint} to represent the exponents.
31
32
33%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34
35\DESCRIPTION
36
37A \code{quadratic_number_power_product} is a pair $p = (b,e)$, where $b$ is of type
38\SEE{quadratic_number_power_product_basis} and $e$ is of type \SEE{math_vector} over
39\SEE{bigint}.  Let $b = (b_{0}, \dots, b_{n-1})$ and $e = (e_{0}, \dots, e_{n-1})$.  Then the
40pair $p$ represents the power product
41\begin{displaymath}
42  p = \prod_{i=0}^{n-1} b_{i}^{e_{i}} \enspace.
43\end{displaymath}
44The class manages a list of elements of type \SEE{quadratic_number_power_product_basis}.  When a
45power product is the result of an operation, then the basis object for the result is the same as
46that for the operands and only a reference is copied.  This applies for all operations on power
47products, unless stated otherwise.
48
49
50%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
51
52\CONS
53
54\begin{fcode}{ct}{quadratic_number_power_product}{}
55  creates a power product with no elements.
56\end{fcode}
57
58\begin{fcode}{ct}{quadratic_number_power_product}{const quadratic_number_power_product & $q$}
59  initializes with $q$.
60\end{fcode}
61
62\begin{fcode}{dt}{~quadratic_number_power_product}{}
63  deletes the object.
64\end{fcode}
65
66
67%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
68
69\ASGN
70
71Let $p$ be of type \code{quadratic_number_power_product}.  The operator \code{=} is overloaded
72for \SEE{quadratic_number_power_product} and \SEE{quadratic_number_standard}.  The following
73functions are also implemented:
74
75\begin{fcode}{void}{$p$.set_basis}{const quadratic_number_power_product_basis & $x$}
76  Assigns a copy of $x$ to the basis of $p$ and leaves the exponent vector unchanged.
77\end{fcode}
78
79\begin{fcode}{void}{$p$.set_basis}{const quadratic_number_power_product & $x$}
80  Assigns the basis of $x$ to the basis of $p$.
81\end{fcode}
82
83\begin{fcode}{void}{$p$.set_exponents}{const base_vector< exp_type > & $e$}
84  Assigns $e$ to the exponent vector of $p$.
85\end{fcode}
86
87\begin{fcode}{void}{$p$.reset}{}
88  Deletes the basis and the exponent vector of $p$.
89\end{fcode}
90
91\begin{fcode}{void}{$p$.assign}{const quadratic_number_power_product & $q$}
92  $p = q$.
93\end{fcode}
94
95\begin{fcode}{void}{$p$.assign}{const quadratic_number_standard & $g$}
96  $p = g^1$.
97\end{fcode}
98
99\begin{fcode}{void}{$p$.assign_one}{const quadratic_order & $\Or$}
100  $p = 1^1$ with $1 \in \Or$.
101\end{fcode}
102
103\begin{fcode}{void}{$p$.assign}{const quadratic_ideal & $I$, const xbigfloat & $t$, int $s$}
104  Let $\Or$ be the real quadratic order of $I$.  It is assumed that $I$ is a principal ideal in
105  $\Or$ with $a \Or = I$ and $|t - \Ln(a)| < 2^{-4}$, $\sgn(a) = s$.  Then $a$ is uniquely
106  determined by $I,t,s$.  The function initializes the power product by a compact representation
107  of $a$.  If the above conditions are not satisfied, the result is undefined.  The $\sgn(a)$ is
108  $-1$, if $a < 0$, and $1$ otherwise.
109
110  Let $\Or$ be a quadratic order of discriminant $\D$, $K$ the field of fractions, and
111  $\alpha\in K$.  Extending the definition in \cite{Buchmann/Thiel/Williams:1995} from quadratic
112  integers to numbers in $K$, we say that $\alpha$ is in compact representation with respect to
113  $\D$, if
114  \begin{displaymath}
115    \alpha = \gamma \prod_{j=1}^k \left(\frac{\alpha_j}{d_j}\right)^{2^{k-j}} \enspace,
116  \end{displaymath}
117  where $\gamma\in K$, $\alpha_j\in \Or$, $d_j\in\bbfZ_{>0}$, $1\leq j\leq k \leq \max\{ 1,
118  \ln_2 \ln_2(H(\alpha) d(\alpha))+2 \}$,
119  \begin{displaymath}
120    d(\gamma) \leq d(\alpha) \enspace, \quad H(\gamma) \leq |N(\alpha)| d(\alpha) \enspace,
121  \end{displaymath}
122  and
123  \begin{displaymath}
124    0 < d_j \leq |\D|^{1/2}\enspace, \quad H(\alpha_j) \leq 2|\D|^{7/4} \quad\text{ for } 1 \leq j \leq k .
125  \end{displaymath}
126  Here, $H(\alpha)$ is the height, $N(\alpha)$ the norm, and $d(\alpha)$ the denominator of
127  $\alpha$.  For further details see \cite{Maurer_Thesis:2000}.
128\end{fcode}
129
130\begin{fcode}{void}{swap}{const quadratic_number_power_product & $p$,
131    const quadratic_number_power_product & $q$}%
132  Swaps $p$ and $q$.
133\end{fcode}
134
135
136%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
137
138\ACCS
139
140Let $p$ be of type \code{quadratic_number_power_product}.
141
142\begin{fcode}{const quadratic_number_power_product_basis &}{$p$.get_basis}{}
143  Returns a \code{const} reference to the basis of $p$.  As usual, the \code{const} reference
144  should only be used to create a copy or to immediately apply another operation to it, because
145  after the next operation applied to $p$ the obtained reference may be invalid.
146\end{fcode}
147
148\begin{fcode}{const base_vector< bigint > &}{$p$.get_exponents}{}
149  Returns a \code{const} reference to the vector of exponents of $p$.  As usual, the
150  \code{const} reference should only be used to create a copy or to immediately apply another
151  operation to it, because after the next operation applied to $p$ the obtained reference may be
152  invalid.
153\end{fcode}
154
155\begin{fcode}{const quadratic_order &}{$p$.get_order}{}
156  Returns a \code{const} reference to the order of the first element in the basis of $p$.  If
157  there is no element in the basis of $p$, the \LEH is called.  This function is for
158  convenience, in the case, that all base elements are defined over the same order.  As usual,
159  the \code{const} reference should only be used to create a copy or to immediately apply
160  another operation to it, because after the next operation applied to $p$ the obtained
161  reference may be invalid.
162\end{fcode}
163
164\begin{fcode}{bool}{$p$.is_initialized}{}
165  Returns \TRUE, if a basis and a vector of exponents has been assigned to $p$, and if both are
166  of same length.  Otherwise, it returns \FALSE.
167\end{fcode}
168
169\begin{fcode}{int}{$p$.get_sign}{}
170  Returns $1$, if $p \geq 0$, and $-1$ otherwise.
171\end{fcode}
172
173
174%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
175
176\ARTH
177
178Let $p$ be of type \code{quadratic_number_power_product}.  In the following, writing
179$(b,c),(e,f)$ means, that the basis $b$ is concatenated with $c$ and that the exponent vector
180$e$ is concatenated with $f$.
181
182\begin{fcode}{void}{$p$.negate}{}
183  $p \assign -p$.
184\end{fcode}
185
186\begin{fcode}{void}{$p$.multiply}{const quadratic_number_power_product & $x$,
187    const quadratic_number_standard & $y$}%
188  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,1)\bigr)$.
189\end{fcode}
190
191\begin{fcode}{void}{$p$.multiply}{const quadratic_number_standard & $y$,
192    const quadratic_number_power_product & $x$}%
193  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,1)\bigr)$.
194\end{fcode}
195
196\begin{fcode}{void}{$p$.multiply}{const quadratic_number_power_product & $x$,
197    const quadratic_number_power_product & $y$}%
198  Let $x = (b,e)$ and $y = (c,f)$.  Then $p \assign \bigl((b,c),(e,f)\bigr)$.
199\end{fcode}
200
201\begin{fcode}{void}{$p$.invert}{const quadratic_number_power_product & $x$}
202  Let $p = (b,e)$.  Then $p \assign (b,-e)$.
203\end{fcode}
204
205\begin{fcode}{void}{$p$.invert_base_elements}{}
206  Let $p = (b,e)$.  Then $p \assign (b^{-1},e)$, i.e., each element of the basis is inverted.
207\end{fcode}
208
209\begin{fcode}{void}{$p$.divide}{const quadratic_number_power_product & $x$,
210    const quadratic_number_standard & $y$}%
211  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,-1)\bigr)$.
212\end{fcode}
213
214\begin{fcode}{void}{$p$.divide}{const quadratic_number_standard & $y$,
215    const quadratic_number_power_product & $x$}%
216  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(-e,1)\bigr)$.
217\end{fcode}
218
219\begin{fcode}{void}{$p$.divide}{const quadratic_number_power_product & $x$,
220    const quadratic_number_power_product & $y$}%
221  Let $x = (b,e)$ and $y = (c,f)$.  Then $p \assign \bigl((b,c),(e,-f)\bigr)$.
222\end{fcode}
223
224\begin{fcode}{void}{$p$.square}{const quadratic_number_power_product & $x$}
225  Let $x = (b,e)$.  Then $p \assign (b,2 \cdot e)$.
226\end{fcode}
227
228\begin{fcode}{void}{$p$.power}{const quadratic_number_power_product & $x$, const bigint & $f$}
229  Let $x = (b,e)$.  Then $p \assign (b,f \cdot e)$.
230\end{fcode}
231
232
233%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
234
235\COMP
236
237The binary operators \code{==} and \code{!=} are overloaded for comparison with
238\code{quadratic_number_power_product} and \SEE{quadratic_number_standard}.
239
240These functions are not efficient, because they evaluate the power products for comparison.
241
242
243%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
244
245\BASIC
246
247Let $p$ be of type \code{quadratic_number_power_product}.
248
249\begin{fcode}{void}{$p$.conjugate}{}
250  Maps $p$ to its conjugate by replacing each element of the basis of $p$ by its conjugate.
251\end{fcode}
252
253\begin{cfcode}{void}{$p$.norm_modulo}{bigint & $\num$, bigint & $\den$, const bigint & $m$}
254  Returns $\num$ and $\den$, i.e., the numerator and denominator of the norm of $p$ modulo $m$,
255  respectively.  If $m$ is zero, the \LEH will be called.  It is $0 \leq \num, \den < m$.
256\end{cfcode}
257
258\begin{cfcode}{quadratic_number_standard}{$p$.evaluate}{}
259  Returns the evaluation of $p$.
260\end{cfcode}
261
262
263%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
264
265\HIGH
266
267\begin{fcode}{void}{$p$.compact_representation}{const quadratic_ideal & $I$}
268  Let $\Or$ be the real quadratic order of $I$.  If $p \Or = q I$, then this function transforms
269  $p$ into compact representation.  Otherwise, the result is undefined.  For a definition of
270  compact representation, see the corresponding \code{assign} function of the class.
271\end{fcode}
272
273\begin{fcode}{void}{$p$.get_short_principal_ideal_generator}{xbigfloat & $l$, bigint & $z$,
274    const quadratic_unit & $\varrho$, long $b$, long $k$}%
275  Let $\Or$ be the real quadratic order of $p$, $\varrho$ its fundamental unit, and let $R =
276  |\Ln(\varrho)|$ denote the regulator of $\Or$.  If $|b - b(\Ln(\varrho))| \leq 1$ and $p$ is a
277  non-rational number in the field of fractions of $\Or$, then this functions computes $z$, such
278  that either $-R/2 < \Ln(p) - z R \leq R/2$ or $0 \leq \Ln p - z R < R$ and also an absolute $k$
279  approximation to $\Ln(a)$, where $a = p / \varrho^z$.  If the conditions are not satisfied,
280  the result is undefined.
281
282  If $k\geq 4$, then $l$ and the ideal $I = p \Or$ can be used to compute a compact
283  representation of $a$ using the \code{assign} function of the class.  If the caller is only
284  interested in $z$, he should choose $k = -b+6$.
285
286  NOTE: The interface of that function will be changed in the future, so that it is not
287  necessary to give the parameters $\varrho$ and $b$ anymore.
288\end{fcode}
289
290
291\SSTITLE{$\Ln$ approximation}
292
293Let $\Ln$ denote the Lenstra logarithm: $\Ln(x) = 1/2 \ln |x / \sigma(x)|$.
294
295\begin{cfcode}{void}{$p$.get_absolute_Ln_approximation}{xbigfloat & $l$, long $k$}
296  Computes an absolute $k$-approximation $l$ to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
297  absolute approximation.
298\end{cfcode}
299
300\begin{cfcode}{void}{$p$.absolute_Ln_approximation}{xbigfloat & $l$, long $k$}
301  Computes an absolute $k$-approximation $l$ to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
302  absolute approximation.
303\end{cfcode}
304
305\begin{cfcode}{xbigfloat}{$p$.get_absolute_Ln_approximation}{long $k$}
306  Returns an absolute $k$-approximation to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
307  absolute approximation.
308\end{cfcode}
309
310\begin{cfcode}{xbigfloat}{$p$.absolute_Ln_approximation}{long $k$}
311  Returns an absolute $k$-approximation to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
312  absolute approximation.
313\end{cfcode}
314
315\begin{cfcode}{void}{$p$.get_relative_Ln_approximation}{xbigfloat & $l$, long $k$, long $m$}
316  Computes a relative $k$-approximation $l$ to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
317  \SEE{xbigfloat} for definition of relative approximation.
318\end{cfcode}
319
320\begin{cfcode}{xbigfloat}{$p$.get_relative_Ln_approximation}{long $k$, long $m$}
321  Returns a relative $k$-approximation to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
322  \SEE{xbigfloat} for definition of relative approximation.
323\end{cfcode}
324
325\begin{cfcode}{xbigfloat}{$p$.relative_Ln_approximation}{long $k$, long $m$}
326  Returns a relative $k$-approximation to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
327  \SEE{xbigfloat} for definition of relative approximation.
328\end{cfcode}
329
330
331\SSTITLE{Operations on quasi-units, i.e., numbers of $\bbfQ^* \cdot \Or^*$}
332
333Let $u$ be a power product of quadratic numbers.  We call $u$ a \emph{quasi-unit} of $\Or$, if
334$u \in \bbfQ^* \cdot \Or^*$, for a real quadratic order $\Or$, i.e., $u$ is the product of a
335rational number and a unit of $\Or$.  The set $\bbfQ^* \cdot \Or^*$ together with multiplication
336forms a group with subgroup $(\bbfQ^*,\cdot)$.  The factor group $\bbfQ^* \cdot \Or^* / \bbfQ^*$
337is isomorphic to $\Or^*$ by mapping $a \cdot \bbfQ^*$ to $a$ for $a\in \Or^*$.  If $u$ is a
338unit, $q$ a non-zero rational number, then $\pm u$ are the only units in the equivalence class
339$(qu)\bbfQ^*$.  Here, $\bbfQ^*$ denotes $\bbfQ\setminus\{0\}$.
340
341\begin{fcode}{void}{$u$.compact_representation_of_unit}{}
342  Transforms $u$ into a compact representation of the positive unit in the equivalence class $u
343  \bbfQ^*$, assuming that $u$ is a quasi unit of its order $\Or$.  Calls
344  \code{$u$.compact_representation($\Or$)}.  If $u$ is not a quasi unit, the result is
345  undefined.  For a definition of compact representation, see the corresponding \code{assign}
346  function of the class.
347\end{fcode}
348
349\begin{cfcode}{bool}{$u$.is_rational}{long $m$}
350  Let $u$ be a quasi-unit of the real quadratic order $\Or$ and let $R > 2^m$, where $R$ is the
351  regulator of $\Or$.  This functions returns \TRUE, if $u$ is rational, and \FALSE otherwise.  If
352  $u$ is not a quasi-unit of its order, the result is undefined.
353\end{cfcode}
354
355\begin{fcode}{void}{$u$.generating_unit}{const quadratic_number_power_product & $q_1$,
356    const quadratic_number_power_product & $q_2$, long $m$}%
357  Let $q_1$ and $q_2$ be quasi-units of the real quadratic order $\Or$ and let $R > 2^m$, where
358  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
359  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
360  generated by the embeddings of $q_1$ and $q_2$.
361\end{fcode}
362
363\begin{fcode}{void}{$u$.generating_unit}{bigint & $x$, bigint & $y$,
364    bigint & $M_1$, bigint & $M_2$, const quadratic_number_power_product & $q_1$,
365    const quadratic_number_power_product & $q_2$, long $m$}%
366  Let $q_1$ and $q_2$ be quasi-units of a real quadratic order $\Or$ and let $R > 2^m$, where
367  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
368  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
369  generated by the embeddings of $q_1$ and $q_2$.
370
371  Identify $u$, $q_1$, and $q_2$ by its embeddings.  The function also returns $M_1$ and $M_2$
372  such that $u^{M_1} = q_1$ and $u^{M_2} = q_2$, as well as $x$ and $y$ such that $q_1^x q_2^y =
373  u$, respectively.  It is $x M_1 + y M_2 = 1$.
374\end{fcode}
375
376\begin{fcode}{void}{$u$.generating_unit}{base_vector< quadratic_number_power_product > & $q$, long $m$}
377  Let $q$ be a vector of quasi-units of a real quadratic order $\Or$ and let $R > 2^m$, where
378  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
379  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
380  generated by the embeddings of the quasi-units in $q$.
381\end{fcode}
382
383\begin{fcode}{void}{$u$.generating_unit}{const matrix< bigint > & $M$,
384    const base_vector< quadratic_number_standard > & $v$, long $l$}%
385  Let $M$ be a matrix with $m$ rows and $n$ columns and $e$ be a vector of size $m$ of quadratic
386  numbers.  It is assumed that $q_j = \prod_{i=0,\dots,m-1} v_i^{M(i,j)}$ for $j = 0,\dots,n-1$
387  are quasi-units of a real quadratic order $\Or$ and $R > 2^l$, where $R$ is the regulator of
388  $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the subgroup generated by
389  the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup generated by the
390  embeddings of the quasi-units $q_0,\dots,q_n-1$.
391\end{fcode}
392
393\begin{fcode}{void}{$u$.generating_unit}{const char * units_input_file}
394  Assumes that the \code{units_input_file} contains a matrix $M$ over \SEE{bigint}, a
395  \SEE{base_vector} $v$ over \SEE{quadratic_number_standard} and a \code{long} $l$.  The
396  functions reads $M$, $v$, and $l$ and calls \code{$u$.generating_unit($M$, $v$, $l$)} to
397  determine the generating quasi-unit $u$.
398
399  Note that \code{quadratic_order::qo_l().set_last} must be called with the quadratic order of the
400  quadratic numbers in $v$.  See input operator of \SEE{quadratic_number_standard} for further
401  details.
402\end{fcode}
403
404\begin{fcode}{void}{quadratic_number_power_product::remove_rationals_from_quasi_units}{
405    base_vector< quadratic_number_power_product > & $p$, long $l$}%
406  Let $p$ be a vector of quasi units of an order $\Or$ and let the regulator of $R$ be strictly
407  larger than $2^l$.  The function removes those quasi units from the vector $q$ that a rational
408  numbers and adjusts the size of $q$.
409\end{fcode}
410
411\begin{Tfcode}{void}{quadratic_number_power_product::cfrac_expansion_bounded_den}{
412    bigint & $\mathit{conv\uscore num}$, bigint & $\mathit{conv\uscore den}$,
413    bigint $\num$, bigint $\den$, const bigint & $S$}%
414  Computes the last convergent $\mathit{conv\uscore num} / \mathit{conv\uscore den}$ of the
415  continued fraction expansion of $\num / \den$, of which absolute value of the denominator is
416  less or equal to $S$, where $S$ must be positive.
417\end{Tfcode}
418
419\begin{Tfcode}{long}{quadratic_number_power_product::estimate_pp_accuracy}{
420    const matrix < bigint > & $M$, long $m$, xbigfloat c}%
421  Returns $k$ such that $k$ heuristically is an upper bound on the largest absolute accuracy
422  needed in the rgcd algorithm.  $2^m$ should be a lower bound on the regulator and $c$ an upper
423  bound on the absolute values of $\Ln(q)$, where $q$ runs over all principal ideal generators,
424  which form the bases in the power products of the quasi units.  $k = b(c) + \max(j) b(\sum_i
425  |M(i,j)|) - 2m + 9$.
426\end{Tfcode}
427
428
429\SSTITLE{Tests for units and quasi units}
430
431Let $u$ be of type \code{quadratic_number_power_product}.
432
433If a test for quasi unit on $u$ returns \FALSE, then $u$ is not a unit.  If a test for unit on
434$u / \sigma(u)$ returns \FALSE, then $u$ is not a quasi unit.  In this way, tests for units can
435be applied for quasi units and vice versa.  This is because a unit is a quasi unit too and if $v
436= q u$ is a quasi unit, $q \in \bbfQ^*$, $u\in \Or^*$, then $v / \sigma(v) = u / \sigma(u) =
437u^{2}/N(u) = u^{2}$ is a unit.
438
439\begin{cfcode}{bool}{$u$.could_be_unit_norm_test}{int $\mathit{trials}$ = 5}
440  If the function returns \FALSE, $u$ is not a unit.  The function computes the numerator $n$ and
441  denominator $d$ of the norm modulo some integer $m$, respectively.  It then checks whether $n
442  \equiv d$ modulo $m$.  If this is not the case, the function returns \FALSE.  If the test is
443  positive for $\mathit{trials}$ chosen moduli $m$, the function returns \TRUE.
444
445  Note that numbers of the form $a / \sigma(a)$ always have norm $1$, but are not necessarily
446  units.
447\end{cfcode}
448
449\begin{cfcode}{bool}{$u$.could_be_quasi_unit_close_test}{}
450  If the function returns \FALSE, $u$ is not a quasi unit of its order $\Or$.  The function
451  approximates $\Ln(u)$ by $t$ close enough, such that one out of three ideals that are close to
452  $t$ must be $\Or$.  If this is not the case, the function returns \FALSE, otherwise it returns
453  \TRUE.  It uses the \code{order_close} function of \SEE{quadratic_ideal} to do this test.
454\end{cfcode}
455
456\begin{cfcode}{int}{$u$.could_be_unit_refinement_test}{}
457  If the function returns $0$, $u$ is not a unit in its order $\Or$.  If it returns $1$, then
458  $u$ is a unit in $\Or$.  If it returns $-1$, then $u$ is a unit in a overorder of $\Or$.  The
459  function uses factor refinement, to determine its answer.  See
460  \cite{Buchmann/Eisenbrand:1999}.  This method is rather slowly compared to the other unit
461  tests.
462\end{cfcode}
463
464
465%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
466
467\IO
468
469Let $p = (b,e)$ be of type \code{quadratic_number_power_product}.
470
471\code{istream} operator \code{>>} and \code{ostream} operator \code{<<} are overloaded.  Input
472and output of a \code{quadratic_number_power_product} are in the following format:
473\begin{displaymath}
474  (b, e)
475\end{displaymath}
476For example, to input the power product $(1 + \sqrt{5})/2$, you have to do the following.
477Because elements of type \SEE{quadratic_number_standard} are entered only by their coefficients,
478you first have to initialize a quadratic order $\Or$ with the discriminant $5$ and to set
479\begin{verbatim}
480  quadratic_order::qo_l().set_last(&O)
481\end{verbatim}
482Then you can call the operator \code{>>} and enter $( [(1,1,2)], [1] )$.
483
484This behaviour may be improved in the future.
485
486
487%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
488
489\SEEALSO
490
491\SEE{bigfloat}, \SEE{quadratic_order}, \SEE{quadratic_unit}.
492
493
494%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
495
496\EXAMPLES
497
498The following program generates a randomly chosen power product in the field of fractions of the
499real quadratic order of discriminant $5$.  Then it squares the power product.
500
501\begin{quote}
502\begin{verbatim}
503#include <LiDIA/quadratic_order.h>
504#include <LiDIA/quadratic_number_standard.h>
505#include <LiDIA/quadratic_number_power_product.h>
506#include <LiDIA/quadratic_number_power_product_basis.h>
507#include <LiDIA/base_vector.h>
508#include <LiDIA/bigint.h>
509#include <LiDIA/random_generator.h>
510
511int main()
512{
513    // Generate order.
514    //
515    quadratic_order O;
516    O.assign(5);
517
518    // Generate
519    // base_vector< quadratic_number > v and
520    // base_vector< bigint > e.
521    //
522    base_vector< quadratic_number_standard > v;
523    base_vector< bigint > e;
524    lidia_size_t j, sizePPB;
525
526    sizePPB = 5;
527    v.set_capacity(sizePPB);
528    e.set_capacity(sizePPB);
529
530    for (j=0; j < sizePPB; j++) {
531        v[j].assign_order(O);
532        v[j].randomize();
533        e[j].randomize(5);
534    }
535
536    // Generate power product basis b from v.
537    //
538    quadratic_number_power_product_basis b;
539    b.set_basis(v);
540
541    // Generate power product from b and e.
542    //
543    quadratic_number_power_product p;
544    p.set_basis(b);
545    p.set_exponents(e);
546
547    cout << " p = " << p << endl;
548
549    // Square the power product.
550    //
551    p.square(p);
552
553    // Print result.
554    //
555    cout << " p^2 = " << p << endl;
556
557    return 0;
558}
559\end{verbatim}
560\end{quote}
561
562For example, the program could produce the following output.
563\begin{quote}
564\begin{verbatim}
565p = ([ (3,2,3) (4,1,3) (3,3,2) (3,3,1) (0,1,1) ],[ 3 0 0 4 2 ])
566p^2 = ([ (3,2,3) (4,1,3) (3,3,2) (3,3,1) (0,1,1) ],[ 6 0 0 8 4 ])
567\end{verbatim}
568\end{quote}
569
570An extensive example for the use of \code{quadratic_number_power_product} can be found in
571\LiDIA's installation directory under
572\path{LiDIA/src/packages/quadratic_order/quadratic_number_power_product_appl.cc}
573
574
575%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
576
577\AUTHOR
578
579Markus Maurer
580
581%%% Local Variables:
582%%% mode: latex
583%%% TeX-master: t
584%%% End:
585