Magma V2.4 contains a new packed representation for polynomials over
GF(2) which is used to represent elements of finite fields of
characteristic 2. This has led to dramatic speed-ups for computations
within such fields. Magma V2.3 used a two-step representation where a
large field was represented as an extension field of a Zech
representation field, but this representation could only be used if the
degree of the field had a suitable divisor and was not too large. The
prime factorization of the degree of the field is irrelevant in the new
representation so, for example, computation in fields of characteristic
2 with large prime degree is now very much faster.
A database of sparse irreducible polynomials over GF(2) has been
constructed for all degrees up to 11000. Thus any finite field
GF(2^k), for k within this range, may be created without any delay.
The sparseness of the defining polynomial is utilized in the
arithmetic. Computation in fields such as GF(2^10000) and GF(2^10007)
(10007 is prime) is now quite feasible.
The Shoup algorithm for factoring polynomials over large finite fields
has been implemented in V2.4. Combined with the great improvements to
the finite field arithmetic itself, factorization over large finite
fields is now very much faster in V2.4 than in previous versions. For
example, factorizing a polynomial over GF(2^1000) is about 500--1000
[sic] times faster in V2.4 than in V2.3. For fields of higher degree,
the improvement is even greater.
On a 64-bit 200MHz SGI Origin 2000, the n=2048 polynomial from the von
zur Gathen challenge benchmarks (of degree 2048 with sparse
coefficients modulo a 2050-bit prime) is factored by Magma V2.4 in
about 18.8 hours and the n=3000 polynomial from the same benchmarks (of
degree 3000 with sparse coefficients modulo a 3002-bit prime) is
factored by Magma V2.4 in about 75.8 hours. Also, the n=2048
polynomial from the Shoup challenge benchmarks (of degree 2048 with
dense coefficients modulo a 2048-bit prime) is factored by Magma V2.4
in about 36.0 hours on the same machine. (The times taken for the same
problems are about twice as long on a 250MHz Sun Ultrasparc.)
Summary of new features:
New database of sparse irreducible polynomials over GF(2) for all
degrees up to 11000 (accessed by IrreduciblePolynomial(GF(2), d)
and also used internally by functions such as the creation function
FiniteField).
The arithmetic for univariate polynomials over finite fields, and
arithmetic of medium-sized non-prime fields has been sped up by use
of FFT methods, etc. (see Univariate Polynomial Rings below).
Using a new efficient packed representation, arithmetic with finite
fields of characteristic 2 has been dramatically improved.
New Shoup factorization algorithm for polynomials over finite
fields (automatically selected by Factorization when appropriate or
by a parameter).
The computation of square roots of elements of finite fields of
characteristic 2 has been sped up.
The function FiniteField(p, n) now has a parameter Check; setting
Check to false will cause the function to skip the check that p is
prime.
New function NormEquation to solve norm equations in finite
fields.
New function AllRoots to return all n-th roots of a given element
of a finite field.
New function RootsInSplittingField(f), which, given a polynomial
over a finite field K, computes a splitting field S of f as an
extension field of K, and returns the roots of f in S, together
with S.
New function FactorizationOverSplittingField(f), which, given a
polynomial over a finite field K, computes a splitting field S of f
as an extension field of K, and returns the factorization (into
linears) of f over S, together with S.
New function Log(b, x) to compute the discrete logarithm of x to
the base b, for any primitive element b.
New procedure SetPrimitiveElement(K, x) to set the internal
primitive element of K to be x (useful when computing many
logarithms with respect to a particular base).
The computation of discrete logarithms has been sped up
(particularly for fields whose cardinality is less than 10^10).
The function Log may now be applied to an element of any finite
field of arbitrary size. The Pohlig-Hellman algorithm for
computing discrete algorithms is now combined with both the Shanks
baby-step/giant-step and Pollard-rho algorithms. In V2.4,
computing the logarithm of any element of a field having
cardinality less than 10^10 takes less than a second, and computing
the logarithm of any element of a field where the largest prime
divisor of the order of the multiplicative group is 15 decimal
digits now takes about 100 seconds (on a 250MHz Sun Ultrasparc).
Univariate Polynomial Rings [HB 28]
Magma V2.4 incorporates new fast methods for performing arithmetic with
univariate polynomials. These include two FFT-based methods for
multiplication: the Schoenhage-Strassen FFT method where the
coefficients are large compared with the degree, and the small-prime
modular FFT with Chinese remaindering method where the coefficients are
small compared with the degree. These new methods are applied to
multiplication of polynomials over the integer ring, the rational
field, integer residue class rings and prime finite fields. For some
kinds of coefficients, at least one of the FFT methods beats the
Karatsuba method as low as degree 32 or 64; for all of the kinds of
coefficients listed, the FFT methods beat the Karatsuba method for
degree 128 or greater.
An asymptotically-fast division algorithm (which reduces division to
multiplication) is now used for polynomials over all coefficient rings
(similar to the algorithm used for integers).
Factorization of univariate polynomials over all finite field types has
been dramatically improved---see the section on Finite Fields above.
Changes:
The function SquareFreeFactorization has been renamed to
SquarefreeFactorization; the old function name has been removed
from the documentation but kept in the executable to allow old code
to continue to work for this release.
Summary of new features:
New Schoenhage-Strassen FFT algorithm for multiplication of
polynomials (with large coefficients).
New small-prime modular FFT algorithm for multiplication of
polynomials (with small coefficients).
New asymptotically-fast division algorithm.
Modular exponentiation sped up by use of pre-inversion of modulus
and fast multiplication (and thus leading to a speed up in all
algorithms, such as factorization, which use this).
New fast modular algorithm for the computation of the extended GCD
of two univariate polynomials over the rational field.
Factorization of polynomials over all finite fields greatly
improved---see the section on Finite Fields.
New parameter Global for polynomial ring creation functions. This
now allows the creation of multiple non-global polynomial rings
with different generator names.
The function Evaluate for univariate polynomial rings has been
changed and extended to use the common over-ring of its arguments;
this overcomes some previous confusing behaviour caused by
automatic coercion.
The common over-structure of univariate polynomial rings is now
supported for the first time (used by automatic coercion).
New function HasPolynomialFactorization(R) to determine whether
factorization of polynomials over the ring R is allowed in Magma.
New function Valuation for univariate polynomials.
Multivariate Polynomial Rings [HB 29]
New algorithms for factorization of bivariate polynomials and general
multivariate polynomials over finite fields have been implemented. The
previous implementations failed on various inputs and were rather
unsatisfactory.
Changes:
The function Variety now returns a sequence of tuples.
The function SquareFreeFactorization has been renamed to
SquarefreeFactorization.
New features:
The dimension of a full polynomial ring (considered as an ideal) is
now defined to be -1, so the functions Dimension,
IsZeroDimensional, etc. may be applied to such.
New improved algorithm for factorization of multivariate
polynomials over finite fields.
New fast algorithm for the computation of GCDs of multivariate
polynomials over all fields of characteristic zero using
evaluation-interpolation techniques.
New fast algorithm for factorization of multivariate polynomials
over algebraic number fields (including quadratic and cyclotomic
fields) by better use of resultants.
New function TriangularDecomposition to compute the triangular
decomposition of zero-dimensional ideals (algorithm of D. Lazard).
The primary decomposition algorithm has been significantly improved
by use of the triangular decomposition algorithm together with
other techniques.
Invariant Rings of Finite Groups [HB 30]
New features:
The functions IsInvariant(f, g) and IsInvariant(f, G) have been
documented for the first time.
The functions PrimaryAlgebra and PrimaryIdeal have been documented
for the first time.
Algebraic Number Fields [HB 35]
The KANT number field machinery corresponding to Kash 1.9 has been
installed. This is the first major upgrade of the Magma general number
field facility since Kash V1.6 was installed in early 1996. This
version of KANT provides the Magma user with greatly enhanced
performance for many fundamental algorithms. Of particular note is the
new KANT maximal order algorithm that combines both the Round 2 and
Round 4 methods. Both conditional and unconditional computation of
class groups has been greatly improved and the result is far superior
performance to that provided in previous versions of Magma.
Major new number field facilities available in Magma V2.4 (courtesy of
KANT) are ray class groups, S-unit groups, prime ideal decompositions
of fractional ideals, automorphism groups of normal and abelian
extensions, solution of Thue equations, unit equations and index form
equations.
Changes:
The function BetterPolynomial has been replaced by
OptimizedRepresentation. The function BetterPolynomial will remain
for a transition period.
The function MaximalOrder has new parameters reflecting changes to
the underlying algorithm.
The function ClassGroup has new parameters reflecting changes to
the underlying algorithm.
The number field function BetterPolynomial has been replaced by
OptimizedRepresentation which has slightly different semantics.
The old function will be retained for compatibility in the medium
term.
All number field functions that return (inexact) real or complex
numbers have been changed so that instead of returning fixed
precision numbers, they now return free numbers (type FldPrElt).
New features:
The function RadicalExtension allows easy construction of radical
extensions.
The function CompositeFields creates the composition of two number
fields.
The function SplittingField will construct the splitting field of a
number field directly.
The function RelativeField allows the construction of relative
extensions.
The function AbsoluteDegree gives the absolute degree of an order
or number field.
The functions IsNormal and IsAbelian test a number field for being
a normal (respectively normal abelian) extension of Q.
The functions CharacteristicPolynomial and
AbsoluteCharacteristicPolynomial give the characteristic polynomial
of a field element.
The function Divisors, applied to an algebraic integer, returns all
its divisors.
The function Zeros gives the zeros of the defining polynomial of a
field or order.
The functions Index gives the index of an ideal in an over-order.
The infix operator meet has been extended so as to compute the
intersections of two ideals belonging to an order.
The function Decomposition, applied to a rational prime p, finds
the factorization of p into prime ideals in a designated order. If
this function is applied to an order element a it finds the
factorization of a into prime ideals.
The function InertiaDegree gives the degree of inertia of a prime
ideal.
The function Verify is provided for checking a conditional class
group computation.
Unconditional and conditional (GRH) computation of ray class groups
is provided by the function RayClassGroup.
The function ClassRepresentative, applied to an ideal I belonging
to an order whose class group is known, will give the chosen
representative of the ideal class containing I.
The group of S-units corresponding to a set S of prime ideals is
provided by the function SUnitGroup.
Function TorsionUnitGroup gives the torsion part of the unit group
of a number field or order.
The machinery developed by Klueners for computing subfields has
been greatly improved. It has been sucessfully used to compute all
subfields in an extension of degree 60.
The functions Automorphisms and AutomorphismGroup provide for the
calculation of the automorphism group of a normal extension.
The machinery for solving Thue equations has been improved and an
additional function ThueEval, for evaluating the homogeneous form,
is provided.
Bug fixes:
A number of bugs present in V2.3 and earlier versions, and arising
in the computation of class groups, unit groups and testing ideals
for being principal are fixed with the installation of the new
version of KANT.
Rational Function Fields, [HB 35]
New features:
The function Evaluate for univariate function fields has been
changed and extended to use the common over-ring of its arguments;
this avoids its previous confusing behaviour caused by automatic
coercion.
New function Derivative for function field elements (4 separate
signatures).
New function PartialFractionDecomposition which computes the
complete partial fraction decomposition of a function field
element. (PartialFractionDecomposition now factorizes fully and
the original functionality is now given by the function
SquarefreePartialFractionDecomposition.)
Coercion from one rational function field to a compatible field is
now allowed and the common over-structure of two function fields is
computed correctly.
New functions Degree, TotalDegree and WeightedDegree for function
field elements.
Real and Complex Fields [HB 36]
New features:
The function ExponentialIntegral(x) computes the exponential
integral of x.
Bug fixes:
A bug in Xavier Gourdon's root finding program in the case of badly
conditioned polynomials has been fixed.
Power Series [HB 37]
The module for computing with formal series has been completely
rewritten for Magma V2.4. Many bugs and leaks have been removed in the
process.
The arithmetic for series over the rational field is generally 5 times
faster (as a consequence of the use of fraction-free methods).
Asymptotically-fast methods for arithmetic are now used for the first
time (based on the new integer and polynomial methods). The 10000-th
Bernoulli number B_10000 may be computed in about 14 hours on a 250MHz
Sun Ultrasparc directly from its generating function.
New features:
Series with fractional exponents are now available. Arbitrary
exponent denominators are allowed and such series may be freely
mixed. Practically all series functions apply to series with
fractional exponents if the result is meaningful and computable.
The new category names for series rings and series are: RngSerPow
(power series ring), RngSerPowElt (power series), RngSerLaur
(Laurent series ring), RngSerLaurElt (Laurent series), RngSerPuis
(Puiseux series ring), RngSerPuisElt (Puiseux series), RngSerPuis
(any series ring), RngSerPuisElt (any series).
The functions PowerSeriesAlgebra and LaurentSeriesAlgebra have been
removed; the new creation functions are PowerSeriesRing,
LaurentSeriesRing and PuiseuxSeriesRing.
New parameter Global for series ring creation functions. This now
allows the creation of multiple non-global series rings with
different generator names.
New function ExponentDenominator to return the denominator of
exponents of a Puiseux series.
New functions LeadingCoefficient and LeadingTerm.
The function Reversion now works (for the first time) in the case
of fields having non-zero characteristic and for series with
general positive valuation.
Intrinsics for the inverse trigonometric functions Arcsin, Arccos
and Arctan and inverse hyperbolic functions Argsinh, Argcosh,
Argtanh have been installed.
Intrinsics for the trigonometric functions Sec, Cosec and Cot have
been installed.
The intrinsic function HypergeometricSeries is provided for
computing hypergeometric series.
New functions AGM, Gamma, LogGamma and Polylog.
New intrinsic functions for computing with Elliptic and Modular
functions have been implemented: Jacobi theta (JacobiTheta),
Dedekind eta (DedekindEta), j-invariant (jInvariant), Delta
function (Delta), Eisenstein function (Eisenstein) and Weierstrass
p-function (WeierstrassSeries).
Modules
Vector Spaces and R-spaces [HB 40]
New features:
New function Moduli to return the column moduli of an R-space over
a Euclidean domain.
R-Modules [HB 41]
New features:
Function SingleMinimalSubmodule documented for the first time.
Algebras
Group Algebras [HB 49]
Changes:
The sub-constructor for group algebras now returns a sub-group
algebra (in category AlgGrpSub) instead of an associative algebra.
This is more natural.
Ideals and subalgebras now make use of generators resulting in a
very considerable speed-up in closure operations.
Matrix Algebras [HB 50]
New features:
Genuine 64-bit versions for packed matrices over GF(2) have been
implemented for 64-bit machines.
The function Adjoint now works over any ring which has an exact
division algorithm (and is now correct for the first time!).
A matrix algebra element over a ring R is now coercible into a
matrix group over another ring S if elements of R are coercible
into S.
Geometry
Elliptic Curves [HB 52]
The facilities for elliptic curves have undergone major expansion.
Noteworthy is the introduction of general machinery for working with
isomorphisms, isogenies and rational maps between curves. The
implementation introduces new data types for such things as subgroups
and subschemes of elliptic curves. The image of a subgroup under an
isogeny (whose kernel is contained in the subgroup) can be calculated,
an operation which is used to construct an isogeny from its kernel but
is also of independent interest.
The implemented functions together form a powerful toolkit for working
with elliptic curves. The interplay between elliptic curves, isogenies
and subgroups is particularly beneficial. The toolkit allows
comparatively easy computation of structures such as the endomorphism
ring of a curve over a finite field and the eigenvalues of the
Frobenius automorphism (the latter being useful in point-counting).
Changes:
The category name for elliptic curves has been changed to CurveEll
and the category name for elliptic curve points has been changed to
CurveEllPt.
General Elliptic Curves
New features:
Extension and lifting of curves induced by maps of base rings:
BaseExtend, ChangeRing.
Division polynomials and m-torsion subgroups: DivisionPolynomial.
mTorsionSubgroup.
The (starred) modular equations are currently available for all primes in
the range 23 to 293: ModularEquation.
Order of a point an elliptic curve: Order.
The zeta-function of an elliptic curve at a given prime:
ZetaFunction.
Creation of isogenies, isomorphisms, rational maps between curves
and translation maps on a curve: Morphism, Isogeny, Automorphism,
TranslationMap and RationalMap.
Velu's formula for constructing an isogeny with a given kernel:
IsogenyFromKernel, and IsogenyFromKernelFactored.
Polynomials defining isogenies: IsogenyMapOmega, IsogenyMapPhi,
IsogenyMapPhiMulti, IsogenyMapPsi.
Kernel and image of an isogeny as subgroups, image and preimage of
a subgroup under an isogeny: Kernel, PushThroughIsogeny, etc.
Operations with isogenies: degree, composition, construction with
given kernel, Frobenius endomorphism: Degree, etc.
Operations with isomorphisms: inverses, composition.
Test whether two elliptic curves are isogeneous or isomorphic:
IsIsogenous and IsIsomorphism.
Subgroups of an elliptic curve as a type: Subgroup, Order,
mTorsionSubgroup and RationalPoints.
Subschemes of an elliptic curve as a type: Subscheme, DefiningIdeal,
and RationalPoints.
The database of elliptic curves having conductor up to 5300
constructed by John Cremona is now included: CremonaDatabase
and many others.
Elliptic Curves over Finite Fields
In V2.4 the computation of the order of an elliptic curve over a finite
field is performed using the plain Schoof algorithm (with the
restriction that the characteristic of the field must be greater than
3). An efficient implementation of the Schoof-Elkies-Atkin-Lercier
algorithm is under development and will be available in Magma V2.5.
New features for elliptic curves over finite fields:
Plain Schoof algorithm for counting the points on a curve over
a field having characteristic greater than 3 Order.
Trace of a curve (function Trace).
Random point of a curve (function Random).
Quadratic twist of a curve (function QuadraticTwist).
Non-deterministic tests for deciding whether a curve is supersingular:
IsProvenSupersingular, IsProbablyOrdinary.
Enumeration of all points of a curve (for small fields).
Function ModularEquation to return Atkin's variation of the
modular polynomial for a given prime p.
Incidence Structures
Enumerative Combinatorics [HB 53]
Changes:
The function BernoulliNumber has been sped up very significantly by
the use of power series (with asymptotically-fast arithmetic).
Incidence Structures and Designs [HB 55]
Changes:
Most point and block functions now take an extra argument: the
incidence structure in which the operation should be performed.
This allows for more flexibility when working with incidence
structures, and makes the incidence structure module more
consistent with others such as groups.
New features:
New function HadamardNormalize to normalize a Hadamard matrix to
have only ones in the first row and first column.
New function HadamardAutomorphismGroup to compute the automorphism
group of a Hadamard matrix.
Finite Planes [HB 56]
Facilities for subplanes of finite projective and affine planes have
been improved so as to make working with planes and subplanes much
easier.
Changes:
Most point and line functions now take an extra argument: the
incidence structure in which the operation should be performed.
This allows for more flexibility when working with planes and makes
the module compatible with others.
The following plane intrinsics have changed to accept the plane in
which the operation should be performed as the first argument:
AllPassants, AllSecants, AllTangents, CentralCollineationGroup,
Conic, ContainsQuadrangle, Coordinates, Exterior, ExternalLines,
Index, Interior, IsArc, IsCollinear, IsComplete, IsConcurrent,
IsParallel, IsUnital, Knot, ParallelClass, Pencil, QuadraticForm,
Support, Tangent, UnitalFeet.
Error-correcting Codes [HB 57]
New features:
The function IsEquivalent has been documented for the first time.