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



July 10, 15:30 ~ 16:20

3-ranks of cubic class groups

Peter Stevenhagen

Universiteit Leiden, Netherlands   -

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   -

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

Fast Arithmetic in the Divisor Class Group

Jens Bauch

Simon Fraser University, Canada   -

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   -

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   -

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   -

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

Computing twists of hyperelliptic curves

Elisa Lorenzo García

Université de Rennes 1, Francia   -

In this talk we will see an algorithm for computing twists of hyperelliptic curves. We will see in details some of the key steps for computing the twists as well as some illustrative examples.

Joint work with D. Lombardo (Hannover).

View abstract PDF

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

Kummer arithmetic and compact signature schemes

Benjamin Smith

Inria and École polytechnique, France   -

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   -

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   -

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   -

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   -

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   -

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.