Algorithmic Number Theory

The Hodge conjecture asserts that the presence of algebraic cycles on a (smooth, projective) variety over the complex numbers can be detected in its Betti cohomology equipped with the Hodge structure arising from its relation with complex deRham cohomology. The Tate conjecture makes a similar assertion with ℓ-adic cohomology replacing Betti cohomology. One of the difficulties with these conjectures is that the predictions that they make are often hard to test numerically, even in specific concrete instances. Unlike closely related parts of number theory (a case in point being the Birch and Swinnerton-Dyer conjecture) the study of algebraic cycles has therefore not been as strongly affected by the growth of the experimental and computational community as it perhaps could be. In this lecture, I will describe some numerical experiments that are designed to “test” the Hodge and Tate conjectures for certain varieties (of arbitrarily large dimension) which arise from elliptic curves with complex multiplication and theta series of CM Hecke characters.

In this talk, we construct curves of genus 3 with automorphism group equal to S₃; we give some applications of this construction to the problem of optimal curves, i.e. of curves over a finite field \(\mathbb{F}_q\) having a number of points equal to the Serre-Weil bound M _q ; in particular, we prove that there exists infinitely many fields \(\mathbb{F}_{3^n}\) having optimal curves; we prove also that there exists an integer C such that, for any finite field \(\mathbb{F}_{7^n}\), there exists a curve of genus 3 defined over having at least M _q  − C points.

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. After a short introduction to the area, we will discuss recent work on making LWE and its applications truly efficient by exploiting extra algebraic structure. Namely, we will define the ring-LWE problem, and prove that it too enjoys very strong hardness guarantees.

Based on joint work with Vadim Lyubashevsky and Chris Peikert.

A lattice is a finitely generated discrete subgroup of Euclidean space. Lattices are an important algorithmic tool in number theory, integral representation theory, geometry, information theory, cryptography, crystallography and have various other applications within mathematics and beyond. Any lattice has only finitely many vectors of a given length, they form the layers of the lattice, which are finite subsets of spheres in the underlying Euclidean space.

We establish a conjecture of Brizolis that for every prime p > 3 there is a primitive root g and an integer x in the interval [1,p − 1] with log _g x = x. Here, log _g is the discrete logarithm function to the base g for the cyclic group (ℤ/pℤ)^×. Tools include a numerically explicit “smoothed” version of the Pólya–Vinogradov inequality for the sum of values of a Dirichlet character on an interval, a simple lower bound sieve, and an exhaustive search over small cases.

Coleman’s theory of p-adic integration figures prominently in several number-theoretic applications, such as finding torsion and rational points on curves, and computing p-adic regulators in K-theory (including p-adic heights on elliptic curves). We describe an algorithm for computing Coleman integrals on hyperelliptic curves, and its implementation in Sage.

We present a variant of the Lagrange-Gauss reduction of quadratic forms designed to minimize the norm of the reduction matrix within a quadratic complexity. The matrix computed by our algorithm on the input f has norm \(O(\parallel f \parallel^{1/2}/\Delta_{f}^{1/4})\), which is the square root of the best previously known bounds using classical algorithms. This new bound allows us to fully prove the heuristic lattice based attack against NICE Cryptosystems, which consists in factoring a particular subclass of integers of the form pq ². In the process, we set up a homogeneous variant of Boneh-Durfee-HowgraveGraham’s algorithm which finds small rational roots of a polynomial modulo unknown divisors. Such algorithm can also be used to speed-up factorization of pq ^r for large r.

We present improvements to the index-calculus algorithm for the computation of the ideal class group and regulator of a real quadratic field. Our improvements consist of applying the double large prime strategy, an improved structured Gaussian elimination strategy, and the use of Bernstein’s batch smoothness algorithm. We achieve a significant speed-up and are able to compute the ideal class group structure and the regulator corresponding to a number field with a 110-decimal digit discriminant.

The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of \(\sqrt 2\) generally reported in the literature, it is supported by practical evidence.

The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n)logn), using Schönhage’s fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n)logn) algorithm based on the binary recursive gcd algorithm of Stehlé and Zimmermann. Our implementation — which to our knowledge is the first to run in time O(M(n)logn) — is faster than GMP’s quadratic implementation for inputs larger than about 10000 decimal digits.

In this paper we study structures related to torsion of elliptic curves defined over number fields. The aim is to build families of elliptic curves more efficient to help factoring numbers of special form, including numbers from the Cunningham Project. We exhibit a family of curves with rational ℤ/4ℤ×ℤ/4ℤ torsion and positive rank over the field ℚ(ζ ₈) and a family of elliptic curves with rational ℤ/6ℤ×ℤ/3ℤ torsion and positive rank over the field ℚ(ζ ₃). These families have been used in finding new prime factors for the numbers 2⁹⁷² + 1 and 2¹⁰⁴⁸ + 1. Along the way, we classify and give a parameterization of modular curves for some torsion subgroups.

Mazur proved that any element ξ of order three in the Shafarevich-Tate group of an elliptic curve E over a number field k can be made visible in an abelian surface A in the sense that ξ lies in the kernel of the natural homomorphism between the cohomology groups \(H^1({\rm Gal}({\overline k}/k),E) \rightarrow H^1({\rm Gal}({\overline k}/k),A)\). However, the abelian surface in Mazur’s construction is almost never a jacobian of a genus 2 curve. In this paper we show that any element of order three in the Shafarevich-Tate group of an elliptic curve over a number field can be visualized in the jacobians of a genus 2 curve. Moreover, we describe how to get explicit models of the genus 2 curves involved.

For K3 surfaces, we derive some conditions the characteristic polynomial of the Frobenius on the étale cohomology must satisfy. These conditions may be used to speed up the computation of Picard numbers and the decision of the sign in the functional equation^**. Our investigations are based on the Artin-Tate formula.

We adapt the CRT approach for computing Hilbert class polynomials to handle a wide range of class invariants. For suitable discriminants D, this improves its performance by a large constant factor, more than 200 in the most favourable circumstances. This has enabled record-breaking constructions of elliptic curves via the CM method, including examples with |D| > 10¹⁵.

Lattices over number fields arise from a variety of sources in algorithmic algebra and more recently cryptography. Similar to the classical case of ℤ-lattices, the choice of a nice, “short” (pseudo)-basis is important in many applications. In this article, we provide the first algorithm that computes such a “short” (pseudo)-basis. We utilize the LLL algorithm for ℤ-lattices together with the Bosma-Pohst-Cohen Hermite Normal Form and some size reduction technique to find a pseudo-basis where each basis vector belongs to the lattice and the product of the norms of the basis vectors is bounded by the lattice determinant, up to a multiplicative factor that is a field invariant. As it runs in polynomial time, this provides an effective variant of Minkowski’s second theorem for lattices over number fields.

Let p be a rational prime and let Φ(X) be a monic irreducible polynomial in Z[X], with nΦ = degΦ and δΦ = v _p (discΦ). In [13] Montes describes an algorithm for the decomposition of the ideal \(p\mathcal{O}K\) in the algebraic number field K generated by a root of Φ. A simplified version of the Montes algorithm, merely testing Φ(X) for irreducibility over Q _p , is given in [19], together with a full Maple implementation and a demonstration that in the worst case, when Φ(X) is irreducible over Q _p , the expected number of bit operations for termination is O(nΦ^3 + ε δΦ^2 + ε ). We now give a refined analysis that yields an improved estimate of O(nΦ^3 + ε δΦ + nΦ^2 + ε δΦ^2 + ε ) bit operations. Since the worst case of the simplified algorithm coincides with the worst case of the original algorithm, this estimate applies as well to the complete Montes algorithm.

We report on a computation of congruent numbers, which subject to the Birch and Swinnerton-Dyer conjecture is an accurate list up to 10¹². The computation involves multiplying long theta series as per Tunnell (1983). The method, which we describe in some detail, uses a multimodular disk based technique for multiplying polynomials out-of-core which minimises expensive disk access by keeping data truncated.

Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are ℓ-isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his thesis (1996) and later on, by Fouquet and Morain (2001). However, up to now, no method was known, to predict, before taking a step on the volcano, the direction of this step. Hence, in Kohel’s and Fouquet-Morain algorithms, we take many steps before choosing the right direction. In particular, ascending or horizontal isogenies are usually found using a trial-and-error approach. In this paper, we propose an alternative method that efficiently finds all points P of order ℓ such that the subgroup generated by P is the kernel of an horizontal or an ascending isogeny. In many cases, our method is faster than previous methods.

An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous best known algorithm has a worst case running time which is exponential in the length of the input. In this paper we show this problem can be solved in subexponential time under reasonable heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

This paper revisits a model for elliptic curves over ℚ introduced by Huff in 1948 to study a diophantine problem. Huff’s model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of ℤ/4ℤ ×ℤ/2ℤ is birationally equivalent to a Huff curve over the original field.

This paper extends and generalizes Huff’s model. It presents fast explicit formulæ for point addition and doubling on Huff curves. It also addresses the problem of the efficient evaluation of pairings over Huff curves. Remarkably, the so-obtained formulæ feature some useful properties, including completeness and independence of the curve parameters.

In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller’s algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension 1 and 2 abelian varieties our algorithms lead to implementations which are efficient and naturally deterministic. We also introduce symmetric Weil and Tate pairings on Kummer varieties and explain how to compute them efficiently. We exhibit a nice algorithmic compatibility between some algebraic groups quotiented by the action of the automorphism − 1, where the ℤ-action can be computed efficiently with a Montgomery ladder type algorithm.

Let f(x) ∈ Z[x] be a totally real polynomial with roots α ₁ ≤ ... ≤ α _d . The span of f(x) is defined to be α _d  − α ₁. Monic irreducible f(x) of span less than 4 are special. In this paper we give a complete classification of those small-span polynomials which arise as characteristic polynomials of integer symmetric matrices. As one application, we find some low-degree polynomials that do not arise as the minimal polynomial of any integer symmetric matrix: these provide low-degree counterexamples to a conjecture of Estes and Guralnick [6].

We propose some kind of new attack which gives the solution of the discrete logarithm problem for the Jacobian of a curve defined over an extension field \(\mathbb{F}_{q^{n}}\), considering the set of the union of factor basis and large primes B ₀ given by points of the curve whose x-coordinates lie in \(\mathbb{F}_q\). In this attack, an element of the divisor group which is written by a sum of some elements of factor basis and large primes is called (potentially) decomposed and the set of the factors that appear in the sum, is called decomposed factors. So, it will be called decomposition attack. In order to analyze the running of the decomposition attack, a test for the (potential) decomposedness and the computation of the decomposed factors are needed. Here, we show that the test to determine if an element of the Jacobian (i.e., reduced divisor) is written by an ng sum of the elements of the decomposed factors and the computation of decomposed factors are reduced to the problem of solving some multivariable polynomial system of equations by using the Riemann-Roch theorem. In particular, in the case of hyperelliptic curves of genus g, we construct a concrete system of equations, which satisfies these properties and consists of (n ² − n)g quadratic equations. Moreover, in the case of (g,n) = (1,3),(2,2) and (3,2), we give examples of the concrete computation of the decomposed factors by using the computer algebra system Magma.

We present an algorithm for factoring polynomials over local fields, in which the Montes algorithm is combined with elements from Zassenhaus Round Four algorithm. This algorithm avoids the computation of characteristic polynomials and the resulting precision problems that occur in the Round Four algorithm.

We prove a result that finishes the study of primitive arithmetic progressions consisting of squares and fifth powers that was carried out by Hajdu and Tengely in a recent paper: The only arithmetic progression in coprime integers of the form (a ², b ², c ², d ⁵) is (1, 1, 1, 1). For the proof, we first reduce the problem to that of determining the sets of rational points on three specific hyperelliptic curves of genus 4. A 2-cover descent computation shows that there are no rational points on two of these curves. We find generators for a subgroup of finite index of the Mordell-Weil group of the last curve. Applying Chabauty’s method, we prove that the only rational points on this curve are the obvious ones.

We extend the known tables of pseudosquares and pseudocubes, discuss the implications of these new data on the conjectured distribution of pseudosquares and pseudocubes, and present the details of the algorithm used to do this work. Our algorithm is based on the space-saving wheel data structure combined with doubly-focused enumeration, run in parallel on a cluster supercomputer.

We show that a specific even unimodular lattice of dimension 80, first investigated by Schulze-Pillot and others, is extremal (i.e., the minimal nonzero norm is 8). This is the third known extremal lattice in this dimension. The known part of its automorphism group is isomorphic to SL ₂(F ₇₉), which is smaller (in cardinality) than the two previous examples. The technique to show extremality involves using the positivity of the Θ-series, along with fast vector enumeration techniques including pruning, while also using the automorphisms of the lattice.

We extend methods of Greenberg and the author to compute in the cohomology of a Shimura curve defined over a totally real field with arbitrary class number. Via the Jacquet-Langlands correspondence, we thereby compute systems of Hecke eigenvalues associated to Hilbert modular forms of arbitrary level over a totally real field of odd degree. We conclude with two examples which illustrate the effectiveness of our algorithms.

In August 2002, Agrawal, Kayal, and Saxena described an unconditional, deterministic algorithm for proving the primality of an integer N. Though of immense theoretical interest, their technique, even incorporating the many improvements that have been proposed since its publication, remains somewhat slow for practical application. This paper describes a new, highly efficient method for certifying the primality of an integer \(N \equiv 1 \pmod 3\), making use of quantities known as Eisenstein pseudocubes. This improves on previous attempts, including the peudosquare-based approach of Lukes et al., and the pseudosquare improvement proposed by Berrizbeitia, et al.

Let F/ℚ be a number field. The space of positive definite binary Hermitian forms over F form an open cone in a real vector space. There is a natural decomposition of this cone into subcones. In the case of an imaginary quadratic field these subcones descend to hyperbolic space to give rise to tessellations of 3-dimensional hyperbolic space by ideal polytopes. We compute the structure of these polytopes for a range of imaginary quadratic fields.