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