Home | List of participants | Program summary | Full program | Abstracts |
---|
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.
Bryan BIRCH (Oxford)
Abstract: Problems I gave Phd students...
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.
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 C_{l}, D_{l}, A_{4} and S_{4} (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 (10^{37} in the best case C_{3}).
This is joint work with F. Diaz y Diaz and M. Olivier.
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.
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.
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.
Tom FISHER (Cambridge)
Abstract: Some explicit descent calculations, with a discussion of finding units and/or Cassels-Tate pairing.
Victor FLYNN (Liverpool)
Abstract: A study of rational points on Fermat quartics of the form X^{4} + Y^{4} = 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.
David FORD (Concordia)
David Ford, Sebastian Pauli, and Xavier-François Roblot
Abstract: In the last year several new algorithms have appeared for the factorization of polynomials over finite extensions of .
Then there exists an algorithm that gives a factorization
of
into irreducible factors with the number of
additions and multiplications in
k being
Termination of Pauli's algorithm is guaranteed by the proposition below,
which is derived in part from Krasner's lemma.
Gerhard FREY (Essen)
Abstract:
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 G_{Q}, 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 G_{Q} related to the quintic polynomial X^{5} +5X^{2}-6X+27.
Steven GALBRAITH (Essen), Nigel SMART (Bristol)
Abstract / Outline of the lectures:
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.
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.
Mike JACOBSON (Waterloo)
Abstract: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)
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).
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.
B. Heinrich MATZAT (Heidelberg)
Abstract: We present an introduction to and applications of differential Galois Theory in positive characteristic.
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 L_{D}[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 L_{D}[1/2,v] is the size of the factor base, a method with complexity L_{D}[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 L_{D}[1/2,5v]. I will present a L_{D}[1/2,3v] method, that uses continued fractions.
Francois MORAIN (Ecole Polytechnique)
Abstract: Weber's functions f, f_{1}, f_{2} 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 W_{N}_{0}(N) where W_{N} is the Atkin-Lehner involution. Many numerical examples will be given.
Renate SCHEIDLER (Waterloo)
Abstract: Function fields of small unit rank in cryptography and their relevance to invariant computation.
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.
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.
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.
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.
Hugh WILLIAMS (Manitoba)
Abstract: I will speak about a key exchange protocol based on real quadratic fields, its implementation and its security.
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 |
---|