Search

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections., Comment: 29 pages, 20 figures

In this paper we introduce a new problem called the Isogenous Embedding Problem (IEP). The existence of solutions to this problem is related to the primes of bad reduction of CM curves of genus $3$ and we can detect potentially good reduction in absence of solutions. We propose an algorithm for computing the solutions to the IEP and run the algorithm through different families of curves. We were able to prove the reduction type of some particular curves at certain primes that were open cases in [LLLR21].

The paper concerns several theoretical aspects of oriented supersingular $\ell$-isogeny volcanoes and their relationship to closed walks in the supersingular $\ell$-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular $\ell$-isogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular $\ell$-isogeny graph over $\overline{\mathbb{F}}_p$. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of $p$ in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular $\ell$-isogeny graph exactly as a sum of class numbers of these orders, and also give an explicit upper bound by estimating the class numbers., Comment: 41 pages, 7 figures

In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (Wesolowski [54]), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don't assume the knowledge of the primitive order associated with the endomorphism., Comment: 40 pages, 1 figure; 3rd revision implements small corrections and expositional improvements

Cryptographic hash functions from expander graphs were proposed by Charles, Goren, and Lauter in [CGL] based on the hardness of finding paths in the graph. In this paper, we propose a new candidate for a hash function based on the hardness of finding paths in the graph of Markoff triples modulo p. These graphs have been studied extensively in number theory and various other fields, and yet finding paths in the graphs remains difficult. We discuss the hardness of finding paths between points, based on the structure of the Markoff graphs. We investigate several possible avenues for attack and estimate their running time to be greater than O(p). In particular, we analyze a recent groundbreaking proof in [BGS1] that such graphs are connected and discuss how this proof gives an algorithm for finding paths

In this paper, we study isogeny graphs of supersingular elliptic curves. Supersingular isogeny graphs were introduced as a hard problem into cryptography by Charles, Goren, and Lauter for the construction of cryptographic hash functions [CGL06]. These are large expander graphs, and the hard problem is to find an efficient algorithm for routing, or path-finding, between two vertices of the graph. We consider four aspects of supersingular isogeny graphs, study each thoroughly and, where appropriate, discuss how they relate to one another. First, we consider two related graphs that help us understand the structure: the `spine' $\mathcal{S}$, which is the subgraph of $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ given by the $j$-invariants in $\mathbb{F}_p$, and the graph $\mathcal{G}_\ell(\mathbb{F}_p)$, in which both curves and isogenies must be defined over $\mathbb{F}_p$. We show how to pass from the latter to the former. The graph $\mathcal{S}$ is relevant for cryptanalysis because routing between vertices in $\mathbb{F}_p$ is easier than in the full isogeny graph. The $\mathbb{F}_p$-vertices are typically assumed to be randomly distributed in the graph, which is far from true. We provide an analysis of the distances of connected components of $\mathcal{S}$. Next, we study the involution on $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ that is given by the Frobenius of $\mathbb{F}_p$ and give heuristics on how often shortest paths between two conjugate $j$-invariants are preserved by this involution (mirror paths). We also study the related question of what proportion of conjugate $j$-invariants are $\ell$-isogenous for $\ell = 2,3$. We conclude with experimental data on the diameters of supersingular isogeny graphs when $\ell = 2$ and compare this with previous results on diameters of LPS graphs and random Ramanujan graphs., Comment: 46 pages. Comments welcome

In this article we prove an analogue of a theorem of Lachaud, Ritzenthaler, and Zykin, which allows us to connect invariants of binary oc-tics to Siegel modular forms of genus 3. We use this connection to show that certain modular functions, when restricted to the hyperelliptic locus, assume values whose denominators are products of powers of primes of bad reduction for the associated hyperelliptic curves. We illustrate our theorem with explicit computations. This work is motivated by the study of the value of these modular functions at CM points of the Siegel upper-half space, which, if their denominators are known, can be used to effectively compute models of (hyperelliptic, in our case) curves with CM.

We describe a framework for constructing an efficient non-interactive key exchange (NIKE) protocol for n parties for any n >= 2. Our approach is based on the problem of computing isogenies between isogenous elliptic curves, which is believed to be difficult. We do not obtain a working protocol because of a missing step that is currently an open mathematical problem. What we need to complete our protocol is an efficient algorithm that takes as input an abelian variety presented as a product of isogenous elliptic curves, and outputs an isomorphism invariant of the abelian variety. Our framework builds a cryptographic invariant map, which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.

In this paper we study the security of a proposal for Post-Quantum Cryptography from both a number theoretic and cryptographic perspective. Charles-Goren-Lauter in 2006 [CGL06] proposed two hash functions based on the hardness of finding paths in Ramanujan graphs. One is based on Lubotzky-Phillips-Sarnak (LPS) graphs and the other one is based on Supersingular Isogeny Graphs. A 2008 paper by Petit-Lauter-Quisquater breaks the hash function based on LPS graphs. On the Supersingular Isogeny Graphs proposal, recent work has continued to build cryptographic applications on the hardness of finding isogenies between supersingular elliptic curves. A 2011 paper by De Feo-Jao-Pl\^{u}t proposed a cryptographic system based on Supersingular Isogeny Diffie-Hellman as well as a set of five hard problems. In this paper we show that the security of the SIDH proposal relies on the hardness of the SIG path-finding problem introduced in [CGL06]. In addition, similarities between the number theoretic ingredients in the LPS and Pizer constructions suggest that the hardness of the path-finding problem in the two graphs may be linked. By viewing both graphs from a number theoretic perspective, we identify the similarities and differences between the Pizer and LPS graphs., Comment: 33 pages

We give bounds on the primes of geometric bad reduction for curves of genus three of primitive CM type in terms of the CM orders. In the case of genus one, there are no primes of geometric bad reduction because CM elliptic curves are CM abelian varieties, which have potential good reduction everywhere. However, for genus at least two, the curve can have bad reduction at a prime although the Jacobian has good reduction. Goren and Lauter gave the first bound in the case of genus two. In the cases of hyperelliptic and Picard curves, our results imply bounds on primes appearing in the denominators of invariants and class polynomials, which are important for algorithmic construction of curves with given characteristic polynomials over finite fields., Comment: 16 pages, some minor updates, some typos are corrected

Given a sextic CM field $K$, we give an explicit method for finding all genus 3 hyperelliptic curves defined over $\mathbb{C}$ whose Jacobians are simple and have complex multiplication by the maximal order of this field, via an approximation of their Rosenhain invariants. Building on the work of Weng, we give an algorithm which works in complete generality, for any CM sextic field $K$, and computes minimal polynomials of the Rosenhain invariants for any period matrix of the Jacobian. This algorithm can be used to generate genus 3 hyperelliptic curves over a finite field $\mathbb{F}_p$ with a given zeta function by finding roots of the Rosenhain minimal polynomials modulo $p$., Comment: 20 pages; to appear in ANTS XII

In this paper, we survey the status of attacks on the ring and polynomial learning with errors problems (RLWE and PLWE). Recent work on the security of these problems [Eisentr\"ager-Hallgren-Lauter, Elias-Lauter-Ozman-Stange] gives rise to interesting questions about number fields. We extend these attacks and survey related open problems in number theory, including spectral distortion of an algebraic number and its relationship to Mahler measure, the monogenic property for the ring of integers of a number field, and the size of elements of small order modulo q., Comment: 20 Pages

The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [Eisentr\"ager-Hallgren-Lauter]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-$2$ cyclotomic fields, presented using the minimal polynomial of $\zeta_{2^n} \pm 1$., Comment: 24 pages including computer code, minor modifications and typos corrected

Let $C$ be a smooth, absolutely irreducible genus-$3$ curve over a number field $M$. Suppose that the Jacobian of $C$ has complex multiplication by a sextic CM-field $K$. Suppose further that $K$ contains no imaginary quadratic subfield. We give a bound on the primes $\mathfrak{p}$ of $M$ such that the stable reduction of $C$ at $\mathfrak{p}$ contains three irreducible components of genus $1$.

Let $\cO$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$ of prime discriminant $p$, and $\ell$ a small prime. We describe a probabilistic algorithm, which for a given left $O$-ideal, computes a representative in its left ideal class of $\ell$-power norm. In practice the algorithm is efficient, and subject to heuristics on expected distributions of primes, runs in expected polynomial time. This breaks the underlying problem for a quaternion analog of the Charles-Goren-Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves., Comment: To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference

We study the problem of efficiently constructing a curve C of genus 2 over a finite field F for which either the curve C itself or its Jacobian has a prescribed number N of F-rational points. In the case of the Jacobian, we show that any `CM-construction' to produce the required genus-2 curves necessarily takes time exponential in the size of its input. On the other hand, we provide an algorithm for producing a genus-2 curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-2 curve having exactly 10^2014 + 9703 (prime) points, and two genus-2 curves each having exactly 10^2013 points. In an appendix we provide a complete parametrization, over an arbitrary base field k of characteristic neither 2 nor 3, of the family of genus-2 curves over k that have k-rational degree-3 maps to elliptic curves, including formulas for the genus-2 curves, the associated elliptic curves, and the degree-3 maps., Comment: Made a number of clarifications and corrected some typographical errors

Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for CM(K).G_1 under strong assumptions on the ramification in K. Yang later proved this conjecture under slightly stronger assumptions on the ramification. In recent work, Lauter and Viray proved a different formula for CM(K).G_1 for primitive quartic CM fields with a mild assumption, using a method of proof independent from that of Yang. In this paper we show that these two formulas agree, for a class of primitive quartic CM fields which is slightly larger than the intersection of the fields considered by Yang and Lauter and Viray. Furthermore, the proof that these formulas agree does not rely on the results of Yang or Lauter and Viray. As a consequence of our proof, we conclude that the Bruinier-Yang formula holds for a slightly largely class of quartic CM fields K than what was proved by Yang, since it agrees with the Lauter-Viray formula, which is proved in those cases. The factorization of these intersection numbers has applications to cryptography: precise formulas for them allow one to compute the denominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography., Comment: 17 pages

In this paper we prove an explicit formula for the arithmetic intersection number (CM(K).G1)_{\ell} on the Siegel moduli space of abelian surfaces, generalizing the work of Bruinier-Yang and Yang. These intersection numbers allow one to compute the denominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography. Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for the intersection number (CM(K).G1)_{\ell} under strong assumptions on the ramification of the primitive quartic CM field K. Yang later proved this conjecture assuming that O_K is freely generated by one element over the ring of integers of the real quadratic subfield. In this paper, we prove a formula for (CM(K).G1)_{\ell} for more general primitive quartic CM fields, and we use a different method of proof than Yang. We prove a tight bound on this intersection number which holds for all primitive quartic CM fields. As a consequence, we obtain a formula for a multiple of the denominators of the Igusa class polynomials for an arbitrary primitive quartic CM field. Our proof entails studying the Embedding Problem posed by Goren and Lauter and counting solutions using our previous article that generalized work of Gross-Zagier and Dorman to arbitrary discriminants., Comment: 30 pages. Minor edits

Let d1 and d2 be discriminants of distinct quadratic imaginary orders O_d1 and O_d2 and let J(d1,d2) denote the product of differences of CM j-invariants with discriminants d1 and d2. In 1985, Gross and Zagier gave an elegant formula for the factorization of the integer J(d1,d2) in the case that d1 and d2 are relatively prime and discriminants of maximal orders. To compute this formula, they first reduce the problem to counting the number of simultaneous embeddings of O_d1 and O_d2 into endomorphism rings of supersingular curves, and then solve this counting problem. Interestingly, this counting problem also appears when computing class polynomials for invariants of genus 2 curves. However, in this application, one must consider orders O_d1 and O_d2 that are non-maximal. Motivated by the application to genus 2 curves, we generalize the methods of Gross and Zagier and give a computable formula for v_p(J(d1,d2)) for any distinct pair of discriminants d1,d2 and any prime p>2. In the case that d1 is squarefree and d2 is the discriminant of any quadratic imaginary order, our formula can be stated in a simple closed form. We also give a conjectural closed formula when the conductors of d1 and d2 are relatively prime., Comment: 33 pages. Changed the abstract and made small changes to the introduction. Reorganized section 3.2, 4, and proof of Proposition 8.1. Some remarks added to section 7

We provide new upper bounds on N_q(g), the maximum number of rational points on a smooth absolutely irreducible genus-g curve over F_q, for many values of q and g. Among other results, we find that N_4(7) = 21 and N_8(5) = 29, and we show that a genus-12 curve over F_2 having 15 rational points must have characteristic polynomial of Frobenius equal to one of three explicitly given possibilities. We also provide sharp upper bounds for the lengths of the shortest vectors in Hermitian lattices of small rank and determinant over the maximal orders of small imaginary quadratic fields of class number 1. Some of our intermediate results can be interpreted in terms of Mordell-Weil lattices of constant elliptic curves over one-dimensional function fields over finite fields. Using the Birch and Swinnerton-Dyer conjecture for such elliptic curves, we deduce lower bounds on the orders of certain Shafarevich-Tate groups., Comment: LaTeX, 35 pages

We prove a higher dimensional generalization of Gross and Zagier's theorem on the factorization of differences of singular moduli. Their result is proved by giving a counting formula for the number of isomorphisms between elliptic curves with complex multiplication by two different imaginary quadratic fields $K$ and $K^\prime$, when the curves are reduced modulo a supersingular prime and its powers. Equivalently, the Gross-Zagier formula counts optimal embeddings of the ring of integers of an imaginary quadratic field into particular maximal orders in $B_{p, \infty}$, the definite quaternion algebra over $\QQ$ ramified only at $p$ and infinity. Our work gives an analogous counting formula for the number of simultaneous embeddings of the rings of integers of primitive CM fields into superspecial orders in definite quaternion algebras over totally real fields of strict class number 1. Our results can also be viewed as a counting formula for the number of isomorphisms modulo $\frak{p} | p$ between abelian varieties with CM by different fields. Our counting formula can also be used to determine which superspecial primes appear in the factorizations of differences of values of Siegel modular functions at CM points associated to two different CM fields, and to give a bound on those supersingular primes which can appear. In the special case of Jacobians of genus 2 curves, this provides information about the factorizations of numerators of Igusa invariants, and so is also relevant to the problem of constructing genus 2 curves for use in cryptography., Comment: 32 pages

We give a classification of all principally polarized abelian surfaces that admit an $(l,l)$-isogeny to themselves, and show how to compute all the abelian surfaces that occur. We make the classification explicit in the simplest case $l=2$. As part of our classification, we also show how to find all principally polarized abelian surfaces with multiplication by a given imaginary quadratic order., Comment: 25 pages

Bruinier and Yang conjectured a formula for an intersection number on the arithmetic Hilbert modular surface, CM(K).T_m, where CM(K) is the zero-cycle of points corresponding to abelian surfaces with CM by a primitive quartic CM field K, and T_m is the Hirzebruch-Zagier divisors parameterizing products of elliptic curves with an m-isogeny between them. In this paper, we examine fields not covered by Yang's proof of the conjecture. We give numerical evidence to support the conjecture and point to some interesting anomalies. We compare the conjecture to both the denominators of Igusa class polynomials and the number of solutions to the embedding problem stated by Goren and Lauter., Comment: 27 pages, 1 table, 1 appendix with Magma code. To appear in Fields Communications Volume WIN - Women In Numbers, Proceedings of the WIN Workshop, Banff International Research Station, Banff, Canada

The moduli space of principally polarized abelian surfaces is parametrized by three Igusa functions. In this article we investigate a new way to evaluate these functions by using Siegel Eisenstein series. We explain how to compute the Fourier coefficients of certain Siegel modular forms using classical modular forms of half-integral weight. One of the results in this paper is an explicit algorithm to evaluate the Igusa functions to a prescribed precision.

Genus 2 curves are useful in cryptography for both discrete-log based and pairing-based systems, but a method is required to compute genus 2 curves such that the Jacobian has a given number of points. Currently, all known methods involve constructing genus 2 curves with complex multiplication via computing their three Igusa class polynomials. These polynomials have rational coefficients and require extensive computation and precision to compute. Both the computation and the complexity analysis of these algorithms can be improved by a more precise understanding of the denominators of the coefficients of the polynomials. The main goal of this paper is to give a bound on the denominators of Igusa class polynomials of genus 2 curves with CM by a primitive quartic CM field. We give an overview of Igusa's results on the moduli space of genus two curves and the method to construct genus 2 curves via their Igusa invariants. We also give a complete characterization of the reduction type of a CM abelian surface, for biquadratic, cyclic, and non-Galois quartic CM fields, and for any type of prime decomposition of the prime, including ramified primes. The methods of the proof of the main result involve studying the embedding problem of the quartic CM field into certain matrix algebras over quaternions and invoking techniques from crystalline deformation theory.

We present a new algorithm to compute the classical modular polynomial Phi_n in the rings Z[X,Y] and (Z/mZ)[X,Y], for a prime n and any positive integer m. Our approach uses the graph of n-isogenies to efficiently compute Phi_n mod p for many primes p of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of O(n^3 (log n)^3 log log n), and compute Phi_n mod m using O(n^2 (log n)^2 + n^2 log m) space. We have used the new algorithm to compute Phi_n with n over 5000, and Phi_n mod m with n over 20000. We also consider several modular functions g for which Phi_n^g is smaller than Phi_n, allowing us to handle n over 60000., Comment: corrected a typo in equation (14), 31 pages

For a complex abelian variety $A$ with endomorphism ring isomorphic to the maximal order in a quartic CM-field $K$, the Igusa invariants $j_1(A), j_2(A),j_3(A)$ generate an abelian extension of the reflex field of $K$. In this paper we give an explicit description of the Galois action of the class group of this reflex field on $j_1(A),j_2(A),j_3(A)$. We give a geometric description which can be expressed by maps between various Siegel modular varieties. We can explicitly compute this action for ideals of small norm, and this allows us to improve the CRT method for computing Igusa class polynomials. Furthermore, we find cycles in isogeny graphs for abelian surfaces, thereby implying that the `isogeny volcano' algorithm to compute endomorphism rings of ordinary elliptic curves over finite fields does not have a straightforward generalization to computing endomorphism rings of abelian surfaces over finite fields.

Modular polynomials are an important tool in many algorithms involving elliptic curves. In this article we investigate their generalization to the genus 2 case following pioneering work by Gaudry and Dupont. We prove various properties of these genus 2 modular polynomials and give an improved way to explicitly compute them.

We define three hard problems in the theory of elliptic divisibility sequences (EDS Association, EDS Residue and EDS Discrete Log), each of which is solvable in sub-exponential time if and only if the elliptic curve discrete logarithm problem is solvable in sub-exponential time. We also relate the problem of EDS Association to the Tate pairing and the MOV, Frey-R\"{u}ck and Shipsey EDS attacks on the elliptic curve discrete logarithm problem in the cases where these apply., Comment: 18 pages; revised version includes some small mathematical corrections, reformatted

We present and analyze two algorithms for computing the Hilbert class polynomial $H_D$ . The first is a p-adic lifting algorithm for inert primes p in the order of discriminant D < 0. The second is an improved Chinese remainder algorithm which uses the class group action on CM-curves over finite fields. Our run time analysis gives tighter bounds for the complexity of all known algorithms for computing $H_D$, and we show that all methods have comparable run times.

Kolyvagin used Heegner points to associate a system of cohomology classes to an elliptic curve over $\Q$ and conjectured that the system contains a non-trivial class. His conjecture has profound implications on the structure of Selmer groups. We provide new computational and theoretical evidence for Kolyvagin's conjecture. More precisely, we explicitly compute Heegner points over ring class fields and use these points to verify the conjecture for specific elliptic curves of rank two. We explain how Kolyvagin's conjecture implies that if the analytic rank of an elliptic curve is at least two then the $\Z_p$-corank of the corresponding Selmer group is at least two as well. We also use explicitly computed Heegner points to produce non-trivial classes in the Shafarevich-Tate group., Comment: 20 pages

We present algorithms which, given a genus 2 curve $C$ defined over a finite field and a quartic CM field $K$, determine whether the endomorphism ring of the Jacobian $J$ of $C$ is the full ring of integers in $K$. In particular, we present probabilistic algorithms for computing the field of definition of, and the action of Frobenius on, the subgroups $J[\ell^d]$ for prime powers $\ell^d$. We use these algorithms to create the first implementation of Eisentr\"ager and Lauter's algorithm for computing Igusa class polynomials via the Chinese Remainder Theorem \cite{el}, and we demonstrate the algorithm for a few small examples. We observe that in practice the running time of the CRT algorithm is dominated not by the endomorphism ring computation but rather by the need to compute $p^3$ curves for many small primes $p$., Comment: Revised version, with minor corrections and incorporating reader comments. Proposition 3.7 and Lemma 6.5 are new. To appear in Proceedings of SAGA 2007, Tahiti

For a quartic primitive CM field $K$, we say that a rational prime $p$ is {\it evil} if at least one of the abelian varieties with CM by $K$ reduces modulo a prime ideal $\gerp| p$ to a product of supersingular elliptic curves with the product polarization. We call such primes {\it evil primes for $K$}. In \cite{GL}, we showed that for fixed $K$, such primes are bounded by a quantity related to the discriminant of the field $K$. In this paper, we show that evil primes are ubiquitous in the sense that, for any rational prime $p$, there are an infinite number of fields $K$ for which $p$ is evil for $K$. The proof consists of two parts: (1) showing the surjectivity of the abelian varieties with CM by $K$, for $K$ satisfying some conditions, onto the the superspecial points modulo $\gerp$ of the Hilbert modular variety associated to the intermediate real quadratic field of $K$, and (2) showing the surjectivity of the superspecial points modulo $\gerp$ of the Hilbert modular variety associated to a large enough real quadratic field onto the superspecial points modulo $\gerp$ with principal polarization on the Siegel moduli space., Comment: 11 pages

We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas., Comment: 8 pages, appendix added with correction to Elkies' running time, final version to appear in London Math Society Journal of Computation and Mathematics

We present a new method for constructing genus 2 curves over a finite field with a given number of points on its Jacobian. This method has important applications in cryptography, where groups of prime order are used as the basis for discrete-log based cryptosystems. Our algorithm provides an alternative to the traditional CM method for constructing genus 2 curves. For a quartic CM field K with primitive CM type, we compute the Igusa class polynomials modulo p for certain small primes p and then use the Chinese remainder theorem (CRT) and a bound on the denominators to construct the class polynomials. We also provide an algorithm for determining endomorphism rings of ordinary Jacobians of genus 2 curves over finite fields, generalizing the work of Kohel for elliptic curves., Comment: 16 pages. to appear in Proceedings of AGCT-10

One can define class invariants for a quartic primitive CM field K as special values of certain Siegel (or Hilbert) modular functions at CM points corresponding to K. We provide explicit bounds on the primes appearing in the denominators of these algebraic numbers. This allows us, in particular, to construct S-units in certain abelian extensions of K, where S is effectively determined by K. It also yields class polynomials for primitive quartic CM fields whose coefficients are S-integers., Comment: 14 pages

A curve over a field k is pointless if it has no k-rational points. We show that there exist pointless genus-3 hyperelliptic curves over a finite field F_q if and only if q < 26, that there exist pointless smooth plane quartics over F_q if and only if either q < 24 or q = 29 or q = 32, and that there exist pointless genus-4 curves over F_q if and only if q < 50., Comment: LaTeX, 15 pages

We present algorithms for computing the squared Weil and Tate pairings on elliptic curves and the squared Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30% over the usual pairings., Comment: 15 pages, new version revised for publication in ANTS-6, references added

The purpose of this note is to suggest an analogue for genus 2 curves of part of Gross and Zagier's work on elliptic curves. Experimentally, for genus 2 curves with CM by a quartic CM field K, it appears that primes dividing the denominators of the discriminants of the Igusa class polynomials all have the property 1) that they are bounded by d, the absolute value of the discriminant of K, and 2) that they divide d-x^2, for some integer x whose square is less than d. A slightly stronger condition is given in Section 3. Such primes are primes of bad reduction for the genus 2 curve and primes of supersingular reduction for the Jacobian of the genus 2 curve., Comment: 3 pages

We present an algorithm which speeds scalar multiplication on a general elliptic curve by an estimated 3.8 % to 8.5 % over the best known general methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P+Q from given points P, Q on the curve. We give applications to simultaneous multiple scalar multiplication and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8 %., Comment: 12 pages, added some consequences for computing the Weil Pairing, to appear in Proceedings of RSA-CT 2003

We give new arguments that improve the known upper bounds on the maximal number N_q(g) of rational points of a curve of genus g over a finite field F_q for a number of pairs (q,g). Given a pair (q,g) and an integer N, we determine the possible zeta functions of genus-g curves over F_q with N points, and then deduce properties of the curves from their zeta functions. In many cases we can show that a genus-g curve over F_q with N points must have a low-degree map to another curve over F_q, and often this is enough to give us a contradiction. In particular, we able to provide eight previously unknown values of N_q(g), namely: N_4(5) = 17, N_4(10) = 27, N_8(9) = 45, N_{16}(4) = 45, N_{128}(4) = 215, N_3(6) = 14, N_9(10) = 54, and N_{27}(4) = 64. Our arguments also allow us to give a non-computer-intensive proof of the recent result of Savitt that there are no genus-4 curves over F_8 having exactly 27 rational points. Furthermore, we show that there is an infinite sequence of q's such that for every g with 0 < g < log_2 q, the difference between the Weil-Serre bound on N_q(g) and the actual value of N_q(g) is at least g/2., Comment: LaTex, 40 pages. There was a mistake in Section 7 that invalidated the proofs of two of our results. We correct the error in Section 7, and add an appendix with new proofs of the two results

This paper proves that the maximum number of rational points on a smooth, absolutely irreducible genus 4 curve over the field of 8 elements is 25. The body of the paper shows that 27 points is not possible using techniques from algebraic geometry. The appendix shows that 26 points is not possible by examining the zeta functions., Comment: 16 pages, 5 page appendix; replaced July 7, 2002. Paper by David Savitt with an Appendix by Kristin Lauter. Includes a collection of examples by David Savitt that will not be included in the print version of the paper

Elliptic curves with a known number of points over a given prime field with n elements are often needed for use in cryptography. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of a root modulo n of the Hilbert class polynomial H(X) for a fundamental discriminant D. The usual way is to compute H(X) over the integers and then to find the root modulo n. We present a modified version of the Chinese remainder theorem (CRT) to compute H(X) modulo n directly from the knowledge of H(X) modulo enough small primes. Our complexity analysis suggests that asymptotically our algorithm is an improvement over previously known methods., Comment: 14 pages, complexity analysis redone, several sections rewritten

Currently, the best upper bounds on the number of rational points on an absolutely irreducible, smooth, projective algebraic curve of genus g defined over a finite field F_q come either from Serre's refinement of the Weil bound if the genus is small compared to q, or from Oesterle's optimization of the explicit formulae method if the genus is large. This paper presents three methods for improving these bounds. The arguments used are the indecomposability of the theta divisor of a curve, Galois descent, and Honda-Tate theory. Examples of improvements on the bounds include lowering them for a wide range of small genus when q=2^3, 2^5, 2^{13}, 3^3, 3^5, 5^3, 5^7, and when q=2^{2s}, s>1. For large genera, isolated improvements are obtained for q=3,8,9., Comment: 16 pages including the appendix. Main paper by Kristin Lauter, appendix by Jean-Pierre Serre

We show that for all finite fields F_q, there exists a curve C over F_q of genus 3 such that the number of rational points on C is within 3 of the Serre-Weil upper or lower bound. For some q, we also obtain improvements on the upper bound for the number of rational points on a genus 3 curve over F_q., Comment: 28 pages including the appendix. Main paper by Kristin Lauter, appendix by Jean-Pierre Serre