Back to Patch Notes

Upcoming changes (not yet released)

Changes not yet released. Updated areas: Algebraic Number Fields and Orders, Language/System, Algebraic Curves, Algebraic Number Fields, Elliptic Curves and 16 more.

21 areas

Changes and Removals

Algebraic Number Fields and Orders

Language/System

  • ShowMemoryUsage is no longer available in released versions of Magma, where its report did not reflect Magma’s memory use. Use GetMemoryUsage and GetMaximumMemoryUsage to see how much memory Magma is using. Reported by Abhijit Mudigonda.

New Features

Algebraic Curves

Algebraic Number Fields

  • Support of the rationals as a subfield of an embedded number field was added. (Issue #127) Reported by Jeroen Sijsling.

Elliptic Curves

  • TracesOfFrobenius for elliptic curves over the rationals accepts a new signature TracesOfFrobenius(E, Ps), returning the traces of Frobenius at the primes in the sequence Ps, with the i-th result corresponding to Ps[i]. The entries may be given in any order and may repeat, and each entry is checked to be prime. A sequence with more entries than a result sequence can contain is rejected with an error. The traces are computed by the same fast path as the existing bound and range forms, using the threads set by SetNthreads.

  • TracesOfFrobenius for elliptic curves over the rationals is now substantially faster when computing the traces of Frobenius at many good primes. On non-CM curves the traces are found through a bulk path that runs in parallel across the threads set by SetNthreads; CM curves, primes of bad reduction, and any prime outside that path use the existing per-prime computation. The returned traces are unchanged for bounds accepted by the pre-existing two-argument form, which now takes any non-negative bound that fits a machine integer and whose result fits in a sequence rather than only a small one; on a standard build that second limit already rejects a bound of about 2.5e10.

    A new signature TracesOfFrobenius(E, B0, B1) returns one trace of Frobenius for every prime in the interval [B0, B1], including primes of bad reduction. Its results are in increasing order of prime, one for each prime of the interval; for instance, over a range where PrimesInInterval(B0, B1) can be called, the i-th result corresponds to its i-th entry. Both this and TracesOfFrobenius(E, B) sieve the primes of the range, so an upper endpoint beyond the reach of that sieve is rejected with an error naming the largest endpoint the sieve can address; that reach depends on the binary variant, and is about 1.15e18 on a standard build. A request whose result would hold more traces than a sequence can contain is also rejected with an error, before any traces are computed.

Language/System

Bug Fixes

Algebraic Curves

  • EulerFactor of genus-2 curves over the rationals at large odd bad primes could run out of memory, grind for hours, or fail with “Could not compute local data”. These factors are now computed in seconds.

Algebraic Geometry

  • A bug in ParametrizeRationalNormalCurve causing problems in CurveQuotient was fixed.

  • Fixed an error that aborted DualResolutionGraph for some normal surface singularities, such as the \(E_6\) singularity \(x^2+y^3+z^4\) over a field where two exceptional curves meet in a Galois-conjugate point. The related minimal-graph, fibre zeta function and fibre point-count intrinsics are fixed likewise.

  • Corrected ZetaFunctionOfResolutionFibre and NumberOfPointsOnResolutionFibre (and their minimal-resolution variants) over finite fields. When the Frobenius folds conjugate exceptional curves together, the fibre zeta function could be returned in an invalid form (constant term not equal to 1) and the fibre point count could come back with the wrong sign or change depending on whether the zeta function or the point count was requested first. Both now agree and return the correct value.

  • Fixed a “Bad argument types” runtime error in Genus for a blow-up divisor of a surface desingularisation when DualResolutionGraph had already been computed for the same desingularisation. Requesting the genus first was unaffected, so the call succeeded or aborted depending on the order of the two requests; it now returns the genus in both orders.

  • Fixed runtime-error aborts in MinimalDualResolutionGraph (such as “Bad argument types”) on resolutions that require contracting a \((-1)\)-curve. It now returns the minimal dual graph and its intersection matrix instead of aborting.

  • Corrected the values of SelfIntersection, CanonicalIntersection and ArithmeticGenus for exceptional divisors that are Galois orbits of conjugate curves, such as the two conjugate exceptional curves in the resolution of \(x^2+y^4+z^8\) over \(\mathbb{Q}\). The reported values came from a single geometric component and under-counted the orbit; they now agree with the orbit-folded intersection matrix.

  • Fixed a crash in surface singularity resolution (ResolveSingularSurface, ResolveSingByBlowUp) over base fields other than finite fields and the rationals, such as number fields like \(\mathbb{Q}(i)\).

  • Fixed a crash in surface singularity resolution (ResolveSingularSurface, ResolveSingByBlowUp) that aborted with an internal assertion error on some singular surfaces, such as a quartic surface over GF(2) or a quintic surface over \(\mathbb{Q}\). A singular curve that had already been resolved could be rediscovered and blown up again, producing a spurious extra exceptional divisor that the resolution could not reconcile. These surfaces now resolve correctly.

Algebraic Number Fields

Algebraic Surfaces

  • Additional input checking for IntersectionMatrixOnDegree2K3 was added, as the input was required to be reduced, but no checking was done. Reported by Edgar Costa.

Algebras

  • Fixed Eltseq on an element of a group algebra created with Rep := "Terms", which aborted with an internal error on Apple silicon (and crashed on optimized builds) while returning the correct answer elsewhere. The sequence of coefficient and group element pairs is now built correctly on every platform. Reported by Edgar Costa.

Coding Theory

Complex Field

  • Fixed a memory leak in Root for complex numbers.

Elliptic Curves

  • EllipticCurve applied to a genus 1 hyperelliptic curve over a finite field failed when the curve had no rational Weierstrass point and no rational point at infinity. It now finds a rational point itself.

  • A numerical precision problem in the reduction of elliptic curves over number fields has been fixed. Reported by David Zureick-Brown.

  • A slowness in the point counting for elliptic curves over finite fields has been fixed. Reported by Eric Rains.

Finite Fields

  • In Magma format (print F : Magma;), a prime field F printed as GF(p, 1) for \(p > 2^{30}\) in the Standard version of Magma. The Large version did so for \(p > 2^{62}\), and a matrix over such a field padded its entries to the widest entry. Prime fields now print as GF(p) for every p in both versions, with matrix entries over them padded to the number of digits of p. (Issue #154)

  • In the Large version of Magma, Conway polynomials for primes \(p \ge 131\) were not found in the external Conway polynomial database, so ExistsConwayPolynomial(p, n) wrongly returned false and GF(p^n) was constructed with a non-primitive defining polynomial (e.g. \(x^2 + 1\) for GF(131^2)). Code relying on the generator of GF(q) being a primitive element, such as RecogniseSL2 applied to SimpleGroup(2134), consequently failed. The database reader now handles the 32-bit vs 64-bit issues properly, so both versions of Magma agree. Reported by Eamonn O’Brien.

  • Discrete logarithms by the function field sieve

    A new implementation of the function field sieve (FFS) for discrete logarithms in non-prime finite fields of medium characteristic has been added, following the variant of Joux and Lercier. It is used automatically by Log (and hence by Log(b, x)) for a field \(\GF(p^k)\) with \(7 < p < 2^{20}\) and at least \(2^{32}\) elements when the largest prime dividing \(p^k - 1\) is at least \(2^{37}\) and no stored Coppersmith table applies to the field (apart from a few special cases). Previously such fields, and in particular every such field with \(p > 100\), could only be handled by the Pohlig-Hellman algorithm, whose running time grows with the square root of that largest prime, so that logarithms in them were in practice out of reach.

    As with the other index-calculus methods, there is a precomputation stage which computes the logarithms of a factor base (the irreducible polynomials over \(\GF(p)\) up to some degree \(B\)) and is done once for each \(p\) and \(k\); each individual logarithm is then computed quickly from the stored factor base logarithms, for any field of that cardinality whatever its defining polynomial. For example, the precomputation takes about 3 seconds for \(\GF(101^{13})\), \(\GF(211^{11})\) or \(\GF(1013^9)\), about 6 seconds for \(\GF(101^{17})\) and about 5 minutes for \(\GF(223^{21})\), after which individual logarithms take a small fraction of a second.

    All parameters are chosen automatically. The factor base degree bound, the degrees of the two polynomials defining the function fields and a limit on the size of the factor base follow a rule calibrated on about a thousand timed runs, and for about 140 fields (with \(101 \le p \le 211\) and \(13 \le k \le 25\)) the measured optimal parameters are stored and used directly; these gave speedups of up to a factor of 10 over the general rule. For larger fields, where the factor base contains polynomials of degree 2 or more, only half of those of the top degree are used (a gain of about 1.3 to 1.7 times), and of the top degree factor base elements left undetermined by the linear algebra, only a fixed number (by default 25) have their logarithms computed individually, the rest being treated as large primes.

Finitely Presented Groups

  • An internal error in Index for finitely presented groups has been fixed. (Issue #29) Reported by Don Taylor.

  • In the Large version of Magma, RWSMonoid and RWSGroup misread the Weights of the “WtLex” ordering and the Levels of the “Wreath” ordering. A rewrite rule could then point the wrong way: with Weights := [3, 1], the relation \(a = b^2\) could come back as \(b^2 = a\). The Large version now returns the same rewrite systems as the Standard version.

Galois Groups

  • In the Large version of Magma, the old Galois group algorithm (InternalGaloisGroup) failed with an internal error when reading its group tables from the Galois data files (because of 32-bit vs 64-bit issues). The files are now read with fixed widths, so both versions of Magma agree.

  • InternalGaloisGroup (the old Galois group algorithm) could crash with a segmentation fault for some polynomials, for example \(x^7 - 7x + 3\), because a complex world used for precision bounds was freed while still in use. This is now fixed.

Global Fields

  • In rare cases, the class group proof algorithm stopped with the error No class group proof found. This is caused by reaching the give up bound of the algorithm. The bound is raised to make this error extremely unlikely. A further inspection of the example resulted in several speedups, the given example is now twice as fast. Reported by Armand Brumer.

Graphs

  • Fixed AutomorphismGroup with Al := "Traces" on graphs whose canonical labelling reaches the group order outside the main Traces search. The internal record of the order’s prime factorisation was allocated too late, and was reset after part of the order had already been computed, so such a call either failed with an internal error or returned a group whose order was too small while its generators were correct. The factorisation is now allocated and made available once per call, before any factor is contributed. (Issue #139) Reported by Saul D Freedman.

Groebner Bases

  • An occasional crash in the multi-threaded version of the linear algebra phase of the F4 algorithm when a very large number of threads were used has been fixed.

Hyperelliptic Curves

  • In the Large version of Magma, Theta could fail to return for a period matrix of genus 2 or more, while its memory use kept growing. One example is zero characteristic and zero argument with period matrix \(\mathrm{diag}(i, i)\). The lattice-point search in Theta now handles the 32-bit vs 64-bit issue properly, so both versions of Magma agree.

Language/System

  • Fixed a bug where binary and hexadecimal integers caused a syntax error when following an arithmetic operator. (Issue #42)

  • After an error partway through an arithmetic expression, such as a source file ending just after a +, the statement read next was still taken to be part of a polynomial and was rejected with an unrelated message such as “Illegal left hand side of an assignment statement”. This has been fixed.

  • A hexadecimal or binary integer literal whose leading digit was not 0, such as 9xff or 5b10, was accepted and read as though the leading digit had been 0. Such literals are now rejected.

  • A system package import (import !) now resolves against the directory named by MAGMA_SYSTEM_PACKAGE_ROOT when that environment variable is set. The supplied magma script sets it to the installation’s package directory, so SetLibraryRoot does not move system imports in that case. When the variable is unset, imports retain the previous behaviour: they resolve from the package directory beside the current library root. SetLibraryRoot still moves system imports in that case.

  • Fixed precision parameter passed to PARI in JacobiThetaNullK.

Local Fields

  • Sqrt, IsSquare, Root and IsPower of an imprecise zero \(O(\pi^v)\) of negative valuation over a \(p\)-adic field returned a root whose valuation was too large, claiming precision the root need not have. For an \(n\)-th root the valuation of the result is now Ceiling(\(v/n\)), the sharpest bound that is still correct.

Matrix Groups

  • The file con.m of the Husert package for conjugacy in \(GL_n(\mathbb{Z})\) (package/Group/GrpMat/GLnZ-conjugacy/husert) has been renamed conj.m, because CON is a reserved device name on Windows.

Number Fields

  • Fixed a crash in AutomorphismGroup for non-Galois absolute number fields where evaluating the returned map on non-identity group elements could trigger an internal error. Also fixed the reverse map (@@phi) returning wrong group elements on Galois fields with three or more automorphisms. (Issue #25) Reported by Edgar Costa.

Polynomial Rings

  • Discriminant for a polynomial over Integers(M) with M composite, or over a p-adic quotient ring, or over a polynomial ring over such a ring, could give an internal error or a wrong result when the leading coefficient is a zero divisor. This has been fixed.

  • Multiplying two univariate polynomials with at least 3 terms each in a multivariate polynomial ring over a ring with zero divisors, such as Integers(4), gave an internal error when the product is zero. This has been fixed.

Back to Patch Notes