In this paper, we present novel algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. For these problems, we obtain improved heuristic complexity results in almost all cases and significantly improved performance in practice. The speed-up is especially high in situations where the ideal class group can be computed in advance.

A Maple package which performs the symbolic algebra central to problems in local singularity theory is described. This is a generalisation of previous projects, which dealt only with problems in elementary catastrophe theory. Applications to specific problems are described, and a survey given of the powerful techniques from singularity theory that are used by the package. A description of the underlying algorithm is given, and some of the more important computational aspects discussed. The package, user manual and installation instructions are available in the appendices to this article.

The paper gives formulae for a module presentation of the module of identities among relations for a presentation of a group, in terms of information on 0- and 1-combings of the Cayley graph. These formulae are seen as a special case of formulae for extending a partial free crossed resolution of a group, given a partial contracting homotopy of the universal cover of the partial resolution.

The triple product property (TPP) for subsets of a finite group was introduced by Henry Cohn and Christopher Umans in 2003 as a tool for the study of the complexity of matrix multiplication. This note records some consequences of the simple observation that if (S1,S2,S3) is a TPP triple in a finite group G, then so is (dS1a,dS2b,dS3c) for any a,b,c,d∈G.

Let si:=∣Si∣ for 1≤i≤3. First we prove the inequality s1(s2+s3−1)≤∣G∣ and show some of its uses. Then we show (something a little more general than) that if G has an abelian subgroup of index v, then s1s2s3 ≤v2 ∣G∣.

Consider two ordinary elliptic curves $E,E^{\prime }$ defined over a finite field $\mathbb{F}_{q}$, and suppose that there exists an isogeny $\unicode[STIX]{x1D713}$ between $E$ and $E^{\prime }$. We propose an algorithm that determines $\unicode[STIX]{x1D713}$ from the knowledge of $E$, $E^{\prime }$ and of its degree $r$, by using the structure of the $\ell$-torsion of the curves (where $\ell$ is a prime different from the characteristic $p$ of the base field). Our approach is inspired by a previous algorithm due to Couveignes, which involved computations using the $p$-torsion on the curves. The most refined version of that algorithm, due to De Feo, has a complexity of $\tilde{O} (r^{2})p^{O(1)}$ base field operations. On the other hand, the cost of our algorithm is $\tilde{O} (r^{2})\log (q)^{O(1)}$, for a large class of inputs; this makes it an interesting alternative for the medium- and large-characteristic cases.

We show that there are only finitely many primes $p$ such that $\mathrm{PSL} (2, p)$ has a minimal generating set of size four.

Supplementary materials are available with this article.

We give an approximation for the value of the Bessel function $J_\nu (x)$ in the transition region with an explicit sharp error term.

It is proved, within the constructive theory of apartness spaces, that a strongly continuous mapping from a totally bounded uniform space with a countable base of entourages to a uniform space is uniformly continuous. This lifts a result of Ishihara and Schuster from metric to uniform apartness spaces. The paper is part of a systematic development of computable topology using apartness as the fundamental notion.

Boyd showed that the beta expansion of Salem numbers of degree 4 were always eventually periodic. Based on an heuristic argument, Boyd had conjectured that the same is true for Salem numbers of degree 6 but not for Salem numbers of degree 8. This paper examines Salem numbers of degree 8 and collects experimental evidence in support of Boyd’s conjecture.

The authors present three-point and four-point covers having bad reduction at 2 and 3 only, with Galois group An or Sn for n equal to 9, 10, 12, 18, 28, and 33. By specializing these covers, they obtain number fields ramified at 2 and 3 only, with Galois group An or Sn for n equal to 9, 10, 11, 12, 17, 18, 25, 28, 30, and 33.

Using the cohomology theory of Dwork, as developed by Adolphson and Sperber, we exhibit a deterministic algorithm to compute the zeta function of a nondegenerate hypersurface defined over a finite field. This algorithm is particularly well suited to work with polynomials in small characteristic that have few monomials (relative to their dimension). Our method covers toric, affine, and projective hypersurfaces, and also can be used to compute the L-function of an exponential sum.

We develop the theory of Abelian functions associated with algebraic curves. The growth in computer power and the advancement of efficient symbolic computation techniques have allowed for recent progress in this area. In this paper we focus on the genus three cases, comparing the two canonical classes of hyperelliptic and trigonal curves. We present new addition formulae, derive bases for the spaces of Abelian functions and discuss the differential equations such functions satisfy.

Supplementary materials are available with this article.

The aim of the discrete logarithm problem with auxiliary inputs is to solve for ${\it\alpha}$, given the elements $g,g^{{\it\alpha}},\ldots ,g^{{\it\alpha}^{d}}$ of a cyclic group $G=\langle g\rangle$, of prime order $p$. The best-known algorithm, proposed by Cheon in 2006, solves for ${\it\alpha}$ in the case where $d\mid (p\pm 1)$, with a running time of $O(\sqrt{p/d}+d^{i})$ group exponentiations ($i=1$ or $1/2$ depending on the sign). There have been several attempts to generalize this algorithm to the case of ${\rm\Phi}_{k}(p)$ where $k\geqslant 3$. However, it has been shown by Kim, Cheon and Lee that a better complexity cannot be achieved than that of the usual square root algorithms.

We propose a new algorithm for solving the DLPwAI. We show that this algorithm has a running time of $\widetilde{O}(\sqrt{p/{\it\tau}_{f}}+d)$ group exponentiations, where ${\it\tau}_{f}$ is the number of absolutely irreducible factors of $f(x)-f(y)$. We note that this number is always smaller than $\widetilde{O}(p^{1/2})$.

In addition, we present an analysis of a non-uniform birthday problem.

We classify the simple Lie algebras of dimension at most 9 over GF(2). There is one of dimension 3 and one of dimension 6, there are two of dimension 7 and two of dimension 8, and there is one of dimension 9. The two simple Lie algebras of dimension 8 are restricted Lie algebras. If we extend the ground field to GF(4), then the six-dimensional algebra is no longer simple, and if we extend the ground field to GF(8) then the nine-dimensional algebra is no longer simple. But the other algebras are all central simple.

In this paper we display an explicit polynomial having Galois group SL2(F16), filling in a gap in the tables of Jürgen Klüners and Gunter Malle. Furthermore, the polynomial has small Galois root discriminant; this fact answers a question of John Jones and David Roberts. The computation of this polynomial uses modular forms and their Galois representations.

Let k be a field of characteristic other than 2. There can be an obstruction to a principally polarized abelian threefold (A,a) over k, which is a Jacobian over , being a Jacobian over k; this can be computed in terms of the rationality of the square root of the value of a certain Siegel modular form. We show how to do this explicitly for principally polarized abelian threefolds which are the third power of an elliptic curve with complex multiplication. We use our numerical results to prove or refute the existence of some optimal curves of genus 3.

I give an algorithm for computing the full space of automor-phic forms for definite unitary groups over ℚ, and apply this to calculate the automorphic forms of level G(hat{Z}) and various small weights for an example of a rank 3 unitary group. This leads to some examples of various types of endoscopic lifting from automorphic forms for U1 × U1 × U1 and U1 × U2, and to an example of a non-endoscopic form of weight (3, 3) corresponding to a family of 3-dimensional irreducible ℓ-adic Galois representations. I also compute the 2-adic slopes of some automorphic forms with level structure at 2, giving evidence for the local constancy of the slopes.

Let β∈(1,2) be a Pisot number and let Hβ denote Garsia’s entropy for the Bernoulli convolution associated with β. Garsia, in 1963, showed that Hβ<1 for any Pisot β. For the Pisot numbers which satisfy xm=xm−1+xm−2+⋯+x+1 (with m≥2), Garsia’s entropy has been evaluated with high precision by Alexander and Zagier for m=2 and later by Grabner, Kirschenhofer and Tichy for m≥3, and it proves to be close to 1. No other numerical values for Hβ are known. In the present paper we show that Hβ>0.81 for all Pisot β, and improve this lower bound for certain ranges of β. Our method is computational in nature.

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 $A$ be an abelian variety of dimension $g$ together with a principal polarization ${\it\phi}:A\rightarrow \hat{A}$ defined over a field $k$. Let $\ell$ be an odd integer prime to the characteristic of $k$ and let $K$ be a subgroup of $A[\ell ]$ which is maximal isotropic for the Riemann form associated to ${\it\phi}$. We suppose that $K$ is defined over $k$ and let $B=A/K$ be the quotient abelian variety together with a polarization compatible with ${\it\phi}$. Then $B$, as a polarized abelian variety, and the isogeny $f:A\rightarrow B$ are also defined over $k$. In this paper, we describe an algorithm that takes as input a theta null point of $A$ and a polynomial system defining $K$ and outputs a theta null point of $B$ as well as formulas for the isogeny $f$. We obtain a complexity of $\tilde{O} (\ell ^{(rg)/2})$ operations in $k$ where $r=2$ (respectively, $r=4$) if $\ell$ is a sum of two (respectively, four) squares which constitutes an improvement over the algorithm described in Cosset and Robert (Math. Comput. (2013) accepted for publication). We note that the algorithm is quasi-optimal if $\ell$ is a sum of two squares since its complexity is quasi-linear in the degree of $f$.