Tobias Beck: Computational Formal Resolution of Surfaces in P^3
Richard Brent: Using Magma to find good xorshift random number generators
Marsaglia recently introduced a class of ``xorshift'' random number generators (RNGs) with periods 2^n - 1 for n = 32, 64, etc. We describe a generalisation of Marsaglia's xorshift generators in order to obtain fast and high-quality RNGs with extremely long periods.
RNGs based on primitive trinomials may be unsatisfactory because a trinomial has very small weight (number of nonzero terms). In contrast, our generators can be chosen so that their minimal polynomials have large weight. A search using Magma has found good generators for $n$ a power of two up to 4096. These have been implemented in a free software package xorgens. Aspects of the search using Magma, and a connection with Fermat numbers, will be mentioned.
Reinier Bröker: Constructing elliptic curves for cryptography
Over the last 20 years, efficient algorithms have been developed to count the number of points of a given elliptic curve over a finite field. We discuss the inverse problem of constructing elliptic curves with a given number of points over a finite field. The difficulty of this problem depends on its exact wording. We present a solution to the problem that easily handles curves of the size occuring in cryptographic practice, and explain why it should be expected to do so.
Gavin Brown: Analysing 3-folds that contain a plane
The aim is to show that certain Fano 3-folds in codimension 4 exist---that is, to construct very special graded Gorenstein rings. The theory of unprojection provides the strategy, but I will talk about the practice of implementing it. In short, we must impose a plane on a 3-fold in codimension 3 and then apply general theorems. The familiar cases in lower dimension (imposing a point on a curve or a line on a surface) are superficially similar, but the 3-fold case has a very different flavour: we must control the singularities of the 3-fold that inevitably appear along the embedded plane. We have no general theorems to help here, and we must conduct case-by-case studies. We use Magma to understand the conditions imposed on explicit equations by the new plane and then to analyse the resulting variety. The result is that we always find at least two ways of imposing a plane on such 3-folds---that is, the Hilbert scheme of such Fano 3-folds is not irreducible. This contrasts with the analogous calculations in lower dimensions where the solution is unique. This is joint work with Michael Kerber (Saarbruecken) and Miles Reid (Warwick).
Stephen Coughlan: Free resolutions and birational geometry
Steve Donnelly: Descent on elliptic curves in Magma (TUTORIAL)
A number of tools for investigating elliptic curves over the rationals have been added to Magma (or enhanced) during the last 2 or 3 years. These tools include three descent, four descent, and Heegner points. The talk will give a complete picture of the available machinery, and what it is useful for.
Tom Fisher: Using descent calculations to find points on elliptic curves
I shall give an overview of the methods available for constructing equations for the n-coverings of an elliptic curve, and for adjusting these equations to have small coefficients. Having such equations assists the search for generators of large height on the elliptic curve.
Sebastian Freundt: QaoS
Databases facilitate the discovery of constructive examples and broad, heuristic observations. The KANT database is one of the world's largest databases for algebraic number fields. During the preparations for the current version of KASH, we wanted to generalise the database design and improve accessibility. The result is QaoS (Querying Algebraic Objects System), an easily integrated, stand-alone solution for access to various algebraic and number theoretic databases. QaoS is more versatile and extensible than its predecessors. An improved representation for elements and polynomials provides a feasible and fast way to represent (relative) algebraic and transcendental extensions.
QaoS incorporates data from the original KANT database of number fields, and tables of transitive groups from Alexander Hulpke which are linked to the Galois group entries in the tables of field extensions. Moreover, there is support for function fields and local field extensions.
Designed as a client-server application, QaoS transfers information via the hypertext transport protocol (HTTP). The query language is identical across clients. On the server side, client queries are translated into SQL (structured query language) for use by the database system PostgreSQL. The SQL result is translated back into a format which has been requested by the client before. A web browser, for example, would select hypertext markup language (HTML); whereas a computer algebra system, would choose a format easily read by the system.
Currently, client functions are available for GAP 4, KASH 2.56, KASH 3, Maple, and SAGE (contributed by Steven Simek). A Magma client is under development. Furthermore we are working on the bidirectional communication which empowers users with write access to directly add objects to the databases from within their client computer algebra systems.
Enrique González Jiménez: Equations for modular curves
The talk will present some algorithms for computing equations for modular curves over the rationals. That is, equations for curves C of genus at least 1 defined over Q such that there exists a nonconstant morphism from X_1(N) to C defined over Q for some N. The case of genus 1 (in other words, elliptic curves defined over Q) is well known. Then we will focus in the case of genus greater than 1.
The set of new modular curves over Q of a given genus g, or of a given gonality G, is finite and computable. For genus 2, we have computed all those curves (there are 213 of them). For gonality 2 (hyperelliptic curves), we have computed 300 curves and conjecture this is all. We will also discuss the remaining cases, that is, the non-hyperelliptic case.
All these computations have been implemented in MAGMA.
Markus Grassl: Finding equiangular lines in complex space
We consider the problem of finding a set of d^2 vector in a d-dimensional complex vector space such that the modulus of the inner product of any two vectors is constant. It has been conjectured that such sets exists for any dimension, however, no general construction is known. Using Magma, new solutions for this problems have been found. For this, a combination of group theory, Groebner bases, and number theory has been used.
Sergei Haller: Groups of Lie type in Magma
We will give a brief introduction to the theory of Groups of Lie type and an overview of functionality available in Magma for these groups and related topics (Root data, Coxeter Groups, Lie Algebras). We will also discuss some of the algorithms available in Magma, among which are new or improved algorithms for element multiplication and for working in twisted groups of Lie type.
Mike Harrison: TUTORIAL: Cryptographic applications of curves in Magma
Magma tutorial demonstrating some of the functionality for curves over finite fields with relations to cryptography. Particular examples will include point-counting, pairings on elliptic curves and GHS descent.
Antoine Joux: The function field sieve in medium characteristic
In this talk, we consider the computation of discrete logarithms in finite fields GF(q) where q=p^n and p is not too large (i.e. p=L_q(1/3)). In a first part, we show that a simple variation of the function field sieve can be used whenever p is below this bound. This variation of the function field sieve can be de- scribed in elementary terms, using only finite fields and polyno- mials. Together with a companion algorithm based on the number field sieve, this results yields L(1/3) complexity for the dis- crete logarithm problem in all finite fields. Interestingly, de- pending on the exact relation between p and p^n, the constant \alpha when writing the complexity as L(1/3, \alpha) greatly varies. In the second part, we consider the complexity analysis, both for the FFS and the NFS cases.
Kamal Khuri-Makdisi: Fast algorithms for Picard groups of general curves
Let C be a smooth projective algebraic curve over a field K. The Picard group of C is the group of (degree zero) K-rational divisors modulo principal divisors; it is analogous to the ideal class group of an algebraic number field. This group has several applications in cryptography and in algorithmic number theory.
I will describe fast algorithms for addition and inversion in the Picard group of an arbitrary curve of genus g. These algorithms consist of linear algebra on matrices of size O(g log g) x O(g). Each operation in the Picard group takes O(g^2.376) field operations in K using fast linear algebra. This represents a significant improvement over the previously best known algorithms for a general curve of genus g, which had a complexity of O(g^4).
Jürgen Klüners: Computing Galois groups
We present a new algorithm for computing Galois groups of univariate polynomials over the rationals which is implemented in Magma. This algorithm does not use any stored data and is therefore degree independent. Furthermore the algorithm is not restricted to irreducible polynomials.
The method can be extended to other ground fields and is based on the so-called Stauduhar algorithm. We use p-adic approximations of the roots of the given polynomial for our computations. A huge amount of work was spent to get an efficient program to compute "relative" invariants of permutation groups. This is joint work with Claus Fieker.
Gabi Nebe: Lattices and spherical designs
A t-design lattice is a lattice whose minimal vectors form a spherical t-design (as introduced by Delsarte, Goethals and Seidel in 1977). For t at least 4, these lattices yield local maxima for the density function. In the talk I will report on the classification of t-design lattices, which is known when t is at least 4 for n up to 12, and when t is at least 6 for n up to 22 and for n = 24.
There are only four 11-design lattices of dimension greater than 1 known: The Leech lattice in dimension 24 and the 3 known unimodular 48-dimensional lattices with minimum 6. The existence of t-design lattices for t at least 12 and n greater than 1 is still open.
This is joint work with Boris Venkov.
Alvaro Nolla de Celis: Mckay correspondence and Hilbert schemes
The Mckay correspondence was originally a correspondence between the topology of the minimal resolution of a quotient singularity originated by the action on C^2 by a finite subgroup G in SL(2,C), and the representation theory of the group G. Ito and Nakamura proved that this minimal resolution is the Hilbert scheme of G-orbits giving a new aproach to the Mckay correspondence. The role of Magma appears in the explicit calculation of this Hilbert scheme, where the study of the representation of the group G and the syzygies arising from it are required.
Andreas Previtali: Irreducible Constituents of Monomial Representations
We describe an algorithm to obtain the central primitive idempotents of the algebra associated to a monomial representation. As a consequence, we obtain its irreducible constituents. This is implemented in { Magma}, using an algorithm based on Dixon's modular approach. In the case of permutation representations, we get a simplified version of algorithms of Michler and Weller.
Jordi Quer: Fields of Definition of Building Blocks
I'll describe an implementation in Magma of the computation of the obstruction to descend the field of definition of a simple factor of the modular jacobian J_1(N), and show several interesting numerical examples obtained using that implementation, and applications.
Daniel Ryder: Elliptic and K3 fibrations birational to Fano varieties
Jasper Scholten: Cover attacks on the discrete logarithm problem on curves
Let C be a curve defined over a finite field. If the genus of C is small enough, the discrete logarithm problem (DLP) in the degree-zero divisor class group of C can be solved with Pollard's rho method, which has running time proportional to the square root of the group size. However, for certain curves defined over extension fields, the DLP can also be solved by a cover attack. In such an attack, the original DLP is transfered to a DLP on a curve of higher genus defined over a smaller field. In this talk we will given an overview of known constructions of curves for which a cover attack is more efficient than Pollard's rho method.
Allan Steel: TUTORIAL: Fundamentals of commutative algebra in Magma
We present an overview of all the fundamental structures and operations which lie at the base of Commutative Algebra in Magma. Many aspects of Groebner bases will be discussed, and their application to computations with ideals and quotients of multivariate polynomial rings.
Damien Stehlé: The new LLL routine in the Magma computational algebra system
The Lenstra Lenstra Lovasz algorithm is extensively used in the MAGMA computational algebra system, making it crucial to have a LLL routine which is as reliable and as fast as possible. For this purpose, the underlying code has been almost entirely rewritten, and the user interface has been changed.
In this talk, we will stress the improvements over the previous version by considering a few examples, explaining the new algorithms and heuristics that have been implemented and describing the updated user interface.
Yuri Tschinkel: Algebraic varieties over small fields
I will discuss recent results and constructions in higher- dimensional algebraic geometry over finite fields. In particular, I will explain rational connectivity questions over finite fields and their closures, and present examples of interesting surfaces of intermediate and general type.
Osmanbey Uzunkol: Recent Developments in KASH
Frederik Vercauteren: The number field sieve in the medium prime case
This talk describes several variations of the number field sieve to compute discrete logarithms in finite fields of the form GF(p^n), with p a medium to large prime. We show that when n is not too large, this yields a L_p^n(1/3) algorithm with efficiency similar to that of the regular number field sieve over prime fields. This approach complements the recent results of Joux and Lercier on the function field sieve (see Joux's talk). Combining both results, we deduce that computing discrete logarithms have heuristic complexity L_p^n(1/3) in all finite fields. To illustrate the efficiency of the algorithm, we provide details of a discrete logarithm computation in a 120-digit finite field F_p^3.
John Voight: Computational aspects of Shimura curves
The study of the classical modular curves has long proved rewarding for mathematicians both theoretically and computationally, and an expanding list of conjectures have been naturally generalized from to the setting of Shimura curves. However, only recently have the computational aspects of these curves been explored systematically.
We introduce Shimura curves and discuss some of the algorithmic problems in this area, including the computation of a fundamental domain.
Robert Vollmert: Computation in convex geometry with applications
The link between algebraic and convex geometry through toric geometry is well known. Magma does not yet implement parts of this large subject, although it is well placed to do so. I will explain some of the calculations that are used routinely by some geometers and illustrate them with Matthias Franz' package 'convex'.
Mark Watkins: Searching for points p-adically
We discuss a p-adic variant of the method of Elkies to find points on a rational variety. It works by finding all local solutions, computing a basis whose span contains all lifts to a given precision, and then testing for global solutions. Strangely, the method works better in higher dimension, as higher derivatives can be used to approximate the variety more closely. The method is quite practical for curves, but is more unwieldy as the dimension of the variety (and thus number of tangent directions) increases. We give additional examples from surfaces and threefolds, and discuss some aspects of the Magma implementation.