LMS Durham Symposium on Computational Number Theory
24 July - 3 August 2000

Home List of participants Program summary Full program Abstracts

Abstract of talks

Bernstein, Birch, Bruin, Cohen, Couveignes, Davenport, de Smit, Fisher, Flynn, Ford, Frey,
Galbraith and Smart, Gaudry, Hünlein, Jacobson, Klüners, Lauder, Matzat, Maurer, Morain,
Scheidler, Smyth, Teske, van der Poorten, Watkins, Williams, Stein

Rethinking the number field sieve

Dan BERNSTEIN (Chicago)

Abstract: How quickly can we factor 300-digit integers? This talk will review the number field sieve and explain some recent improvements.

40 years on

Bryan BIRCH (Oxford)

Abstract: Problems I gave Phd students...

Finding Rational Points on Curves of genus 3

Nils BRUIN (Utrecht)

Abstract: We will talk about covering techniques for finding rational points on curves of genus 3. A double cover of a curve of genus 5 can be mapped into a 2-dimensional variety. These are better understood than genus 3 Jacobians.

Explicit construction of number field extensions of small degree, with applications to discriminant counting

(Two talks)

Henri COHEN (Bordeaux)

Abstract: After reviewing some results coming from Class Field Theory and the theory of higher ramification groups, we show how to construct explicitly extensions of number fields of type Cl, Dl, A4 and S4 (l prime). We deduce from this both asymptotic and exact formulas for the number of such extensions. For absolute extensions, we explain some elementary number-theoretical methods which have allowed us to count the number of desired extensions up to very high discriminant (1037 in the best case C3).

This is joint work with F. Diaz y Diaz and M. Olivier.

Coverings of algebraic curves : explicit methods and applications

Jean-Marc COUVEIGNES (Toulouse)

Abstract: I would like to present a few notions from combinatorics, arithmetic , and toplogy that are of much use for the study of covers and then show applications to classical problems.

Recent Developments in Cryptography: What is "breaking RSA"

James DAVENPORT (Bath)

Abstract: RSA encryption has been with us for some 25 years, and the only known way of breaking it was to factor N=pq, find (N)=(p-1)(q-1) and hence the decrypting exponent. Coppersmith (1996) showed that certain uses of RSA could be broken by other means, viz. lattice reduction. We explain this, via Howgrave-Graham's (1999) approach to this. This leads us to explore the diference between "breaking a system" and "breaking the way a system is used". No prior knowledge of lattice reduction is required.

The interactive group theory of arithmetically equivalent fields

Bart DE SMIT (Leiden)

Abstract: This talk is about the classification of all possible Galois configurations of pairs of non-isomorphic number fields with the same zeta-function. This classification is now complete for solvable groups, and for extensions up to degree 22. These results stem from a combination of both computational and purely group-theoretic methods.

Estimating the rank of an elliptic curve over its field of n-division points

Tom FISHER (Cambridge)

Abstract: Some explicit descent calculations, with a discussion of finding units and/or Cassels-Tate pairing.

Fermat Quartics and a Challenge Curve of Serre

Victor FLYNN (Liverpool)

Abstract: A study of rational points on Fermat quartics of the form X4 + Y4 = c immediately reveals many values of c which can be dismissed by congruence considerations. Many other values of c can be dismissed if one of two associated elliptic curves has rank 0. What remains are the stubborn values of c which cannot be trivially dismissed: c = 17, 82, 97 and 257 being the only such less than 300. A solution of the case c = 17 (posed as a challenge by Serre) is presented, representing the first success with a nontrivial value of c, and we discuss the extent to which the method might hope to solve other difficult values of c. The talk is based on joint work with Joe Wetherell.

Polynomial factorization over p-adic fields

David FORD (Concordia)

David Ford, Sebastian Pauli, and Xavier-François Roblot


In the last year several new algorithms have appeared for the factorization of polynomials over finite extensions of ${\mathbb{Q} }_p$.

Height Conjectures and Galois Representations Attached to Elliptic Curves

Gerhard FREY (Essen)


I. The central question is: let K be a field with an interesting arithmetic (e.g. a finitely generated field) and A an étale finite group scheme defined over K. Can we find arithmetical or geometrical conditions for abelian varieties B defined over K such that A can (resp. cannot) be embedded (over K) into B?
We shall discuss this question mainly in the case that B is an elliptic curve.
As motivation we use results for function fields one variable over a perfect field. Here the Riemann-Hurwitz genus formula gives an easy proof for the ABC-conjecture. Its relation with height conjectures for elliptic curves and implications for Galois representations are explained and generalized to fields with divisor theory.

II. We discuss the special case that K=Q. Modular forms, modular curves and related Galois representations give both deep theoretical insights and can be used to compute interesting examples. Key words: Congruence primes and relations to the degree conjecture for modular parametrization and to the height conjecture for elliptic curves, Serre's conjecture for odd two-dimensional representations of GQ, theorems of Ribet-Carayol-Diamond, relation with Artin's conjecture. To illustrate these techniques we present work of A. Jehanne and M. Müller proving that Artin's conjecture is true for the isosahedral representation of GQ related to the quintic polynomial X5 +5X2-6X+27.

Elliptic Curve Cryptography and Weil descent

(Four talks)

Steven GALBRAITH (Essen), Nigel SMART (Bristol)

Abstract / Outline of the lectures:

  1. Galbraith: ECC -- Mathematical basis
    • ECDLP
    • Schoof
    • BSGS/Pollard
    • MOV/Frey-Ruck and SmartASS
    • hyperelliptic curves
  2. Smart: ECC -- Implementation
    • Protocols: ECDH, ECDSA, MQV, Implicit Certificates
    • Finite field implementations
    • Curve implementations
    • Interoperability and standards
  3. Smart: Weil Descent -- recent work
    • The problem: Frey's initial ideas
    • Some examples
    • The main theorem mapping the ECDLP to a HCDLP
    • Gaudry's method
    • Complexity
    • Constructive facets
    • Implications
  4. Galbraith: Weil Descent -- further and future work
    • Higher genus curves
    • Jacobians of curves
    • Open problems

Schoof's Algorithm in genus 2

Pierrick GAUDRY (Ecole Polytechnique)

Abstract: We shall present a genus 2 analogue of Schoof's Algorithm, and give some ideas towards an Elkies-Atkin approach.

Imaginary quadratic orders and cryptography

Detlef HÜHNLEIN (Secunet)

Abstract: A survey of cryptosystems based on imaginary quadratic orders including the principle of a generalization of Smart's anomalous attack against ECC.

Non-interactive Public-Key Cryptography

Mike JACOBSON (Waterloo)


A well-known problem with public-key cryptosystems in practice is that it is possible for an adversary to impersonate a user by substituting his public key for that of the user. Thus, before encryption, it is necessary to verify that the public key obtained does belong to the correct user. One common solution to this problem is to have a Key Generation Center (KGC) generate and issue the keys to all users, and provide certificates of authenticity for those keys upon request.

Another approach is to use a non-interactive identity-based public key distribution system. Here, the public keys are derived directly from some unique identification information (for example, the user's email address). The method used to embed identity information into the public key is published, so anyone can compute any user's public key. Authentication of keys is no longer required, but the KGC now has to compute the private keys for each user.

We present a new non-interactive public key distribution system based on the ideal class group of a non-maximal imaginary quadratic order. The main advantage of our system over earlier proposals based on integer arithmetic modulo a composite number is that embedding identity information into group elements in a cyclic subgroup of the class group is easy and secure, since the entire class group is cyclic with very high probability. In order to compute private keys the KGC must be able to solve the so-called discrete logarithm problem in the class group. We show that using certain trap-door information not available to the users, the KGC can compute these discrete logarithms reasonably efficiently while an adversary who does not possess the trap-door information cannot.

(Joint work with D. Hühnlein and D. Weber)

Constructive Galois Theory

Jürgen KLÜNERS (Heidelberg)

Abstract: We show that each transitive group up to degree 15 is a Galois group of a regular extension of Q(t). Furthermore we report on a database of fields up to degree 15 over Q which cover all transitive groups up to that degree and most of the possible signatures. For the completion of this database it is necessary to study central embedding problems. We prove that SL(2,11) is a Galois group of a regular extension of Q(t). Using methods from class field theory we explicitly construct a polynomial over Q with Galois group SL(2,11).

Fast absolute irreducibility testing for sparse polynomials

Alan LAUDER (Oxford)

Abstract: An algorithm for testing n-variable polynomials over arbitrary fields for absolute irreducibility will be presented. The algorithm, though heuristic, is especially effective for sparse polynomials with n>2. A "typical" polynomial with a few hundred terms will be checked to be absolutely irreducible in seconds.

Iterative Differential Equations and Abhyankar's Conjecture

B. Heinrich MATZAT (Heidelberg)

Abstract: We present an introduction to and applications of differential Galois Theory in positive characteristic.

Finding a generating unit by real-gcd computations

Markus MAURER (Darmstadt)

Abstract: Assuming the Extended Riemann Hypothesis, the complexity of the fastest method for computing the class number of a quadratic order of a number field is subexponential in the size of the discriminant D. Recently, it was shown by Vollmer [1], that for imaginary-quadratic orders the complexity is LD[1/2, 32/4], but he was not able to prove the same bound for real-quadratic orders. One reason is the lack of a fast method for finding a generating unit for a given set of units. If LD[1/2,v] is the size of the factor base, a method with complexity LD[1/2,3v] would be necessary. But the only method, of which complexity has been analyzed, uses the LLL-algorithm to solve the generating unit problem, and its complexity is LD[1/2,5v]. I will present a LD[1/2,3v] method, that uses continued fractions.

Modular Curves and Class Invariants

Francois MORAIN (Ecole Polytechnique)

Abstract: Weber's functions f, f1, f2 are used to compute "small" defining polynomials for ring class fields of imaginary quadratic fields. The functions are the roots of a modular equation for 0(2) and this fact has a great importance for the study of their algebraic properties. We show that replacing 0(2) by 0(N) for many values of N, we get new functions that ultimately give smaller defining polynomials. We also extend these results to the the group 0(N) U WN0(N) where WN is the Atkin-Lehner involution. Many numerical examples will be given.

Function Fields: Invariants and Cryptography

Renate SCHEIDLER (Waterloo)

Abstract: Function fields of small unit rank in cryptography and their relevance to invariant computation.

Finding torsion cosets on hypersurfaces

Chris SMYTH (Edinburgh)

Abstract: The problem of developing an algorithm for finding all torsion cosets on a hypersurface is considered. Also, the problem of finding bounds for the number of such torsion cosets of each relevant dimension is discussed.

Joint work with Beukers.

The parallelized Pollard Kangaroo method in real quadratic function fields

Edlyn TESKE (Waterloo)

Abstract: The Pollard kangaroo method is used to compute discrete logarithms in arbitray cyclic groups if the discrete log is known to lie in a certain interval. In contrast to the baby step-giant step method, it is very space efficient and can be parallelized with linear speed up.

In our talk, we discuss the parallelized kangaroo method and show how to apply it to the infrastructure in real quadratic function fields. We announce the computation of a 29-digit regulator of a random real quadratic function field of odd characteristic and of genus 3, which is the largest such computation done so far.

An introduction to NUCOMP

Alf VAN DER POORTEN (Macquarie)

Abstract: I provide a detailed explanation of the notorious Banff talks of Daniel Shanks and in particular generalise NUCOMP (composition with simultaneous reduction) to the case of indefinite forms.

Real zeros of real odd Dirichlet L-functions and class numbers of imaginary quadratic fields

Mark WATKINS (Georgia)

Abstract: We describe a method due to Low in the 1960s to show via computation that a real odd Dirichlet L-function has no real positive zeros. Then we say how we extended his results, and how the resulting experimental data helped us in the resolution of the class number 16 problem for imaginary quadratic fields.

A key exchange protocol based on real quadratic fields

Hugh WILLIAMS (Manitoba)

Abstract: I will speak about a key exchange protocol based on real quadratic fields, its implementation and its security.

Shafarevich-Tate groups of modular abelian varieties

William STEIN (Berkeley)

Abstract: I will describe the computation of provably nontrivial visible elements of Shafarevich-Tate groups of abelian varieties of large dimension.

Home List of participants Program summary Full program Abstracts

Page maintained by John Cremona
Last updated: 19 July 2000