Workshop A3 - Computational Number Theory


Organizers: Christophe Ritzenhaler (Université de Rennes 1, France) - Enric Nart (Universitat Autònoma de Barcelona, Spain) - Tanja Lange (Technische Universiteit Eindhoven, Netherlands)

View workshop abstracts PDF

 

Talks


July 10, 15:30 ~ 16:20

3-ranks of cubic class groups

Peter Stevenhagen

Universiteit Leiden, Netherlands   -   psh@math.leidenuniv.nl

A lot is known about the 2-part of class groups of quadratic number fields, with fundamental results as old as Gauss's description of the genera of binary quadratic forms, and of their ambiguous classes. Results for 4-ranks and 8-ranks of quadratic class groups were proved by Redei (1939), and his methods have been used to prove density results for quadratic discriminants with 2-class groups of prescribed behaviour, and even some cases of the largely unproved Cohen-Lenstra heuristics for class groups.

In this talk, we explore analogues of the quadratic results in the context of 3-parts of class groups of cubic number fields.

Joint work with Erick Knight (Max Planck Institut für Mathematik, Bonn) and Abtien Javanpeykar (Universiteit Leiden).

View abstract PDF


July 10, 17:00 ~ 17:40

Rational points on high genus curves over finite fields

Alp Bassa

Bogazici University, Turkey   -   alp.bassa@boun.edu.tr

In this talk we will be concerned with rational points on algebraic curves over finite fields. The central result in this area is without doubt the Hasse—Weil Theorem, which implies strong bounds on the number of rational points. As noticed by Ihara, for curves of large genus this bound can be improved significantly. We will be interested in the question of how many rational points a high genus curve over a finite field can have. We will introduce several approaches to this problem and present a recent result (joint work with Beelen, Garcia, Stichtenoth) which provides strong lower bounds for the maximal possible number of rational points on curves over non-prime finite fields.

Joint work with Peter Beelen (DTU), Arnaldo Garcia (IMPA) and Henning Stichtenoth (Sabanci University).

View abstract PDF


July 10, 17:40 ~ 18:20

Construction of good families of codes from algebraic surfaces

Alain Couvreur

INRIA & LIX, Ecole Polytechnique, France   -   alain.couvreur@lix.polytechnique.fr

We present a new manner to bound below the parameters and in particular the minimum distance of a code from a smooth algebraic surface. Compared to previous approaches, this lower bound behaves well in the relative case: given a flat map $\pi : X \longrightarrow Y$ between to smooth projective surfaces, from a lower bound on the distance of a code on $Y$ associated to a divisor $G$, one deduces easily a lower bound for the distance of a code on $X$ associated to $\pi^*G$.

This motivates the study of criteria on surfaces to be the base of a tower providing asymptotically good codes. We present in particular a criterion based on cohomological and class field theoretical tools, to prove the existence of infinite étale towers above a given surface in which some fixed set of rational points splits totally.

Joint work with Philippe Lebacque (Laboratoire de Mathématiques de Besançon, France) and Marc Perret (Institut de Mathématiques de Toulouse, France).

View abstract PDF


July 10, 18:20 ~ 19:00

Fast Arithmetic in the Divisor Class Group

Jens Bauch

Simon Fraser University, Canada   -   jd.bauch@gmail.com

Let $C$ be a smooth projective geometrically irreducible algebraic curve of genus $g$ over a field $k$. The Jacobian variety $J$ of $C$ is a $g$-dimensional algebraic group that parametrizes the degree zero divisors on $C$, up to linear equivalence. Khuri-Makdisi showed that the basic arithmetic in $J$ can be realized in an asymptotic complexity of $O(g^{3+\epsilon})$ field operations in $k$. Denote by $F=k(C)$ the function field of the curve. Then the elements of $J$ can be identified with divisor classes $[D]$ of the function field $F/k$ where $D$ can be represented by a lattice $L_D$ over the polynomial ring $k[t]$. In fact, the class $[D]$ can be parametrized in terms of invariants of the lattice $L_D$. The basic arithmetic (addition and inversion) in $J$ can then be realized asymptotically in $O(g^3)$ field operations in $k$ and beats the one of Khuri-Makdisi. Under reasonable assumptions the runtime can be reduced to $O(g^2)$ field operations.

View abstract PDF


July 11, 14:50 ~ 15:30 - Room B6

A kilobit hidden SNFS discrete logarithm computation

Nadia Heninger

University of Pennsylvania, United States   -   nadiah@cis.upenn.edu

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software.

Our chosen prime $p$ looks random, and $p-1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our $p$ has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\mathbb{F}_p^*$, yet detecting that $p$ has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of backdoored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple conspicuously weak primes found in use in the wild.

Joint work with Joshua Fried (University of Pennsylvania), Pierrick Gaudry (INRIA, CNRS, Université de Lorraine) and Emmanuel Thomé (INRIA, CNRS, Université de Lorraine).

View abstract PDF


July 11, 15:30 ~ 16:20 - Room B6

Short generators without quantum computers: the case of multiquadratics

Daniel J. Bernstein

University of Illinois at Chicago, United States   -   conference-34e5ec3b68733@box.cr.yp.to

Finding a short element $g$ of a number field, given the ideal generated by $g$, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart--Vercauteren, Gentry--Halevi, Garg--Gentry--Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low *post-quantum* security level. The point of this talk is that for some number fields this problem has a surprisingly low *pre-quantum* security level.

Joint work with Jens Bauch, Henry de Valence, Tanja Lange and Christine van Vredendaal.

View abstract PDF


July 11, 17:00 ~ 17:40 - Room B6

Improvements to point counting on hyperelliptic curves of genus two

Maike Massierer

University of New South Wales, Australia   -   maike@unsw.edu.au

Schoof's algorithm is a standard method for counting points on elliptic curves defined over finite fields of large characteristic, and it was extended by Pila to higher-dimensional abelian varieties. Improvements by Elkies and Atkin lead to an even faster method for elliptic curves, known as the SEA algorithm. This is the current state of the art for elliptic curves. Motivated by the fact that Jacobians of hyperelliptic curves of genus two have been found to be good alternatives to elliptic curves in cryptography, we investigate the possibility of applying the improvements of Elkies and Atkin to Pila's point counting algorithm for such varieties. We prove analogous theoretical results for genus two Jacobians with real multiplication by maximal orders, and we discuss the challenges involved in the practical implementation, such as the computation of suitable modular ideals.

Joint work with S. Ballentine (University of Maryland), A. Guillevic (INRIA), E. Lorenzo García (Université de Rennes 1), C. Martindale (Universiteit Leiden), B. Smith (INRIA and LIX) and J. Top (University of Groningen).

View abstract PDF


July 11, 17:40 ~ 18:20 - Room B6

Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication

Elisa Lorenzo García

Université de Rennes 1, Francia   -   elisa.lorenzogarcia@univ-rennes1.fr

Schoof's classic algorithm allows point-counting for elliptic curves over finite fields in polynomial time. This algorithm was subsequently improved by Atkin, using factorizations of modular polynomials, and by Elkies, using a theory of explicit isogenies. Moving to Jacobians of genus-2 curves, the current state of the art for point counting is a generalization of Schoof's algorithm. While we are currently missing the tools we need to generalize Elkies' methods to genus 2, recently Martindale and Milio have computed analogues of modular polynomials for genus-2 curves whose Jacobians have real multiplication by maximal orders of small discriminant. In this article, we prove Atkin-style results for genus-2 Jacobians with real multiplication by maximal orders, with a view to using these new modular polynomials to improve the practicality of point-counting algorithms for these curves.

Joint work with S. Ballentine (University of Maryland), A. Guillevic (INRIA), C. Martindale (Universiteit Leiden), M. Massierer (University of New South Wales), B. Smith (INRIA and LIX) and J. Top (University of Groningen).

View abstract PDF


July 11, 18:20 ~ 19:00 - Room B6

Kummer arithmetic and compact signature schemes

Benjamin Smith

Inria and École polytechnique, France   -   smith@lix.polytechnique.fr

The Kummer surfaces of certain genus 2 curves offer fast scalar multiplication algorithms with a measure of built-in resistance to basic side-channel attacks. The corresponding algorithms for the Jacobians of these curves are far slower, more complicated, and are ultimately not competitive with elliptic curve-based cryptographic implementations. When implementing discrete logarithm-based signature schemes such as Schnorr signatures (and generalizations of ECDSA), the group structure on the Jacobian appears essential.

In recent work with Chung and Costello, we proposed algorithms to compute Jacobian-based signatures while exploiting the speed and safety of Kummer arithmetic. Moving from theory to practice, these algorithms were subsequently implemented for microcontroller platforms (with very limited computing resources) in joint work with Renes, Schwabe, and Batina; the results provided easily the most efficient secure signatures for microcontrollers to date. However, the increase in speed comes at the cost of heavy memory usage, largely due to the complicated formulae relating fast Kummer surfaces with their Jacobians.

In this talk we explain how to remove Jacobians from the picture entirely, presenting the first signature schemes requiring only Kummer arithmetic. The result is faster, simpler signatures with a much smaller memory footprint, suitable for use in constrained environments.

Joint work with Joost Renes (Radboud University Nijmegen, The Netherlands).

View abstract PDF


July 12, 14:50 ~ 15:30 - Room B6

Congruences, graphs and modular forms

Samuele Anni

University of Heidelberg, Germany   -   samuele.anni@gmail.com

The theory of congruences between modular forms is a central topic in contemporary number theory, lying at the basis of the proof of Mazur's theorem on torsion in elliptic curves, Fermat's Last Theorem, and Sato-Tate, amongst others. Congruences are a display of the interplay between geometry and arithmetic. In order to study them, in a joint work with Vandita Patel (University of Warwick), we are constructing graphs encoding congruence relations between newforms. These graphs have extremely interesting features: they help our understanding of the structure of Hecke algebras, and they are also a new tool in the study of numerous conjectures. In this talk I will describe these new objects, show examples and explain some of the possible applications.

Joint work with Vandita Patel (University of Warwick).

View abstract PDF


July 12, 15:30 ~ 16:20 - Room B6

Parity of ranks of abelian surfaces

Celine Maistret

University of Bristol, United Kingdom   -   c.maistret@warwick.ac.uk

Let $K$ be a number field and $A/K$ an abelian surface. By the Mordell-Weil theorem, the group of $K$-rational points on $A$ is finitely generated and as for elliptic curves, its rank is predicted by the Birch and Swinnerton-Dyer conjecture. A basic consequence of this conjecture is the parity conjecture: the sign of the functional equation of the L-series determines the parity of the rank of $A/K$. Under suitable local constraints and finiteness of the Shafarevich-Tate group, we prove the parity conjecture for principally polarized abelian surfaces. We also prove analogous unconditional results for Selmer groups.

View abstract PDF


July 12, 17:00 ~ 17:40 - Room B6

Rigorous computation of the endomorphism ring of a Jacobian

Jeroen Sijsling

Universität Ulm, Germany   -   sijsling@gmail.com

Consider a curve $X$, defined by an explicit equation, over a number field. Let $J$ be the Jacobian of $X$. The endomorphism ring $E$ of $J$ is an important arithmetic invariant of $X$; for example, the Sato-Tate group of $X$ can be recovered from the Galois module structure of $E$.

Heuristically, the ring $E$ can be determined quite quickly. In this talk, we consider the rigor of such calculations. In particular, we give an algorithm that verifies whether a putative tangent representation of an endomorphism in fact globalizes, It does not use complex approximations and is, to our knowledge, the first general-purpose algorithm over number fields that provably terminates. We then discuss how this algorithm can be combined with other techniques to rigorously compute the ring $E$.

Joint work with Edgar Costa (Dartmouth College), Nicolas Mascot (University of Warwick) and John Voight (Dartmouth College).

View abstract PDF


July 12, 17:40 ~ 18:20 - Room B6

Genetics of polynomials over local fields

Guàrdia Jordi

Universitat Politècnica de Catalunya, Catalunya   -   jordi.guardia-rubies@upc.edu

Let $(K,v)$ be a discrete valued field with valuation ring $\mathcal{O}$, and let $\mathcal{O}_v$ be the completion of $\mathcal{O}$ with respect to the $v$-adic topology. In our talk we will discuss the advantages of manipulating polynomials in $\mathcal{O}_v[x]$ in a computer by means of OM representations of prime polynomials. An OM representation supports discrete data that are a kind of DNA sequence common to all individuals in the Okutsu equivalence class of the prime polynomial. These discrete parameters contain relevant arithmetic information about the polynomial and the extension of $K_v$ it determines.

Joint work with Enric Nart (Universitat Autònoma de Barcelona, Catalonia).

View abstract PDF


July 12, 18:20 ~ 19:00 - Room B6

Rational point count distributions for plane quartic curves over finite fields

Nathan Kaplan

University of California, Irvine, USA   -   nckaplan@math.uci.edu

We use ideas from coding theory, specifically the MacWilliams theorem, to study rational point count distributions for quartic curves in the projective plane over a finite field. We explain how the set of all homogeneous quartic polynomials in three variables gives rise to an evaluation code, and how low-weight coefficients of the weight enumerator of the dual code give information about rational point count distributions for quartic curves. No previous familiarity with coding theory will be assumed.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.