In this paper we consider ordinary elliptic curves over global function fields of characteristic $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}2$. We present a method for performing a descent by using powers of the Frobenius and the Verschiebung. An examination of the local images of the descent maps together with a duality theorem yields information about the global Selmer groups. Explicit models for the homogeneous spaces representing the elements of the Selmer groups are given and used to construct independent points on the elliptic curve. As an application we use descent maps to prove an upper bound for the naive height of an $S$-integral point on $A$. To illustrate our methods, a detailed example is presented.

We construct explicit $K3$ surfaces over $\mathbb{Q}$ having real multiplication. Our examples are of geometric Picard rank 16. The standard method for the computation of the Picard rank provably fails for the surfaces constructed.

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}f\in S_2(\Gamma _0(N))$ be a normalized newform such that the abelian variety $A_f$ attached by Shimura to $f$ is the Jacobian of a genus-two curve. We give an efficient algorithm for computing Galois representations associated to such newforms.

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie in overlattices or translated cosets of overlattices. The key idea is hence no longer to work with a single lattice but to move the problems around in a tower of related lattices. We initiate the algorithm by sampling very short vectors in an overlattice of the original lattice that admits a quasi-orthonormal basis and hence an efficient enumeration of vectors of bounded norm. Taking sums of vectors in the sample, we construct short vectors in the next lattice. Finally, we obtain solution vector(s) in the initial lattice as a sum of vectors of an overlattice. The complexity analysis relies on the Gaussian heuristic. This heuristic is backed by experiments in low and high dimensions that closely reflect these estimates when solving hard lattice problems in the average case.

This new approach allows us to solve not only shortest vector problems, but also closest vector problems, in lattices of dimension $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}n$ in time $2^{0.3774\, n}$ using memory $2^{0.2925\, n}$. Moreover, the algorithm is straightforward to parallelize on most computer architectures.

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\mathcal{O}$ be a maximal order in the quaternion algebra $B_p$ over $\mathbb{Q}$ ramified at $p$ and $\infty $. The paper is about the computational problem: construct a supersingular elliptic curve $E$ over $\mathbb{F}_p$ such that ${\rm End}(E) \cong \mathcal{O}$. We present an algorithm that solves this problem by taking gcds of the reductions modulo $p$ of Hilbert class polynomials.

New theoretical results are required to determine the complexity of our algorithm. Our main result is that, under certain conditions on a rank three sublattice $\mathcal{O}^T$ of $\mathcal{O}$, the order $\mathcal{O}$ is effectively characterized by the three successive minima and two other short vectors of $\mathcal{O}^T\! .$ The desired conditions turn out to hold whenever the $j$-invariant $j(E)$, of the elliptic curve with ${\rm End}(E) \cong \mathcal{O}$, lies in $\mathbb{F}_p$. We can then prove that our algorithm terminates with running time $O(p^{1+\varepsilon })$ under the aforementioned conditions.

As a further application we present an algorithm to simultaneously match all maximal order types with their associated $j$-invariants. Our algorithm has running time $O(p^{2.5 + \varepsilon })$ operations and is more efficient than Cerviño’s algorithm for the same problem.

We present a higher-dimensional generalization of the Gama–Nguyen algorithm (STOC ’08) for approximating the shortest vector problem in a lattice. This generalization approximates the densest sublattice by using a subroutine solving the exact problem in low dimension, such as the Dadush–Micciancio algorithm (SODA ’13). Our approximation factor corresponds to a natural inequality on Rankin’s constant derived from Rankin’s inequality.

In this paper we give a new formula for adding $2$-coverings and $3$-coverings of elliptic curves that avoids the need for any field extensions. We show that the $6$-coverings obtained can be represented by pairs of cubic forms. We then prove a theorem on the existence of such models with integer coefficients and the same discriminant as a minimal model for the Jacobian elliptic curve. This work has applications to finding rational points of large height on elliptic curves.

We study new families of curves that are suitable for efficiently parametrizing their moduli spaces. We explicitly construct such families for smooth plane quartics in order to determine unique representatives for the isomorphism classes of smooth plane quartics over finite fields. In this way, we can visualize the distributions of their traces of Frobenius. This leads to new observations on fluctuations with respect to the limiting symmetry imposed by the theory of Katz and Sarnak.

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}G$ be a cyclic group written multiplicatively (and represented in some concrete way). Let $n$ be a positive integer (much smaller than the order of $G$). Let $g,h\in G$. The bounded height discrete logarithm problem is the task of finding positive integers $a$ and $b$ (if they exist) such that $a\leq n$, $b\leq n$ and $g^a=h^b$. (Provided that $b$ is coprime to the order of $g$, we have $h=g^{a/b}$ where $a/b$ is a rational number of height at most $n$. This motivates the terminology.)

The paper provides a reduction to the two-dimensional discrete logarithm problem, so the bounded height discrete logarithm problem can be solved using a low-memory heuristic algorithm for the two-dimensional discrete logarithm problem due to Gaudry and Schost. The paper also provides a low-memory heuristic algorithm to solve the bounded height discrete logarithm problem in a generic group directly, without using a reduction to the two-dimensional discrete logarithm problem. This new algorithm is inspired by (but differs from) the Gaudry–Schost algorithm. Both algorithms use $O(n)$ group operations, but the new algorithm is faster and simpler than the Gaudry–Schost algorithm when used to solve the bounded height discrete logarithm problem. Like the Gaudry–Schost algorithm, the new algorithm can easily be carried out in a distributed fashion.

The bounded height discrete logarithm problem is relevant to a class of attacks on the privacy of a key establishment protocol recently published by EMVCo for comment. This protocol is intended to protect the communications between a chip-based payment card and a terminal using elliptic curve cryptography. The paper comments on the implications of these attacks for the design of any final version of the EMV protocol.

This paper presents an algorithm to construct cryptographically strong genus $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}2$ curves and their Kummer surfaces via Rosenhain invariants and related Kummer parameters. The most common version of the complex multiplication (CM) algorithm for constructing cryptographic curves in genus 2 relies on the well-studied Igusa invariants and Mestre’s algorithm for reconstructing the curve. On the other hand, the Rosenhain invariants typically have much smaller height, so computing them requires less precision, and in addition, the Rosenhain model for the curve can be written down directly given the Rosenhain invariants. Similarly, the parameters for a Kummer surface can be expressed directly in terms of rational functions of theta constants. CM-values of these functions are algebraic numbers, and when computed to high enough precision, LLL can recognize their minimal polynomials. Motivated by fast cryptography on Kummer surfaces, we investigate a variant of the CM method for computing cryptographically strong Rosenhain models of curves (as well as their associated Kummer surfaces) and use it to generate several example curves at different security levels that are suitable for use in cryptography.

This paper introduces ‘hyper-and-elliptic-curve cryptography’, in which a single high-security group supports fast genus-2-hyperelliptic-curve formulas for variable-base-point single-scalar multiplication (for example, Diffie–Hellman shared-secret computation) and at the same time supports fast elliptic-curve formulas for fixed-base-point scalar multiplication (for example, key generation) and multi-scalar multiplication (for example, signature verification).

The problem of solving polynomial equations over finite fields has many applications in cryptography and coding theory. In this paper, we consider polynomial equations over a ‘large’ finite field with a ‘small’ characteristic. We introduce a new algorithm for solving this type of equations, called the successive resultants algorithm (SRA). SRA is radically different from previous algorithms for this problem, yet it is conceptually simple. A straightforward implementation using Magma was able to beat the built-in Roots function for some parameters. These preliminary results encourage a more detailed study of SRA and its applications. Moreover, we point out that an extension of SRA to the multivariate case would have an important impact on the practical security of the elliptic curve discrete logarithm problem in the small characteristic case.

Supplementary materials are available with this article.

In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thomé, a quasi-polynomial time algorithm is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular when the field is not a Kummer extension. We propose a fix to the algorithm in non-Kummer cases, without altering the heuristic quasi-polynomial time complexity. Further study is required in order to fully understand the effectiveness of the new approach.

In this paper we study the discrete logarithm problem in medium- and high-characteristic finite fields. We propose a variant of the number field sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\mathbb{F}_{p^n}$ for the whole range of applicability of the NFS and lowers the asymptotic complexity from $L_{p^n}({1/3},({128/9})^{1/3})$ to $L_{p^n}({1/3},(2^{13}/3^6)^{1/3})$ in the medium-characteristic case, and from $L_{p^n}({1/3},({64/9})^{1/3})$ to $L_{p^n}({1/3},((92 + 26 \sqrt{13})/27)^{1/3})$ in the high-characteristic case.

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}A^{0}(\Gamma _{2})$ denote the ring of scalar-valued Siegel modular forms of degree two, level $1$ and even weights. In this paper, we prove the determinant of a basis of the module of vector-valued Siegel modular forms $\bigoplus _{k \equiv \epsilon \ {\rm mod}\ {2}}A_{\det ^{k}\otimes \mathrm{Sym}(j)}(\Gamma _{2})$ over $A^{0}(\Gamma _{2})$ is equal to a power of the cusp form of degree two and weight $35$ up to a constant. Here $j = 4, 6$ and $\epsilon = 0, 1$. The main result in this paper was conjectured by Ibukiyama (Comment. Math. Univ. St. Pauli 61 (2012) 51–75).

We present an efficient algorithm to compute the Hasse–Witt matrix of a hyperelliptic curve $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}C/\mathbb{Q}$ modulo all primes of good reduction up to a given bound $N$, based on the average polynomial-time algorithm recently proposed by the first author. An implementation for hyperelliptic curves of genus 2 and 3 is more than an order of magnitude faster than alternative methods for $N = 2^{26}$.

We present a new method to propagate $p$-adic precision in computations, which also applies to other ultrametric fields. We illustrate it with some examples and give a toy application to the stable computation of the SOMOS 4 sequence.

We propose a fast method of calculating the $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}p$-part of the class numbers in certain non-cyclotomic $\mathbb{Z}_p$-extensions of an imaginary quadratic field using elliptic units constructed by Siegel functions. We carried out practical calculations for $p=3$ and determined $\lambda $-invariants of such $\mathbb{Z}_3$-extensions which were not known in our previous paper.

There is an algorithm of Schoof for finding divisors of class numbers of real cyclotomic fields of prime conductor. In this paper we introduce an improvement of the elliptic analogue of this algorithm by using a subgroup of elliptic units given by Weierstrass forms. These elliptic units which can be expressed in terms of $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}x$-coordinates of points on elliptic curves enable us to use the fast arithmetic of elliptic curves over finite fields.

We find all quadratic post-critically finite (PCF) rational functions defined over $\mathbb{Q}$, up to conjugation by elements of $\mathop{\rm PGL}_2(\overline{\mathbb{Q}})$. We describe an algorithm to search for possibly PCF functions. Using the algorithm, we eliminate all but 12 rational functions, all of which are verified to be PCF. We also give a complete description of all possible rational preperiodic structures for quadratic PCF functions defined over $\mathbb{Q}$.