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 describe algorithms that allow the computation of fundamental domains in the Bruhat–Tits tree for the action of discrete groups arising from quaternion algebras. These algorithms are used to compute spaces of rigid modular forms of arbitrary even weight, and we explain how to evaluate such forms to high precision using overconvergent methods. Finally, these algorithms are applied to the calculation of conjectural equations for the canonical embedding of p-adically uniformizable rational Shimura curves. We conclude with an example in the case of a genus 4 Shimura curve.

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.

We show that if a Barker sequence of length $n>13$ exists, then either n $=$ 3 979 201 339 721 749 133 016 171 583 224 100, or $n > 4\cdot 10^{33}$. This improves the lower bound on the length of a long Barker sequence by a factor of nearly $2000$. We also obtain eighteen additional integers $n<10^{50}$ that cannot be ruled out as the length of a Barker sequence, and find more than 237 000 additional candidates $n<10^{100}$. These results are obtained by completing extensive searches for Wieferich prime pairs and using them, together with a number of arithmetic restrictions on $n$, to construct qualifying integers below a given bound. We also report on some updated computations regarding open cases of the circulant Hadamard matrix problem.

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.

As a contribution to an eventual solution of the problem of the determination of the maximal subgroups of the Monster we prove that the Monster does not contain any subgroup isomorphic to $\mathrm{PSL}_2(27)$.

Supplementary materials are available with this article.

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.

The zeros of certain different sequences of orthogonal polynomials interlace in a well-defined way. The study of this phenomenon and the conditions under which it holds lead to a set of points that can be applied as bounds for the extreme zeros of the polynomials. We consider different sequences of the discrete orthogonal Meixner and Kravchuk polynomials and use mixed three-term recurrence relations, satisfied by the polynomials under consideration, to identify bounds for the extreme zeros of Meixner and Kravchuk polynomials.

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.

Let $Q(N;q,a)$ be the number of squares in the arithmetic progression $qn+a$, for $n=0$,$1,\ldots,N-1$, and let $Q(N)$ be the maximum of $Q(N;q,a)$ over all non-trivial arithmetic progressions $qn + a$. Rudin’s conjecture claims that $Q(N)=O(\sqrt{N})$, and in its stronger form that $Q(N)=Q(N;24,1)$ if $N\ge 6$. We prove the conjecture above for $6\le N\le 52$. We even prove that the arithmetic progression $24n+1$ is the only one, up to equivalence, that contains $Q(N)$ squares for the values of $N$ such that $Q(N)$ increases, for $7\le N\le 52$ ($N=8,13,16,23,27,36,41$ and $52$).

Supplementary materials are available with this article.

This paper contains some applications of the description of knot diagrams by genus, and Gabai’s methods of disk decomposition. We show that there exists no genus one knot of canonical genus 2, and that canonical genus 2 fiber surfaces realize almost every Alexander polynomial only finitely many times (partially confirming a conjecture of Neuwirth).

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.

Let $G(q)$ be a finite Chevalley group, where $q$ is a power of a good prime $p$, and let $U(q)$ be a Sylow $p$-subgroup of $G(q)$. Then a generalized version of a conjecture of Higman asserts that the number $k(U(q))$ of conjugacy classes in $U(q)$ is given by a polynomial in $q$ with integer coefficients. In [S. M. Goodwin and G. Röhrle, J. Algebra 321 (2009) 3321–3334], the first and the third authors of the present paper developed an algorithm to calculate the values of $k(U(q))$. By implementing it into a computer program using $\mathsf{GAP}$, they were able to calculate $k(U(q))$ for $G$ of rank at most five, thereby proving that for these cases $k(U(q))$ is given by a polynomial in $q$. In this paper we present some refinements and improvements of the algorithm that allow us to calculate the values of $k(U(q))$ for finite Chevalley groups of rank six and seven, except $E_7$. We observe that $k(U(q))$ is a polynomial, so that the generalized Higman conjecture holds for these groups. Moreover, if we write $k(U(q))$ as a polynomial in $q-1$, then the coefficients are non-negative.

Under the assumption that $k(U(q))$ is a polynomial in $q-1$, we also give an explicit formula for the coefficients of $k(U(q))$ of degrees zero, one and two.

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.

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field ${\mathbb{F}}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the art by focusing on prime degree polynomials; let $n$ be the degree. If $(n-1)$ has a ‘large’ $r$-smooth divisor $s$, then we find a nontrivial factor of $f(x)$ in deterministic $\mbox{poly}(n^r,\log q)$ time, assuming GRH and that $s=\Omega (\sqrt{n/2^r})$. Thus, for $r=O(1)$ our algorithm is polynomial time. Further, for $r=\Omega (\log \log n)$ there are infinitely many prime degrees $n$ for which our algorithm is applicable and better than the best known, assuming GRH. Our methods build on the algebraic-combinatorial framework of $m$-schemes initiated by Ivanyos, Karpinski and Saxena (ISSAC 2009). We show that the $m$-scheme on $n$ points, implicitly appearing in our factoring algorithm, has an exceptional structure, leading us to the improved time complexity. Our structure theorem proves the existence of small intersection numbers in any association scheme that has many relations, and roughly equal valencies and indistinguishing numbers.

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.

Computational Galois theory, in particular the problem of computing the Galois group of a given polynomial, is a very old problem. Currently, the best algorithmic solution is Stauduhar’s method. Computationally, one of the key challenges in the application of Stauduhar’s method is to find, for a given pair of groups $H<G$, a $G$-relative $H$-invariant, that is a multivariate polynomial $F$ that is $H$-invariant, but not $G$-invariant. While generic, theoretical methods are known to find such $F$, in general they yield impractical answers. We give a general method for computing invariants of large degree which improves on previous known methods, as well as various special invariants that are derived from the structure of the groups. We then apply our new invariants to the task of computing the Galois groups of polynomials over the rational numbers, resulting in the first practical degree independent algorithm.

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.

We study the radius of absolute monotonicity $R$ of rational functions with numerator and denominator of degree $s$ that approximate the exponential function to order $p$. Such functions arise in the application of implicit $s$-stage, order $p$ Runge–Kutta methods for initial value problems, and the radius of absolute monotonicity governs the numerical preservation of properties like positivity and maximum-norm contractivity. We construct a function with $p=2$ and $R>2s$, disproving a conjecture of van de Griend and Kraaijevanger. We determine the maximum attainable radius for functions in several one-parameter families of rational functions. Moreover, we prove earlier conjectured optimal radii in some families with two or three parameters via uniqueness arguments for systems of polynomial inequalities. Our results also prove the optimality of some strong stability preserving implicit and singly diagonally implicit Runge–Kutta methods. Whereas previous results in this area were primarily numerical, we give all constants as exact algebraic numbers.