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