****************************************************************************** GTM138: A Course in Computational Algebraic Number Theory ****************************************************************************** Chapter 1 ------------------------------------------------------------------------------ overflow overflow remainder hiremainder add addll sub subll addx addllx subx subllx mul mulll div divll shiftl shiftll shiftr shiftlr bfffo bfffo addition + subtraction - multiplication * division / integer division \ division and remainder divrem Binary Powering ^, gpow Euclid gcd Euclid Extended bezout Chinese chinese Continued Fraction contfrac, contfracpnqn Gauss qflll / qfbsolve Order in (Z/nZ)^* znorder Primitive Root znprimroot Legendre-Kronecker-Jacobi Symbol kronecker Square Root mod p sqrt Cornacchia qfbsolve Roots mod p polrootsmod Integer Square Root sqrtint Square Test issquare Squarefree Test issquarefree Prime Power Test is_odd_power (internal) ------------------------------------------------------------------------------ Chapter 2 ------------------------------------------------------------------------------ Make vector Vec Make matrix Mat Square Linear System matsolve Inverse of a Matrix M^(-1), 1/M Determinant matdet Characteristic Polynomial charpoly Adjoint Matrix matadjoint Hessenberg Form mathess Kernel matker Image matimage Inverse Image matinverseimage Supplement matsupplement, matimagecompl Intersection of Subspaces matintersect Hermite Normal Form mathnf Hermite Normal Form modulo D matdetint, mathnfmod Kernel over Z matkerint Smith Normal Form matsnf LLL, Integral LLL qflll Linear Dependence lindep Algebraic Dependence algdep Short Vectors qfminim ------------------------------------------------------------------------------ Chapter 3 ------------------------------------------------------------------------------ Make polynomial Pol Degree poldegree Leading Coefficient pollead Euclidean Division \ Euclidean Division with Remainder divrem Content content Subresultant polresultant Discriminant poldisc Factorization mod p factormod Factorization (general) factor Factorization over a number field nffactor, factornf Root Finding over C polroots ------------------------------------------------------------------------------ Chapter 4 ------------------------------------------------------------------------------ Sturm polsturm Conjugate Vector Representation conjvec Trace trace Norm norm Characteristic Polynomial charpoly Polynomial Reduction polred Pseudo-Canonical Polynomial polredabs Initialize Number Field nfinit Subfield Problem nfisincl Isomorphism Problem nfisisom Ideal Test nfisideal Make Principal Ideal idealprincipal Ideal Sum idealadd Ideal Product idealmul Ideal Power idealpow Ideal Norm idealnorm Ideal Hermite Normal Form idealhnf Two-Element Representation of Ideal idealtwoelt Decomposition of Prime Numbers idealprimedec Valuation at a Prime Ideal idealval Ideal Inverse idealinv Ideal Division idealdiv Different nf.diff Codifferent nf.codiff Ideal Factorization idealfactor Roots of Unity nfrootsof1 Dedekind Zeta Evaluation zetakinit, zetak Dedekind Zeta Dirichlet Series dirzetak ------------------------------------------------------------------------------ Chapter 5 ------------------------------------------------------------------------------ Make Quadratic Form Qfb h(D) Using Reduced Forms qfbhclassno (if |D| small) Hurwitz Class Number qfbhclassno Reduction of Binary Quadratic Form qfbred Composition * Nucomp, Nudupl qfbnucomp h(D) using Baby Step Giant Step qfbclassno (heuristic) Subexponential Class Group quadclassunit Rho Reduction Function qfbred h(D) Using Analytic Formulas qfbclassno h(D) Using Shanks's Heuristic --- Fundamental Unit quadunit Regulator quadregulator Regulator Using Infrastructure --- Composition with Distance * Subexponential Class and Unit Group quadclassunit Real GCD gcdreal (static in buch1.c) ------------------------------------------------------------------------------ Chapter 6 ------------------------------------------------------------------------------ Round 2/Round 4 nfbasis Discriminant nfdisc Galois polgalois (for degree<=11) Ideal Reduction Along v idealred General Class and Unit Group bnfinit, bnfclassunit Principal Ideal Test bnfisprincipal ------------------------------------------------------------------------------ Chapter 7 ------------------------------------------------------------------------------ Initialize Curve ellinit Compute g2 and g3 elleisnum Compute P(z), P'(z) ellwp, ellztopoint AGM agm Periods ell.omega Elliptic Logarithm ellpointtoz General Cubic Reduction ellfromeqn Shanks-Mestre Counting Points ellap, ellan, ellak Tate's Reduction elllocalred, ellglobalred Rational Torsion elltors Height of a Point or Matrix ellheight, ellheightmatrix, ellbil L-series Value elllseries Local, Global Root Number (not in book yet) ellrootno Complex J value ellj Hilbert Class Polynomial quadhilbert ------------------------------------------------------------------------------ Chapter 8 ------------------------------------------------------------------------------ General Factorization factor Trial Factorization factor Is Strong Pseudo-Prime ispseudoprime Rabin-Miller isprime Pocklington-Lehmer Primality Test isprime Lehman's method --- Pollard Rho factor Shanks's Class Group --- Shanks's SQUFOF factor, also cf examples/ p-1 method factor ------------------------------------------------------------------------------ Chapter 9 ------------------------------------------------------------------------------ Jacobi Sum Primality Test isprime Divisors in Residue Classes divisorslenstra Goldwasser-Killian Test --- Atkin's Primality Test, ECPP isprime, primecert ------------------------------------------------------------------------------ Chapter 10 ------------------------------------------------------------------------------ Continued Fraction Method CFRAC --- Schnorr-Lenstra Class Group Method --- Elliptic Curve Method ECM factor Quadratic Sieve Method MPQS factor Number Field Sieve Method NFS ---