1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2%% 3%% quadratic_order.tex LiDIA documentation 4%% 5%% This file contains the documentation of the class quadratic_order 6%% 7%% Copyright (c) 1996 by LiDIA-Group 8%% 9%% Author: Michael J. Jacobson, Jr. 10%% 11 12%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 13 14\NAME 15 16\CLASS{quadratic_order} \dotfill class describing quadratic 17orders 18 19 20%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 21 22\ABSTRACT 23 24\code{quadratic_order} is a class for representing quadratic orders and computing many related 25invariants and functions, such as the ideal class number, regulator, $L$-function, Littlewood 26indices, etc \dots 27 28 29%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 30 31\DESCRIPTION 32 33A \code{quadratic_order} $\Or$ is represented simply by a \code{bigint} $\D$, which is a 34quadratic discriminant, i.e., a non-square integer congruent to 0 or 1 modulo 4. Unlike the 35case of higher degree orders (see the description of \code{order}), we do not require a 36multiplication table to perform arithmetic with elements in the order since we can represent any 37element in $\Or$ as $a + b(\D + \sqrt{\D})/2$ where $a,b \in \bbfZ$. 38 39Several invariants related to a specific quadratic order are stored along with the discriminant, 40since some of them can be very time-consuming to compute, and knowledge of them often simplifies 41other computations. We store the following invariants once they have been computed: 42\begin{itemize} 43\item factorization of $\D$ (\code{rational_factorization}) 44\item ideal class number (\code{bigint}) 45\item approximation of the regulator (\code{bigfloat}) 46\item elementary divisors of the ideal class group (\code{base_vector< bigint >}) 47\item generators of each cyclic subgroup in the decomposition of the ideal class group 48 (\code{base_vector} of \code{qi_class}) 49\item approximation of $L(1,\chi )$ (\code{bigfloat}) 50\item approximation of $C(\D )$ (\code{bigfloat}) 51\end{itemize} 52 53 54%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 55 56\CONS 57 58\begin{fcode}{ct}{quadratic_order}{} 59 initializes an empty quadratic order ($\D = 0$)). 60\end{fcode} 61 62\begin{fcode}{ct}{quadratic_order}{long $\D$} 63 if $\D$ is a quadratic discriminant, initializes a \code{quadratic_order} of discriminant 64 $\D$, otherwise an empty quadratic order ($\D = 0$) is initialized. 65\end{fcode} 66 67\begin{fcode}{ct}{quadratic_order}{const bigint & $\D$} 68 if $\D$ is a quadratic discriminant, initializes a \code{quadratic_order} of discriminant 69 $\D$, otherwise an empty quadratic order ($\D = 0$) is initialized. 70\end{fcode} 71 72\begin{fcode}{ct}{quadratic_order}{const quadratic_order & $\Or$} 73 initializes a copy of $\Or$. 74\end{fcode} 75 76\begin{fcode}{dt}{~quadratic_order}{} 77\end{fcode} 78 79 80%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 81 82\INIT 83 84Let $\Or$ be of type \code{quadratic_order}. 85 86\begin{fcode}{static void}{quadratic_order::verbose}{int $\mathit{state}$} 87 sets the amount of information which is printed during computations. If $\mathit{state} = 1$, 88 then the elapsed CPU time of some computations is printed. If $\mathit{state} = 2$, then 89 extra run-time data is printed during the execution of the subexponential class group 90 algorithm and verifications. If $\mathit{state} = 0$, no extra information is printed. The 91 default is $\mathit{state} = 0$. 92\end{fcode} 93 94\begin{fcode}{static void}{quadratic_order::verification}{int $\mathit{level}$} 95 sets the level of post-computation verification performed. If $\mathit{level} = 0$ no extra 96 verification is performed, otherwise, the following levels of verification are used: 97 \begin{itemize} 98 \item $\mathit{level} = 1$ --- regulator is verified, orders of generators of the class group 99 are verified 100 \item $\mathit{level} = 2$ --- same as $1$, plus all prime ideals not in the factor base with 101 norm less than Bach's bound are factored over the factor base (only for the subexponential 102 algorithm) 103 \item $\mathit{level} = 3$ --- same as $2$, plus all prime ideals with norm less than Bach's 104 bound are represented over a system of generators (only for the subexponential algorithm) 105%\item $\mathit{level} = 4$ --- same as $2$, but all primes less than 106%Minkowski's bound are factored over the factor base 107%\item $\mathit{level} = 5$ --- same as $3$, but all primes less than 108%Minkowski's bound are represented over a system of generators 109 \end{itemize} 110 Note that level $2$ is sufficient to provide a conditional verification of the output of the 111 subexponential algorithm under the Extended Riemann Hypothesis (ERH). 112%and level $5$ provides an unconditional verification. Naturally, an 113%unconditional verification is rather time-consuming, and is not recommended 114%for large discriminants. 115 The success of the verification will be output only if the verbose mode is set to a non-zero 116 value, but any failures are always output. The default is $\mathit{level} = 0$. 117\end{fcode} 118 119 120%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 121 122\ASGN 123 124Let $\Or$ be of type \code{quadratic_order}. The operator \code{=} is overloaded. For 125efficiency reasons, the following functions are also implemented: 126 127\begin{fcode}{bool}{$\Or$.assign}{long $\D$} 128 if $D$ is a quadratic discriminant, $\Or$ is set to the quadratic order of discriminant $D$ 129 and \TRUE is returned, otherwise $\Or$ is set to an empty quadratic order ($\D = 0$) and 130 \FALSE is returned. 131\end{fcode} 132 133\begin{fcode}{bool}{$\Or$.assign}{const bigint & $\D$} 134 if $D$ is a quadratic discriminant, $\Or$ is set to the quadratic order of discriminant $D$ 135 and \TRUE is returned, otherwise $\Or$ is set to an empty quadratic order ($\D = 0$) and 136 \FALSE is returned. 137\end{fcode} 138 139\begin{fcode}{void}{$\Or$.assign}{const quadratic_order & $\Or_2$} 140 $\Or \assign \Or_2$. 141\end{fcode} 142 143 144%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 145 146\ACCS 147 148Let $\Or$ be of type \code{quadratic_order}. 149 150\begin{cfcode}{bigint}{$\Or$.discriminant}{} 151 returns the discriminant $\D$ of $\Or$. 152\end{cfcode} 153 154 155%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 156 157\COMP 158 159The binary operators \code{==}, \code{!=}, \code{<=}, \code{<} (true subset), \code{>=}, 160\code{>} and the unary operator \code{!} (comparison with $(0)$) are overloaded and can be used 161in exactly the same way as in the programming language C++. Let $\Or$ be of type 162\code{quadratic_order}. 163 164\begin{cfcode}{bool}{$\Or$.is_zero}{} 165 returns \TRUE if the discriminant is zero, \FALSE otherwise. 166\end{cfcode} 167 168\begin{cfcode}{bool}{$\Or$.is_equal}{const quadratic_order & $\Or_2$} 169 returns \TRUE if $\Or = \Or_2$, \FALSE otherwise. 170\end{cfcode} 171 172\begin{fcode}{bool}{$\Or$.is_subset}{quadratic_order & $\Or_2$} 173 returns \TRUE if $\Or$ is a subset of $\Or_2$, \FALSE otherwise. The discriminant is factored 174 if necessary. 175\end{fcode} 176 177\begin{fcode}{bool}{$\Or$.is_proper_subset}{quadratic_order & $\Or_2$} 178 returns \TRUE if $\Or$ is a proper subset of $\Or_2$, \FALSE otherwise. The discriminant is 179 factored if necessary. 180\end{fcode} 181 182 183%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 184 185\BASIC 186 187\begin{fcode}{bool}{is_quadratic_discriminant}{const long $\D$} 188 returns \TRUE if $D$ is a quadratic discriminant, \FALSE otherwise. 189\end{fcode} 190 191\begin{fcode}{bool}{is_quadratic_discriminant}{const bigint & $\D$} 192 returns \TRUE if $D$ is a quadratic discriminant, \FALSE otherwise. 193\end{fcode} 194 195\begin{cfcode}{bool}{$\Or$.is_imaginary}{} 196 returns \TRUE if $\Or$ is an imaginary quadratic order (negative discriminant), \FALSE 197 otherwise. 198\end{cfcode} 199 200\begin{cfcode}{bool}{$\Or$.is_real}{} 201 returns \TRUE if $\Or$ is a real quadratic order (positive discriminant), \FALSE otherwise. 202\end{cfcode} 203 204\begin{fcode}{void}{swap}{quadratic_order & $A$, quadratic_order & $B$} 205 exchanges $A$ and $B$. 206\end{fcode} 207 208 209%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 210 211\HIGH 212 213Let $\Or$ be of type \code{quadratic_order}. 214 215\begin{fcode}{int}{$\Or$.bach_bound}{} 216 returns a constant such that the prime ideals of norm less than this constant generate the 217 class group (under the ERH). This function assumes that $\Or$ is not maximal. 218\end{fcode} 219 220\begin{fcode}{int}{$\Or$.bach_bound}{bool $\mathit{is\uscore max}$} 221 returns a constant such that the prime ideals of norm less than this constant generate the 222 class group (under the ERH). If the parameter is \TRUE, $\Or$ will be assumed to be maximal, 223 otherwise non-maximal. 224\end{fcode} 225 226\begin{fcode}{bigint}{$\Or$.conductor}{} 227 returns the conductor of $\Or$, i.e., the integer $f$ such that $\D = f^2 \D_0$ where $\D_0$ is 228 a fundamental discriminant (the discriminant of a maximal order). The factorization of the 229 discriminant is computed if it has not been already. 230\end{fcode} 231 232\begin{fcode}{bool}{$\Or$.is_maximal}{} 233 returns \TRUE if $\Or$ is a maximal order, \FALSE otherwise. The factorization of the 234 discriminant is computed if it has not been already. 235\end{fcode} 236 237\begin{fcode}{quadratic_order}{$\Or$.maximize}{} 238 returns the maximal order in which $\Or$ is contained. The factorization of the discriminant 239 is computed if it has not been already. 240\end{fcode} 241 242 243%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 244 245\SSTITLE{$L$-functions, Littlewood indices, $C$-function} 246 247The function $L(s,\chi ) = \sum_{n=1}^{\infty} \frac{\chi (n)}{n^s}$, where $\chi$ is taken to 248be the Kronecker symbol, is intimately related to computations in class groups of quadratic 249orders, especially at $s=1$, due to the analytic class number formula of Dirichlet. 250 251The Littlewood indices \cite{Littlewood:1928,Shanks:1973} are values which test the accuracy of 252Littlewood's bounds on $L(1,\chi )$ and a related function $L_{\D}(1) = (2 - 253\kronecker{\D}{2})/2 \,L(1,\chi )$ defined by Shanks \cite{Shanks:1973}. Under the ERH, we 254expect the lower Littlewood indices to be greater than 1 for all discriminants $\D$ (with a few 255exceptions of very small discriminants) and that they should come close to 1 for discriminants 256with exceptionally small values of $L(1,\chi )$ or $L_D(1)$. Similarly, we expect the upper 257Littlewood indices to be less than 1 and to approach 1 for discriminants with exceptionally 258large values of $L(1,\chi )$ or $L_{\D}(1)$. 259 260The function $C(\D) = \prod_{p \geq 3} 1 - \kronecker{\D}{p} / (p-1)$ provides an indication of 261whether a related quadratic polynomial will have an asymptotically large number of prime values, 262based on a conjecture of Hardy and Littlewood \cite{Hardy/Littlewood:1923,Fung/Williams:1990}. 263If $\D$ is odd, then for $A = (1-\D)/4$ the polynomial $x^2 + x + A$ will have a large 264asymptotic density of prime values when $C(\D )$ is large. If $\D$ is even, then for $A = \D / 2654$ the corresponding polynomial is $x^2 + A$. 266 267\begin{fcode}{int}{kronecker}{const bigint & $D$, const bigint & $p$} 268 computes the value of the Kronecker symbol $\kronecker{D}{p}$, where $p$ is prime. 269\end{fcode} 270 271\begin{fcode}{long}{$\Or$.generate_optimal_Q}{} 272 generates the optimal value of $Q$ for the function \code{estimate_L1} to compute a 273 sufficiently accurate estimate from which a value $h^*$ can be computed satisfying $h^* < h < 274 2h^*$ for imaginary orders and $h^* < hR < 2h^*$ for real orders. 275\end{fcode} 276 277\begin{fcode}{long}{$\Or$.get_optimal_Q}{} 278 returns, from a precomputed list, a value of Q that is sufficiently large to satisfy the 279 conditions given above. 280\end{fcode} 281 282\begin{fcode}{long}{$\Or$.generate_optimal_Q_cnum}{const bigfloat & $h_2$, const bigfloat & $t$} 283 generates the optimal value of $Q$ for the function \code{estimate_L1} to compute a 284 sufficiently accurate estimate to prove that $h = h_2$ when the fractional part of the 285 approximation of $h$ is less that $t$. See \cite{Mollin/Williams:1992} for more details. 286\end{fcode} 287 288\begin{fcode}{long}{$\Or$.get_optimal_Q_cnum}{} 289 returns, from a precomputed list, a value of Q that is sufficiently large to satisfy the 290 conditions given above. 291\end{fcode} 292 293\begin{fcode}{bigfloat}{$\Or$.estimate_L}{const int $s$, const long $Q$} 294 computes a truncated product approximation of $L(s, \chi)$ using primes less than $Q$. 295\end{fcode} 296 297\begin{fcode}{bigfloat}{$\Or$.estimate_L1}{const long $Q$} 298 computes an approximation of $L(1, \chi)$ using Bach's averaging method \cite{Bach:1995} 299 with primes less than $2 Q$. 300\end{fcode} 301 302\begin{fcode}{bigfloat}{$\Or$.estimate_L1_error}{const long $Q$} 303 computes an estimate of the error (conditional on EHR) in the approximation of $L(1, \chi)$ 304 using Bach's method \cite{Bach:1995} with primes less than $2Q$. 305\end{fcode} 306 307\begin{fcode}{bigfloat}{$\Or$.Lfunction}{} 308 computes an approximation of $L(1, \chi)$ via the analytic class number formula. The class 309 number and regulator are computed if they have not been already. 310\end{fcode} 311 312\begin{fcode}{bigfloat}{$\Or$.LDfunction}{} 313 returns an approximation of $L_{\D}(1)$. The class number and regulator are computed if they 314 have not been already. 315\end{fcode} 316 317\begin{fcode}{bigfloat}{$\Or$.LLI}{} 318 returns an approximation of the lower Littlewood index related to a lower bound on $L(1, 319 \chi)$ due to Littlewood. The class number and regulator are computed if they have not been 320 already. 321\end{fcode} 322 323\begin{fcode}{bigfloat}{$\Or$.LLI_D}{} 324 returns an approximation of the lower Littlewood index related to a lower bound on $L_{\D}(1)$ 325 due to Shanks. The class number and regulator are computed if they have not been already. 326\end{fcode} 327 328\begin{fcode}{bigfloat}{$\Or$.ULI}{} 329 returns an approximation of the upper Littlewood index related to an upper bound on $L(1, 330 \chi)$ due to Littlewood. The class number and regulator are computed if they have not been 331 already. 332\end{fcode} 333 334\begin{fcode}{bigfloat}{$\Or$.ULI_D}{} 335 returns an approximation of the upper Littlewood index related to an upper bound on 336 $L_{\D}(1)$ due to Shanks. The class number and regulator are computed if they have not been 337 already. 338\end{fcode} 339 340\begin{fcode}{bigfloat}{$\Or$.Cfunction}{} 341 returns an approximation of the function $C(\D)$ accurate to 8 significant digits. The class 342 number, regulator, and the prime factorization of $\D$ are computed if they have not been 343 already. 344\end{fcode} 345 346 347%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 348 349\SSTITLE{Regulator, class number, and class group} 350 351The regulator is defined as the natural logarithm of the fundamental unit and the class number 352is the order of the group of ideal equivalence classes. We denote the regulator by $R$, the 353class group by $\Cl$ and the class number by $h$. By the structure of the class group, we mean 354the unique positive integers $m_1, \dots, m_k$ with $m_1 > 1$, $m_i \mid m_{i+1}$ for $1 \leq i 355\leq k$ such that there is an isomorphism $\phi : \Cl \rightarrow \bbfZ /m_1 \bbfZ \times \dots 356\times \bbfZ /m_k \bbfZ$. The integers $m_i$ are called the elementary divisors of the class 357group. 358 359The following general functions are provided, which intelligently select an appropriate 360algorithm based on the size of the discriminant. 361 362\begin{fcode}{bigfloat}{$\Or$.regulator}{} 363 returns an approximation of the regulator of $\Or$. If the regulator has not already been 364 computed, either \code{regulator_BJT}, \code{regulator_shanks}, or \code{regulator_subexp} is 365 used, depending on the size of the discriminant. If $\Or$ is imaginary, the regulator is set 366 to $1$. 367\end{fcode} 368 369\begin{fcode}{bigint}{$\Or$.class_number}{} 370 returns the ideal class number of $\Or$. If the class number has not already been computed, 371 either \code{class_number_shanks} or \code{class_group_subexp} is used, depending on the size 372 of the discriminant. 373\end{fcode} 374 375\begin{fcode}{base_vector< bigint >}{$\Or$.class_group}{} 376 returns the vector of invariants representing the structure of the ideal class group of $\Or$. 377 If the class group has not already been computed, either \code{class_group_BJT}, 378 \code{class_group_shanks}, \code{class_group_randexp}, \code{class_group_mpqs}, or 379 \code{class_group_siqs} depending on the size of the discriminant. 380\end{fcode} 381 382The following functions all make use of a specific algorithm. 383 384\begin{fcode}{bigfloat}{$\Or$.regulator_BJT}{} 385 computes an unconditionally correct approximation of the regulator of $\Or$ using a variation 386 of the algorithm of \cite{Biehl/Buchmann:1995} which has unconditional complexity 387 $\Omikron(\sqrt{R})$. If $\Or$ is not real, the regulator is set to $1$. If the regulator 388 has already been computed, the function simply returns this value. 389\end{fcode} 390 391\begin{fcode}{bigfloat}{$\Or$.regulator_shanks}{} 392 computes an unconditionally correct approximation of the regulator of $\Or$ using the 393 algorithm of \cite{Jacobson/Lukes/Williams:1995} based on the baby-step giant-step method in 394 \cite{Mollin/Williams:1992}, which has complexity $\Omikron(\D ^{1/5})$ under the ERH. If 395 $\Or$ is not real, the regulator is set to $1$. If the regulator has already been computed, 396 the function simply returns this value. 397\end{fcode} 398 399%\begin{fcode}{bigfloat}{$\Or$.regulator_subexp}{} 400%computes an approximation of the regulator of $\Or$ using the 401%subexponential algorithm of \cite{Jacobson:1999}. 402%If $\Or$ is not real, the regulator is set to 403%$1$. If the regulator has already been computed, the 404%function simply returns this value. The computation is done by calling 405%the function \code{class_group_subexp}, so the structure of the class group 406%is computed simultaneously. 407%\end{fcode} 408 409\begin{fcode}{bool}{$\Or$.verify_regulator}{} 410 returns true if the regulator is correct, as determined by a polynomial-time verification. 411\end{fcode} 412 413\begin{fcode}{bigint}{$\Or$.class_number_shanks}{} 414 computes the ideal class number of $\Or$ using the algorithm of \cite{Fung/Williams:1990} 415 based on the ideas of \cite{LenstraHW:1982} for imaginary quadratic orders, and the algorithm 416 of \cite{Jacobson/Lukes/Williams:1995} based on the ideas in \cite{Mollin/Williams:1992} for 417 real quadratic orders. Both algorithms have complexity $\Omikron(|\D |^(1/5))$, and the 418 correctness and the complexity are both conditional on the truth of the ERH. If the class 419 number has already been computed, the function simply returns this value. 420\end{fcode} 421 422\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_BJT}{} 423 computes the structure of the ideal class group of $\Or$ using the method of 424 \cite{Buchmann/Jabobson/Teske:1997} for imaginary orders and \cite{Jacobson:1998} for real 425 orders, which have complexity $\Omikron(\sqrt{h})$ and $\Omikron(\sqrt{h R})$ respectively. 426 The correctness of both algorithms is conditional on the truth of the ERH but the complexity 427 results are not. If the class group has already been computed, the function simply returns 428 this value. 429\end{fcode} 430 431\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_shanks}{} 432 computes the structure of the ideal class group of $\Or$ using variations of the methods of 433 \cite{Schoof:1982} which have complexity $\Omikron(|\D|^(1/4))$. The correctness and 434 complexity of both algorithms are conditional on the truth of the ERH. If the class group has 435 already been computed, the function simply returns this value. 436\end{fcode} 437 438\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_randexp}{} 439 computes the structure of the ideal class group of $\Or$ using a practical variation of the 440 sub-exponential method of Hafner and McCurley \cite{Hafner/McCurley:1989} due to D\"ullmann 441 \cite{Duellmann_Thesis:1991} for imaginary orders and Cohen, Diaz y Diaz, and Olivier 442 \cite{Cohen/Diaz/Olivier:1993} for real orders, as presented in \cite{Jacobson_Thesis:1999}. 443 Note that if $\Or$ is real, this function also computes the regulator. If the class group has 444 already been computed, the function simply returns this value. Turning the verification off 445 with \code{quadratic_order::verification($0$)} will result in much faster execution of this 446 algorithm, but the result is no longer certifiably correct under the ERH since a smaller 447 factor-base is used than is theoretically necessary. However, as experimental results show 448 \cite{Jacobson:1998}, it is extremely unlikely that the computed result will be false. 449\end{fcode} 450 451\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_mpqs}{} 452 computes the structure of the ideal class group of $\Or$ using the algorithm of 453 \cite{Jacobson:1999} as presented in \cite{Jacobson_Thesis:1999}, in which the relation 454 generation strategy is based on the MPQS factoring algorithm. Note that if $\Or$ is real, 455 this function also computes the regulator. If the class group has already been computed, the 456 function simply returns this value. Turning the verification off with 457 \code{quadratic_order::verification($0$)} will result in much faster execution of this 458 algorithm, but the result is no longer certifiably correct under the ERH since a smaller 459 factor-base is used than is theoretically necessary. However, as experimental results show 460 \cite{Jacobson:1998}, it is extremely unlikely that the computed result will be false. 461\end{fcode} 462 463\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_siqs}{} 464 computes the structure of the ideal class group of $\Or$ using an algorithm from 465 \cite{Jacobson_Thesis:1999}, in which the relation generation strategy is based on the 466 self-initializing MPQS factoring algorithm. Note that if $\Or$ is real, this function also 467 computes the regulator. If the class group has already been computed, the function simply 468 returns this value. Turning the verification off with 469 \code{quadratic_order::verification($0$)} will result in much faster execution of this 470 algorithm, but the result is no longer certifiably correct under the ERH since a smaller 471 factor-base is used than is theoretically necessary. However, as experimental results show 472 \cite{Jacobson:1998}, it is extremely unlikely that the computed result will be false. 473\end{fcode} 474 475\begin{fcode}{base_vector< bigint >}{$\Or$.class_group_lp}{} 476 computes the structure of the ideal class group of $\Or$ using an algorithm from 477 \cite{Jacobson_Thesis:1999}, in which the relation generation strategy is based on the 478 self-initializing MPQS factoring algorithm with large prime variant. Note that if $\Or$ is 479 real, this function also computes the regulator. If the class group has already been 480 computed, the function simply returns this value. Turning the verification off with 481 \code{quadratic_order::verification($0$)} will result in much faster execution of this 482 algorithm, but the result is no longer certifiably correct under the ERH since a smaller 483 factor-base is used than is theoretically necessary. However, as experimental results show 484 \cite{Jacobson:1998}, it is extremely unlikely that the computed result will be false. 485\end{fcode} 486 487\begin{fcode}{bool}{$\Or$.verify_class_group}{int level} 488 returns true if the class group is correct as determined by a polynomial-time verification, 489 using the given verification level 490\end{fcode} 491 492\begin{fcode}{bool}{$\Or$.verify_class_group}{} 493 returns true if the class group is correct as determined by a polynomial-time verification, 494 using the global verification level. 495\end{fcode} 496 497 498%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 499 500\SSTITLE{Additional functions} 501 502\begin{fcode}{rational_factorization}{$\Or$.factor_h}{} 503 returns a \code{rational_factorization} of the class number. The class number is computed if 504 it has not been already. 505\end{fcode} 506 507\begin{fcode}{bigint}{$\Or$.exponent}{} 508 returns the exponent of the class group, i.e., the largest cyclic factor. The class group is 509 computed if it has not been already. 510\end{fcode} 511 512\begin{fcode}{int}{$\Or$.p_rank}{const bigint & $p$} 513 returns the p-rank of the ideal class group. The class group is computed if it has not been 514 already. 515\end{fcode} 516 517\begin{fcode}{base_vector< qi_class >}{$\Or$.generators}{} 518 returns a vector of generators of the cyclic subgroups of the ideal class group of $\Or$. The 519 class group is computed if it has not been already. 520\end{fcode} 521 522\begin{fcode}{rational_factorization}{$\Or$.factor_discriminant}{} 523 returns the prime factorization of the discriminant of $\Or$ using the 2-Sylow subgroup of the 524 class group. The class group and a set of generators are computed if they have not been 525 already. At present, this function is only implemented for imaginary orders. If $\Or$ is 526 real, the discriminant is simply factored with the \code{rational_factorization} function 527 \code{factor}. 528\end{fcode} 529 530\begin{fcode}{math_vector < bigint >}{$\Or$.represent_over_generators}{qi_class & $A$} 531 returns an exponent vector corresponding to the representation of $A$ over the system of 532 generators of the class group. 533\end{fcode} 534 535 536%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 537 538\IO 539 540Let $\Or$ be of type \code{quadratic_order}. The \code{istream} operator \code{>>} and the 541\code{ostream} operator \code{<<} are overloaded. Input consists of reading a \code{bigint} 542value for the discriminant. Output of a \code{quadratic_order} has the following format: 543 544\begin{verbatim} 545Quadratic Order: 546 Delta = (discriminant of QO) (decimal digits) 547 = (prime factorization of the discriminant of QO) 548 R = (regulator) 549 h = (class number) 550 CL = (vector of class group invariants) 551 generators = (vector of generators of the cyclic subgroups) 552 L(1,X) = (L function) 553 C(Delta) = (C function) 554\end{verbatim} 555 556The discriminant is always displayed, while the other invariants are displayed only if they have 557been computed. 558 559 560%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 561 562\SEEALSO 563 564\SEE{qi_class}, 565\SEE{qi_class_real}, 566\SEE{order} 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 582int main() 583{ 584 bigint D; 585 quadratic_order QO; 586 587 do { 588 cout << "Please enter a quadratic discriminant: "; cin >> D; 589 } while (!QO.assign(D)); 590 cout << endl; 591 592 QO.class_group(); 593 QO.generators(); 594 QO.Lfunction(); 595 596 cout << QO; 597 598 cout << " ULI = " << QO.ULI() << endl; 599 cout << " LLI = " << QO.LLI() << endl; 600 601 return 0; 602} 603\end{verbatim} 604\end{quote} 605 606Example: 607\begin{quote} 608\begin{verbatim} 609Please enter a quadratic discriminant: -501510767 610 611Quadratic Order: 612 Delta = -501510767 (9) 613 h = 18522 614 CL = [ 7 7 378 ] 615 generators = [ (3286, 1657) (1144, 439) (2934, 61) ] 616 L(1,X) = 2.5983498285787 617 ULI = 0.243356600232444 618 LLI = 16.865670804095 619\end{verbatim} 620\end{quote} 621 622For further examples please refer to 623\path{LiDIA/src/packages/quadratic_order/quadratic_order_appl.cc}. 624 625 626%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 627 628\AUTHOR 629 630Michael J.~Jacobson, Jr. 631