1% Copyright (c) 2000 The PARI Group 2% 3% This file is part of the PARI/GP documentation 4% 5% Permission is granted to copy, distribute and/or modify this document 6% under the terms of the GNU General Public License 7\newpage 8\chapter{Algebraic Number Theory} 9 10\section{General Number Fields} 11 12\subsec{Number field types} 13 14None of the following routines thoroughly check their input: they 15distinguish between \emph{bona fide} structures as output by PARI routines, 16but designing perverse data will easily fool them. To give an example, a 17square matrix will be interpreted as an ideal even though the $\Z$-module 18generated by its columns may not be an $\Z_K$-module (i.e. the expensive 19\kbd{nfisideal} routine will \emph{not} be called). 20 21\fun{long}{nftyp}{GEN x}. Returns the type of number field structure stored in 22\kbd{x}, \tet{typ_NF}, \tet{typ_BNF}, or \tet{typ_BNR}. Other answers 23are possible, meaning \kbd{x} is not a number field structure. 24 25\fun{GEN}{get_nf}{GEN x, long *t}. Extract an \var{nf} structure from 26\kbd{x} if possible and return it, otherwise return \kbd{NULL}. Sets 27\kbd{t} to the \kbd{nftyp} of \kbd{x} in any case. 28 29\fun{GEN}{get_bnf}{GEN x, long *t}. Extract a \kbd{bnf} structure from 30\kbd{x} if possible and return it, otherwise return \kbd{NULL}. Sets 31\kbd{t} to the \kbd{nftyp} of \kbd{x} in any case. 32 33\fun{GEN}{get_nfpol}{GEN x, GEN *nf} try to extract an \var{nf} structure 34from \kbd{x}, and sets \kbd{*nf} to \kbd{NULL} (failure) or to the \var{nf}. 35Returns the (monic, integral) polynomial defining the field. 36 37\fun{GEN}{get_bnfpol}{GEN x, GEN *bnf, GEN *nf} try to extract a \var{bnf} 38and an \var{nf} structure from \kbd{x}, and sets \kbd{*bnf} 39and \kbd{*nf} to \kbd{NULL} (failure) or to the corresponding structure. 40Returns the (monic, integral) polynomial defining the field. 41 42\fun{GEN}{checknf}{GEN x} if an \var{nf} structure can be extracted from 43\kbd{x}, return it; otherwise raise an exception. The more general 44\kbd{get\_nf} is often more flexible. 45 46\fun{GEN}{checkbnf}{GEN x} if an \var{bnf} structure can be extracted from 47\kbd{x}, return it; otherwise raise an exception. The more general 48\kbd{get\_bnf} is often more flexible. 49 50\fun{GEN}{checkbnf_i}{GEN bnf} same as \kbd{checkbnf} but return \kbd{NULL} 51instead of raising an exception. 52 53\fun{void}{checkbnr}{GEN bnr} Raise an exception if the argument 54is not a \var{bnr} structure. 55 56\fun{GEN}{checkbnr_i}{GEN bnr} same as \kbd{checkbnr} but returns the 57\var{bnr} or \kbd{NULL} instead of raising an exception. 58 59\fun{GEN}{checknf_i}{GEN nf} same as \kbd{checknf} but return \kbd{NULL} 60instead of raising an exception. 61 62\fun{void}{checkrnf}{GEN rnf} Raise an exception if the argument is not an 63\var{rnf} structure. 64 65\fun{int}{checkrnf_i}{GEN rnf} same as \kbd{checkrnf} but return $0$ 66on failure and $1$ on success. 67 68\fun{void}{checkbid}{GEN bid} Raise an exception if the argument is not a 69\var{bid} structure. 70 71\fun{GEN}{checkbid_i}{GEN bid} same as \kbd{checkbid} but return \kbd{NULL} 72instead of raising an exception and return \kbd{bid} on success. 73 74\fun{GEN}{checkznstar_i}{GEN G} return $G$ if it is a \var{znstar}; 75else return \kbd{NULL} on failure. 76 77\fun{GEN}{checkgal}{GEN x} if a \var{galoisinit} structure can be extracted 78from \kbd{x}, return it; otherwise raise an exception. 79 80\fun{void}{checksqmat}{GEN x, long N} check whether \kbd{x} is a square matrix 81of dimension \kbd{N}. May be used to check for ideals if \kbd{N} is the field 82degree. 83 84\fun{void}{checkprid}{GEN pr} Raise an exception if the argument is not a 85prime ideal structure. 86 87\fun{int}{checkprid_i}{GEN pr} same as \kbd{checkprid} but return $0$ 88instead of raising an exception and return $1$ on success. 89 90\fun{int}{is_nf_factor}{GEN F} return $1$ if $F$ is an ideal factorization 91and $0$ otherwise. 92 93\fun{int}{is_nf_extfactor}{GEN F} return $1$ if $F$ is an extended ideal 94factorization (allowing $0$ or negative exponents) and $0$ otherwise. 95 96\fun{GEN}{get_prid}{GEN ideal} return the underlying prime ideal structure 97if one can be extracted from \kbd{ideal} (ideal or extended ideal), and 98return \kbd{NULL} otherwise. 99 100\fun{void}{checkabgrp}{GEN v} Raise an exception if the argument 101is not an abelian group structure, i.e. a \typ{VEC} with either $2$ or $3$ 102entries: $[N,\var{cyc}]$ or $[N,\var{cyc}, \var{gen}]$. 103 104\fun{GEN}{abgrp_get_no}{GEN x} 105 extract the cardinality $N$ from an abelian group structure. 106 107\fun{GEN}{abgrp_get_cyc}{GEN x} 108 extract the elementary divisors \var{cyc} from an abelian group structure. 109 110\fun{GEN}{abgrp_get_gen}{GEN x} 111 extract the generators \var{gen} from an abelian group structure. 112 113\fun{GEN}{cyc_get_expo}{GEN cyc} 114 return the exponent of the group with structure \kbd{cyc}; $0$ for an infinite 115group. 116 117\fun{void}{checkmodpr}{GEN modpr} Raise an exception if the argument is not a 118\kbd{modpr} structure (from \kbd{nfmodprinit}). 119 120\fun{GEN}{get_modpr}{GEN x} return $x$ if it is a \kbd{modpr} structure 121and \kbd{NULL} otherwise. 122 123\fun{GEN}{checknfelt_mod}{GEN nf, GEN x, const char *s} given an \var{nf} 124structure \kbd{nf} and a \typ{POLMOD} \kbd{x}, return the attached 125polynomial representative (shallow) if \kbd{x} and \kbd{nf} are compatible. 126Raise an exception otherwise. Set $s$ to the name of the caller for a 127meaningful error message. 128 129\fun{void}{check_ZKmodule}{GEN x, const char *s} check whether $x$ looks like 130$\Z_K$-module (a pair $[A,I]$, where $A$ is a matrix and $I$ is a list of 131ideals; $A$ has as many columns as $I$ has elements. Otherwise 132raises an exception. Set $s$ to the name of the caller for a 133meaningful error message. 134 135\fun{long}{idealtyp}{GEN *ideal, GEN *fa} The input is \kbd{ideal}, a pointer 136to an ideal (or extended ideal), which is usually modified, \kbd{fa} being 137set as a side-effect. Returns the type of the underlying ideal among 138\tet{id_PRINCIPAL} (a number field element), \tet{id_PRIME} (a prime ideal) 139\tet{id_MAT} (an ideal in matrix form). 140 141If \kbd{ideal} pointed to an ideal, set \kbd{fa} to \kbd{NULL}, and 142possibly simplify \kbd{ideal} (for instance the zero ideal is replaced by 143\kbd{gen\_0}). If it pointed to an extended ideal, replace 144\kbd{ideal} by the underlying ideal and set \kbd{fa} to the factorization 145matrix component. 146 147\subsec{Extracting info from a \kbd{nf} structure} 148 149These functions expect a true \var{nf} argument attached to a number field 150$K = \Q[x]/(T)$, e.g.~a \var{bnf} will not work. Let $n = [K:\Q]$ be the 151field degree. 152 153\fun{GEN}{nf_get_pol}{GEN nf} returns the polynomial $T$ (monic, in $\Z[x]$). 154 155\fun{long}{nf_get_varn}{GEN nf} returns the variable number of the number 156field defining polynomial. 157 158\fun{long}{nf_get_r1}{GEN nf} returns the number of real places $r_1$. 159 160\fun{long}{nf_get_r2}{GEN nf} returns the number of complex places $r_2$. 161 162\fun{void}{nf_get_sign}{GEN nf, long *r1, long *r2} sets $r_1$ and $r_2$ 163to the number of real and complex places respectively. Note that 164$r_1+2r_2$ is the field degree. 165 166\fun{long}{nf_get_degree}{GEN nf} returns the number field degree, $n = r_1 + 1672r_2$. 168 169\fun{GEN}{nf_get_disc}{GEN nf} returns the field discriminant. 170 171\fun{GEN}{nf_get_index}{GEN nf} returns the index of $T$, i.e. the index of 172the order generated by the power basis $(1,x,\ldots,x^{n-1})$ in the 173maximal order of $K$. 174 175\fun{GEN}{nf_get_zk}{GEN nf} returns a basis $(w_1,w_2,\ldots,w_n)$ for the 176maximal order of $K$. Those are polynomials in $\Q[x]$ of degree $<n$; it is 177guaranteed that $w_1 = 1$. 178 179\fun{GEN}{nf_get_zkden}{GEN nf} returns the denominator of \tet{nf_get_zk}, 180as a positive \typ{INT}. 181 182\fun{GEN}{nf_get_zkprimpart}{GEN nf} returns \tet{nf_get_zk} times its 183denominator. 184 185\fun{GEN}{nf_get_invzk}{GEN nf} returns the matrix $(m_{i,j})\in M_n(\Z)$ 186giving the power basis $(x^i)$ in terms of the $(w_j)$, i.e such that 187$x^{j-1} = \sum_{i = 1}^n m_{i,j} w_i$ for all $1\leq j \leq n$; since $w_1 = 1881 = x^0$, we have $m_{i,1} = \delta_{i,1}$ for all $i$. The conversion 189functions in the \kbd{algtobasis} family essentially amount to a left 190multiplication by this matrix. 191 192\fun{GEN}{nf_get_roots}{GEN nf} returns the $r_1$ real roots of the polynomial 193defining the number fields: first the $r_1$ real roots (as \typ{REAL}s), then 194the $r_2$ representatives of the pairs of complex conjugates. 195 196\fun{GEN}{nf_get_allroots}{GEN nf} returns all the complex roots of $T$: 197first the $r_1$ real roots (as \typ{REAL}s), then the $r_2$ pairs of complex 198conjugates. 199 200\fun{GEN}{nf_get_M}{GEN nf} returns the $(r_1+r_2)\times n$ matrix $M$ 201giving the embeddings of $K$: $M[i,j]$ contains $w_j(\alpha_i)$, where 202$\alpha_i$ is the $i$-th element of \kbd{nf\_get\_roots(nf)}. In particular, 203if $v$ is an $n$-th dimensional \typ{COL} representing the element 204$\sum_{i=1}^n v[i] w_i$ of $K$, then \kbd{RgM\_RgC\_mul(M,v)} represents the 205embeddings of $v$. 206 207\fun{GEN}{nf_get_G}{GEN nf} returns a $n\times n$ real matrix $G$ such that 208$Gv \cdot Gv = T_2(v)$, where $v$ is an $n$-th dimensional \typ{COL} 209representing the element $\sum_{i=1}^n v[i] w_i$ of $K$ and $T_2$ is the 210standard Euclidean form on $K\otimes \R$, i.e.~$T_2(v) 211= \sum_{\sigma} |\sigma(v)|^2$, where $\sigma$ runs through all $n$ complex 212embeddings of $K$. 213 214\fun{GEN}{nf_get_roundG}{GEN nf} returns a rescaled version of $G$, rounded 215to nearest integers, specifically \tet{RM_round_maxrank}$(G)$. 216 217\fun{GEN}{nf_get_ramified_primes}{GEN nf} returns the vector of ramified 218primes. 219 220\fun{GEN}{nf_get_Tr}{GEN nf} returns the matrix of the Trace quadratic form 221on the basis $(w_1,\ldots,w_n)$: its $(i,j)$ entry is $\text{Tr} w_i w_j$. 222 223\fun{GEN}{nf_get_diff}{GEN nf} returns the primitive part of the inverse of 224the above Trace matrix. 225 226\fun{long}{nf_get_prec}{GEN nf} returns the precision (in words) to which the 227\var{nf} was computed. 228 229\subsec{Extracting info from a \kbd{bnf} structure} 230 231These functions expect a true \var{bnf} argument, e.g.~a \var{bnr} will not 232work. 233 234\fun{GEN}{bnf_get_nf}{GEN bnf} returns the underlying \var{nf}. 235 236\fun{GEN}{bnf_get_clgp}{GEN bnf} returns the class group in \var{bnf}, 237which is a $3$-component vector $[h, \var{cyc}, \var{gen}]$. 238 239\fun{GEN}{bnf_get_cyc}{GEN bnf} returns the elementary divisors 240of the class group (cyclic components) $[d_1,\ldots, d_k]$, where 241$d_k \mid \ldots \mid d_1$. 242 243\fun{GEN}{bnf_get_gen}{GEN bnf} returns the generators $[g_1,\ldots,g_k]$ 244of the class group. Each $g_i$ has order $d_i$, and the full module of relations 245between the $g_i$ is generated by the $d_ig_i = 0$. 246 247\fun{GEN}{bnf_get_no}{GEN bnf} returns the class number. 248 249\fun{GEN}{bnf_get_reg}{GEN bnf} returns the regulator. 250 251\fun{GEN}{bnf_get_logfu}{GEN bnf} returns (complex floating point 252approximations to) the logarithms of the complex embeddings of our system of 253fundamental units. 254 255\fun{GEN}{bnf_get_fu}{GEN bnf} returns the fundamental units. Raise 256an error if the \var{bnf} does not contain units in algebraic form. 257 258\fun{GEN}{bnf_get_fu_nocheck}{GEN bnf} as \tet{bnf_get_fu} without 259checking whether units are present. Do not use this unless 260you initialize the \var{bnf} yourself! 261 262\fun{GEN}{bnf_get_tuU}{GEN bnf} returns a generator of the torsion part 263of $\Z_K^*$. 264 265\fun{long}{bnf_get_tuN}{GEN bnf} returns the order of the torsion part of 266$\Z_K^*$, i.e.~the number of roots of unity in $K$. 267 268\fun{GEN}{bnf_get_sunits}{GEN bnf} allows access to the algebraic data 269stored by \kbd{bnfinit(,1)}. It returns \kbd{NULL} unless the \kbd{bnf} 270was initialized by \kbd{bnfinit(,1)}, else a vector $[X,U,E,\kbd{lim}]$ where 271 272\item $X$ is a vector of rational primes and algebraic integers all of whose 273prime divisors have norm less than \kbd{lim}, 274 275\item $U$ is a matrix of exponents whose columns yield the fundamental units 276\kbd{bnf.fu}. More precisely, 277$$\kbd{bnf.fu}[j] = \prod_i X[i]^{U[i,j]}.$$ 278 279\item $G$ is a matrix of exponents whose columns yield the generators 280of principal ideals attached to the HNF of the \kbd{bnf} relation matrix 281between the maximal ideals of norm less \kbd{lim} (that generate the class 282group under GRH). More precisely, \kbd{bnf[5]} contains the prime factor 283base $P$ (its first $r$ elements being independant class group generators), 284\kbd{bnf[1]} contains a matrix $W$ in HNF in $M_r(\Z)$ and 285\kbd{bnf[2]}, contains a matrix $B$ in $M_{r \times c}(\Z)$. We define 286algebraic numbers $e_j$ for $j \leq r+c$ such that 287 288$$\kbd{\prod_{i \leq r} P_i^{W[i,j]}} = (e_j),\quad j \leq r$$ 289 290$$ P_j \kbd{\prod_{i \leq r} P_i^{B[i,j]}} = (e_j), j > r$$ 291 292\noindent Then $e_j = \prod_i X[i]^{E[i,j]}$. 293 294\fun{GEN}{bnf_has_fu}{GEN bnf} return fundamental units in expanded form if 295\kbd{bnf} contains them. Else return \kbd{NULL}. 296 297\fun{GEN}{bnf_compactfu}{GEN bnf} return fundamental units as a vector 298of algebraic numbers in compact form if \kbd{bnf} contains them. Else return 299\kbd{NULL}. 300 301\fun{GEN}{bnf_compactfu_mat}{GEN bnf} as a pair $(X,U)$, where $X$ is a 302vector of $S$-units and $U$ is a matrix with integer entries (without $0$ 303rows), see \kbd{bnf\_get\_sunits}, if \kbd{bnf} contains them. Else return 304\kbd{NULL}. 305 306\subsec{Extracting info from a \kbd{bnr} structure} 307 308These functions expect a true \var{bnr} argument. 309 310\fun{GEN}{bnr_get_bnf}{GEN bnr} returns the underlying \var{bnf}. 311 312\fun{GEN}{bnr_get_nf}{GEN bnr} returns the underlying \var{nf}. 313 314\fun{GEN}{bnr_get_clgp}{GEN bnr} returns the ray class group. 315 316\fun{GEN}{bnr_get_no}{GEN bnr} returns the ray class number. 317 318\fun{GEN}{bnr_get_cyc}{GEN bnr} returns the elementary divisors 319of the ray class group (cyclic components) $[d_1,\ldots, d_k]$, where 320$d_k \mid \ldots \mid d_1$. 321 322\fun{GEN}{bnr_get_gen}{GEN bnr} returns the generators $[g_1,\ldots,g_k]$ of 323the ray class group. Each $g_i$ has order $d_i$, and the full module of 324relations between the $g_i$ is generated by the $d_ig_i = 0$. Raise 325a generic error if the \var{bnr} does not contain the ray class group 326generators. 327 328\fun{GEN}{bnr_get_gen_nocheck}{GEN bnr} as \tet{bnr_get_gen} without 329checking whether generators are present. Do not use this unless 330you initialize the \var{bnr} yourself! 331 332\fun{GEN}{bnr_get_bid}{GEN bnr} returns the \var{bid} attached 333to the \var{bnr} modulus. 334 335\fun{GEN}{bnr_get_mod}{GEN bnr} returns the modulus attached 336to the \var{bnr}. 337 338\subsec{Extracting info from an \kbd{rnf} structure} 339 340These functions expect a true \var{rnf} argument, attached to an extension 341$L/K$, $K = \Q[y]/(T)$, $L = K[x]/(P)$. 342 343\fun{long}{rnf_get_degree}{GEN rnf} returns the \emph{relative} degree 344$[L:K]$. 345 346\fun{long}{rnf_get_absdegree}{GEN rnf} returns the absolute degree 347$[L:\Q]$. 348 349\fun{long}{rnf_get_nfdegree}{GEN rnf} returns the degree of the base 350field $[K:\Q]$. 351 352\fun{GEN}{rnf_get_nf}{GEN rnf} returns the base field $K$, an \var{nf} 353structure. 354 355\fun{GEN}{rnf_get_nfpol}{GEN rnf} returns the polynomial $T$ defining the 356base field $K$. 357 358\fun{long}{rnf_get_nfvarn}{GEN rnf} returns the variable $y$ attached to the 359base field $K$. 360 361\fun{GEN}{rnf_get_nfzk}{GEN rnf} returns the integer basis 362of the base field $K$. 363 364\fun{GEN}{rnf_get_pol}{GEN rnf} returns the relative polynomial defining 365$L/K$. 366 367\fun{long}{rnf_get_varn}{GEN rnf} returns the variable $x$ attached to $L$. 368 369\fun{GEN}{rnf_get_zk}{GEN nf} returns the relative integer basis generating 370$\Z_L$ as a $\Z_K$-module, as a pseudo-matrix $(A,I)$ in HNF. 371 372\fun{GEN}{rnf_get_disc}{GEN rnf} is the output $[\goth{d}, s]$ 373 of \kbd{rnfdisc}. 374 375\fun{GEN}{rnf_get_ramified_primes}{GEN rnf} returns the vector of rational 376primes below ramified primes in the relative extension, i.e. all prime 377numbers appearing in the factorization of 378\bprog 379 idealnorm(rnf_get_nf(rnf), rnf_get_disc(rnf)); 380@eprog 381 382\fun{GEN}{rnf_get_idealdisc}{GEN rnf} is the ideal discriminant $\goth{d}$ 383from \kbd{rnfdisc}. 384 385\fun{GEN}{rnf_get_index}{GEN rnf} is the index ideal $\goth{f}$ 386 387\fun{GEN}{rnf_get_polabs}{GEN rnf} returns an absolute polynomial defining 388$L/\Q$. 389 390\fun{GEN}{rnf_get_alpha}{GEN rnf} a root $\alpha$ of the polynomial 391defining the base field, modulo \kbd{polabs} (cf.~\kbd{rnfequation}) 392 393\fun{GEN}{rnf_get_k}{GEN rnf} 394a small integer $k$ such that $\theta = \beta + k\alpha$ is a root of 395\kbd{polabs}, where $\beta$ is a root of \kbd{pol} 396and $\alpha$ a root of the polynomial defining the base field, 397as in \tet{rnf_get_alpha} (cf.~also \kbd{rnfequation}). 398 399\fun{GEN}{rnf_get_invzk}{GEN rnf} contains $A^{-1}$, where $(A,I)$ 400is the chosen pseudo-basis for $\Z_L$ over $\Z_K$. 401 402\fun{GEN}{rnf_get_map}{GEN rnf} returns technical data attached to the map 403$K\to L$. Currently, this contains data from \kbd{rnfequation}, 404as well as the polynomials $T$ and $P$. 405 406\subsec{Extracting info from a \kbd{bid} structure} 407 408These functions expect a true \var{bid} argument, attached to a modulus $I 409= I_0 I_\infty$ in a number field $K$. 410 411\fun{GEN}{bid_get_mod}{GEN bid} returns the modulus attached to the \var{bid}. 412 413\fun{GEN}{bid_get_grp}{GEN bid} returns the Abelian group attached 414to $(\Z_K/I)^*$. 415 416\fun{GEN}{bid_get_ideal}{GEN bid} return the finite part $I_0$ 417of the \var{bid} modulus (an integer ideal). 418 419\fun{GEN}{bid_get_arch}{GEN bid} return the Archimedean part $I_\infty$ 420of the \var{bid} modulus as a vector of real places in vec01 format, 421see~\secref{se:signatures}. 422 423\fun{GEN}{bid_get_archp}{GEN bid} return the Archimedean part $I_\infty$ 424of the \var{bid} modulus, as a vector of real places in indices format 425see~\secref{se:signatures}. 426 427\fun{GEN}{bid_get_fact}{GEN bid} returns the ideal factorization 428$I_0 = \prod_i \goth{p}_i^{e_i}$. 429 430\fun{GEN}{bid_get_fact2}{GEN bid} as \kbd{bid\_get\_fact} with all factors 431$\goth{p}^1$ with $\goth{p}$ of norm $2$ removed from the factorization. 432(They play no role in the structure of $(\Z_K/I)^*$, except that the 433generators must be made coprime to them.) 434 435\tet{bid_get_ideal}$(\var{bid})$, via \kbd{idealfactor}. 436 437\fun{GEN}{bid_get_no}{GEN bid} returns the cardinality of the 438group $(\Z_K/I)^*$. 439 440\fun{GEN}{bid_get_cyc}{GEN bid} returns the elementary divisors 441of the group $(\Z_K/I)^*$ (cyclic components) $[d_1,\ldots, d_k]$, where $d_k 442\mid \ldots \mid d_1$. 443 444\fun{GEN}{bid_get_gen}{GEN bid} returns the generators of $(\Z_K/I)^*$ 445contained in \var{bid}. Raise a generic error if \var{bid} does not contain 446generators. 447 448\fun{GEN}{bid_get_gen_nocheck}{GEN bid} as \tet{bid_get_gen} without 449checking whether generators are present. Do not use this unless 450you initialize the \var{bid} yourself! 451 452\fun{GEN}{bid_get_sprk}{GEN bid} return a list of structures attached to the 453$(\Z_K/\goth{p}^e)^*$ where $\goth{p}^e$ divides $I_0$ exactly. 454 455\fun{GEN}{bid_get_sarch}{GEN bid} return the structure attached 456to $(\Z_K/I_\infty)^*$, by \kbd{nfarchstar}. 457 458\fun{GEN}{bid_get_U}{GEN bid} return the matrix with integral coefficients 459relating the local generators (from chinese remainders) to the global 460SNF generators (\kbd{\var{bid}.gen}). 461 462\subsec{Extracting info from a \kbd{znstar} structure} 463 464These functions expect an argument $G$ as returned by \kbd{znstar0(N, 1)}, 465attached to a positive $N$ and the abelian group $(\Z/N\Z)^*$. 466Let $(g_i)$ be the SNF generators, where $g_i$ has order $d_i$; 467we call $(g'_i)$ the (canonical) Conrey generators, where $g'_i$ has order 468$d'_i$. Both sets of generators have the same cardinality. 469 470\fun{GEN}{znstar_get_N}{GEN bid} return $N$. 471 472\fun{GEN}{znstar_get_faN}{GEN G} return the factorization \kbd{factor}$(N)$, 473$N = \prod_j p_j^{e_j}$. 474 475\fun{GEN}{znstar_get_pe}{GEN G} return the vector of primary factors 476$(p_j^{e_j})$. 477 478\fun{GEN}{znstar_get_no}{GEN G} the cardinality $\phi(N)$ of $G$. 479 480\fun{GEN}{znstar_get_cyc}{GEN G} elementary divisors $(d_i)$ of $(\Z/N\Z)^*$. 481 482\fun{GEN}{znstar_get_gen}{GEN G} SNF generators divisors $(g_i)$ 483of $(\Z/N\Z)^*$. 484 485\fun{GEN}{znstar_get_conreycyc}{GEN G} orders $(d'_i)$ of Conrey generators. 486 487\fun{GEN}{znstar_get_conreygen}{GEN G} Conrey generators $(g'_i)$. 488 489\fun{GEN}{znstar_get_U}{GEN G} a square matrix $U$ such that 490$(g_i) = U(g'_i)$. 491 492\fun{GEN}{znstar_get_Ui}{GEN G} a square matrix $U'$ such that 493$U'(g_i) = (g'_i)$. In general, $UU'$ will not be the identity. 494 495\subsec{Inserting info in a number field structure} 496 497If the required data is not part of the structure, it is computed then 498inserted, and the new value is returned. 499 500These functions expect a \kbd{bnf} argument: 501 502\fun{GEN}{bnf_build_cycgen}{GEN bnf} the \var{bnf} 503contains generators $[g_1,\ldots,g_k]$ of the class group, each with order 504$d_i$. Then $g_i^{d_i} = (x_i)$ is a principal ideal. This function returns 505the $x_i$ as a factorization matrix (\kbd{famat}) giving the element in 506factored form as a product of $S$-units. 507 508\fun{GEN}{bnf_build_matalpha}{GEN bnf} the class group was 509computed using a factorbase $S$ of prime ideals $\goth{p}_i$, $i \leq r$. 510They satisfy relations of the form $\prod_j \goth{p}_i^{e_{i,j}} = (\alpha_j)$, 511where the $e_{i,j}$ are given by the matrices $\var{bnf}[1]$ ($W$, singling 512out a minimal set of generators in $S$) and $\var{bnf}[2]$ ($B$, expressing the 513rest of $S$ in terms of the singled out generators). This function returns the 514$\alpha_j$ in factored form as a product of $S$-units. 515 516\fun{GEN}{bnf_build_units}{GEN bnf} returns a minimal set of generators 517for the unit group in expanded form. The first element is a torsion unit, the 518others have infinite order. This expands units in compact form contained 519in a \kbd{bnf} from \kbd{bnfinit}$(,1)$ and may be \emph{very} expensive 520if the units are huge. 521 522\fun{GEN}{bnf_build_cheapfu}{GEN bnf} as \kbd{bnf\_build\_units} but only 523expand units in compact form if the computation is inexpensive (a few seconds). 524Return \kbd{NULL} otherwise. 525 526These functions expect a \kbd{rnf} argument: 527 528\fun{GEN}{rnf_build_nfabs}{GEN rnf, long prec} given a \var{rnf} structure 529attached to $L/K$, (compute and) return an \var{nf} structure attached to $L$ 530at precision \kbd{prec}. 531 532\fun{void}{rnfcomplete}{GEN rnf} as \tet{rnf_build_nfabs} using the precision 533of $K$ for \kbd{prec}. 534 535\fun{GEN}{rnf_zkabs}{GEN rnf} returns a $\Z$-basis in HNF for $\Z_L$ as a 536pair $[T, v]$, where $T$ is \tet{rnf_get_polabs}$(\var{rnf})$ and $v$ 537a vector of elements lifted from $\Q[X]/(T)$. Note that the function 538\tet{rnf_build_nfabs} essentially applies \kbd{nfinit} to the output of this 539function. 540 541\subsec{Increasing accuracy} 542 543\fun{GEN}{nfnewprec}{GEN x, long prec}. Raise an exception if \kbd{x} 544is not a number field structure (\var{nf}, \var{bnf} or \var{bnr}). 545Otherwise, sets its accuracy to \kbd{prec} and return the new structure. 546This is mostly useful with \kbd{prec} larger than the accuracy to 547which \kbd{x} was computed, but it is also possible to decrease the accuracy 548of \kbd{x} (truncating relevant components, which may speed up later 549computations). This routine may modify the original \kbd{x} (see below). 550 551This routine is straightforward for \var{nf} structures, but for the 552other ones, it requires all principal ideals corresponding to the \var{bnf} 553relations in algebraic form (they are originally only available via floating 554point approximations). This in turn requires many calls to 555\tet{bnfisprincipal0}, which is often slow, and may fail if the initial 556accuracy was too low. In this case, the routine will not actually fail but 557recomputes a \var{bnf} from scratch! 558 559Since this process may be very expensive, the corresponding data is cached 560(as a \emph{clone}) in the \emph{original} \kbd{x} so that later precision 561increases become very fast. In particular, the copy returned by 562\kbd{nfnewprec} also contains this additional data. 563 564\fun{GEN}{bnfnewprec}{GEN x, long prec}. As \kbd{nfnewprec}, but extracts 565a \var{bnf} structure form \kbd{x} before increasing its accuracy, and 566returns only the latter. 567 568\fun{GEN}{bnrnewprec}{GEN x, long prec}. As \kbd{nfnewprec}, but extracts a 569\var{bnr} structure form \kbd{x} before increasing its accuracy, and 570returns only the latter. 571 572\fun{GEN}{nfnewprec_shallow}{GEN nf, long prec} 573 574\fun{GEN}{bnfnewprec_shallow}{GEN bnf, long prec} 575 576\fun{GEN}{bnrnewprec_shallow}{GEN bnr, long prec} Shallow functions 577underlying the above, except that the first argument must now have the 578corresponding number field type. I.e. one cannot call 579\kbd{nfnewprec\_shallow(nf, prec)} if \kbd{nf} is actually a \var{bnf}. 580 581\subsec{Number field arithmetic} 582The number field $K = \Q[X]/(T)$ is represented by an \kbd{nf} (or \kbd{bnf} 583or \kbd{bnr} structure). An algebraic number belonging to $K$ is given as 584 585\item a \typ{INT}, \typ{FRAC} or \typ{POL} (implicitly modulo $T$), or 586 587\item a \typ{POLMOD} (modulo $T$), or 588 589\item a \typ{COL}~\kbd{v} of dimension $N = [K:\Q]$, representing 590the element in terms of the computed integral basis $(e_i)$, as 591\bprog 592 sum(i = 1, N, v[i] * nf.zk[i]) 593@eprog 594The preferred forms are \typ{INT} and \typ{COL} of \typ{INT}. Routines can 595handle denominators but it is much more efficient to remove denominators 596first (\tet{Q_remove_denom}) and take them into account at the end. 597 598\misctitle{Safe routines} The following routines do not assume that their 599\kbd{nf} argument is a true \var{nf} (it can be any number field type, e.g.~a 600\var{bnf}), and accept number field elements in all the above forms. They 601return their result in \typ{COL} form. 602 603\fun{GEN}{nfadd}{GEN nf, GEN x, GEN y} returns $x+y$. 604 605\fun{GEN}{nfsub}{GEN nf, GEN x, GEN y} returns $x-y$. 606 607\fun{GEN}{nfdiv}{GEN nf, GEN x, GEN y} returns $x / y$. 608 609\fun{GEN}{nfinv}{GEN nf, GEN x} returns $x^{-1}$. 610 611\fun{GEN}{nfmul}{GEN nf,GEN x,GEN y} returns $xy$. 612 613\fun{GEN}{nfpow}{GEN nf,GEN x,GEN k} returns $x^k$, $k$ is in $\Z$. 614 615\fun{GEN}{nfpow_u}{GEN nf,GEN x, ulong k} returns $x^k$, $k\geq 0$. 616 617\fun{GEN}{nfsqr}{GEN nf,GEN x} returns $x^2$. 618 619\fun{long}{nfval}{GEN nf, GEN x, GEN pr} returns the valuation of $x$ at the 620maximal ideal $\goth{p}$ attached to the \var{prid} \kbd{pr}. 621Returns \kbd{LONG\_MAX} if $x$ is $0$. 622 623\fun{GEN}{nfnorm}{GEN nf,GEN x} absolute norm of $x$. 624 625\fun{GEN}{nftrace}{GEN nf,GEN x} absolute trace of $x$. 626 627\fun{GEN}{nfpoleval}{GEN nf, GEN pol, GEN a} evaluate the \typ{POL} \kbd{pol} 628(with coefficients in \kbd{nf}) on the algebraic number $a$ (also in $nf$). 629 630\fun{GEN}{FpX_FpC_nfpoleval}{GEN nf, GEN pol, GEN a, GEN p} evaluate the 631\kbd{FpX} \kbd{pol} on the algebraic number $a$ (also in $nf$). 632 633The following three functions implement trivial functionality akin to 634Euclidean division for which we currently have no real use. Of course, even if 635the number field is actually Euclidean, these do not in general implement a 636true Euclidean division. 637 638\fun{GEN}{nfdiveuc}{GEN nf, GEN a, GEN b} returns the algebraic integer 639closest to $x / y$. Functionally identical to \kbd{ground( nfdiv(nf,x,y) )}. 640 641\fun{GEN}{nfdivrem}{GEN nf, GEN a, GEN b} returns the vector $[q,r]$, where 642\bprog 643 q = nfdiveuc(nf, a, b); 644 r = nfsub(nf, a, nfmul(nf,q,b)); \\ or r = nfmod(nf,a,b); 645@eprog 646 647\fun{GEN}{nfmod}{GEN nf, GEN a, GEN b} returns $r$ such that 648\bprog 649 q = nfdiveuc(nf, a, b); 650 r = nfsub(nf, a, nfmul(nf,q,b)); 651@eprog 652 653\fun{GEN}{nf_to_scalar_or_basis}{GEN nf, GEN x} let $x$ be a number field 654element. If it is a rational scalar, i.e.~can be represented by a \typ{INT} 655or \typ{FRAC}, return the latter. Otherwise returns its basis representation 656(\tet{nfalgtobasis}). Shallow function. 657 658\fun{GEN}{nf_to_scalar_or_alg}{GEN nf, GEN x} let $x$ be a number field 659element. If it is a rational scalar, i.e.~can be represented by a \typ{INT} 660or \typ{FRAC}, return the latter. Otherwise returns its lifted \typ{POLMOD} 661representation (lifted \tet{nfbasistoalg}). Shallow function. 662 663\fun{GEN}{RgX_to_nfX}{GEN nf, GEN x} let $x$ be a \typ{POL} whose coefficients 664are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each 665coefficient and return the resulting new polynomial. Shallow function. 666 667\fun{GEN}{RgM_to_nfM}{GEN nf, GEN x} let $x$ be a \typ{MAT} whose coefficients 668are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each 669coefficient and return the resulting new matrix. Shallow function. 670 671\fun{GEN}{RgC_to_nfC}{GEN nf, GEN x} let $x$ be a \typ{COL} or 672\typ{VEC} whose coefficients 673are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each 674coefficient and return the resulting new \typ{COL}. Shallow function. 675 676\fun{GEN}{nfX_to_monic}{GEN nf, GEN T, GEN *pL} given a nonzero \typ{POL} $T$ 677with coefficients in \var{nf}, return a monic polynomial $f$ with integral 678coefficients such that $f(x) = C T(x/L)$ for some integral $L$ and some $C$ 679in \var{nf}. The function allows coefficients in basis form; if $L \neq 1$, 680it will return them in algebraic form. If \kbd{pL} is not \kbd{NULL}, 681\kbd{*pL} is set to $L$. Shallow function. 682 683\misctitle{Unsafe routines} The following routines assume that their \kbd{nf} 684argument is a true \var{nf} (e.g.~a \var{bnf} is not allowed) and their 685argument are restricted in various ways, see the precise description below. 686 687\fun{GEN}{nfX_disc}{GEN nf, GEN A} given an \var{nf} structure attached to a 688number field $K$ with main variable $Y$ (\kbd{nf\_get\_varn(nf)}), a \typ{POL} 689$A \in K[X]$ given as a lift in $\Q[X,Y]$ (implicitly modulo 690\kbd{nf\_get\_pol(nf)}, return the discriminant of $A$ as a \typ{POL} in 691$\Q[Y]$ (representing an element of $K$). 692 693\fun{GEN}{nfX_resultant}{GEN nf, GEN A, GEN B} analogous to \kbd{nfX\_disc}, 694$A, B\in \Q[X,Y]$; return the resultant of $A$ and $B$ with respect to $X$ 695as a \typ{POL} in $\Q[Y]$ (representing an element of $K$). 696 697\fun{GEN}{nfinvmodideal}{GEN nf, GEN x, GEN A} given an algebraic integer 698$x$ and a nonzero integral ideal $A$ in HNF, returns a $y$ such that 699$xy \equiv 1$ modulo $A$. 700 701\fun{GEN}{nfpowmodideal}{GEN nf, GEN x, GEN n, GEN ideal} given an algebraic 702integer $x$, an integer $n$, and a nonzero integral ideal $A$ in HNF, 703returns an algebraic integer congruent to $x^n$ modulo $A$. 704 705\fun{GEN}{nfmuli}{GEN nf, GEN x, GEN y} returns $x\times y$ assuming 706that both $x$ and $y$ are either \typ{INT}s or \kbd{ZV}s of the correct 707dimension. 708 709\fun{GEN}{nfsqri}{GEN nf, GEN x} returns $x^2$ assuming that $x$ is a \typ{INT} 710or a \kbd{ZV} of the correct dimension. 711 712\fun{GEN}{nfC_nf_mul}{GEN nf, GEN v, GEN x} given a \typ{VEC} or \typ{COL} 713$v$ of elements of $K$ in \typ{INT}, \typ{FRAC} or \typ{COL} form, multiply 714it by the element $x$ (arbitrary form). This is faster than multiplying 715coordinatewise since pre-computations related to $x$ (computing the 716multiplication table) are done only once. The components of the result 717are in most cases \typ{COL}s but are allowed to be \typ{INT}s or \typ{FRAC}s. 718Shallow function. 719 720\fun{GEN}{nfC_multable_mul}{GEN v, GEN mx} same as \tet{nfC_nf_mul}, 721where the argument $x$ is replaced by its multiplication table \kbd{mx}. 722 723\fun{GEN}{zkC_multable_mul}{GEN v, GEN x} same as \tet{nfC_nf_mul}, 724where $v$ is a vector of algebraic integers, $x$ is an algebraic 725integer, and $x$ is replaced by \kbd{zk\_multable}$(x)$. 726 727\fun{GEN}{zk_multable}{GEN nf, GEN x} given a \kbd{ZC} $x$ (implicitly 728representing an algebraic integer), returns the \kbd{ZM} giving the 729multiplication table by $x$. Shallow function (the first column of the result 730points to the same data as $x$). 731 732\fun{GEN}{zk_inv}{GEN nf, GEN x} given a \kbd{ZC} $x$ (implicitly 733representing an algebraic integer), returns the \kbd{QC} giving the 734inverse $x^{-1}$. Return \kbd{NULL} if $x$ is $0$. 735Not memory clean but safe for \kbd{gerepileupto}. 736 737\fun{GEN}{zkmultable_inv}{GEN mx} as \tet{zk_inv}, where 738the argument given is \kbd{zk\_multable}$(x)$. 739 740\fun{GEN}{zkmultable_capZ}{GEN mx} given a nonzero \var{zkmultable} 741\var{mx} attached to $x \in \Z_K$, return the positive generator of 742$(x)\cap \Z$. 743 744\fun{GEN}{zk_scalar_or_multable}{GEN nf, GEN x} given a \typ{INT} or \kbd{ZC} 745$x$, returns a \typ{INT} equal to $x$ if the latter is a scalar 746(\typ{INT} or \kbd{ZV\_isscalar}$(x)$ is 1) and 747\kbd{zk\_multable}$(\var{nf},x)$ otherwise. Shallow function. 748 749\subsec{Number field arithmetic for linear algebra} 750 751The following routines implement multiplication in a commutative $R$-algebra, 752generated by $(e_1 = 1,\dots, e_n)$, and given by a multiplication table $M$: 753elements in the algebra are $n$-dimensional \typ{COL}s, and the matrix 754$M$ is such that for all $1\leq i,j\leq n$, its column with index $(i-1)n + 755j$, say $(c_k)$, gives $e_i\cdot e_j = \sum c_k e_k$. It is assumed that 756$e_1$ is the neutral element for the multiplication (a convenient 757optimization, true in practice for all multiplications we needed to implement). 758If $x$ has any other type than \typ{COL} where an algebra element is 759expected, it is understood as $x e_1$. 760 761\fun{GEN}{multable}{GEN M, GEN x} given a column vector $x$, representing 762the quantity $\sum_{i=1}^N x_i e_i$, returns the multiplication table by $x$. 763Shallow function. 764 765\fun{GEN}{ei_multable}{GEN M, long i} returns the multiplication table 766by the $i$-th basis element $e_i$. Shallow function. 767 768\fun{GEN}{tablemul}{GEN M, GEN x, GEN y} returns $x\cdot y$. 769 770\fun{GEN}{tablesqr}{GEN M, GEN x} returns $x^2$. 771 772\fun{GEN}{tablemul_ei}{GEN M, GEN x, long i} returns $x\cdot e_i$. 773 774\fun{GEN}{tablemul_ei_ej}{GEN M, long i, long j} returns $e_i\cdot e_j$. 775 776\fun{GEN}{tablemulvec}{GEN M, GEN x, GEN v} given a vector $v$ of elements 777in the algebra, returns the $x\cdot v[i]$. 778 779The following routines implement naive linear algebra using the \emph{black box 780field} mechanism: 781 782\fun{GEN}{nfM_det}{GEN nf, GEN M} 783 784\fun{GEN}{nfM_inv}{GEN nf, GEN M} 785 786\fun{GEN}{nfM_mul}{GEN nf, GEN A, GEN B} 787 788\fun{GEN}{nfM_nfC_mul}{GEN nf, GEN A, GEN B} 789 790\subsec{Cyclotomic field arithmetic for linear algebra} 791 792The following routines implement modular algorithms in cyclotomic fields. In 793the prototypes, $P$ is the $n$-th cyclotomic polynomial $\Phi_n$ and $M$ is a 794\typ{MAT} with \typ{INT} or \kbd{ZX} coefficients, understood modulo $P$. 795 796\fun{GEN}{ZabM_ker}{GEN M, GEN P, long n} returns an integral (primitive) 797basis of the kernel of $M$. 798 799\fun{GEN}{ZabM_indexrank}{GEN M, GEN P, long n} return a vector with two 800 \typ{VECSMALL} components givin the rank profile of $M$. Inefficient 801(but correct) when $M$ does not have almost full column rank. 802 803\fun{GEN}{ZabM_inv}{GEN M, GEN P, long n, GEN *pden} 804assume that $M$ is invertible; return $N$ and sets the algebraic integer 805\kbd{*pden} (an integer or a \kbd{ZX}, implicitly modulo $P$) 806such that $M N = \kbd{den} \cdot \Id$. 807 808\fun{GEN}{ZabM_pseudoinv}{GEN M, GEN P, long n, GEN *pv, GEN *pden} analog 809of \kbd{ZM\_pseudoinv}. Not gerepile-safe. 810 811\fun{GEN}{ZabM_inv_ratlift}{GEN M, GEN P, long n, GEN *pden} 812return a primitive matrix $H$ such that $M H$ is $d$ times the identity 813and set \kbd{*pden} to $d$. Uses a multimodular algorithm, attempting 814rational reconstruction along the way. To be used when you expect that the 815denominator of $M^{-1}$ is much smaller than $\det M$ else use \kbd{ZabM\_inv}. 816 817\subsec{Cyclotomic trace} 818 819Given two positive integers $m$ and $n$ such that $K_m = \Q(\zeta_m) \subset 820K_n = \Q(\zeta_n)$, these functions implement relative trace computation from 821$K_n$ to $K_m$. This is in particular useful for character values. 822 823\fun{GEN}{Qab_trace_init}{long n, long m, GEN Pn, GEN Pm} assume 824that \kbd{Pn} is \kbd{polcyclo}$(n)$, \kbd{Pm} is \kbd{polcyclo}$(m)$ 825(both in the same variable), initialize a structure $T$ used in the following 826routines. Shallow function. 827 828\fun{GEN}{Qab_tracerel}{GEN T, long t, GEN z} assume $T$ was created 829by \tet{Qab_trace_init}, $t$ is an integer such that $0 \leq t < [K_n:K_m]$ 830and $z$ belongs to the cyclotomic field 831$\Q(\zeta_n) = \Q[X]/(\kbd{Pn})$. Return the normalized relative trace 832$[K_n:K_m]^{-1}\text{Tr}_{K_n/K_m} (\zeta_n^t z)$. Shallow function. 833 834\fun{GEN}{QabV_tracerel}{GEN T, long t, GEN v} $v$ being a vector of 835entries belonging to $K_n$, apply \tet{Qab_tracerel} to all entries. 836Shallow function. 837 838\fun{GEN}{QabM_tracerel}{GEN T, long t, GEN m} $m$ being a matrix 839of entries belonging to $K_n$, apply \tet{Qab_tracerel} to all entries. 840Shallow function. 841 842\subsec{Elements in factored form} 843 844Computational algebraic theory performs extensively linear 845algebra on $\Z$-modules with a natural multiplicative structure ($K^*$, 846fractional ideals in $K$, $\Z_K^*$, ideal class group), thereby raising 847elements to horrendously large powers. A seemingly innocuous elementary linear 848algebra operation like $C_i\leftarrow C_i - 10000 C_1$ involves raising 849entries in $C_1$ to the $10000$-th power. Understandably, it is often more 850efficient to keep elements in factored form rather than expand every such 851expression. A \emph{factorization matrix} (or \tev{famat}) is a two column 852matrix, the first column containing \emph{elements} (arbitrary objects which 853may be repeated in the column), and the second one contains \emph{exponents} 854(\typ{INT}s, allowed to be 0). By abuse of notation, the empty matrix 855\kbd{cgetg(1, t\_MAT)} is recognized as the trivial factorization (no 856element, no exponent). 857 858Even though we think of a \var{famat} with columns $g$ and $e$ 859as one meaningful object when fully expanded as $\prod g[i]^{e[i]}$, 860\var{famat}s are basically about concatenating information to keep track of 861linear algebra: the objects stored in a \var{famat} need not be 862operation-compatible, they will not even be compared to each other (with one 863exception: \tet{famat_reduce}). Multiplying two \var{famat}s just 864concatenates their elements and exponents columns. In a context where a 865\var{famat} is expected, an object $x$ which is not of type \typ{MAT} will be 866treated as the factorization $x^1$. The following functions all return 867\var{famat}s: 868 869\fun{GEN}{famat_mul}{GEN f, GEN g} $f$, $g$ are \var{famat}, 870or objects whose type is \emph{not} \typ{MAT} (understood as $f^1$ or $g^1$). 871Returns $fg$. The empty factorization is the neutral element for \var{famat} 872multiplication. 873 874\fun{GEN}{famat_mul_shallow}{GEN f, GEN g} shallow version of \tet{famat_mul}. 875 876\fun{GEN}{famat_pow}{GEN f, GEN n} $n$ is a \typ{INT}. If $f$ is a \typ{MAT}, 877assume it is a \var{famat} and return $f^n$ (multiplies the exponent column 878by $n$). Otherwise, understand it as an element and returns the $1$-line 879\var{famat} $f^n$. 880 881\fun{GEN}{famat_pow_shallow}{GEN f, GEN n} shallow version of \tet{famat_pow}. 882 883\fun{GEN}{famat_pows_shallow}{GEN f, long n} shallow version of \tet{famat_pow} 884where $n$ is a small integer. 885 886\fun{GEN}{famat_mulpow_shallow}{GEN f, GEN g, GEN e} \kbd{famat} 887corresponding to $f \cdot g^e$. Shallow function. 888 889\fun{GEN}{famat_mulpows_shallow}{GEN f, GEN g, long e} \kbd{famat} 890shallow version of \tet{famat_mulpow} where $e$ is a small integer. 891 892 893\fun{GEN}{famat_sqr}{GEN f} returns $f^2$. 894 895\fun{GEN}{famat_inv}{GEN f} returns $f^{-1}$. 896 897\fun{GEN}{famat_div}{GEN f, GEN g} return $f/g$. 898 899\fun{GEN}{famat_inv_shallow}{GEN f} shallow version of \tet{famat_inv}. 900 901\fun{GEN}{famat_div_shallow}{GEN f, GEN g} return $f/g$; shallow. 902 903\fun{GEN}{famat_Z_gcd}{GEN M, GEN n} restrict the \var{famat} $M$ to 904the prime power dividing $n$. 905 906\fun{GEN}{to_famat}{GEN x, GEN k} given an element $x$ and an exponent 907$k$, returns the \var{famat} $x^k$. 908 909\fun{GEN}{to_famat_shallow}{GEN x, GEN k} same, as a shallow function. 910 911\fun{GEN}{famatV_factorback}{GEN v, GEN e} given a vector of \kbd{famat}s 912$v$ and a \kbd{ZV} $e$ return the \kbd{famat} $\prod_i v[i]^{e[i]}$. Shallow 913function. 914 915\fun{GEN}{famatV_zv_factorback}{GEN v, GEN e} given a vector of \kbd{famat}s 916$v$ and a \kbd{zv} $e$ return the \kbd{famat} $\prod_i v[i]^{e[i]}$. Shallow 917function. 918 919\fun{GEN}{ZM_famat_limit}{GEN f, GEN limit} given a \var{famat} $f$ with 920\typ{INT} entries, returns a \var{famat} $g$ with all factors larger than 921\kbd{limit} multiplied out as the last entry (with exponent $1$). Shallow 922function. 923 924Note that it is trivial to break up a \var{famat} into its two constituent 925columns: \kbd{gel(f,1)} and \kbd{gel(f,2)} are the elements and exponents 926respectively. Conversely, \kbd{mkmat2} builds a (shallow) \var{famat} from 927two \typ{COL}s of the same length. 928 929\fun{GEN}{famat_reduce}{GEN f} given a \var{famat} $f$, returns a \var{famat} 930$g$ without repeated elements or 0 exponents, such that the expanded forms 931of $f$ and $g$ would be equal. Shallow function. 932 933\fun{GEN}{famat_remove_trivial}{GEN f} given a \var{famat} $f$, returns a 934\var{famat} $g$ without 0 exponents. Shallow function. 935 936\fun{GEN}{famatsmall_reduce}{GEN f} as \kbd{famat\_reduce}, but for exponents 937given by a \typ{VECSMALL}. 938 939\fun{GEN}{famat_to_nf}{GEN nf, GEN f} You normally never want to do this! 940This is a simplified form of \tet{nffactorback}, where we do not check the 941user input for consistency. The elements must be regular algebraic numbers 942(not \var{famat}s) over the given number field. 943 944Why should you \emph{not} want to use this function ? You should not need to: 945most of the functions useful in this context accept \var{famat}s as inputs, 946for instance \tet{nfsign}, \tet{nfsign_arch}, \tet{ideallog} and 947\tet{bnfisunit}. Otherwise, we can hopefully make good use of a quotient 948operation (modulo a fixed conductor, modulo $\ell$-th powers); see the end of 949\secref{se:Ideal_reduction}. If nothing else works, this function is 950available but is expected to be slow or even overflow the possibilities of 951the implementation. 952 953\fun{GEN}{famat_idealfactor}{GEN nf, GEN x} This is a good alternative for 954\kbd{famat\_to\_nf}, returning the factorization of the ideal generated by 955$x$. Since the answer is still given in factorized form, there is no risk of 956coefficient explosion when the exponents are large. Of course, all components 957of $x$ must be factored individually. 958 959\fun{GEN}{famat_nfvalrem}{GEN nf, GEN x, GEN pr, GEN *py} return the 960valuation $v$ at \kbd{pr} of \kbd{famat\_to\_nf}$(x)$, without performing the 961expansion of course. Notive that the output is a \kbd{GEN} since it cannot be 962assumed to fit into a \kbd{long}. If \kbd{py} is not \kbd{NULL} it contains 963the \kbd{famat} obtained by applying \kbd{nfvalrem} to each entry of the 964first column and copying the second column, with $0$ exponents removed. The 965expanded algebraic number is coprime to \kbd{pr} (in fact, all its components 966are coprime do \kbd{pr}) and equal to $x \tau^v$ where $\tau$ is the fixed 967anti-uniformizer for \kbd{pr} (\kbd{pr\_get\_tau}). 968 969\misctitle{Caveat} Receiving a \var{famat} input, \kbd{bnfisunit} assumes that 970it is an actual unit, since this is expensive to check, and normally 971easy to ensure from the user's side. 972 973\subsec{Ideal arithmetic} 974 975\misctitle{Conversion to HNF} 976 977\fun{GEN}{idealhnf}{GEN nf, GEN x} returns the HNF of the ideal defined by $x$: 978$x$ may be an algebraic number (defining a principal ideal), a maximal ideal 979(as given by \tet{idealprimedec} or \tet{idealfactor}), or a matrix whose 980columns give generators for the ideal. This last format is complicated, but 981useful to reduce general modules to the canonical form once in a while: 982 983\item if strictly less than $N = [K:Q]$ generators are given, $x$ is the 984$\Z_K$-module they generate, 985 986\item if $N$ or more are given, it is assumed that they form a $\Z$-basis 987(that the matrix has maximal rank $N$). This acts as \tet{mathnf} since the 988$\Z_K$-module structure is (taken for granted hence) not taken into account 989in this case. 990 991Extended ideals are also accepted, their principal part being discarded. 992 993\fun{GEN}{idealhnf0}{GEN nf, GEN x, GEN y} returns the HNF of the ideal 994generated by the two algebraic numbers $x$ and $y$. 995 996The following low-level functions underlie the above two: they all assume 997that \kbd{nf} is a true \var{nf} and perform no type checks: 998 999\fun{GEN}{idealhnf_principal}{GEN nf, GEN x} 1000returns the ideal generated by the algebraic number $x$. 1001 1002\fun{GEN}{idealhnf_shallow}{GEN nf, GEN x} is \tet{idealhnf} except that the 1003result may not be suitable for \kbd{gerepile}: if $x$ is already in HNF, we 1004return $x$, not a copy! 1005 1006\fun{GEN}{idealhnf_two}{GEN nf, GEN v} assuming $a = v[1]$ is a nonzero 1007\typ{INT} and $b = v[2]$ is an algebraic integer, possibly given in regular 1008representation by a \typ{MAT} (the multiplication table by $b$, see 1009\tet{zk_multable}), returns the HNF of $a\Z_K+b\Z_K$. 1010 1011\misctitle{Operations} 1012 1013The basic ideal routines accept all \kbd{nf}s (\var{nf}, \var{bnf}, 1014\var{bnr}) and ideals in any form, including extended ideals, and return 1015ideals in HNF, or an extended ideal when that makes sense: 1016 1017\fun{GEN}{idealadd}{GEN nf, GEN x, GEN y} returns $x+y$. 1018 1019\fun{GEN}{idealdiv}{GEN nf, GEN x, GEN y} returns $x/y$. Returns an extended 1020ideal if $x$ or $y$ is an extended ideal. 1021 1022\fun{GEN}{idealmul}{GEN nf, GEN x, GEN y} returns $xy$. 1023Returns an extended ideal if $x$ or $y$ is an extended ideal. 1024 1025\fun{GEN}{idealsqr}{GEN nf, GEN x} returns $x^2$. 1026Returns an extended ideal if $x$ is an extended ideal. 1027 1028\fun{GEN}{idealinv}{GEN nf, GEN x} returns $x^{-1}$. 1029Returns an extended ideal if $x$ is an extended ideal. 1030 1031\fun{GEN}{idealpow}{GEN nf, GEN x, GEN n} returns $x^n$. 1032Returns an extended ideal if $x$ is an extended ideal. 1033 1034\fun{GEN}{idealpows}{GEN nf, GEN ideal, long n} returns $x^n$. 1035Returns an extended ideal if $x$ is an extended ideal. 1036 1037\fun{GEN}{idealmulred}{GEN nf, GEN x, GEN y} returns an extended ideal equal 1038to $xy$. 1039 1040\fun{GEN}{idealpowred}{GEN nf, GEN x, GEN n} returns an extended ideal equal 1041to $x^n$. 1042 1043More specialized routines suffer from various restrictions: 1044 1045\fun{GEN}{idealdivexact}{GEN nf, GEN x, GEN y} returns $x/y$, assuming that 1046the quotient is an integral ideal. Much faster than \tet{idealdiv} when the 1047norm of the quotient is small compared to $Nx$. Strips the principal parts 1048if either $x$ or $y$ is an extended ideal. 1049 1050\fun{GEN}{idealdivpowprime}{GEN nf, GEN x, GEN pr, GEN n} returns $x 1051\goth{p}^{-n}$, assuming $x$ is an ideal in HNF or a rational number, and 1052\kbd{pr} a \var{prid} attached to $\goth{p}$. Not suitable for 1053\tet{gerepileupto} since it returns $x$ when $n = 0$. 1054 1055\fun{GEN}{idealmulpowprime}{GEN nf, GEN x, GEN pr, GEN n} returns $x 1056\goth{p}^{n}$, assuming $x$ is an ideal in HNF or a rational number, and 1057\kbd{pr} a \var{prid} attached to $\goth{p}$. Not suitable for 1058\tet{gerepileupto} since it retunrs $x$ when $n = 0$. 1059 1060\fun{GEN}{idealprodprime}{GEN nf, GEN v} given a list $v$ of prime ideals 1061in \var{prid} form, return their product. Assume that \var{nf} is a true 1062\var{nf} structure. 1063 1064\fun{GEN}{idealprod}{GEN nf, GEN v} given a list $v$ of ideals, 1065return their product. 1066 1067\fun{GEN}{idealprodval}{GEN nf, GEN v, GEN pr} given a list $v$ of ideals 1068return the valuation of their product at the prime ideal \kbd{pr}. 1069 1070\fun{GEN}{idealHNF_mul}{GEN nf, GEN x, GEN y} returns $xy$, assuming 1071than \kbd{nf} is a true \var{nf}, $x$ is an integral ideal in HNF and $y$ 1072is an integral ideal in HNF or precompiled form (see below). 1073For maximal speed, the second ideal $y$ may be given in precompiled form $y = 1074[a,b]$, where $a$ is a nonzero \typ{INT} and $b$ is an algebraic integer in 1075regular representation (a \typ{MAT} giving the multiplication table by the 1076fixed element): very useful when many ideals $x$ are going to be multiplied by 1077the same ideal $y$. This essentially reduces each ideal multiplication to 1078an $N\times N$ matrix multiplication followed by a $N\times 2N$ modular 1079HNF reduction (modulo $xy\cap \Z$). 1080 1081\fun{GEN}{idealHNF_inv}{GEN nf, GEN I} returns $I^{-1}$, assuming that 1082\kbd{nf} is a true \var{nf} and $x$ is a fractional ideal in HNF. 1083 1084\fun{GEN}{idealHNF_inv_Z}{GEN nf, GEN I} returns $(I\cap \Z) \cdot I^{-1}$, 1085assuming that \kbd{nf} is a true \var{nf} and $x$ is an integral fractional 1086ideal in HNF. The result is an integral ideal in HNF. 1087 1088\misctitle{Approximation} 1089 1090\fun{GEN}{idealaddtoone}{GEN nf, GEN A, GEN B} given to coprime integer ideals 1091$A$, $B$, returns $[a,b]$ with $a\in A$, $b\in B$, such that $a + b = 1$ 1092The result is reduced mod $AB$, so $a$, $b$ will be small. 1093 1094\fun{GEN}{idealaddtoone_i}{GEN nf, GEN A, GEN B} as \tet{idealaddtoone} except 1095that \kbd{nf} must be a true \var{nf}, and only $a$ is returned. 1096 1097\fun{GEN}{idealaddtoone_raw}{GEN nf, GEN A, GEN B} as \tet{idealaddtoone_i} 1098except that the reduction mod $AB$ is only performed modulo the lcm 1099of $A \cap \Z$ and $B\cap \Z$, which will increase the size of $a$. 1100 1101\fun{GEN}{zkchineseinit}{GEN nf, GEN A, GEN B, GEN AB} given two coprime 1102integral ideals $A$ and $B$ (in any form, preferably HNF) and 1103their product \kbd{AB} (in HNF form), initialize a solution to the Chinese 1104remainder problem modulo $AB$. 1105 1106\fun{GEN}{zkchinese}{GEN zkc, GEN x, GEN y} given \kbd{zkc} from 1107\kbd{zkchineseinit}, and $x$, $y$ two integral elements given as \typ{INT} 1108or \kbd{ZC}, return a $z$ modulo $AB$ such that 1109$z = x \mod A$ and $z = y \mod B$. 1110 1111\fun{GEN}{zkchinese1}{GEN zkc, GEN x} as \kbd{zkchinese} for $y = 1$; useful 1112to lift elements in a nice way from $(\Z_K/A_i)^*$ to $(\Z_K/\prod_i A_i)^*$. 1113 1114\fun{GEN}{hnfmerge_get_1}{GEN A, GEN B} given two square upper HNF integral 1115matrices $A$, $B$ of the same dimension $n > 0$, return $a$ in the image of 1116$A$ such that $1-a$ is in the image of $B$. (By abuse of notation we denote 1117$1$ the column vector $[1,0,\dots,0]$.) If such an $a$ does not exist, return 1118\kbd{NULL}. This is the function underlying \tet{idealaddtoone}. 1119 1120\fun{GEN}{idealaddmultoone}{GEN nf, GEN v} given a list of $n$ (globally) 1121coprime integer ideals $(v[i])$ returns an $n$-dimensional vector $a$ such that 1122$a[i]\in v[i]$ and $\sum a[i] = 1$. If $[K:\Q] = N$, this routine computes 1123the HNF reduction (with $Gl_{nN}(\Z)$ base change) of an $N\times nN$ matrix; 1124so it is well worth pruning "useless" ideals from the list (as long as the 1125ideals remain globally coprime). 1126 1127\fun{GEN}{idealapprfact}{GEN nf, GEN fx} as \tet{idealappr}, except that 1128$x$ \emph{must} be given in factored form. (This is unchecked.) 1129 1130\fun{GEN}{idealcoprime}{GEN nf, GEN x, GEN y}. Given 2 integral ideals $x$ and 1131$y$, returns an algebraic number $\alpha$ such that 1132$\alpha x$ is an integral ideal coprime to $y$. 1133 1134\fun{GEN}{idealcoprimefact}{GEN nf, GEN x, GEN fy} same as 1135\tet{idealcoprime}, except that $y$ is given in factored form, as from 1136\tet{idealfactor}. 1137 1138\fun{GEN}{idealchinese}{GEN nf, GEN x, GEN y} 1139 1140\fun{GEN}{idealchineseinit}{GEN nf, GEN x} 1141 1142\subsec{Maximal ideals} 1143 1144The PARI structure attached to maximal ideals is a \tev{prid} (for 1145\emph{pr}ime \emph{id}eal), usually produced by \tet{idealprimedec} 1146and \tet{idealfactor}. In this section, we describe the format; other sections 1147will deal with their daily use. 1148 1149A \var{prid} attached to a maximal ideal $\goth{p}$ stores the following 1150data: the underlying rational prime $p$, the ramification degree $e\geq 1$, 1151the residue field degree $f\geq 1$, a $p$-uniformizer $\pi$ with valuation 1152$1$ at $\goth{p}$ and valuation $0$ at all other primes dividing $p$ and 1153a rescaled ``anti-uniformizer'' $\tau$ used to compute valuations. This 1154$\tau$ is an algebraic integer such that $\tau/p$ has valuation $-1$ at 1155$\goth{p}$ and is integral at all other primes; in particular, 1156the valuation of $x\in\Z_K$ is positive if and only if the algebraic integer 1157$x\tau$ is divisible by $p$ (easy to check for elements in \typ{COL} form). 1158 1159\fun{GEN}{pr_get_p}{GEN pr} returns $p$. Shallow function. 1160 1161\fun{GEN}{pr_get_gen}{GEN pr} returns $\pi$. Shallow function. 1162 1163\fun{long}{pr_get_e}{GEN pr} returns $e$. 1164 1165\fun{long}{pr_get_f}{GEN pr} returns $f$. 1166 1167\fun{GEN}{pr_get_tau}{GEN pr} returns 1168$\tet{zk_scalar_or_multable}(\var{nf}, \tau)$, which is the \typ{INT}~$1$ 1169iff $p$ is inert, and a \kbd{ZM} otherwise. Shallow function. 1170 1171\fun{int}{pr_is_inert}{GEN pr} returns $1$ if $p$ is inert, $0$ otherwise. 1172 1173\fun{GEN}{pr_norm}{GEN pr} returns the norm $p^f$ of the maximal ideal. 1174 1175\fun{ulong}{upr_norm}{GEN pr} returns the norm $p^f$ of the maximal ideal, as 1176an \kbd{ulong}. Assume that the result does not overflow. 1177 1178\fun{GEN}{pr_hnf}{GEN pr} return the HNF of $\goth{p}$. 1179 1180\fun{GEN}{pr_inv}{GEN pr} return the fractional ideal $\goth{p}^{-1}$, in HNF. 1181 1182\fun{GEN}{pr_inv_p}{GEN pr} return the integral ideal $p \goth{p}^{-1}$, in HNF. 1183 1184\fun{GEN}{idealprimedec}{GEN nf, GEN p} list of maximal ideals dividing the 1185prime $p$. 1186 1187\fun{GEN}{idealprimedec_limit_f}{GEN nf, GEN p, long f} as \tet{idealprimedec}, 1188limiting the list to primes of residual degree $\leq f$ if $f$ is nonzero. 1189 1190\fun{GEN}{idealprimedec_limit_norm}{GEN nf, GEN p, GEN B} as 1191\tet{idealprimedec}, limiting the list to primes of norm $\leq B$, which 1192must be a positive \typ{INT}. 1193 1194\fun{GEN}{idealprimedec_galois}{GEN nf, GEN p} return a single prime ideal 1195above $p$. 1196 1197\fun{GEN}{idealprimedec_degrees}{GEN nf, GEN p} return a (sorted) 1198\typ{VECSMALL} containing the residue degrees $f(\goth{p} / p)$. 1199 1200\fun{GEN}{idealprimedec_kummer}{GEN nf, GEN Ti, long ei, GEN p} let \var{nf} 1201(true \var{nf}) correspond to $K = \Q[X]/(T)$ ($T$ monic \kbd{ZX}). 1202Let $T \equiv \prod_i T_i^{e_i} \pmod{p}$ be the factorization of $T$ and let 1203$(f,g,h)$ be as in Dedekind criterion for prime $p$: $f \equiv \prod T_i$, 1204$g \equiv \prod T_i^{e_i-1}$, $h = (T - fg) / p$, and let $D$ be the gcd 1205of $(f,g,h)$ in $\F_p[X]$. Let \kbd{Ti} (\kbd{FpX}) be one irreducible factor 1206$T_i$ not dividing $D$, with \kbd{ei} $= e_i$. This function returns the 1207prime ideal attached to $T_i$ by Kummer / Dedekind criterion, namely 1208$p \Z_K + T_i(\bar{X}) \Z_K$, which has ramification index $e_i$ over $p$. 1209Shallow function. 1210 1211\fun{GEN}{idealfactor}{GEN nf, GEN x} factors the fractional (hence nonzero) 1212ideal $x$ into prime ideal powers; return the factorization matrix. 1213 1214\fun{GEN}{idealfactor_limit}{GEN nf, GEN x, ulong lim} as \kbd{idealfactor}, 1215including only prime ideals above rational primes $< \kbd{lim}$. 1216 1217\fun{GEN}{idealfactor_partial}{GEN nf, GEN x, GEN L} return partial 1218factorization of fractional ideal $x$ as limited by argument $L$: 1219 1220\item $L = \kbd{NULL}$: as \kbd{idealfactor}; 1221 1222\item $L$ a \typ{INT}: as \kbd{idealfactor\_limit}; 1223 1224\item $L$ a vector of prime ideals of \var{nf} and/or rational primes 1225(standing for ``all prime ideal divisors of given rational prime'') limit 1226factorization to trial division by elements of $L$; do not include the 1227cofactor. 1228 1229\fun{GEN}{idealHNF_Z_factor}{GEN x, GEN *pvN, GEN *pvZ} given an integral 1230(nonzero) ideal $x$ in HNF, compute both the factorization of $Nx$ and 1231of $x\cap\Z$. This returns the vector of prime divisors of both 1232and sets \kbd{*pvN} and \kbd{*pvZ} to the corresponding \typ{VECSMALL} vector 1233of exponents for the factorization for the Norm and intersection with $\Z$ 1234respetively. 1235 1236\fun{GEN}{idealHNF_Z_factor_i}{GEN x, GEN fa, GEN *pvN, GEN *pvZ} internal 1237variant of \tet{idealHNF_Z_factor} where \kbd{fa} is either a partial 1238factorization of $x\cap \Z$ ($= x[1,1]$) or \kbd{NULL}. Returns the prime 1239divisors of $x$ above the rational primes in \kbd{fa} and attached \kbd{vN} 1240and \kbd{vZ}. If \kbd{fa} is \kbd{NULL}, use the full factorization, i.e. 1241identical to \tet{idealHNF_Z_factor}. 1242 1243\fun{GEN}{nf_pV_to_prV}{GEN}{nf, GEN P} given a vector of rational primes 1244$P$, return the vector of all prime ideals above the $P[i]$. 1245 1246\fun{GEN}{nf_deg1_prime}{GEN nf} let \kbd{nf} be a true \var{nf}. This 1247function returns a degree $1$ (unramified) prime ideal not dividing 1248\kbd{nf.index}. In fact it returns an ideal above the smallest prime 1249$p \geq [K:\Q]$ satisfying those conditions. 1250 1251\fun{GEN}{prV_lcm_capZ}{GEN L} given a vector $L$ of \var{prid} 1252(maximal ideals) return the squarefree positive integer generating their 1253lcm intersected with $\Z$. Not \kbd{gerepile}-safe. 1254 1255\fun{GEN}{pr_uniformizer}{GEN pr, GEN F} given a \var{prid} attached to 1256$\goth{p} / p$ and $F$ in $\Z$ divisible exactly by $p$, return an 1257$F$-uniformizer for \kbd{pr}, i.e. a $t$ in $\Z_K$ such that $v_{\goth{p}}(t) 1258= 1$ and $(t, F/\goth{p}) = 1$. Not \kbd{gerepile}-safe. 1259 1260\subsec{Decomposition group} 1261 1262\fun{GEN}{idealramfrobenius}{GEN nf, GEN gal, GEN pr, GEN ram} 1263Let $K$ be the number field defined by $nf$ and assume $K/\Q$ be a 1264Galois extension with Galois group given \kbd{gal=galoisinit(nf)}, 1265and that $pr$ is the prime ideal $\goth{P}$ in prid format, and that 1266$\goth{P}$ is ramified, and \kbd{ram} is its list of ramification groups as 1267output by \kbd{idealramgroups}. 1268This function returns a permutation of \kbd{gal.group} which defines an 1269automorphism $\sigma$ in the decomposition group of $\goth{P}$ 1270such that if $p$ is the unique prime number 1271in $\goth{P}$, then $\sigma(x)\equiv x^p\mod\P$ for all $x\in\Z_K$. 1272 1273\fun{GEN}{idealramfrobenius_aut}{GEN nf, GEN gal, GEN pr, GEN ram, GEN aut} 1274as \kbd{idealramfrobenius(nf, gal, pr, ram}. 1275 1276\fun{GEN}{idealramgroups_aut}{GEN nf, GEN gal, GEN pr, GEN aut} 1277as \kbd{idealramgroups(nf, gal, pr}. 1278 1279\fun{GEN}{idealfrobenius_aut}{GEN nf, GEN gal, GEN pr, GEN aut} 1280faster version of \kbd{idealfrobenius(nf, gal, pr} where 1281\kbd{aut} must be equal to \kbd{nfgaloispermtobasis(nf, gal)}. 1282 1283\subsec{Reducing modulo maximal ideals} 1284 1285\fun{GEN}{nfmodprinit}{GEN nf, GEN pr} returns an abstract \kbd{modpr} 1286structure, attached to reduction modulo the maximal ideal \kbd{pr}, in 1287\kbd{idealprimedec} format. From this data we can quickly project any 1288\kbd{pr}-integral number field element to the residue field. 1289 1290\fun{GEN}{modpr_get_pr}{GEN x} return the \kbd{pr} component from a \kbd{modpr} 1291structure. 1292 1293\fun{GEN}{modpr_get_p}{GEN x} return the $p$ component from a \kbd{modpr} 1294structure (underlying rational prime). 1295 1296\fun{GEN}{modpr_get_T}{GEN x} return the \kbd{T} component from a \kbd{modpr} 1297structure: either \kbd{NULL} (prime of degree $1$) or an irreducible 1298\kbd{FpX} defining the residue field over $\F_p$. 1299 1300In library mode, it is often easier to use directly 1301 1302\fun{GEN}{nf_to_Fq_init}{GEN nf, GEN *ppr, GEN *pT, GEN *pp} concrete 1303version of \kbd{nfmodprinit}: \kbd{nf} and \kbd{*ppr} are the inputs, the 1304return value is a \kbd{modpr} and \kbd{*ppr}, \kbd{*pT} and \kbd{*pp} are set 1305as side effects. 1306 1307The input \kbd{*ppr} is either a maximal ideal or already a \kbd{modpr} (in 1308which case it is replaced by the underlying maximal ideal). The residue field 1309is realized as $\F_p[X]/(T)$ for some monic $T\in\F_p[X]$, and we set 1310\kbd{*pT} to $T$ and \kbd{*pp} to $p$. Set $T = \kbd{NULL}$ if the prime has 1311degree $1$ and the residue field is $\F_p$. 1312 1313In short, this receives (or initializes) a \kbd{modpr} structure, and 1314extracts from it $T$, $p$ and $\goth{p}$. 1315 1316\fun{GEN}{nf_to_Fq}{GEN nf, GEN x, GEN modpr} returns an \kbd{Fq} congruent 1317to $x$ modulo the maximal ideal attached to \kbd{modpr}. The output is 1318canonical: all elements in a given residue class are represented by the same 1319\kbd{Fq}. 1320 1321\fun{GEN}{Fq_to_nf}{GEN x, GEN modpr} returns an \kbd{nf} element lifting 1322the residue field element $x$, either a \typ{INT} or an algebraic integer 1323in \kbd{algtobasis} format. 1324 1325\fun{GEN}{modpr_genFq}{GEN modpr} Returns an \kbd{nf} element whose image by 1326\tet{nf_to_Fq} is $X \pmod T$, if $\deg T>1$, else $1$. 1327 1328\fun{GEN}{zkmodprinit}{GEN nf, GEN pr} as \tet{nfmodprinit}, but we assume we 1329will only reduce algebraic integers, hence do not initialize data allowing to 1330remove denominators. More precisely, we can in fact still handle an $x$ whose 1331rational denominator is not $0$ in the residue field (i.e. if the valuation 1332of $x$ is nonnegative at all primes dividing $p$). 1333 1334\fun{GEN}{zk_to_Fq_init}{GEN nf, GEN *pr, GEN *T, GEN *p} as 1335\kbd{nf\_to\_Fq\_init}, able to reduce only $p$-integral elements. 1336 1337\fun{GEN}{zk_to_Fq}{GEN x, GEN modpr} as \kbd{nf\_to\_Fq}, for 1338a $p$-integral $x$. 1339 1340\fun{GEN}{nfM_to_FqM}{GEN M, GEN nf,GEN modpr} reduces a matrix 1341of \kbd{nf} elements to the residue field; returns an \kbd{FqM}. 1342 1343\fun{GEN}{FqM_to_nfM}{GEN M, GEN modpr} lifts an \kbd{FqM} to a matrix of 1344\kbd{nf} elements. 1345 1346\fun{GEN}{nfV_to_FqV}{GEN A, GEN nf,GEN modpr} reduces a vector 1347of \kbd{nf} elements to the residue field; returns an \kbd{FqV} 1348with the same type as \kbd{A} (\typ{VEC} or \typ{COL}). 1349 1350\fun{GEN}{FqV_to_nfV}{GEN A, GEN modpr} lifts an \kbd{FqV} to a vector of 1351\kbd{nf} elements (same type as \kbd{A}). 1352 1353\fun{GEN}{nfX_to_FqX}{GEN Q, GEN nf,GEN modpr} reduces a polynomial 1354with \kbd{nf} coefficients to the residue field; returns an \kbd{FqX}. 1355 1356\fun{GEN}{FqX_to_nfX}{GEN Q, GEN modpr} lifts an \kbd{FqX} to a polynomial 1357with coefficients in \kbd{nf}. 1358 1359The following functions are technical and avoid computing a true 1360\kbd{nfmodpr}: 1361 1362\fun{GEN}{pr_basis_perm}{GEN nf, GEN pr} given a true \var{nf} structure 1363and a prime ideal \kbd{pr} above $p$, return as a \typ{VECSMALL} the 1364$f(\goth{p}/p)$ indices $i$ such that the \kbd{nf.zk}$[i]$ mod \goth{p} 1365form an $\F_p$-basis of the residue field. 1366 1367\fun{GEN}{QXQV_to_FpM}{GEN v, GEN T, GEN p} let $p$ be a positive integer, 1368$v$ be a vector of $n$ polynomials with rational coefficients whose denominators 1369are coprime to $p$, and $T$ be a \kbd{ZX} (preferably monic) of 1370degree $d$ whose leading coefficient is coprime to $p$. Return the 1371$d \times n$ \kbd{FpM} whose columns are the $v[i]$ mod $T,p$ in the 1372canonical basis $1, X, \dots, X^{d-1}$, see \kbd{RgX\_to\_RgC}. 1373This is for instance useful when $v$ contains a $\Z$-basis of the maximal 1374order of a number field $\Q[X]/(P)$, $p$ is a prime not dividing the index of 1375$P$ and $T$ is an irreducible factor of $P$ mod $p$, attached to a maximal 1376ideal $\goth{p}$: left-multiplication by the matrix maps number field 1377elements (in basis form) to the residue field of $\goth{p}$. 1378 1379\subsec{Valuations} 1380 1381\fun{long}{nfval}{GEN nf, GEN x, GEN P} return $v_P(x)$ 1382 1383\misctitle{Unsafe functions} assume that $P$, $Q$ are \kbd{prid}. 1384 1385\fun{long}{ZC_nfval}{GEN x, GEN P} returns $v_P(x)$, 1386assuming $x$ is a \kbd{ZC}, representing a nonzero algebraic integer. 1387 1388\fun{long}{ZC_nfvalrem}{GEN x, GEN P, GEN *newx} returns $v = v_P(x)$, 1389assuming $x$ is a \kbd{ZC}, representing a nonzero algebraic integer, and sets 1390\kbd{*newx} to $x\tau^v$ which is an algebraic integer coprime to $p$. 1391 1392\fun{int}{ZC_prdvd}{GEN x, GEN P} returns $1$ is $P$ divides $x$ and 1393$0$ otherwise. Assumes that $x$ is a \kbd{ZC}, representing an algebraic 1394integer. Faster than computing $v_P(x)$. 1395 1396\fun{int}{pr_equal}{GEN P, GEN Q} returns 1 is $P$ and $Q$ represent 1397the same maximal ideal: they must lie above the same $p$ and share the same 1398$e,f$ invariants, but the $p$-uniformizer and $\tau$ element may differ. 1399Returns $0$ otherwise. 1400 1401\subsec{Signatures}\label{se:signatures} 1402 1403``Signs'' of the real embeddings of number field element are represented in 1404additive notation, using the standard identification $(\Z/2\Z, +) \to 1405(\{-1,1\},\times)$, $s\mapsto (-1)^s$. 1406 1407With respect to a fixed \kbd{nf} structure, a selection of real places (a 1408divisor at infinity) is normally given as a \typ{VECSMALL} of indices of the 1409roots \kbd{nf.roots} of the defining polynomial for the number field. For 1410compatibility reasons, in particular under GP, the (obsolete) \kbd{vec01} 1411form is also accepted: a \typ{VEC} with \kbd{gen\_0} or \kbd{gen\_1} entries. 1412 1413The following internal functions go back and forth between the two 1414representations for the Archimedean part of divisors (GP: $0/1$ vectors, 1415library: list of indices): 1416 1417\fun{GEN}{vec01_to_indices}{GEN v} given a \typ{VEC} $v$ with \typ{INT} entries 1418return as a \typ{VECSMALL} the list of indices $i$ such that $v[i] \neq 0$. 1419(Typically used with $0,1$-vectors but not necessarily so.) If $v$ is already 1420a \typ{VECSMALL}, return it: not suitable for \kbd{gerepile} in this case. 1421 1422\fun{GEN}{vecsmall01_to_indices}{GEN v} as 1423\bprog 1424 vec01_to_indices(zv_to_ZV(v)); 1425@eprog 1426 1427\fun{GEN}{indices_to_vec01}{GEN p, long n} return the $0/1$ vector of length 1428$n$ with ones exactly at the positions $p[1], p[2], \ldots$ 1429 1430\fun{GEN}{nfsign}{GEN nf,GEN x} $x$ being a number field element and \kbd{nf} 1431any form of number field, return the $0-1$-vector giving the signs of the 1432$r_1$ real embeddings of $x$, as a \typ{VECSMALL}. Linear algebra functions 1433like \tet{Flv_add_inplace} then allow keeping track of signs in series of 1434multiplications. 1435 1436If $x$ is a \typ{VEC} of number field elements, return the matrix whose 1437columns are the signs of the $x[i]$. 1438 1439\fun{GEN}{nfsign_arch}{GEN nf,GEN x,GEN arch} \kbd{arch} being a list of 1440distinct real places, either in \kbd{vec01} (\typ{VEC} with \kbd{gen\_0} or 1441\kbd{gen\_1} entries) or \kbd{indices} (\typ{VECSMALL}) form (see 1442\tet{vec01_to_indices}), returns the signs of $x$ at the corresponding 1443places. This is the low-level function underlying \kbd{nfsign}. 1444 1445\fun{int}{nfchecksigns}{GEN nf, GEN x, GEN pl} \var{pl} is a 1446\typ{VECSMALL} with $r_1$ components, all of which are in $\{-1,0,1\}$. 1447Return $1$ if $\sigma_i(x) \var{pl}[i] \geq 0$ for all $i$, and $0$ otherwise. 1448 1449\fun{GEN}{nfsign_units}{GEN bnf, GEN archp, int add_tu} 1450\kbd{archp} being a divisor at infinity in \kbd{indices} form (or \kbd{NULL} 1451for the divisor including all real places), return the signs at \kbd{archp} 1452of a \kbd{bnf.tu} and of system of fundamental units for the field 1453\kbd{bnf.fu}, in that order if \kbd{add\_tu} is set; and in the same order as 1454\kbd{bnf.fu} otherwise. 1455 1456\fun{GEN}{nfsign_fu}{GEN bnf, GEN archp} returns the signs at \kbd{archp} 1457of the fundamental units \kbd{bnf.fu}. This is an alias for 1458\kbd{nfsign\_units} with \kbd{add\_tu} unset. 1459 1460\fun{GEN}{nfsign_tu}{GEN bnf, GEN archp} returns the signs at \kbd{archp} 1461of the torsion unit generator \kbd{bnf.tu}. 1462 1463\fun{GEN}{nfsign_from_logarch}{GEN L, GEN invpi, GEN archp} given $L$ 1464the vector of the $\log \sigma(x)$, where $\sigma$ runs through the (real 1465or complex) embeddings of some number field, \kbd{invpi} being 1466a floating point approximation to $1/\pi$, and \kbd{archp} being a divisor 1467at infinity in \kbd{indices} form, return the signs of $x$ 1468at the corresponding places. This is the low-level function underlying 1469\kbd{nfsign\_units}; the latter is actually a trivial wrapper 1470\kbd{bnf} structures include the $\log \sigma(x)$ for a system of fundamental 1471units of the field. 1472 1473\fun{GEN}{set_sign_mod_divisor}{GEN nf, GEN x, GEN y, GEN sarch} 1474let $f = f_0f_\infty$ be a divisor, let \kbd{sarch} be the output of 1475\kbd{nfarchstar(nf, f0, finf)}, let $x$ encode a vector of signs at 1476the places of $f_\infty$ (see below), and let $y$ be a nonzero 1477number field element. Returns $z$ congruent to $y$ mod $f_0$ (integral if $y$ 1478is) such that $z$ and $x$ have the same signs at $f_\infty$. 1479 1480The following formats are supported for $x$: a $\{0,1\}$-vector of signs 1481as a \typ{VECSMALL} (0 for positive, 1 for negative); \kbd{NULL} for a 1482totally positive element (only $0$s); a number field element which 1483is replaced by its signature at $f_\infty$. 1484 1485\fun{GEN}{nfarchstar}{GEN nf, GEN f0, GEN finf} for a divisor $f = 1486f_0f_\infty$ represented by the integral ideal \kbd{f0} in HNF and 1487the \kbd{finf} in \kbd{indices} form, returns $(\Z_K/f_\infty)^*$ in a form 1488suitable for computations mod $f$. See \tet{set_sign_mod_divisor}. 1489 1490\fun{GEN}{idealprincipalunits}{GEN nf, GEN pr, long e} returns the 1491multiplicative group $(1 + \var{pr}) / (1 + \var{pr}^e)$ as an abelian group. 1492Faster than \tet{idealstar} when the norm of \var{pr} is large, since it 1493avoids (useless) work in the multiplicative group of the residue field. 1494 1495\subsec{Complex embeddings} 1496 1497\fun{GEN}{nfembed}{GEN nf, GEN x, long k} returns a floating point 1498approximation of the $k$-th embedding of $x$ (attached to the $k$-th 1499complex root in \kbd{nf.roots}). 1500 1501\fun{GEN}{nf_cxlog}{GEN nf, GEN x, long prec} return the vector of complex 1502logarithmic embeddings $(e_i \text{Log}(\sigma_i X))$ where $e_i = 1$ if $i \leq 1503r_1$ and $e_i = 2$ if $r_1 < i \leq r_2$ of $X = \kbd{Q\_primpart}(x)$. 1504Returns \kbd{NULL} if loss of accuracy. Not \kbd{gerepile}-clean but suitable 1505for \kbd{gerepileupto}. Allows $x$ in compact representation, in which 1506case \kbd{Q\_primpart} is taken componentwise. 1507 1508\fun{GEN}{nf_cxlog_normalize}{GEN nf, GEN x, long prec} an \var{nf} structure 1509attached to a number field $K$ and $x$ from \kbd{nf\_cxlog}$(\var{nf}, X)$ 1510(a column vector of complex logarithmic embeddings with $r_1 + r_2$ 1511components) and let $e = (e_1,\dots,e_{r_1+r_2})$. 1512Return 1513$$ x - \dfrac{\log \big(N_{K/\Q} X\big)}{[K:\Q]} e $$ 1514where the imaginary parts are further normalized modulo $2\pi i \cdot e$. 1515 1516The composition \kbd{nf\_cxlog} followed by~\kbd{nf\_cxlog\_normalize} is a 1517morphism from $(K^*/\Q_+^*, \times)$ to 1518$((\C/2\pi i\Z)^{r_1} \times (\C/4\pi i\Z)^{r_2}, +)$. 1519Its real part maps the units $\Z_K^*$ to a lattice in the hyperplane 1520$\sum_i x_i = 0$ in $\R^{r_1+r_2}$. 1521 1522\fun{GEN}{nfV_cxlog}{GEN nf, GEN x, long prec} applies \kbd{nf\_cxlog} 1523to each component of the vector $x$. Returns \kbd{NULL} if loss of 1524accuracy for even one component. Not \kbd{gerepile}-clean. 1525 1526\fun{GEN}{nflogembed}{GEN nf, GEN x, GEN *emb, long prec} 1527return the vector of real logarithmic embeddings $(e_i \text{Log}|\sigma_i x|)$ 1528where $e_i = 1$ if $i \leq r_1$ and $e_i = 2$ if $r_1 < i \leq r_2$. Returns 1529\kbd{NULL} if loss of accuracy. Not \kbd{gerepile}-clean. If \kbd{emb} 1530is non-\kbd{NULL} set it to $(e_i \sigma_i x)$. 1531Allows $x$ in compact representation, in which case \kbd{emb} is returned 1532in compact representation as well, as a factorization matrix (expanding the 1533factorization may overflowexponents). 1534 1535\subsec{Maximal order and discriminant, conversion to \kbd{nf} structure} 1536 1537A number field $K = \Q[X]/(T)$ is defined by a monic $T\in\Z[X]$. The 1538low-level function computing a maximal order is 1539 1540\fun{void}{nfmaxord}{nfmaxord_t *S, GEN T0, long flag}, where 1541the polynomial $T_0$ is squarefree with integer coefficients. Let $K$ be the 1542\'etale algebra $\Q[X]/(T_0)$ and let $T = \kbd{ZX\_Q\_normalize}(T_0)$, 1543i.e. $T = C T_0(X/L)$ is monic and integral for some $C,Q\in \Q$. 1544 1545The structure \tet{nfmaxord_t} is initialized by the call; it has the 1546following fields: 1547\bprog 1548 GEN T0, T, dT, dK; /* T0, T, discriminants of T and K */ 1549 GEN unscale; /* the integer L */ 1550 GEN index; /* index of power basis in maximal order */ 1551 GEN dTP, dTE; /* factorization of |dT|, primes / exponents */ 1552 GEN dKP, dKE; /* factorization of |dK|, primes / exponents */ 1553 GEN basis; /* Z-basis for maximal order of Q[X]/(T) */ 1554@eprog\noindent The exponent vectors are \typ{VECSMALL}. The primes 1555in \kbd{dTP} and \kbd{dKP} are pseudoprimes, not proven primes. We recommend 1556restricting to $T = T_0$, i.e. either to pass the input polynomial through 1557\tet{ZX_Q_normalize} \emph{before} the call, or to forget about $T_0$ 1558and go on with the polynomial $T$; otherwise $\kbd{unscale}\neq 1$, all data 1559is expressed in terms of $T\neq T_0$, and needs to be converted to $T_0$. For 1560instance to convert the basis to $\Q[X]/(T_0)$: 1561\bprog 1562 RgXV_unscale(S.basis, S.unscale) 1563@eprog 1564 1565Instead of passing $T$ (monic \kbd{ZX}), one can use the format 1566$[T,\var{listP}]$ as in \kbd{nfbasis} or \kbd{nfinit}, which computes an 1567order which is maximal at a set of primes, but need not be the maximal order. 1568 1569The \kbd{flag} is an or-ed combination of the binary flags, both of them 1570deprecated: 1571 1572\tet{nf_PARTIALFACT}: do not try to fully factor \kbd{dT} and only look for 1573primes less than \kbd{primelimit}. In that case, the elements in \kbd{dTP} 1574and \kbd{dKP} need not all be primes. But the resulting \kbd{dK}, 1575\kbd{index} and \kbd{basis} are correct provided there exists no prime $p > 1576\kbd{primelimit}$ such that $p^2$ divides the field discriminant \kbd{dK}. 1577This flag is \emph{deprecated}: the $[T,\var{listP}]$ format is safer and more 1578flexible. 1579 1580\tet{nf_ROUND2}: this flag is \emph{deprecated} and now ignored. 1581 1582\fun{void}{nfinit_basic}{nfmaxord_t *S, GEN T0} a wrapper around 1583\kbd{nfmaxord} (without the deprecated \kbd{flag}) that also accepts number 1584field structures (\var{nf}, \var{bnf}, \dots) for \kbd{T0}. 1585 1586\fun{GEN}{nfmaxord_to_nf}{nfmaxord_t *S, GEN ro, long prec} convert an 1587\tet{nfmaxord_t} to an \var{nf} structure at precision \kbd{prec}, 1588where \kbd{ro} is \kbd{NULL}. The argument \kbd{ro} may also be set to a 1589vector with $r_1 + r_2$ components containing the roots of \kbd{S->T} 1590suitably ordered, i.e. first $r_1$ \typ{REAL} roots, then $r_2$ \typ{COMPLEX} 1591representing the conguate pairs, but this is \emph{strongly discouraged}: the 1592format is error-prone, and it is hard to compute the roots to the right 1593accuracy in order to achieve \kbd{prec} accuracy for the \kbd{nf}. This 1594function uses the integer basis \kbd{S->basis} as is, \emph{without} 1595performing LLL-reduction. Unless the basis is already known to be reduced, 1596use rather the following higher-level function: 1597 1598\fun{GEN}{nfinit_complete}{nfmaxord_t *S, long flag, long prec} convert 1599an \tet{nfmaxord_t} to an \var{nf} structure at precision \kbd{prec}. 1600The \kbd{flag} has the same meaning as in \kbd{nfinitall}. If 1601\kbd{S->basis} is known to be reduced, it will be faster to 1602use \tet{nfmaxord_to_nf}. 1603 1604\fun{GEN}{indexpartial}{GEN T, GEN dT} $T$ a monic separable \kbd{ZX}, 1605\kbd{dT} is either \kbd{NULL} (no information) or a multiple of the 1606discriminant of $T$. Let $K = \Q[X]/(T)$ and $\Z_K$ its maximal order. 1607Returns a multiple of the exponent of the quotient group $\Z_K/(\Z[X]/(T))$. 1608In other word, a \emph{denominator} $d$ such that $d x\in\Z[X]/(T)$ for all 1609$x\in\Z_K$. 1610 1611\fun{GEN}{FpX_gcd_check}{GEN x, GEN y, GEN D} let $x$ and $y$ be two 1612coprime polynomials with integer coefficients and let $D$ be 1613a factor of the resultant of $x$ and $y$; try to factor $D$ by running the 1614Euclidean algorithm on $x$ and $y$ modulo $D$. This returns \kbd{NULL} 1615or a non trivial factor of $D$. This is the low-level function underlying 1616\kbd{poldiscfactors} (applied to $x$, \kbd{ZX\_deriv}$(x)$ and the 1617discriminant of $x$). It succeeds when $D$ has at least two prime divisors 1618$p$ and $q$ such that one sub-resultant of $x$ and $y$ is divisible by $p$ 1619but not by $q$. 1620 1621\subsec{Computing in the class group} 1622 1623We compute with arbitrary ideal representatives (in any of the various 1624formats seen above), and call 1625 1626\fun{GEN}{bnfisprincipal0}{GEN bnf, GEN x, long flag}. The \kbd{bnf} 1627structure already contains information about the class group in the form 1628$\oplus_{i=1}^n (\Z/d_i\Z) g_i$ for canonical integers $d_i$ 1629(with $d_n\mid\dots\mid d_1$ all $> 1$) and essentially random generators 1630$g_i$, which are ideals in HNF. We normally do not need the value of the 1631$g_i$, only that they are fixed once and for all and that any (nonzero) 1632fractional ideal $x$ can be expressed uniquely as $x = (t)\prod_{i=1}^n 1633g_i^{e_i}$, where $0 \leq e_i < d_i$, and $(t)$ is some principal ideal. 1634Computing $e$ is straightforward, but $t$ may be very expensive to obtain 1635explicitly. The routine returns (possibly partial) information about the pair 1636$[e,t]$, depending on \kbd{flag}, which is an or-ed combination of the 1637following symbolic flags: 1638 1639\item \tet{nf_GEN} tries to compute $t$. 1640Returns $[e,t]$, with $t$ an empty vector if the computation failed. This 1641flag is normally useless in nontrivial situations since the next two serve 1642analogous purposes in more efficient ways. 1643 1644\item \tet{nf_GENMAT} tries to compute $t$ in factored form, which is 1645much more efficient than \kbd{nf\_GEN} if the class group is moderately 1646large; imagine a small ideal $x = (t)g^{10000}$: the norm of $t$ has $10000$ 1647as many digits as the norm of $g$; do we want to see it as a vector 1648of huge meaningless integers? The idea is to compute $e$ first, which is 1649easy, then compute $(t)$ as $x \prod g_i^{-e_i}$ using successive 1650\tet{idealmulred}, where the ideal reduction extracts small principal ideals 1651along the way, eventually raised to large powers because of the binary 1652exponentiation technique; the point is to keep this principal part in 1653factored \emph{unexpanded} form. Returns $[e,t]$, with $t$ an empty vector if 1654the computation failed; this should be exceedingly rare, unless the initial 1655accuracy to which \kbd{bnf} was computed was ridiculously low (and then 1656\kbd{bnfinit} should not have succeeded either). Setting/unsetting 1657\kbd{nf\_GEN} has no effect when this flag is set. 1658 1659\item \tet{nf_GEN_IF_PRINCIPAL} tries to compute $t$ \emph{only} if the 1660ideal is principal ($e = 0$). Returns \kbd{gen\_0} if the ideal is not 1661principal. Setting/unsetting \kbd{nf\_GEN} has no effect when this flag is 1662set, but setting/unsetting \kbd{nf\_GENMAT} is possible. 1663 1664\item \tet{nf_FORCE} in the above, insist on computing $t$, even if it 1665requires recomputing a \kbd{bnf} from scratch. This is a last resort, and 1666normally the accuracy of a \kbd{bnf} can be increased without trouble, but it 1667may be that some algebraic information simply cannot be recovered from what 1668we have: see \tet{bnfnewprec}. It should be very rare, though. 1669 1670In simple cases where you do not care about $t$, you may use 1671 1672\fun{GEN}{isprincipal}{GEN bnf, GEN x}, which is a shortcut for 1673\kbd{bnfisprincipal0(bnf, x, 0)}. 1674 1675The following low-level functions are often more useful: 1676 1677\fun{GEN}{isprincipalfact}{GEN bnf, GEN C, GEN L, GEN f, long flag} is 1678about the same as \kbd{bnfisprincipal0} applied to $C \prod L[i]^{f[i]}$, 1679where the $L[i]$ are ideals, the $f[i]$ integers and $C$ is either an ideal 1680or \kbd{NULL} (omitted). Make sure to include \tet{nf_GENMAT} in \kbd{flag}! 1681 1682\fun{GEN}{isprincipalfact_or_fail}{GEN bnf, GEN C, GEN L, GEN f} is 1683for delicate cases, where we must be more clever than \kbd{nf\_FORCE} 1684(it is used when trying to increase the accuracy of a \var{bnf}, for 1685instance). If performs 1686\bprog 1687 isprincipalfact(bnf,C, L, f, nf_GENMAT); 1688@eprog\noindent 1689but if it fails to compute $t$, it just returns a \typ{INT}, which is the 1690estimated precision (in words, as usual) that would have been sufficient to 1691complete the computation. The point is that \kbd{nf\_FORCE} does exactly this 1692internally, but goes on increasing the accuracy of the \kbd{bnf}, then 1693discarding it, which is a major inefficiency if you intend to compute lots of 1694discrete logs and have selected a precision which is just too low. 1695(It is sometimes not so bad since most of the really expensive data is cached 1696in \kbd{bnf} anyway, if all goes well.) With this function, the \emph{caller} 1697may decide to increase the accuracy using \tet{bnfnewprec} (and keep the 1698resulting \kbd{bnf}!), or avoid the computation altogether. In any case the 1699decision can be taken at the place where it is most likely to be correct. 1700 1701\fun{void}{bnftestprimes}{GEN bnf, GEN B} is an ingredient to certify 1702unconditionnally a \kbd{bnf} computed assuming GRH, cf. \kbd{bnfcertify}. 1703Running this function successfully proves that the classes of all prime 1704ideals of norm $\leq B$ belong to the subgroup of the class group generated 1705by the factorbase used to compute the \kbd{bnf} (equal to the class group 1706under GRH). If the condition is not true, then (GRH is false and) the 1707function will run forever. 1708 1709If it is known that primes of norm less than $B$ generate the class group 1710(through variants of Minkowski's convex body or Zimmert's twin classes 1711theorems), then the true class group is proven to be a quotient of 1712\kbd{bnf.clgp}. 1713 1714\subsec{Floating point embeddings, the $T_2$ quadratic form} 1715 1716We assume the \var{nf} is a true \kbd{nf} structure, attached to a number 1717field $K$ of degree $n$ and signature $(r_1,r_2)$. We saw that 1718 1719\fun{GEN}{nf_get_M}{GEN nf} returns the $(r_1+r_2)\times n$ matrix $M$ 1720giving the embeddings of $K$, so that if $v$ is an $n$-th dimensional 1721\typ{COL} representing the element $\sum_{i=1}^n v[i] w_i$ of $K$, then 1722\kbd{RgM\_RgC\_mul(M,v)} represents the embeddings of $v$. Its first $r_1$ 1723components are real numbers (\typ{INT}, \typ{FRAC} or \typ{REAL}, usually the 1724latter), and the last $r_2$ are complex numbers (usually of \typ{COMPLEX}, 1725but not necessarily for embeddings of rational numbers). 1726 1727\fun{GEN}{embed_T2}{GEN x, long r1} assuming $x$ is the vector of floating point 1728embeddings of some algebraic number $v$, i.e. 1729\bprog 1730 x = RgM_RgC_mul(nf_get_M(nf), algtobasis(nf,v)); 1731@eprog\noindent returns $T_2(v)$. If the floating point embeddings themselves 1732are not needed, but only the values of $T_2$, it is more efficient to 1733restrict to real arithmetic and use 1734\bprog 1735 gnorml2( RgM_RgC_mul(nf_get_G(nf), algtobasis(nf,v))); 1736@eprog 1737 1738\fun{GEN}{embednorm_T2}{GEN x, long r1} analogous to \tet{embed_T2}, 1739applied to the \kbd{gnorm} of the floating point embeddings. Assuming that 1740\bprog 1741 x = gnorm( RgM_RgC_mul(nf_get_M(nf), algtobasis(nf,v)) ); 1742@eprog\noindent returns $T_2(v)$. 1743 1744\fun{GEN}{embed_roots}{GEN z, long r1} given a vector $z$ of $r_1+r_2$ 1745complex embeddings of the algebraic number $v$, return the $r_1+2r_2$ roots 1746of its characteristic polynomial. Shallow function. 1747 1748\fun{GEN}{embed_disc}{GEN z, long r1, long prec} given a vector $z$ of 1749$r_1+r_2$ complex embeddings of the algebraic number $v$, return a floating 1750point approximation of the discriminant of its characteristic polynomial as a 1751\typ{REAL} of precision \kbd{prec}. 1752 1753\fun{GEN}{embed_norm}{GEN x, long r1} given a vector $z$ of $r_1+r_2$ complex 1754embeddings of the algebraic number $v$, return (a floating point 1755approximation of) the norm of $v$. 1756 1757\subsec{Ideal reduction, low level} 1758 1759In the following routines \var{nf} is a true \kbd{nf}, attached to a number 1760field $K$ of degree $n$: 1761 1762\fun{GEN}{nf_get_Gtwist}{GEN nf, GEN v} assuming $v$ is a \typ{VECSMALL} 1763with $r_1+r_2$ entries, let 1764$$|| x ||_v^2 = \sum_{i=1}^{r_1+r_2} 2^{v_i}\varepsilon_i|\sigma_i(x)|^2,$$ 1765where as usual the $\sigma_i$ are the (real and) complex embeddings and 1766$\varepsilon_i = 1$, resp.~$2$, for a real, resp.~complex place. 1767This is a twisted variant of the $T_2$ quadratic form, the standard Euclidean 1768form on $K\otimes \R$. In applications, only the relative size of the $v_i$ 1769will matter. 1770 1771Let $G_v\in M_n(\R)$ be a square matrix such that if $x\in K$ is represented by 1772the column vector $X$ in terms of the fixed $\Z$-basis of $\Z_K$ in \var{nf}, 1773then 1774$$||x||_v^2 = {}^t (G_v X) \cdot G_v X.$$ 1775(This is a kind of Cholesky decomposition.) This function 1776returns a rescaled copy of $G_v$, rounded to nearest integers, specifically 1777\tet{RM_round_maxrank}$(G_v)$. 1778Suitable for \kbd{gerepileupto}, but does not collect garbage. For 1779convenience, also allow $v = $\kbd{NULL} (\tet{nf_get_roundG}) and $v$ 1780a \typ{MAT} as output from the function itself: in both these cases, 1781shallow function. 1782 1783\fun{GEN}{nf_get_Gtwist1}{GEN nf, long i}. Simple special case. Returns the 1784twisted $G$ matrix attached to the vector $v$ whose entries are all $0$ 1785except the $i$-th one, which is equal to $10$. 1786 1787\fun{GEN}{idealpseudomin}{GEN x, GEN G}. Let $x$, $G$ be two \kbd{ZM}s, 1788such that the product $Gx$ is well-defined. This returns a ``small'' integral 1789linear combinations of the columns of $x$, given by the LLL-algorithm applied 1790to the lattice $G x$. Suitable for \kbd{gerepileupto}, but does not collect 1791garbage. 1792 1793In applications, $x$ is an integral ideal, $G$ approximates a Cholesky form for 1794the $T_2$ quadratic form as returned by \tet{nf_get_Gtwist}, and we return 1795a small element $a$ in the lattice $(x,T_2)$. This is used to implement 1796\tet{idealred}. 1797 1798\fun{GEN}{idealpseudomin_nonscalar}{GEN x, GEN G}. As \tet{idealpseudomin}, 1799but we insist of returning a nonscalar $a$ (\kbd{ZV\_isscalar} is false), if 1800the dimension of $x$ is $> 1$. 1801 1802In the interpretation where $x$ defines an integral ideal on a fixed $\Z_K$ 1803basis whose first element is $1$, this means that $a$ is not rational. 1804 1805\fun{GEN}{idealpseudominvec}{GEN x, GEN G}. As \tet{idealpseudomin_nonscalar}, 1806but we return about $n^2/2$ nonscalar elements in $x$ with small $T_2$-norm, 1807where the dimension of $x$ is $n$. 1808 1809\fun{GEN}{idealpseudored}{GEN x, GEN G}. As \tet{idealpseudomin} but we 1810return the full reduced $\Z$-basis of $x$ as a \typ{MAT} instead of a single 1811vector. 1812 1813\fun{GEN}{idealred_elt}{GEN nf, GEN x} shortcut for 1814\bprog 1815 idealpseudomin(x, nf_get_roundG(nf)) 1816@eprog 1817 1818\subsec{Ideal reduction, high level} \label{se:Ideal_reduction} 1819 1820Given an ideal $x$ this means finding a ``simpler'' ideal in the same ideal 1821class. The public GP function is of course available 1822 1823\fun{GEN}{idealred0}{GEN nf, GEN x, GEN v} finds an $a\in K^*$ such that 1824$(a) x$ is integral of small norm and returns it, as an ideal in HNF. 1825What ``small'' means depends on the parameter $v$, see the GP description. 1826More precisely, $a$ is returned by \kbd{idealpseudomin}$((x_\Z) x^(-1),G)$ 1827divided by $x_\Z$, where $x_\Z = (x\cap \Z)$ and where $G$ is 1828\tet{nf_get_Gtwist}$(\var{nf}, v)$ for $v\neq \kbd{NULL}$ and 1829\tet{nf_get_roundG}$(\var{nf})$ otherwise. 1830 1831\noindent Usually one sets $v = \kbd{NULL}$ to obtain an element of small $T_2$ 1832norm in $x$: 1833 1834\fun{GEN}{idealred}{GEN nf, GEN x} is a shortcut for \kbd{idealred0(nf,x,NULL)}. 1835 1836The function \kbd{idealred} remains complicated to use: in order not to lose 1837information $x$ must be an extended ideal, otherwise the value of $a$ is lost. 1838There is a subtlety here: the principal ideal $(a)$ is easy to recover, but $a$ 1839itself is an instance of the principal ideal problem which is very difficult 1840given only an \var{nf} (once a \var{bnf} structure is available, 1841\tet{bnfisprincipal0} will recover it). 1842 1843\fun{GEN}{idealmoddivisor}{GEN bnr, GEN x} A proof-of-concept implementation, 1844useless in practice. If \kbd{bnr} is attached to some modulus $f$, returns a 1845``small'' ideal in the same class as $x$ in the ray class group modulo $f$. 1846The reason why this is useless is that using extended ideals with principal 1847part in a computation, there is a simple way to reduce them: simply reduce 1848the generator of the principal part in $(\Z_K/f)^*$. 1849 1850\fun{GEN}{famat_to_nf_moddivisor}{GEN nf, GEN g, GEN e, GEN bid} 1851given a true \var{nf} attached to a number field $K$, a \var{bid} structure 1852attached to a modulus $f$, and an algebraic number in factored form $\prod 1853g[i]^{e[i]}$, such that $(g[i],f) = 1$ for all $i$, returns a small element in 1854$\Z_K$ congruent to it mod $f$. Note that if $f$ contains places at infinity, 1855this includes sign conditions at the specified places. 1856 1857A simpler case when the conductor has no place at infinity: 1858 1859\fun{GEN}{famat_to_nf_modideal_coprime}{GEN nf, GEN g, GEN e, GEN f, GEN expo} 1860as above except that the ideal $f$ is now integral in HNF (no need for a full 1861\var{bid}), and we pass the exponent of the group $(\Z_K/f)^*$ as \kbd{expo}; 1862any multiple will also do, at the expense of efficiency. Of course if a 1863\var{bid} for $f$ is available, if is easy to extract $f$ and the exact value 1864of \kbd{expo} from it (the latter is the first elementary divisor in the 1865group structure). A useful trick: if you set \kbd{expo} to \emph{any} 1866positive integer, the result is correct up to \kbd{expo}-th powers, hence 1867exact if \kbd{expo} is a multiple of the exponent; this is useful when trying 1868to decide whether an element is a square in a residue field for instance! 1869(take \kbd{expo}$ = 2$). 1870 1871\fun{GEN}{nf_to_Fp_coprime}{GEN nf, GEN x, GEN modpr} this low-level function 1872is variant of 1873\tet{famat_to_nf_modideal_coprime}: \var{nf} is a true \var{nf} structure, 1874\kbd{modpr} is from \kbd{zkmodprinit} attached to a prime of degree $1$ above 1875the prime number $p$, and $x$ is either a number field element or a 1876\kbd{famat} factorization matrix. We finally assume that no component of $x$ 1877has a denominator $p$. 1878 1879What to do when the $g[i]$ are not coprime to $f$, but only $\prod 1880g[i]^{e[i]}$ is? Then the situation is more complicated, and we advise to 1881solve it one prime divisor of $f$ at a time. Let $v$ be the valuation 1882attached to a maximal ideal \kbd{pr}: 1883 1884\fun{GEN}{famat_makecoprime}{GEN nf, GEN g, GEN e, GEN pr, GEN prk, GEN expo} 1885returns an element in $(\Z_K/\kbd{pr}^k)^*$ congruent to the product 1886$\prod g[i]^{e[i]}$, assumed to be globally coprime to \kbd{pr}. As above, 1887\kbd{expo} is any positive multiple of the exponent of $(\Z_K/\kbd{pr}^k)^*$, 1888for instance $(Nv-1)p^{k-1}$, if $p$ is the underlying rational prime. You 1889may use other values of \kbd{expo} (see the useful trick in 1890\tet{famat_to_nf_modideal_coprime}). 1891 1892\fun{GEN}{sunits_makecoprime}{GEN g, GEN pr, GEN prk} is a 1893specialized variant that allows to precondition a vector of $g[i]$ assumed to 1894be integral primes or algebraic integers so that it becomes suitable for 1895\kbd{famat\_to\_nf\_modideal\_coprime} modulo \kbd{pr}. This is in particular 1896useful for the output of \kbd{bnf\_get\_sunits}. 1897 1898\fun{GEN}{Idealstarprk}{GEN nf, GEN pr, long k, long flag} same as 1899\kbd{Idealstar} for $I = \kbd{pr}^k$ 1900 1901\subsec{Class field theory} 1902 1903Under GP, a class-field theoretic description of a number field is given by a 1904triple $A$, $B$, $C$, where the defining set $[A,B,C]$ can have any of the 1905following forms: $[\var{bnr}]$, $[\var{bnr},\var{subgroup}]$, 1906$[\var{bnf},\var{modulus}]$, $[\var{bnf},\var{modulus},\var{subgroup}]$. 1907You can still use directly all of (\kbd{libpari}'s routines implementing) GP's 1908functions as described in Chapter~3, but they are often awkward in the context 1909of \kbd{libpari} programming. In particular, it does not make much sense to 1910always input a triple $A,B,C$ because of the fringe 1911$[\var{bnf},\var{modulus},\var{subgroup}]$. The first routine to call, is 1912thus 1913 1914\fun{GEN}{Buchray}{GEN bnf, GEN mod, long flag} initializes a \var{bnr} 1915structure from \kbd{bnf} and modulus \kbd{mod}. \kbd{flag} is an or-ed 1916combination of \kbd{nf\_GEN} (include generators) and \kbd{nf\_INIT} (if 1917omitted, do not return a \var{bnr}, only the ray class group as an abelian 1918group). In fact, the single most useful value of \kbd{flag} is 1919\kbd{nf\_INIT} to initialize a proper \var{bnr}: omitting 1920\kbd{nf\_GEN} saves a lot of time and will not adversely affect 1921any class field theoretic function; adding \kbd{nf\_GEN} makes debugging 1922easier. The flag 0 allows to compute only the ray class group structure but 1923will gain little time; if we only need the \emph{order} of the ray class 1924group, then \tet{bnrclassno} is fastest. 1925 1926Now we have a proper \var{bnr} encoding a \kbd{bnf} and a modulus, we no longer 1927need the $[\var{bnf},\var{modulus}]$ and 1928$[\var{bnf},\var{modulus},\var{subgroup}]$ forms, which would internally call 1929\tet{Buchray} anyway. Recall that a subgroup $H$ is given by a matrix in HNF, 1930whose column express generators of $H$ on the fixed generators of the ray class 1931group that stored in our \var{bnr}. You may also code the trivial subgroup by 1932\kbd{NULL}. It is also allowed to replace $H$ by a character $\chi$ of the ray 1933class group modulo \kbd{mod}: it represents the subgroup $\text{Ker} \chi$. 1934 1935\fun{GEN}{bnr_subgroup_check}{GEN bnr, GEN H, GEN *pdeg} given a \var{bnr} 1936attached to a modulus \var{mod}, check whether $H$ represents a congruence 1937subgroup (of the ray class group modulo \var{mod}) and returns a normalized 1938representation: \kbd{NULL} for the trivial subgroup, or in HNF, reduced 1939modulo the elementary divisors of the ray class group. In particular, if $H$ 1940is a character of the ray class group, the returned value is the character 1941kernel. If \kbd{pdeg} is not \kbd{NULL}, \kbd{*pdeg} is set to the degree of the 1942attached class field: the index of $H$ in the ray class group. 1943 1944\fun{GEN}{bnrconductor}{GEN bnr, GEN H, long flag} see the documentation of 1945the GP function. 1946 1947\fun{GEN}{bnrconductor_factored}{GEN bnr, GEN H} 1948return a pair $[F,\var{fa}]$ where $F$ is the conductor and \var{fa} is the 1949factorization of the finite part of the conductor. Shallow function. 1950 1951\fun{GEN}{bnrconductor_raw}{GEN bnr, GEN H} return the conductor of $H$. 1952Shallow function. 1953 1954\fun{long}{bnrisconductor}{GEN bnr, GEN H} returns 1 is the class field 1955defined by the subgroup $H$ (of the ray class group mod $f$ coded in \kbd{bnr}) 1956has conductor $f$. Returns 0 otherwise. 1957 1958\fun{GEN}{ideallog_units}{GEN bnf, GEN bid} return the images of the units 1959generators \kbd{bnf.tu} and \kbd{bnf.tu} in the finite abelian group 1960$(\Z_K/f)^*$ attached to \kbd{bid}. 1961 1962\fun{GEN}{ideallog_units0}{GEN bnf, GEN bid, GEN N} let 1963$G = (\Z_K/f)^*$ be the finite abelian group attached to \kbd{bid}. 1964Return the images of the units generators \kbd{bnf.tu} and \kbd{bnf.tu} in 1965$G / G^N$. If $N$ is \kbd{NULL}, same as \tet{ideallog_units}. 1966 1967\fun{GEN}{bnrchar_primitive}{GEN bnr, GEN chi, GEN bnrc} 1968Given a normalized character $\kbd{chi} = [d,c]$ on \kbd{bnr.clgp} (see 1969\tet{char_normalize}) of conductor \kbd{bnrc.mod}, compute the primitive 1970character \kbd{chic} on \kbd{bnrc.clgp} equivalent to \kbd{chi}, given as a 1971normalized character $[D,C]$ : \kbd{chic(bnrc.gen[i])} is $\zeta_D^{C[i]}$, 1972where $D$ is minimal. It is easier to use \kbd{bnrconductor\_i(bnr,chi,2)}, 1973but the latter recomputes \kbd{bnrc} for each new character. 1974 1975\fun{GEN}{bnrchar_primitive_raw}{GEN bnr, GEN chi, GEN bnrc} as 1976\tet{bnrchar_primitive}, with \kbd{chi} a regular (unnormalized) character 1977on \kbd{bnr.clgp} of conductor \kbd{bnrc.mod}. Return a regular 1978(unnormalized) primitive character on \kbd{bnrc}. 1979 1980\fun{GEN}{bnrdisc}{GEN bnr, GEN H, long flag} returns the discriminant and 1981signature of the class field defined by \kbd{bnr} and $H$. See the description 1982of the GP function for details. \fl\ is an or-ed combination of the flags 1983\tet{rnf_REL} (output relative data) and \tet{rnf_COND} (return 0 unless the 1984modulus is the conductor). 1985 1986\fun{GEN}{bnrsurjection}{GEN BNR, GEN bnr} \kbd{BNR} and \kbd{bnr} 1987defined over the same field $K$, for moduli $F$ and $f$ with 1988$F\mid f$, returns the canonical surjection 1989$\text{Cl}_K(F)\to \text{Cl}_K(f)$ as a triple $[M,\var{cyc}_F,\var{cyc}_f]$. 1990$M$ gives the image of the fixed ray class group generators of \kbd{BNR} in 1991terms of the ones in \kbd{bnr}, $\var{cyc}_F$ and $\var{cyc}_f$ are the cyclic 1992structures of \kbd{BNR} and \kbd{bnr} respectively (as per \tet{bnr_get_cyc}). 1993Shallow function. 1994 1995\fun{GEN}{ABC_to_bnr}{GEN A, GEN B, GEN C, GEN *H, int addgen} This is a 1996quick conversion function designed to go from the too general (inefficient) 1997$A$, $B$, $C$ form to the preferred \var{bnr}, $H$ form for class fields. 1998Given $A$, $B$, $C$ as explained above (omitted entries coded by \kbd{NULL}), 1999return the attached \var{bnr}, and set $H$ to the attached subgroup. If 2000\kbd{addgen} is $1$, make sure that if the \var{bnr} needed to be computed, 2001then it contains generators. 2002 2003\subsec{Grunwald--Wang theorem} 2004 2005\fun{GEN}{nfgwkummer}{GEN nf, GEN Lpr, GEN Ld, GEN pl, long var} 2006low-level version of \kbd{nfgrunwaldwang}, assuming that \kbd{nf} contains 2007suitable roots of unity, and directly using Kummer theory to construct the 2008extension. 2009 2010\fun{GEN}{bnfgwgeneric}{GEN bnf, GEN Lpr, GEN Ld, GEN pl, long var} 2011low-level version of \kbd{nfgrunwaldwang}, assuming that \kbd{bnf} is a 2012\kbd{bnfinit} structure, and calling \kbd{rnfkummer} to construct the extension. 2013 2014\subsec{Relative equations, Galois conjugates} 2015 2016\fun{GEN}{nfissquarefree}{GEN nf, GEN P} given $P$ a polynomial with 2017coefficients in \var{nf}, return $1$ is $P$ is squarefree, and $0$ 2018otherwise. If is allowed (though less efficient) to replace \var{nf} 2019by a monic \kbd{ZX} defining the field. 2020 2021\fun{GEN}{rnfequationall}{GEN A, GEN B, long *pk, GEN *pLPRS} $A$ is either an 2022\var{nf} type (corresponding to a number field $K$) or an irreducible \kbd{ZX} 2023defining a number field $K$. $B$ is an irreducible polynomial in $K[X]$. 2024Returns an absolute equation $C$ (over $\Q$) for the number field $K[X]/(B)$. 2025$C$ is the characteristic polynomial of $b + k a$ for some roots $a$ of $A$ 2026and $b$ of $B$, and $k$ is a small rational integer. Set \kbd{*pk} to $k$. 2027 2028If \kbd{pLPRS} is not \kbd{NULL} set it to $[h_0, h_1]$, $h_i\in \Q[X]$, 2029where $h_0+h_1 Y$ is the last nonconstant polynomial in the pseudo-Euclidean 2030remainder sequence attached to $A(Y)$ and $B(X-kY)$, leading to $C = 2031\text{Res}_Y(A(Y), B(X-kY))$. In particular $a := -h_0/h_1$ is a root of $A$ 2032in $\Q[X]/(C)$, and $X - ka$ is a root of $B$. 2033 2034\fun{GEN}{nf_rnfeq}{GEN A, GEN B} wrapper around \tet{rnfequationall} to allow 2035mapping $K\to L$ (\kbd{eltup}) and converting elements of $L$ 2036between absolute and relative form (\kbd{reltoabs}, \kbd{abstorel}), 2037\emph{without} computing a full \var{rnf} structure, which is useful if the 2038relative integral basis is not required. In fact, since $A$ may be a \typ{POL} 2039or an \var{nf}, the integral basis of the base field is not needed either. The 2040return value is the same as \tet{rnf_get_map}. Shallow function. 2041 2042\fun{GEN}{nf_rnfeqsimple}{GEN A, GEN B} as \tet{nf_rnfeq} except some 2043fields are omitted, so that only the \tet{abstorel} operation is supported. 2044Shallow function. 2045 2046\fun{GEN}{eltabstorel}{GEN rnfeq, GEN x} \kbd{rnfeq} is as 2047given by \tet{rnf_get_map} (but in this case \tet{rnfeltabstorel} is more 2048robust), \tet{nf_rnfeq} or \tet{nf_rnfeqsimple}, return $x$ as an element 2049of $L/K$, i.e. as a \typ{POLMOD} with \typ{POLMOD} coefficients. Shallow 2050function. 2051 2052\fun{GEN}{eltabstorel_lift}{GEN rnfeq, GEN x} same as \tet{eltabstorel}, 2053except that $x$ is returned in partially lifted form, i.e.~ as a 2054\typ{POL} with \typ{POLMOD} coefficients. 2055 2056\fun{GEN}{eltreltoabs}{GEN rnfeq, GEN x} \kbd{rnfeq} is as given by 2057\tet{rnf_get_map} (but in this case \tet{rnfeltreltoabs} is more robust) 2058or \tet{nf_rnfeq}, return $x$ in absolute form. 2059 2060\fun{GEN}{nf_nfzk}{GEN nf, GEN rnfeq} \kbd{rnfeq} as 2061given by \tet{nf_rnfeq}, \kbd{nf} a true \var{nf} structure, return a 2062a suitable representation of \kbd{nf.zk} allowing quick 2063computation of the map $K\to L$ by the function \tet{nfeltup}, \emph{without} 2064computing a full \var{rnf} structure, which is useful if the relative 2065integral basis is not required. The computed value is the same as in 2066\tet{rnf_get_nfzk}. Shallow function. 2067 2068\fun{GEN}{nfeltup}{GEN nf, GEN x, GEN zknf} \kbd{zknf} and is initialized by 2069\tet{nf_nfzk} or \tet{rnf_get_nfzk} (but in this case \tet{rnfeltup} is more 2070robust); \kbd{nf} is a true \var{nf} structure for $K$, returns $x \in K$ as 2071a (lifted) element of $L$, in absolute form. 2072 2073\fun{GEN}{rnfdisc_factored}{GEN nf, GEN pol, GEN *pd} variant of \kbd{rnfdisc} 2074returning the relative discriminant ideal \emph{factorization}, and setting 2075\kbd{*pd} to the discriminant as an element in $K^*/(K^*)^2$. Shallow 2076function. 2077 2078\fun{GEN}{Rg_nffix}{const char *f, GEN T, GEN c, int lift} given 2079a \kbd{ZX} $T$ and a ``coefficient'' $c$ supposedly belonging to $\Q[y]/(T)$, 2080check whether this is a the case and return a cleaned up version of $c$. 2081The string $f$ is the calling function name, used to report errors. 2082 2083This means that $c$ must be one of \typ{INT}, \typ{FRAC}, \typ{POL} in the 2084variable $y$ with rational coefficients, or \typ{POLMOD} modulo $T$ which lift 2085to a rational \typ{POL} as above. The cleanup consists in the following 2086improvements: 2087 2088\item \typ{POL} coefficients are reduced modulo $T$. 2089 2090\item \typ{POL} and \typ{POLMOD} belonging to $\Q$ are converted to rationals, 2091\typ{INT} or \typ{FRAC}. 2092 2093\item if \kbd{lift} is nonzero, convert \typ{POLMOD} to \typ{POL}, 2094and otherwise convert \typ{POL} to \typ{POLMOD}s modulo $T$. 2095 2096\fun{GEN}{RgX_nffix}{const char *f, GEN T, GEN P, int lift} check whether 2097$P$ is a polynomials with coefficients in the number field defined by the 2098absolute equation $T(y) = 0$, where $T$ is a \kbd{ZX} and returns a cleaned 2099up version of $P$. This checks whether $P$ is indeed a \typ{POL} 2100with variable compatible with coefficients in $\Q[y]/(T)$, i.e. 2101\bprog 2102 varncmp(varn(P), varn(T)) < 0 2103@eprog\noindent and applies \tet{Rg_nffix} to each coefficient. 2104 2105\fun{GEN}{RgV_nffix}{const char *f, GEN T, GEN P, int lift} as \tet{RgX_nffix} 2106for a vector of coefficients. 2107 2108\fun{GEN}{polmod_nffix}{const char *f, GEN rnf, GEN x, int lift} given 2109a \typ{POLMOD} $x$ supposedly defining an element of \var{rnf}, check this 2110and perform \tet{Rg_nffix} cleanups. 2111 2112\fun{GEN}{polmod_nffix2}{const char *f, GEN T, GEN P, GEN x, int lift} 2113as in \tet{polmod_nffix}, where the relative extension is explicitly 2114defined as $L = (\Q[y]/(T))[x]/(P)$, instead of by an \kbd{rnf} structure. 2115 2116\fun{long}{numberofconjugates}{GEN T, long pinit} returns a quick 2117multiple for the number of $\Q$-automorphism of the (integral, monic) 2118\typ{POL} $T$, from modular factorizations, starting from prime \kbd{pinit} 2119(you can set it to $2$). This upper bounds often coincides with the 2120actual number of conjugates. Of course, you should use \tet{nfgaloisconj} 2121to be sure. 2122 2123\fun{GEN}{nfroots_if_split}{GEN *pt, GEN T} let \kbd{*pt} point 2124either to a number field structure or an irreducible \kbd{ZX}, defining 2125a number field $K$. Given $T$ a monic squarefree polynomial with 2126coefficients in $\Z_K$, return the list of roots of \kbd{pol} in $K$ 2127if the polynomial splits completely, and \kbd{NULL} otherwise. 2128In other words, this checks whether $K[X]/(T)$ is normal over $K$ (hence 2129Galois since $T$ is separable by assumption). 2130 2131In the case where \kbd{*pT} is a \kbd{ZX}, the function has to compute 2132internally a conditional \kbd{nf} attached to $K$ , whose \kbd{nf.zk} may not 2133define the maximal order $\Z_K$ (see \kbd{nfroots}); \kbd{*pT} is then 2134replaced by the conditional \kbd{nf} to avoid losing that information. 2135 2136\subsec{Cyclotomics units} 2137 2138\fun{GEN}{nfrootsof1}{GEN nf} returns a two-component vector $[w,z]$ where $w$ 2139is the number of roots of unity in the number field \var{nf}, and $z$ is a 2140primitive $w$-th root of unity. 2141 2142\fun{GEN}{nfcyclotomicunits}{GEN nf, GEN zu} where \kbd{zu} is as output by 2143\kbd{nfrootsof1(nf)}, return the vector of the cyclotomic units in \kbd{nf} 2144expressed over the integral basis. 2145 2146\subsec{Obsolete routines} 2147 2148Still provided for backward compatibility, but should not be used in new 2149programs. They will eventually disappear. 2150 2151\fun{GEN}{zidealstar}{GEN nf, GEN x} short for \kbd{Idealstar(nf,x,nf\_GEN)} 2152 2153\fun{GEN}{zidealstarinit}{GEN nf, GEN x} 2154short for \kbd{Idealstar(nf,x,nf\_INIT)} 2155 2156\fun{GEN}{zidealstarinitgen}{GEN nf, GEN x} 2157short for \kbd{Idealstar(nf,x,nf\_GEN|nf\_INIT)} 2158 2159\fun{GEN}{idealstar0}{GEN nf, GEN x,long flag} short 2160for \kbd{idealstarmod(nf, ideal, flag, NULL)}. Use \kbd{Idealstarmod} or 2161\kbd{Idealstar}. 2162 2163\fun{GEN}{bnrinit0}{GEN bnf,GEN ideal,long flag} short 2164for \kbd{bnrinitmod(bnf,ideal,flag,NULL)}. Use \kbd{Buchray} or 2165\kbd{Buchraymod}. 2166 2167\fun{GEN}{buchimag}{GEN D, GEN c1, GEN c2, GEN gCO} short for 2168\bprog 2169 Buchquad(D,gtodouble(c1),gtodouble(c2), /*ignored*/0) 2170@eprog 2171 2172\fun{GEN}{buchreal}{GEN D, GEN gsens, GEN c1, GEN c2, GEN RELSUP, long prec} 2173short for 2174\bprog 2175Buchquad(D,gtodouble(c1),gtodouble(c2), prec) 2176@eprog 2177 2178The following use a naming scheme which is error-prone and not easily 2179extensible; besides, they compute generators as per \kbd{nf\_GEN} and 2180not \kbd{nf\_GENMAT}. Don't use them: 2181 2182\fun{GEN}{isprincipalforce}{GEN bnf,GEN x} 2183 2184\fun{GEN}{isprincipalgen}{GEN bnf, GEN x} 2185 2186\fun{GEN}{isprincipalgenforce}{GEN bnf, GEN x} 2187 2188\fun{GEN}{isprincipalraygen}{GEN bnr, GEN x}, use \tet{bnrisprincipal}. 2189 2190\noindent Variants on \kbd{polred}: use \kbd{polredbest}. 2191 2192\fun{GEN}{factoredpolred}{GEN x, GEN fa} 2193 2194\fun{GEN}{factoredpolred2}{GEN x, GEN fa} 2195 2196\fun{GEN}{smallpolred}{GEN x} 2197 2198\fun{GEN}{smallpolred2}{GEN x}, use \tet{Polred}. 2199 2200\fun{GEN}{polred0}{GEN x, long flag, GEN p} 2201 2202\fun{GEN}{polredabs}{GEN x} 2203 2204\fun{GEN}{polredabs2}{GEN x} 2205 2206\fun{GEN}{polredabsall}{GEN x, long flun} 2207 2208\noindent Superseded by \tet{bnrdisclist0}: 2209 2210\fun{GEN}{discrayabslist}{GEN bnf,GEN L} 2211 2212\fun{GEN}{discrayabslistarch}{GEN bnf, GEN arch, long bound} 2213 2214\noindent Superseded by \tet{idealappr} (\fl is ignored) 2215 2216\fun{GEN}{idealappr0}{GEN nf, GEN x, long flag} 2217 2218\noindent Superseded by \kbd{bnrconductor\_raw} or \kbd{bnrconductormod}: 2219 2220\fun{GEN}{bnrconductor_i}{GEN bnr, GEN H, long flag} shallow variant of 2221\kbd{bnrconductor}. 2222 2223\fun{GEN}{bnrconductorofchar}{GEN bnr, GEN chi} 2224 2225\section{Galois extensions of $\Q$} 2226 2227This section describes the data structure output by the function 2228\tet{galoisinit}. This will be called a \kbd{gal} structure in 2229the following. 2230 2231\subsec{Extracting info from a \kbd{gal} structure} 2232 2233The functions below expect a \kbd{gal} structure and are shallow. See the 2234documentation of \tet{galoisinit} for the meaning of the member functions. 2235 2236\fun{GEN}{gal_get_pol}{GEN gal} returns \kbd{gal.pol} 2237 2238\fun{GEN}{gal_get_p}{GEN gal} returns \kbd{gal.p} 2239 2240\fun{GEN}{gal_get_e}{GEN gal} returns the integer $e$ such that 2241\kbd{gal.mod==gal.p\pow e}. 2242 2243\fun{GEN}{gal_get_mod}{GEN gal} returns \kbd{gal.mod}. 2244 2245\fun{GEN}{gal_get_roots}{GEN gal} returns \kbd{gal.roots}. 2246 2247\fun{GEN}{gal_get_invvdm}{GEN gal} \kbd{gal[4]}. 2248 2249\fun{GEN}{gal_get_den}{GEN gal} return \kbd{gal[5]}. 2250 2251\fun{GEN}{gal_get_group}{GEN gal} returns \kbd{gal.group}. 2252 2253\fun{GEN}{gal_get_gen}{GEN gal} returns \kbd{gal.gen}. 2254 2255\fun{GEN}{gal_get_orders}{GEN gal} returns \kbd{gal.orders}. 2256 2257\subsec{Miscellaneous functions} 2258 2259\fun{GEN}{nfgaloispermtobasis}{GEN nf, GEN gal} 2260return the images of the field generator by the automorphisms 2261\kbd{gal.orders} expressed on the integral basis \kbd{nf.zk}. 2262 2263\fun{GEN}{nfgaloismatrix}{GEN nf, GEN s} returns the \kbd{ZM} attached to 2264the automorphism $s$, seen as a linear operator expressend on the number 2265field integer basis. This allows to use 2266\bprog 2267 M = nfgaloismatrix(nf, s); 2268 sx = ZM_ZC_mul(M, x); /* or RgM_RgC_mul(M, x) if x is not integral */ 2269@eprog\noindent 2270instead of 2271\bprog 2272 sx = nfgaloisapply(nf, s, x); 2273@eprog\noindent 2274for an algebraic integer $x$. 2275 2276\fun{GEN}{nfgaloismatrixapply}{GEN nf, GEN M, GEN x} given an automorphism 2277$M$ in \kbd{nfgaloismatrix} form, return the image of $x$ under the 2278automorphism. Variant of \kbd{galoisapply}. 2279 2280\section{Quadratic number fields and quadratic forms} 2281 2282\subsec{Checks} 2283 2284\fun{void}{check_quaddisc}{GEN x, long *s, long *mod4, const char *f} 2285checks whether the \kbd{GEN} $x$ is a quadratic discriminant (\typ{INT}, 2286not a square, congruent to $0,1$ modulo $4$), and raise an exception 2287otherwise. Set \kbd{*s} to the sign of $x$ and \kbd{*mod4} to $x$ modulo 2288$4$ (0 or 1). 2289 2290\fun{void}{check_quaddisc_real}{GEN x, long *mod4, const char *f} as 2291\tet{check_quaddisc}; check that \kbd{signe(x)} is positive. 2292 2293\fun{void}{check_quaddisc_imag}{GEN x, long *mod4, const char *f} as 2294\tet{check_quaddisc}; check that \kbd{signe(x)} is negative. 2295 2296\subsec{Class number} 2297 2298The function \kbd{quadclassunit} uses index calculus and runs in 2299subexponential time but it assumes the truth of the GRH. For imaginary 2300quadratic orders, it is comparatively slow for \emph{small} values, 2301say $|D|\leq 10^{18}$. Here are some alternatives: 2302 2303 \fun{GEN}{classno}{GEN D} corresponds to \kbd{qfbclassno(D,0)} and is only 2304useful for $D < 0$, uses a baby-step giant-step technique and runs in time 2305$O(D{1/4})$. The result is guaranteed correct for $|D| < 2\cdot 10^{10}$ 2306and fastest in that range. For larger values of $|D|$, the algorithm is no 2307longer rigorous and may give incorrect results (we know no concrete example); 2308it also becomes relatively less interesting compared to \kbd{quadclassunit}. 2309 2310\fun{GEN}{classno2}{GEN D} corresponds to \kbd{qfbclassno(D,1)} and runs in 2311time $O(D^{1/2})$; it is provided for testing purposes only: it is never 2312competitive. 2313 2314\fun{GEN}{hclassno}{GEN d} returns the Hurwitz-Kronecker class number $H(d)$. 2315These play a central role in trace fomulas and are usually needed for many 2316consecutive values of $d$. Thus, the function uses a cache so that later 2317calls for \emph{small} consecutive values of $d$ are instantaneous, see 2318\kbd{getcache}. Large values of $d$ ($d > 500000$) call \kbd{quadclassunit} 2319individually and are not memoized. 2320 2321\fun{GEN}{hclassno6}{GEN d} assuming $d > 0$, returns the integer $6 H(d)$. 2322This is a low-level function behind \kbd{hclassno}. 2323 2324\fun{ulong}{hclassno6u}{ulong d} assuming $d > 0$, returns the integer 2325$6 H(d)$. 2326 2327\subsec{\typ{QFI}, \typ{QFR}} 2328 2329\fun{GEN}{qfi}{GEN x, GEN y, GEN z} creates the \typ{QFI} $(x,y,z)$. 2330 2331\fun{GEN}{qfr}{GEN x, GEN y, GEN z, GEN d} creates the \typ{QFR} $(x,y,z)$ 2332with distance component $d$. 2333 2334\fun{GEN}{qfr_1}{GEN q} given a \typ{QFR} $q$, return the unit form $q^0$. 2335 2336\fun{GEN}{qfi_1}{GEN q} given a \typ{QFI} $q$, return the unit form $q^0$. 2337 2338\fun{int}{qfb_equal1}{GEN q} returns 1 if the \typ{QFI} or \typ{QFR} 2339$q$ is the unit form. 2340 2341\subsubsec{Composition} 2342 2343\fun{GEN}{qficomp}{GEN x, GEN y} compose the two \typ{QFI} $x$ and $y$, 2344then reduce the result. This is the same as \kbd{gmul(x,y)}. 2345 2346\fun{GEN}{qfrcomp}{GEN x, GEN y} compose the two \typ{QFR} $x$ and $y$, 2347then reduce the result. This is the same as \kbd{gmul(x,y)}. 2348 2349\fun{GEN}{qfisqr}{GEN x} as \kbd{qficomp(x,y)}. 2350 2351\fun{GEN}{qfrsqr}{GEN x} as \kbd{qfrcomp(x,y)}. 2352 2353\noindent Same as above, \emph{without} reducing the result: 2354 2355\fun{GEN}{qficompraw}{GEN x, GEN y} 2356 2357\fun{GEN}{qfrcompraw}{GEN x, GEN y} 2358 2359\fun{GEN}{qfisqrraw}{GEN x} 2360 2361\fun{GEN}{qfrsqrraw}{GEN x} 2362 2363\fun{GEN}{qfbcompraw}{GEN x, GEN y} compose two \typ{QFI}s or two \typ{QFR}s, 2364without reduce the result. 2365 2366\subsubsec{Powering} 2367 2368\fun{GEN}{powgi}{GEN x, GEN n} computes $x^n$ (will work for many more types 2369than \typ{QFI} and \typ{QFR}, of course). Reduce the result. 2370 2371\fun{GEN}{qfrpow}{GEN x, GEN n} computes $x^n$ for a \typ{QFR} $x$, reducing 2372along the way. If the distance component is initially $0$, leave it alone; 2373otherwise update it. 2374 2375\fun{GEN}{qfbpowraw}{GEN x, long n} compute $x^n$ (pure composition, no 2376reduction), for a \typ{QFI} or \typ{QFR} $x$. 2377 2378\fun{GEN}{qfipowraw}{GEN x, long n} as \tet{qfbpowraw}, for a \typ{QFI} $x$. 2379 2380\fun{GEN}{qfrpowraw}{GEN x, long n} as \tet{qfbpowraw}, for a \typ{QFR} $x$. 2381 2382\subsubsec{Order, discrete log} 2383 2384\fun{GEN}{qfi_order}{GEN q, GEN o} 2385assuming that the \typ{QFI} $q$ has order dividing $o$, compute its 2386order in the class group. The order can be given in all formats allowed by 2387generic discrete log functions, the preferred format being \kbd{[ord, fa]} 2388(\typ{INT} and its factorization). 2389 2390\fun{GEN}{qfi_log}{GEN a, GEN g, GEN o} given a \typ{QFI} $a$ and assuming 2391that the \typ{QFI} $g$ has order $o$, compute an integer $k$ such that $a^k = 2392g$. Return \kbd{cgetg(1, t\_VEC)} if there are no solutions. Uses a generic 2393Pollig-Hellman algorithm, then either Shanks (small $o$) or Pollard rho 2394(large $o$) method. The order can be given in all formats allowed by generic 2395discrete log functions, the preferred format being \kbd{[ord, fa]} 2396(\typ{INT} and its factorization). 2397 2398\fun{GEN}{qfi_Shanks}{GEN a, GEN g, long n} given a \typ{QFI} $a$ and 2399assuming that the \typ{QFI} $g$ has (small) order $n$, compute an integer $k$ 2400such that $a^k = g$. Return \kbd{cgetg(1, t\_VEC)} if there are no solutions. 2401Directly uses Shanks algorithm, which is inefficient when $n$ is composite. 2402 2403\subsubsec{Solve, Cornacchia} 2404 2405The following functions underly \tet{qfbsolve}; $p$ denotes a prime number. 2406 2407\fun{GEN}{qfisolvep}{GEN Q, GEN p} solves $Q(x,y) = p$ over the integers, for 2408a \typ{QFI} $Q$. Return \kbd{gen\_0} if there are no solutions. 2409 2410\fun{GEN}{qfrsolvep}{GEN Q, GEN p} solves $Q(x,y) = p$ over the integers, for 2411a \typ{QFR} $Q$. Return \kbd{gen\_0} if there are no solutions. 2412 2413\fun{long}{cornacchia}{GEN d, GEN p, GEN *px, GEN *py} solves 2414$x^2+ dy^2 = p$ over the integers, where $d > 0$. Return $1$ if there is a 2415solution (and store it in \kbd{*x} and \kbd{*y}), $0$ otherwise. 2416 2417\fun{long}{cornacchia2}{GEN d, GEN p, GEN *px, GEN *py} as \kbd{cornacchia}, 2418for the equation $x^2 + dy^2 = 4p$. 2419 2420\fun{long}{cornacchia2_sqrt}{GEN d, GEN p, GEN b, GEN *px, GEN *py} as \kbd{cornacchia2}, 2421where $p > 2$ and $b$ is the smallest squareroot of $d$ modulo $p$. 2422 2423\subsubsec{Prime forms} 2424 2425\fun{GEN}{primeform_u}{GEN x, ulong p} \typ{QFI} whose first coefficient 2426is the prime $p$. 2427 2428\fun{GEN}{primeform}{GEN x, GEN p, long prec} 2429 2430\subsec{Efficient real quadratic forms} Unfortunately, \typ{QFR}s 2431are very inefficient, and are only provided for backward compatibility. 2432 2433\item they do not contain needed quantities, which are thus constantly 2434recomputed (the discriminant $D$, $\sqrt{D}$ and its integer part), 2435 2436\item the distance component is stored in logarithmic form, which involves 2437computing one extra logarithm per operation. It is much more efficient 2438to store its exponential, computed from ordinary multiplications and 2439divisions (taking exponent overflow into account), and compute its logarithm 2440at the very end. 2441 2442Internally, we have two representations for real quadratic forms: 2443 2444\item \tet{qfr3}, a container $[a,b,c]$ with at least 3 entries: the three 2445coefficients; the idea is to ignore the distance component. 2446 2447\item \tet{qfr5}, a container with at least 5 entries $[a,b,c,e,d]$: the 2448three coefficients a \typ{REAL} $d$ and a \typ{INT} $e$ coding the distance 2449component $2^{Ne} d$, in exponential form, for some large fixed $N$. 2450 2451It is a feature that \kbd{qfr3} and \kbd{qfr5} have no specified length or 2452type. It implies that a \kbd{qfr5} or \typ{QFR} will do whenever a \kbd{qfr3} 2453is expected. Routines using these objects all require a global context, 2454provided by a \kbd{struct qfr\_data *}: 2455\bprog 2456 struct qfr_data { 2457 GEN D; /* discriminant, t_INT */ 2458 GEN sqrtD; /* sqrt(D), t_REAL */ 2459 GEN isqrtD; /* floor(sqrt(D)), t_INT */ 2460 }; 2461@eprog 2462\fun{void}{qfr_data_init}{GEN D, long prec, struct qfr_data *S} 2463given a discriminant $D > 0$, initialize $S$ for computations at precision 2464\kbd{prec} ($\sqrt{D}$ is computed to that initial accuracy). 2465 2466\noindent All functions below are shallow, and not stack clean. 2467 2468\fun{GEN}{qfr3_comp}{GEN x, GEN y, struct qfr_data *S} compose two 2469\kbd{qfr3}, reducing the result. 2470 2471\fun{GEN}{qfr3_pow}{GEN x, GEN n, struct qfr_data *S} compute $x^n$, reducing 2472along the way. 2473 2474\fun{GEN}{qfr3_red}{GEN x, struct qfr_data *S} reduce $x$. 2475 2476\fun{GEN}{qfr3_rho}{GEN x, struct qfr_data *S} perform one reduction step; 2477\kbd{qfr3\_red} just performs reduction steps until we hit a reduced form. 2478 2479\fun{GEN}{qfr3_to_qfr}{GEN x, GEN d} recover an ordinary \typ{QFR} from the 2480\kbd{qfr3} $x$, adding distance component $d$. 2481 2482Before we explain \kbd{qfr5}, recall that it corresponds to an ideal, that 2483reduction corresponds to multiplying by a principal ideal, and that the 2484distance component is a clever way to keep track of these principal ideals. 2485More precisely, reduction consists in a number of reduction steps, 2486going from the form $(a,b,c)$ to $\rho(a,b,c) = (c, -b \mod 2c, *)$; 2487the distance component is multiplied by (a floating point approximation to) 2488$(b + \sqrt{D}) / (b - \sqrt{D})$. 2489 2490\fun{GEN}{qfr5_comp}{GEN x, GEN y, struct qfr_data *S} compose two 2491\kbd{qfr5}, reducing the result, and updating the distance component. 2492 2493\fun{GEN}{qfr5_pow}{GEN x, GEN n, struct qfr_data *S} compute $x^n$, reducing 2494along the way. 2495 2496\fun{GEN}{qfr5_red}{GEN x, struct qfr_data *S} reduce $x$. 2497 2498\fun{GEN}{qfr5_rho}{GEN x, struct qfr_data *S} perform one reduction step. 2499 2500\fun{GEN}{qfr5_dist}{GEN e, GEN d, long prec} decode the distance component 2501from exponential (\kbd{qfr5}-specific) to logarithmic form (as in a 2502\typ{QFR}). 2503 2504\fun{GEN}{qfr_to_qfr5}{GEN x, long prec} convert a \typ{QFR} to a 2505\kbd{qfr5} with initial trivial distance component ($= 1$). 2506 2507\fun{GEN}{qfr5_to_qfr}{GEN x, GEN d}, assume $x$ is a \kbd{qfr5} and 2508$d$ was the original distance component of some \typ{QFR} that we converted 2509using \tet{qfr_to_qfr5} to perform efficiently a number of operations. 2510Convert $x$ to a \typ{QFR} with the correct (logarithmic) distance component. 2511 2512\section{Linear algebra over $\Z$} 2513\subsec{Hermite and Smith Normal Forms} 2514 2515\fun{GEN}{ZM_hnf}{GEN x} returns the upper triangular Hermite Normal Form of the 2516\kbd{ZM} $x$ (removing $0$ columns), using the \tet{ZM_hnfall} algorithm. If you 2517want the true HNF, use \kbd{ZM\_hnfall(x, NULL, 0)}. 2518 2519\fun{GEN}{ZM_hnfmod}{GEN x, GEN d} returns the HNF of the \kbd{ZM} $x$ 2520(removing $0$ columns), assuming the \typ{INT} $d$ is a multiple of the 2521determinant of $x$. This is usually faster than \tet{ZM_hnf} (and uses less 2522memory) if the dimension is large, $> 50$ say. 2523 2524\fun{GEN}{ZM_hnfmodid}{GEN x, GEN d} returns the HNF of the \kbd{ZM} 2525$x$ concatenated with the diagonal matrix with diagonal $d$, where $d$ is a 2526vector of integers of compatible dimension. Variant: if $d$ is a \typ{INT}, 2527then concatenate $d \text{Id}$. 2528 2529\fun{GEN}{ZM_hnfmodprime}{GEN x, GEN p} returns the HNF of the matrix $(x \mid p 2530\text{Id})$ (removing $0$ columns), for a \kbd{ZM} $x$ and a prime number $p$. 2531The algorithm involves only $\F_p$-linear algebra and is is faster than 2532\tet{ZM_hnfmodid} (which will call it when $d$ is prime). 2533 2534\fun{GEN}{ZM_hnfmodall}{GEN x, GEN d, long flag} low-level function 2535underlying the \kbd{ZM\_hnfmod} variants. If \kbd{flag} is $0$, calls 2536\kbd{ZM\_hnfmod(x,d)}; \kbd{flag} is an or-ed combination of: 2537 2538\item \tet{hnf_MODID} call \kbd{ZM\_hnfmodid} instead of \kbd{ZM\_hnfmod}, 2539 2540\item \tet{hnf_PART} return as soon as we obtain an upper triangular matrix, 2541saving time. The pivots are nonnegative and give the diagonal of the true HNF, 2542but the entries to the right of the pivots need not be reduced, i.e.~they may be 2543large or negative. 2544 2545\item \tet{hnf_CENTER} returns the centered HNF, where the entries to the 2546right of a pivot $p$ are centered residues in $[-p/2, p/2[$, hence smallest 2547possible in absolute value, but possibly negative. 2548 2549\fun{GEN}{ZM_hnfmodall_i}{GEN x, GEN d, long flag} as \tet{ZM_hnfmodall} 2550without final garbage collection. Not \kbd{gerepile}-safe. 2551 2552\fun{GEN}{ZM_hnfall}{GEN x, GEN *U, long remove} returns the upper triangular 2553HNF $H$ of the \kbd{ZM} $x$; if $U$ is not \kbd{NULL}, set if to the matrix 2554$U$ such that $x U = H$. If $\kbd{remove} = 0$, $H$ is the true HNF, 2555including $0$ columns; if $\kbd{remove} = 1$, delete the $0$ columns from $H$ 2556but do not update $U$ accordingly (so that the integer kernel may still be 2557recovered): we no longer have $x U = H$; if $\kbd{remove} = 2$, remove $0$ 2558columns from $H$ and update $U$ so that $x U = H$. The matrix $U$ is square 2559and invertible unless $\kbd{remove} = 2$. 2560 2561This routine uses a naive algorithm which is potentially exponential in the 2562dimension (due to coefficient explosion) but is fast in practice, although it 2563may require lots of memory. The base change matrix $U$ may be very large, 2564when the kernel is large. 2565 2566\fun{GEN}{ZM_hnfall_i}{GEN x, GEN *U, long remove} as \tet{ZM_hnfall} without 2567final garbage collection. Not \kbd{gerepile}-safe. 2568 2569\fun{GEN}{ZM_hnfperm}{GEN A, GEN *ptU, GEN *ptperm} returns the hnf 2570$H = P A U$ of the matrix $P A$, where $P$ is a suitable permutation matrix, 2571and $U\in \text{Gl}_n(\Z)$. $P$ is chosen so as to (heuristically) minimize the 2572size of $U$; in this respect it is less efficient than \kbd{ZM\_hnflll} 2573but usually faster. Set \kbd{*ptU} to $U$ and \kbd{*pterm} to a \typ{VECSMALL} 2574representing the row permutation attached to $P = (\delta_{i,\kbd{perm}[i]}$. 2575If \kbd{ptU} is set to \kbd{NULL}, $U$ is not computed, saving some time; 2576although useless, setting \kbd{ptperm} to \kbd{NULL} is also allowed. 2577 2578\fun{GEN}{ZM_hnf_knapsack}{GEN x} given a \kbd{ZM} $x$, compute its 2579HNF $h$. Return $h$ if it has the knapsack property: every column contains 2580only zeroes and ones and each row contains a single $1$; 2581return \kbd{NULL} otherwise. Not suitable for gerepile. 2582 2583\fun{GEN}{ZM_hnflll}{GEN x, GEN *U, int remove} returns the HNF $H$ of the 2584\kbd{ZM} $x$; if $U$ is not \kbd{NULL}, set if to the matrix $U$ such that $x 2585U = H$. The meaning of \kbd{remove} is the same as in \tet{ZM_hnfall}. 2586 2587This routine uses the \idx{LLL} variant of Havas, Majewski and Mathews, which is 2588polynomial time, but rather slow in practice because it uses an exact LLL 2589over the integers instead of a floating point variant; it uses polynomial 2590space but lots of memory is needed for large dimensions, say larger than 300. 2591On the other hand, the base change matrix $U$ is essentially optimally small 2592with respect to the $L_2$ norm. 2593 2594\fun{GEN}{ZM_hnfcenter}{GEN M}. Given a \kbd{ZM} in HNF $M$, update it in 2595place so that nondiagonal entries belong to a system of \emph{centered} 2596residues. Not suitable for gerepile. 2597 2598Some direct applications: the following routines apply to upper triangular 2599integral matrices; in practice, these come from HNF algorithms. 2600 2601\fun{GEN}{hnf_divscale}{GEN A, GEN B,GEN t} $A$ an upper triangular \kbd{ZM}, 2602$B$ a \kbd{ZM}, $t$ an integer, such that $C := tA^{-1}B$ is integral. 2603Return $C$. 2604 2605\fun{GEN}{hnf_invscale}{GEN A, GEN t} $A$ an upper triangular \kbd{ZM}, 2606$t$ an integer such that $C := tA^{-1}$ is integral. Return $C$. Special case 2607of \tet{hnf_divscale} when $B$ is the identity matrix. 2608 2609\fun{GEN}{hnf_solve}{GEN A, GEN B} $A$ a \kbd{ZM} in upper HNF (not 2610necessarily square), $B$ a \kbd{ZM} or \kbd{ZC}. Return $A^{-1}B$ if it is 2611integral, and \kbd{NULL} if it is not. 2612 2613\fun{GEN}{hnf_invimage}{GEN A, GEN b} $A$ a \kbd{ZM} in upper HNF 2614(not necessarily square), $b$ a \kbd{ZC}. Return $A^{-1}B$ if it is 2615integral, and \kbd{NULL} if it is not. 2616 2617\fun{int}{hnfdivide}{GEN A, GEN B} $A$ and $B$ are two upper triangular 2618\kbd{ZM}. Return $1$ if $A^{-1} B$ is integral, and $0$ otherwise. 2619 2620\misctitle{Smith Normal Form} 2621 2622\fun{GEN}{ZM_snf}{GEN x} returns the Smith Normal Form (vector of 2623elementary divisors) of the \kbd{ZM} $x$. 2624 2625\fun{GEN}{ZM_snfall}{GEN x, GEN *U, GEN *V} returns 2626\kbd{ZM\_snf(x)} and sets $U$ and $V$ to unimodular matrices such that $U\, 2627x\, V = D$ (diagonal matrix of elementary divisors). Either (or both) $U$ or 2628$V$ may be \kbd{NULL} in which case the corresponding matrix is not computed. 2629 2630\fun{GEN}{ZV_snfall}{GEN d, GEN *U, GEN *V} here $d$ is a \kbd{ZV}; same as 2631\tet{ZM_snfall} applied to \kbd{diagonal(d)}, but faster. 2632 2633\fun{GEN}{ZM_snfall_i}{GEN x, GEN *U, GEN *V, long flag} low level version of 2634\kbd{ZM\_snfall}: 2635 2636\item if the first bit of \fl\ is $0$, return a diagonal matrix (as in 2637\kbd{ZM\_snfall}), else a vector of elementary divisors (as in 2638\kbd{ZM\_snf}). 2639 2640\item if the second bit of \fl\ is $1$, assume that $x$ is invertible 2641and allow $U$ and $V$ to have determinant congruent to $1$ modulo $d$, 2642where $d$ is the largest elementary divisor of $x$. Rationale: the finite 2643group $G = \Z^n/\Im x$ has exponent $d$ and we are only interested 2644in the action of $U$, $V$ as they act on $G$ not in genuine unimodular 2645matries. (See \kbd{ZM\_snf\_group}.) 2646 2647\fun{void}{ZM_snfclean}{GEN d, GEN U, GEN V} assuming $d$, $U$, $V$ come 2648from \kbd{d = ZM\_snfall(x, \&U, \&V)}, where $U$ or $V$ may be \kbd{NULL}, 2649cleans up the output in place. This means that elementary divisors equal to 1 2650are deleted and $U$, $V$ are updated. The output is not suitable for 2651\kbd{gerepileupto}. 2652 2653\fun{void}{ZV_snf_trunc}{GEN D} given a vector $D$ of elementary divisors 2654(i.e. a \kbd{ZV} such that $d_i \mid d_{i+1}$), truncate it \emph{in place} 2655to leave out the trivial divisors (equal to $1$). 2656 2657\fun{GEN}{ZM_snf_group}{GEN H, GEN *U, GEN *Uinv} this function computes data 2658to go back and forth between an abelian group (of finite type) given by 2659generators and relations, and its canonical SNF form. Given an abstract 2660abelian group with generators $g = (g_1,\dots,g_n)$ and a vector 2661$X=(x_i)\in\Z^n$, we write $g X$ for the group element $\sum_i x_i g_i$; 2662analogously if $M$ is an $n\times r$ integer matrix $g M$ is a vector 2663containing $r$ group elements. The group neutral element is $0$; by abuse of 2664notation, we still write $0$ for a vector of group elements all equal to the 2665neutral element. The input is a full relation matrix $H$ among the 2666generators, i.e. a \kbd{ZM} (not necessarily square) such that $gX = 0$ for 2667some $X\in\Z^n$ if and only if $X$ is in the integer image of $H$, so that 2668the abelian group is isomorphic to $\Z^n/\text{Im} H$. \emph{The routine 2669assumes that $H$ is in HNF;} replace it by its HNF if it is not the case. (Of 2670course this defines the same group.) 2671 2672Let $G$ a minimal system of generators in SNF for our abstract group: 2673if the $d_i$ are the elementary divisors ($\dots \mid d_2\mid d_1$), each 2674$G_i$ has either infinite order ($d_i = 0$) or order $d_i > 1$. Let $D$ 2675the matrix with diagonal $(d_i)$, then 2676$$G D = 0,\quad G = g U_{\text{inv}},\quad g = G U,$$ 2677for some integer matrices $U$ and $U_{\text{inv}}$. Note that these are not 2678even square in general; even if square, there is no guarantee that these are 2679unimodular: they are chosen to have minimal entries given the known relations 2680in the group and only satisfy $D \mid (U U_{\text{inv}} - \text{Id})$ and $H 2681\mid (U_{\text{inv}}U - \text{Id})$. 2682 2683The function returns the vector of elementary divisors $(d_i)$; if \kbd{U} is 2684not \kbd{NULL}, it is set to $U$; if \kbd{Uinv} is not \kbd{NULL} it is 2685set to $U_{\text{inv}}$. The function is not memory clean. 2686 2687\fun{GEN}{ZV_snf_group}{GEN d, GEN *newU, GEN *newUi}, here $d$ is a 2688\kbd{ZV}; same as \tet{ZM_snf_group} applied to \kbd{diagonal(d)}, but faster. 2689 2690\fun{GEN}{ZV_snf_gcd}{GEN v, GEN N} given a vector $v$ of integers and a 2691positive integer $N$, return the vector whose entries are the gcds 2692$(v[i],N)$. Use case: if $v$ gives the cyclic components for some Abelian 2693group $G$ of finite type, then this returns the structure of the finite 2694groupe $G/G^N$. 2695 2696The following routines underly the various \tet{matrixqz} variants. 2697In all case the $m\times n$ \typ{MAT} $x$ is assumed to have rational 2698(\typ{INT} and \typ{FRAC}) coefficients 2699 2700\fun{GEN}{QM_ImQ}{GEN x} returns a basis for 2701$\text{Im}_\Q x \cap \Z^n$. 2702 2703\fun{GEN}{QM_ImZ}{GEN x} returns a basis for 2704$\text{Im}_\Z x \cap \Z^n$. 2705 2706\fun{GEN}{QM_ImQ_hnf}{GEN x} returns an HNF basis for 2707$\text{Im}_\Q x \cap \Z^n$. 2708 2709\fun{GEN}{QM_ImZ_hnf}{GEN x} returns an HNF basis for 2710$\text{Im}_\Z x \cap \Z^n$. 2711 2712\fun{GEN}{QM_ImQ_hnfall}{GEN A, GEN *pB, long remove} as \tet{QM_ImQ_hnf}, 2713further returning the transformation matrix as in \tet{ZM_hnfall}. 2714 2715\fun{GEN}{QM_ImZ_hnfall}{GEN A, GEN *pB, long remove} as \tet{QM_ImZ_hnf}, 2716further returning the transformation matrix as in \tet{ZM_hnfall}. 2717 2718\fun{GEN}{QM_ImQ_all}{GEN A, GEN *pB, long remove, long hnf} as \tet{QM_ImQ}, 2719further returning the transformation matrix as in \tet{ZM_hnfall}, and 2720returning an HNF basis if \kbd{hnf} is nonzero. 2721 2722\fun{GEN}{QM_ImZ_all}{GEN A, GEN *pB, long remove, long hnf} as \tet{QM_ImZ}, 2723further returning the transformation matrix as in \tet{ZM_hnfall}, and 2724returning an HNF basis if \kbd{hnf} is nonzero. 2725 2726\fun{GEN}{QM_minors_coprime}{GEN x, GEN D}, assumes $m\geq n$, and returns 2727a matrix in $M_{m,n}(\Z)$ with the same $\Q$-image as $x$, such that 2728the GCD of all $n\times n$ minors is coprime to $D$; if $D$ is \kbd{NULL}, 2729we want the GCD to be $1$. 2730\smallskip 2731 2732The following routines are simple wrappers around the above ones and are 2733normally useless in library mode: 2734 2735\fun{GEN}{hnf}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls \tet{ZM_hnf}. 2736Normally useless in library mode. 2737 2738\fun{GEN}{hnfmod}{GEN x, GEN d} checks whether $x$ is a \kbd{ZM}, then calls 2739\tet{ZM_hnfmod}. Normally useless in library mode. 2740 2741\fun{GEN}{hnfmodid}{GEN x,GEN d} checks whether $x$ is a \kbd{ZM}, then calls 2742\tet{ZM_hnfmodid}. Normally useless in library mode. 2743 2744\fun{GEN}{hnfall}{GEN x} calls 2745\kbd{ZM\_hnfall(x, \&U, 1)} and returns $[H, U]$. Normally useless in library 2746mode. 2747 2748\fun{GEN}{hnflll}{GEN x} calls \kbd{ZM\_hnflll(x, \&U, 1)} and returns $[H, 2749U]$. Normally useless in library mode. 2750 2751\fun{GEN}{hnfperm}{GEN x} calls \kbd{ZM\_hnfperm(x, \&U, \&P)} and returns 2752$[H, U, P]$. Normally useless in library mode. 2753 2754\fun{GEN}{smith}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls 2755\kbd{ZM\_snf}. Normally useless in library mode. 2756 2757\fun{GEN}{smithall}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls 2758\kbd{ZM\_snfall(x, \&U, \&V)} and returns $[U,V,D]$. Normally useless in 2759library mode. 2760 2761\noindent Some related functions over $K[X]$, $K$ a field: 2762 2763\fun{GEN}{gsmith}{GEN A} the input matrix must be square, returns the 2764elementary divisors. 2765 2766\fun{GEN}{gsmithall}{GEN A} the input matrix must be square, returns the 2767$[U,V,D]$, $D$ diagonal, such that $UAV = D$. 2768 2769\fun{GEN}{RgM_hnfall}{GEN A, GEN *pB, long remove} analogous to \tet{ZM_hnfall}. 2770 2771\fun{GEN}{smithclean}{GEN z} cleanup the output of \kbd{smithall} or 2772\kbd{gsmithall} (delete elementary divisors equal to $1$, updating base 2773change matrices). 2774 2775\subsec{The LLL algorithm}\sidx{LLL} 2776 2777The basic GP functions and their immediate variants are normally not very 2778useful in library mode. We briefly list them here for completeness, see the 2779documentation of \kbd{qflll} and \kbd{qflllgram} for details: 2780 2781\item \fun{GEN}{qflll0}{GEN x, long flag} 2782 2783\fun{GEN}{lll}{GEN x} \fl = 0 2784 2785\fun{GEN}{lllint}{GEN x} \fl = 1 2786 2787\fun{GEN}{lllkerim}{GEN x} \fl = 4 2788 2789\fun{GEN}{lllkerimgen}{GEN x} \fl = 5 2790 2791\fun{GEN}{lllgen}{GEN x} \fl = 8 2792 2793\item \fun{GEN}{qflllgram0}{GEN x, long flag} 2794 2795\fun{GEN}{lllgram}{GEN x} \fl = 0 2796 2797\fun{GEN}{lllgramint}{GEN x} \fl = 1 2798 2799\fun{GEN}{lllgramkerim}{GEN x} \fl = 4 2800 2801\fun{GEN}{lllgramkerimgen}{GEN x} \fl = 5 2802 2803\fun{GEN}{lllgramgen}{GEN x} \fl = 8 2804 2805\smallskip 2806 2807The basic workhorse underlying all integral and floating point LLLs is 2808 2809\fun{GEN}{ZM_lll}{GEN x, double D, long flag}, where $x$ is a \kbd{ZM}; 2810$D \in ]1/4,1[$ is the Lov\'{a}sz constant determining the frequency of 2811swaps during the algorithm: a larger values means better guarantees for 2812the basis (in principle smaller basis vectors) but longer running times 2813(suggested value: $D = 0.99$). 2814 2815\misctitle{Important} This function does not collect garbage and its output 2816is not suitable for either \kbd{gerepile} or \kbd{gerepileupto}. We expect 2817the caller to do something simple with the output (e.g. matrix 2818multiplication), then collect garbage immediately. 2819 2820\noindent\kbd{flag} is an or-ed combination of the following flags: 2821 2822\item \tet{LLL_GRAM}. If set, the input matrix $x$ is the Gram matrix ${}^t 2823v v$ of some lattice vectors $v$. 2824 2825\item \tet{LLL_INPLACE}. Incompatible with \kbd{LLL\_GRAM}. If unset, we 2826return the base change matrix $U$, otherwise the transformed matrix $x U$. 2827Implies \tet{LLL_IM} (see below). 2828 2829\item \tet{LLL_KEEP_FIRST}. The first vector in the output basis is the same 2830one as was originally input. Provided this is a shortest nonzero vector of 2831the lattice, the output basis is still LLL-reduced. This is used to reduce 2832maximal orders of number fields with respect to the $T_2$ quadratic form, to 2833ensure that the first vector in the output basis corresponds to $1$ (which is 2834a shortest vector). 2835 2836\item \tet{LLL_COMPATIBLE}. DEPRECATED. This is now a no-op. 2837 2838The last three flags are mutually exclusive, either 0 or a single one must be 2839set: 2840 2841\item \tet{LLL_KER} If set, only return a kernel basis $K$ (not LLL-reduced). 2842 2843\item \tet{LLL_IM} If set, only return an LLL-reduced lattice basis $T$. 2844(This is implied by \tet{LLL_INPLACE}). 2845 2846\item \tet{LLL_ALL} If set, returns a 2-component vector $[K, T]$ 2847corresponding to both kernel and image. 2848 2849 2850\fun{GEN}{lllfp}{GEN x, double D, long flag} is a variant for matrices 2851with inexact entries: $x$ is a matrix with real coefficients (types 2852\typ{INT}, \typ{FRAC} and \typ{REAL}), $D$ and $\fl$ are as in \tet{ZM_lll}. 2853The matrix is rescaled, rounded to nearest integers, then fed to 2854\kbd{ZM\_lll}. The flag \kbd{LLL\_INPLACE} is still accepted but less useful 2855(it returns an LLL-reduced basis attached to rounded input, instead of an 2856exact base change matrix). 2857 2858\fun{GEN}{ZM_lll_norms}{GEN x, double D, long flag, GEN *ptB} slightly more 2859general version of \kbd{ZM\_lll}, setting \kbd{*ptB} to a vector containing 2860the squared norms of the Gram-Schmidt vectors $(b_i^*)$ attached to the 2861output basis $(b_i)$, $b_i^* = b_i + \sum_{j < i} \mu_{i,j} b_j^*$. 2862 2863\fun{GEN}{lllintpartial_inplace}{GEN x} given a \kbd{ZM} $x$ of maximal rank, 2864returns a partially reduced basis $(b_i)$ for the space spanned by the 2865columns of $x$: $|b_i \pm b_j| \geq |b_i|$ for any two distinct basis vectors 2866$b_i$, $b_j$. This is faster than the LLL algorithm, but produces much larger 2867bases. 2868 2869\fun{GEN}{lllintpartial}{GEN x} as \kbd{lllintpartial\_inplace}, but returns 2870the base change matrix $U$ from the canonical basis to the $b_i$, i.e. $x U$ 2871is the output of \kbd{lllintpartial\_inplace}. 2872 2873\fun{GEN}{RM_round_maxrank}{GEN G} given a matrix $G$ with real floating 2874point entries and independent columns, let $G_e$ be the 2875rescaled matrix $2^e G$ rounded to nearest integers, for $e \geq 0$. 2876Finds a small $e$ such that the rank of $G_e$ is equal to the rank of $G$ 2877(its number of columns) and return $G_e$. This is useful as a preconditioning 2878step to speed up LLL reductions, see \tet{nf_get_Gtwist}. 2879Suitable for \kbd{gerepileupto}, but does not collect garbage. 2880 2881\subsec{Linear dependencies} 2882 2883The following functions underly the \kbd{lindep} GP function: 2884 2885\fun{GEN}{lindep}{GEN v} real/complex entries, guess that about only the 288680\% leading bits of the input are correct. 2887 2888\fun{GEN}{lindep_bit}{GEN v, long b} real/complex entries, explicit form of the 2889above: multiply the input by $2^b$ and round to nearest integer before 2890looking for a linear dependency. Truncating dubious bits allows to find 2891better relations. 2892 2893\fun{GEN}{lindepfull_bit}{GEN v, long b} as \kbd{lindep\_bit} but return a 2894matrix $M$ with $n = \#v$ columns and $r$ rows, with $r = n+1$ (if $v$ is 2895real) or $n+2$ (general case) which is an LLL-reduced basis of the lattice 2896formed by concatenating vertically an identity matrix and the floor of $2^b 2897\kbd{real}(v)$ and $2^b \kbd{imag}(v)$ if $r = n+2$. The first $n$ rows of 2898$M$ potentially correspond to relations: whenever the last $r-n$ entries of a 2899column are small. The function \kbd{lindep\_bit} essentially returns the 2900first column of $M$ truncated to $n$ components. 2901 2902\fun{GEN}{lindep_padic}{GEN v} $p$-adic entries. 2903 2904\fun{GEN}{lindep_Xadic}{GEN v} polynomial entries. 2905 2906\fun{GEN}{deplin}{GEN v} returns a nonzero kernel vector for a \typ{MAT} input. 2907 2908Deprecated routine: 2909 2910\fun{GEN}{lindep2}{GEN x, long dig} analogous to \kbd{lindep\_bit}, with 2911\kbd{dig} counting decimal digits. 2912 2913\subsec{Reduction modulo matrices} 2914 2915\fun{GEN}{ZC_hnfremdiv}{GEN x, GEN y, GEN *Q} assuming $y$ is an 2916invertible \kbd{ZM} in HNF and $x$ is a \kbd{ZC}, returns the \kbd{ZC} $R$ 2917equal to $x$ mod $y$ (whose $i$-th entry belongs to $[-y_{i,i}/2, y_{i,i}/2[$). 2918Stack clean \emph{unless} $x$ is already reduced (in which case, returns $x$ 2919itself, not a copy). If $Q$ is not \kbd{NULL}, set it to the \kbd{ZC} such that 2920$x = yQ + R$. 2921 2922\fun{GEN}{ZM_hnfdivrem}{GEN x, GEN y, GEN *Q} reduce 2923each column of the \kbd{ZM} $x$ using \kbd{ZC\_hnfremdiv}. If $Q$ is not 2924\kbd{NULL}, set it to the \kbd{ZM} such that $x = yQ + R$. 2925 2926\fun{GEN}{ZC_hnfrem}{GEN x, GEN y} alias for \kbd{ZC\_hnfremdiv(x,y,NULL)}. 2927 2928\fun{GEN}{ZM_hnfrem}{GEN x, GEN y} alias for \kbd{ZM\_hnfremdiv(x,y,NULL)}. 2929 2930\fun{GEN}{ZC_reducemodmatrix}{GEN v, GEN y} Let $y$ be a ZM, not necessarily 2931square, which is assumed to be LLL-reduced (otherwise, very poor reduction is 2932expected). Size-reduces the ZC $v$ modulo the $\Z$-module $Y$ spanned by $y$ 2933: if the columns of $y$ are denoted by $(y_1,\dots, y_{n-1})$, we return $y_n 2934\equiv v$ modulo $Y$, such that the Gram-Schmidt coefficients $\mu_{n,j}$ are 2935less than $1/2$ in absolute value for all $j < n$. In short, $y_n$ is almost 2936orthogonal to $Y$. 2937 2938\fun{GEN}{ZM_reducemodmatrix}{GEN v, GEN y} Let $y$ be as in 2939\tet{ZC_reducemodmatrix}, and $v$ be a ZM. This returns a matrix $v$ which is 2940congruent to $v$ modulo the $\Z$-module spanned by $y$, whose columns are 2941size-reduced. This is faster than repeatedly calling \tet{ZC_reducemodmatrix} 2942on the columns since most of the Gram-Schmidt coefficients can be reused. 2943 2944\fun{GEN}{ZC_reducemodlll}{GEN v, GEN y} Let $y$ be an arbitrary ZM, 2945LLL-reduce it then call \tet{ZC_reducemodmatrix}. 2946 2947\fun{GEN}{ZM_reducemodlll}{GEN v, GEN y} Let $y$ be an arbitrary ZM, 2948LLL-reduce it then call \tet{ZM_reducemodmatrix}. 2949 2950Besides the above functions, which were specific to integral input, we also 2951have: 2952 2953\fun{GEN}{reducemodinvertible}{GEN x, GEN y} $y$ is an invertible matrix 2954and $x$ a \typ{COL} or \typ{MAT} of compatible dimension. 2955Returns $x - y\lfloor y^{-1}x \rceil$, which has small entries and differs 2956from $x$ by an integral linear combination of the columns of $y$. Suitable 2957for \kbd{gerepileupto}, but does not collect garbage. 2958 2959\fun{GEN}{closemodinvertible}{GEN x, GEN y} returns $x - 2960\kbd{reducemodinvertible}(x,y)$, i.e. an integral linear combination of 2961the columns of $y$, which is close to $x$. 2962 2963\fun{GEN}{reducemodlll}{GEN x,GEN y} LLL-reduce the nonsingular \kbd{ZM} $y$ 2964and call \kbd{reducemodinvertible} to find a small representative of $x$ mod $y 2965\Z^n$. Suitable for \kbd{gerepileupto}, but does not collect garbage. 2966 2967\section{Finite abelian groups and characters} 2968 2969\subsec{Abstract groups} 2970 2971A finite abelian group $G$ in GP format is given by its Smith 2972Normal Form as a pair $[h,d]$ or triple $[h,d,g]$. 2973Here $h$ is the cardinality of $G$, $(d_i)$ is the vector of elementary 2974divisors, and $(g_i)$ is a vector of generators. In short, 2975$G = \oplus_{i\leq n} (\Z/d_i\Z) g_i$, with $d_n \mid \dots \mid d_2 \mid d_1$ 2976and $\prod d_i = h$. 2977 2978Let $e(x) := \exp(2i\pi x)$. For ease of exposition, we restrict to 2979complex-valued characters, but everything applies to more general fields $K$ 2980where $e$ denotes a morphism $(\Q,+) \to (K^*,\times)$ such that $e(a/b)$ 2981denotes a $b$-th root of unity. 2982 2983A \tev{character} on the abelian group $\oplus (\Z/d_j\Z) g_j$ 2984is given by a row vector $\chi = [a_1,\ldots,a_n]$ such that 2985$\chi(\prod g_j^{n_j}) = e(\sum a_j n_j / d_j)$. 2986 2987\fun{GEN}{cyc_normalize}{GEN d} shallow function. Given a vector 2988$(d_i)_{i \leq n}$ 2989of elementary divisors for a finite group (no $d_i$ vanish), returns the vector 2990$D = [1]$ if $n = 0$ (trivial group) and 2991 $[d_1, d_1/d_2, \dots, d_1/d_n]$ otherwise. This will allow to define 2992characters as $\chi(\prod g_j^{x_j}) = e(\sum_j x_j a_j D_j / D_1)$, 2993see \tet{char_normalize}. 2994 2995\fun{GEN}{char_normalize}{GEN chi, GEN ncyc} shallow function. Given a 2996character \kbd{chi} $ = (a_j)$ and \var{ncyc} from \kbd{cyc\_normalize} 2997above, returns the normalized representation $[d, (n_j)]$, such that 2998$\chi(\prod g_j^{x_j}) = \zeta_d^{\sum_j n_j x_j}$, where $\zeta_d = 2999e(1/d)$ and $d$ is \emph{minimal}. In particular, $d$ is the order 3000of \kbd{chi}. Shallow function. 3001 3002\fun{GEN}{char_simplify}{GEN D, GEN N} given a quasi-normalized character 3003$[D, (N_j)]$ such that $\chi(\prod g_j^{x_j}) = \zeta_D^{\sum_j N_j x_j}$, 3004but where we only assume that $D$ is a multiple of the character 3005order, return a normalized character $[d, (n_j)]$ with $d$ \emph{minimal}. 3006Shallow function. 3007 3008\fun{GEN}{char_denormalize}{GEN cyc, GEN d, GEN n} given a normalized 3009representation $[d, n]$ (where $d$ need not be minimal) of a character on the 3010abelian group with abelian divisors \kbd{cyc}, return the attached character 3011(where the image of each generator $g_i$ is given in terms of roots 3012of unity of different orders $\kbd{cyc}[i]$). 3013 3014\fun{GEN}{charconj}{GEN cyc, GEN chi} return the complex conjugate of 3015\kbd{chi}. 3016 3017\fun{GEN}{charmul}{GEN cyc, GEN a, GEN b} return the product character $a\times 3018b$. 3019 3020\fun{GEN}{chardiv}{GEN cyc, GEN a, GEN b} returns the character 3021$a / b = a \times \overline{b}$. 3022 3023\fun{int}{char_check}{GEN cyc, GEN chi} return $1$ if \kbd{chi} is a character 3024compatible with cyclic factors \kbd{cyc}, and $0$ otherwise. 3025 3026\fun{GEN}{cyc2elts}{GEN d} given a \typ{VEC} $d = (d_1,\dots,d_n)$ 3027of nonnegative integers, return the vector of all \typ{VECSMALL}s of length 3028$n$ whose $i$-th entry lies in $[0,d_i[$. Assumes that the product 3029of the $d_i$ fits in a \kbd{long}. 3030 3031\fun{long}{zv_cyc_minimize}{GEN d, GEN c, GEN coprime} given $d = 3032(d_1,\dots,d_n)$, $d_n \mid \dots \mid d_1 \neq 0$ a list of elementary 3033divisors for a finite abelian group as a \typ{VECSMALL}, given $c = 3034[g_1,\dots,g_n]$ representing an element in the group, and given a mask 3035\kbd{coprime} (as from \kbd{coprimes\_zv}$(o)$) representing a list of 3036forbidden congruence classes modulo $o$, return an integer $k$ such that 3037\kbd{coprime}$[k \% o]$ is nonzero and $k \cdot c$ is lexicographically 3038minimal. For instance, if $c$ is attached to a Dirichlet character $\chi$ of 3039order $o$ via the usual identification $\chi(g_i) = \zeta_{g_i}^{c_i}$, then 3040$\chi^k$ is a ``canonical'' representative in the Galois orbit of $\chi$. 3041 3042\fun{long}{zv_cyc_minimal}{GEN d, GEN c, GEN coprime} return $1$ if 3043\tet{zv_cyc_minimize} would return $k = 1$, i.e. $c$ is already the canonical 3044representative for the attached character orbit. 3045 3046\subsec{Dirichlet characters} 3047 3048The functions in this section are specific to characters on $(\Z/N\Z)^*$. 3049The argument $G$ is a special \kbd{bid} structure as returned by 3050\kbd{znstar0(N, nf\_INIT)}. In this case, there are additional ways 3051to input character via Conrey's representation. The character \kbd{chi} is 3052either a \typ{INT} (Conrey label), a \typ{COL} (a Conrey logarithm) or a 3053\typ{VEC} (generic character on \kbd{bid.gen} as explained in the previous 3054subsection). The following low-level functions are called by GP's generic 3055character functions. 3056 3057\fun{int}{zncharcheck}{GEN G, GEN chi} return $1$ if \kbd{chi} is 3058a valid character and $0$ otherwise. 3059 3060\fun{GEN}{zncharconj}{GEN G, GEN chi} as \kbd{charconj}. 3061 3062\fun{GEN}{znchardiv}{GEN G, GEN a, GEN b} as \kbd{chardiv}. 3063 3064\fun{GEN}{zncharker}{GEN G, GEN chi} as \kbd{charker}. 3065 3066\fun{GEN}{znchareval}{GEN G, GEN chi, GEN n, GEN z} as \kbd{chareval}. 3067 3068\fun{GEN}{zncharmul}{GEN G, GEN a, GEN b} as \kbd{charmul}. 3069 3070\fun{GEN}{zncharpow}{GEN G, GEN a, GEN n} as \kbd{charpow}. 3071 3072\fun{GEN}{zncharorder}{GEN G, GEN chi} as \kbd{charorder}. 3073 3074The following functions handle characters in Conrey notation (attached to 3075Conrey generators, not \kbd{G.gen}): 3076 3077\fun{int}{znconrey_check}{GEN cyc, GEN chi} return $1$ if \kbd{chi} is 3078a valid Conrey logarithm and $0$ otherwise. 3079 3080\fun{GEN}{znconrey_normalized}{GEN G, GEN chi} return normalized character 3081attached to \kbd{chi}, as in \kbd{char\_normalize} but on Conrey generators. 3082 3083\fun{GEN}{znconreyfromchar}{GEN G, GEN chi} return Conrey logarithm 3084attached to the generic (\typ{VEC}, on \kbd{G.gen}) 3085 3086\fun{GEN}{znconreyfromchar_normalized}{GEN G, GEN chi} return normalized 3087Conrey character attached to the generic (\typ{VEC}, on \kbd{G.gen}) 3088character \kbd{chi}. 3089 3090\fun{GEN}{znconreylog_normalize}{GEN G, GEN m} given a Conrey logarithm $m$ 3091(\typ{COL}), return the attached normalized Conrey character, as in 3092\kbd{char\_normalize} but on Conrey generators. 3093 3094\fun{GEN}{znchar_quad}{GEN G, GEN D} given a nonzero \typ{INT} $D$ congruent 3095to $0,1$ mod $4$, return $(D/.)$ as a character modulo $N$, given by a Conrey 3096logarithm (\typ{COL}). Assume that $|D|$ divides $N$. 3097 3098\fun{GEN}{Zideallog}{GEN G, GEN x} return the \kbd{znconreylog} of $x$ 3099expressed on \kbd{G.gen}, i.e. the ordinary discrete logarithm 3100from \kbd{ideallog}. 3101 3102\fun{GEN}{ncharvecexpo}{GEN G, GEN nchi} 3103given \kbd{nchi} $= [d,n]$ a quasi-normalized character ($d$ 3104may be a multiple of the character order), i.e. $\chi(g_i) = e(n[i]/d)$ 3105for all Conrey or SNF generators $g_i$ (as usual, we use SNF generators 3106if $n$ is a \typ{VEC} and the Conrey generators otherwise). 3107Return a \typ{VECSMALL} $v$ such that $v[i] = -1$ if $(i,N) > 1$ else 3108$\chi(i) = e(v[i]/d)$, $1 \leq i \leq N$. 3109 3110\section{Central simple algebras} 3111 3112\subsec{Initialization} 3113 3114Low-level routines underlying \kbd{alginit}. 3115 3116\fun{GEN}{alg_csa_table}{GEN nf, GEN mt, long v, long maxord} 3117algebra defined by a multiplication table. 3118 3119\fun{GEN}{alg_cyclic}{GEN rnf, GEN aut, GEN b, long maxord} 3120cyclic algebra~$(L/K,\sigma,b)$. 3121 3122\fun{GEN}{alg_hasse}{GEN nf, long d, GEN hi, GEN hf, long v, long maxord} 3123algebra defined by local Hasse invariants. 3124 3125\fun{GEN}{alg_hilbert}{GEN nf, GEN a, GEN b, long v, long maxord} 3126quaternion algebra. 3127 3128\fun{GEN}{alg_matrix}{GEN nf, long n, long v, GEN L, long maxord} 3129matrix algebra. 3130 3131\fun{GEN}{alg_complete}{GEN rnf, GEN aut, GEN hi, GEN hf, long maxord} 3132cyclic algebra~$(L/K,\sigma,b)$ with~$b$ computed from the Hasse invariants. 3133 3134\fun{GEN}{alg_changeorder}{GEN alg, GEN ord} 3135return the algebra with the integral basis replaced by~\kbd{ord} (a \typ{MAT} 3136expressing the basis of the new order in terms of the integral basis of \kbd{alg}). 3137No checks are performed. 3138 3139\subsec{Type checks} 3140 3141\fun{void}{checkalg}{GEN a} raise an exception if $a$ was not initialized 3142by \tet{alginit}. 3143 3144\fun{void}{checklat}{GEN al, GEN lat} raise an exception if \kbd{lat} is not a 3145valid full lattice in the algebra~\kbd{al}. 3146 3147\fun{void}{checkhasse}{GEN nf, GEN hi, GEN hf, long n} raise an exception 3148if~$(\kbd{hi},\kbd{hf})$ do not describe valid Hasse invariants of a central 3149simple algebra of degree~\kbd{n} over~\kbd{nf}. 3150 3151\fun{long}{alg_type}{GEN al} internal function called by \tet{algtype}: assume 3152\kbd{al} was created by \tet{alginit} (thereby saving a call to \kbd{checkalg}). 3153Return values are symbolic rather than numeric: 3154 3155\item \kbd{al\_NULL}: not a valid algebra. 3156 3157\item \kbd{al\_TABLE}: table algebra output by \kbd{algtableinit}. 3158 3159\item \kbd{al\_CSA}: central simple algebra output by \kbd{alginit} and 3160represented by a multiplication table over its center. 3161 3162\item \kbd{al\_CYCLIC}: central simple algebra output by \kbd{alginit} and 3163represented by a cyclic algebra. 3164 3165\fun{long}{alg_model}{GEN al, GEN x} given an element $x$ in algebra \var{al}, 3166check for inconsistencies (raise a type error) and return the representation 3167model used for $x$: 3168 3169\item \kbd{al\_ALGEBRAIC}: \kbd{basistoalg} form, algebraic representation. 3170 3171\item \kbd{al\_BASIS}: \kbd{algtobasis} form, column vector on the integral 3172basis. 3173 3174\item \kbd{al\_MATRIX}: matrix with coefficients in an algebra. 3175 3176\item \kbd{al\_TRIVIAL}: trivial algebra of degree $1$; can be understood 3177as both basis or algebraic form (since $e_1 = 1$). 3178 3179\subsec{Shallow accessors} 3180 3181All these routines assume their argument was initialized by \tet{alginit} 3182and provide minor speedups compared to the GP equivalent. The routines 3183returning a \kbd{GEN} are shallow. 3184 3185\fun{long}{alg_get_absdim}{GEN al} low-level version of \kbd{algabsdim}. 3186 3187\fun{long}{alg_get_dim}{GEN al} low-level version of \kbd{algdim}. 3188 3189\fun{long}{alg_get_degree}{GEN al} low-level version of \kbd{algdegree}. 3190 3191\fun{GEN}{alg_get_aut}{GEN al} low-level version of \kbd{algaut}. 3192 3193\fun{GEN}{alg_get_auts}{GEN al}, given a cyclic algebra $\var{al} = 3194(L/K,\sigma,b)$ of degree $n$, returns the vector of $\sigma^i$, 3195$1 \leq i < n$. 3196 3197\fun{GEN}{alg_get_b}{GEN al} low-level version of \kbd{algb}. 3198 3199\fun{GEN}{alg_get_basis}{GEN al} low-level version of \kbd{algbasis}. 3200 3201\fun{GEN}{alg_get_center}{GEN al} low-level version of \kbd{algcenter}. 3202 3203\fun{GEN}{alg_get_char}{GEN al} low-level version of \kbd{algchar}. 3204 3205\fun{GEN}{alg_get_hasse_f}{GEN al} low-level version of \kbd{alghassef}. 3206 3207\fun{GEN}{alg_get_hasse_i}{GEN al} low-level version of \kbd{alghassei}. 3208 3209\fun{GEN}{alg_get_invbasis}{GEN al} low-level version of \kbd{alginvbasis}. 3210 3211\fun{GEN}{alg_get_multable}{GEN al} low-level version of \kbd{algmultable}. 3212 3213\fun{GEN}{alg_get_relmultable}{GEN al} low-level version of 3214\kbd{algrelmultable}. 3215 3216\fun{GEN}{alg_get_splittingfield}{GEN al} 3217low-level version of \kbd{algsplittingfield}. 3218 3219\fun{GEN}{alg_get_abssplitting}{GEN al} returns the absolute \var{nf} 3220structure attached to the \var{rnf} returned by \kbd{algsplittingfield}. 3221 3222\fun{GEN}{alg_get_splitpol}{GEN al} returns the relative polynomial 3223defining the \var{rnf} returned by \kbd{algsplittingfield}. 3224 3225\fun{GEN}{alg_get_splittingdata}{GEN al} 3226low-level version of \kbd{algsplittingdata}. 3227 3228\fun{GEN}{alg_get_splittingbasis}{GEN al} 3229the matrix \var{Lbas} from \kbd{algsplittingdata} 3230 3231\fun{GEN}{alg_get_splittingbasisinv}{GEN al} 3232the matrix \var{Lbasinv} from \kbd{algsplittingdata}. 3233 3234\fun{GEN}{alg_get_tracebasis}{GEN al} returns the traces of the 3235basis elements; used by \kbd{algtrace}. 3236 3237\fun{GEN}{alglat_get_primbasis}{GEN lat} from the description of \kbd{lat} 3238as~$\lambda L$ with~$L\subset{\cal O}_0$ and~$\lambda\in\Q$, returns a basis 3239of~$L$. 3240 3241\fun{GEN}{alglat_get_scalar}{GEN lat} from the description of \kbd{lat} 3242as~$\lambda L$ with~$L\subset{\cal O}_0$ and~$\lambda\in\Q$, returns~$\lambda$. 3243 3244\subsec{Other low-level functions} 3245 3246\fun{GEN}{conjclasses_algcenter}{GEN cc, GEN p} low-level function underlying 3247\kbd{alggroupcenter}, where \kbd{cc} is the output of 3248\kbd{groupelts\_to\_conjclasses}, and $p$ is either \kbd{NULL} or a prime 3249number. Not stack clean. 3250 3251\fun{GEN}{algsimpledec_ss}{GEN al, long maps} assuming that~\kbd{al} is 3252semisimple, returns the second component of~\kbd{algsimpledec(al,maps)}. 3253 3254\newpage 3255