Faster computation of the Tate pairing

Text

This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curves in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=nideQo-K9ME/.     

Non-hyperelliptic modular curves of genus 3

A curve C defined over Q is modular of level N if there exists a non-constant morphism from X₁(N) onto C defined over Q for some positive integer N. We provide a sufficient and necessary condition for the existence of a modular non-hyperelliptic curve C of genus 3 and level N such that Jac C is Q-isogenous to a given three dimensional Q-quotient of J₁(N). Using this criterion, we present an algorithm to compute explicitly equations for modular non-hyperelliptic curves of genus 3. Let C be a modular curve of level N, we say that C is new if the corresponding morphism between J₁(N) and Jac C factors through the new part of J₁(N). We compute equations of 44 non-hyperelliptic new modular curves of genus 3, that we conjecture to be the complete list of this kind of curves. Furthermore, we describe some aspects of non-new modular curves and we present some examples that show the ambiguity of the non-new modular case.     

A geometric approach to Euler’s addition formula

Plane quartic curves given by equations of the form y ²=P(x) with polynomials P of degree 4 represent singular models of elliptic curves which are directly related to elliptic integrals in the form studied by Euler and for which he developed his famous addition formulas. For cubic curves, the well-known secant and tangent construction establishes an immediate connection of addition formulas for the corresponding elliptic integrals with the structure of an algebraic group. The situation for quartic curves is considerably more complicated due to the presence of the singularity. We present a geometric construction, similar in spirit to the secant method for cubic curves, which defines an addition law on a quartic elliptic curve given by rational functions. Furthermore, we show how this addition on the curve itself corresponds to the addition in the (generalized) Jacobian variety of the curve, and we show how any addition formula for elliptic integrals of the form \(\int (1/\sqrt{P(x)})\,\mathrm{d}x\) with a quartic polynomial P can be derived directly from this addition law.     

Models of some genus one curves with applications to descent

Let p denote a prime, and K a field of characteristic prime to p and containing the pth roots of unity. For p equal to 3 and 5, the author finds a scheme T_p and a family of genus one curves over T_p such that any genus one curve defined over the field K of index p whose Jacobian elliptic curve E has is isomorphic to a curve lying over a K-point of T_p. The author then relates the explicit presentation of such families to the program of descent on elliptic curves.     

Zeta function of the projective curveaY 21 =bX 21 +cZ 21 over a class of finite fields, for odd primesl

Letp andl be rational primes such thatl is odd and the order ofp modulol is even. For such primesp andl, and fore = l, 2l, we consider the non-singular projective curvesaY ²¹ =bX ²¹ +cZ ²¹ defined over finite fields F_q such thatq = p ^α? l(mode).We see that the Fermat curves correspond precisely to those curves among each class (fore = l, 2l), that are maximal or minimal over F_q. We observe that each Fermat prime gives rise to explicit maximal and minimal curves over finite fields of characteristic 2. Fore = 2l, we explicitly determine the ζ -function(s) for this class of curves, over F_q, as rational functions in the variablet, for distinct cases ofa, b, andc, in F _q ^* . Theζ-function in each case is seen to satisfy the Weil conjectures (now theorems) for this concrete class of curves. Fore = l, 2l, we determine the class numbers for the function fields associated to each class of curves over F_q. As a consequence, when the field of definition of the curve(s) is fixed, this provides concrete information on the growth of class numbers for constant field extensions of the function field(s) of the curve(s).     

A geometric approach to Euler’s addition formula A direct formulation of the addition law for elliptic curves given in?terms of Weierstra? quartics

Plane quartic curves given by equations of the form y ²=P(x) with polynomials P of degree 4 represent singular models of elliptic curves which are directly related to elliptic integrals in the form studied by Euler and for which he developed his famous addition formulas. For cubic curves, the well-known secant and tangent construction establishes an immediate connection of addition formulas for the corresponding elliptic integrals with the structure of an algebraic group. The situation for quartic curves is considerably more complicated due to the presence of the singularity. We present a geometric construction, similar in spirit to the secant method for cubic curves, which defines an addition law on a quartic elliptic curve given by rational functions. Furthermore, we show how this addition on the curve itself corresponds to the addition in the (generalized) Jacobian variety of the curve, and we show how any addition formula for elliptic integrals of the form ò(1/?{P(x)}) dx\int (1/\sqrt{P(x)})\,\mathrm{d}x with a quartic polynomial P can be derived directly from this addition law.     

Curves on Generic Surfaces of High Degree Through a Complete Intersection in P 3

We consider general surfaces, S, of high degree containing a given complete intersection space curve, Y. We study integral curves in the subgroup of Pic(S) generated by Y and the plane section. We determine the cohomological invariants of these curves and classify the subcanonical ones. Then using these subcanonical curves we produce stable rank two vector bundles on P ³.     

Uniqueness of signature for simple curves

We propose a topological approach to the problem of determining a curve from its iterated integrals. In particular, we prove that a family of terms in the signature series of a two dimensional closed curve with finite p   variation, 1≤p<2$1\le p<2$, are in fact moments of its winding number. This relation allows us to prove that the signature series of a class of simple non-smooth curves uniquely determine the curves. This implies that outside a Chordal SLE_κ${\text{SLE}}_{\kappa }$ null set, where 0<κ≤4$0<\kappa \le 4$, the signature series of curves uniquely determine the curves. Our calculations also enable us to express the Fourier transform of the n-point functions of SLE curves in terms of the expected signature of SLE curves. Although the techniques used in this article are deterministic, the results provide a platform for studying SLE curves through the signatures of their sample paths.     

Approximate Bézier curves by cubic LN curves

In order to derive the offset curves by using cubic Bézier curves with a linear field of normal vectors (the so-called LN Bézier curves) more efficiently, three methods for approximating degree n Bézier curves by cubic LN Bézier curves are considered, which includes two traditional methods and one new method based on Hausdorff distance. The approximation based on shifting control points is equivalent to solving a quadratic equation, and the approximation based on L₂ norm is equivalent to solving a quartic equation. In addition, the sufficient and necessary condition of optimal approximation based on Hausdorff distance is presented, accordingly the algorithm for approximating the degree n Bézier curves based on Hausdorff distance is derived. Numerical examples show that the error of approximation based on Hausdorff distance is much smaller than that of approximation based on shifting control points and L₂ norm, furthermore, the algorithm based on Hausdorff distance is much simple and convenient.     

On squares in Lucas sequences

Let P and Q be non-zero integers. The Lucas sequence {Un(P,Q)} is defined by U₀=0, U₁=1, Un=PUn−1−QUn−2 (n?2). The question of when Un(P,Q) can be a perfect square has generated interest in the literature. We show that for n=2,…,7, Un is a square for infinitely many pairs (P,Q) with gcd(P,Q)=1; further, for n=8,…,12, the only non-degenerate sequences where gcd(P,Q)=1 and Un(P,Q)=□, are given by U₈(1,−4)=²¹², U₈(4,−17)=⁶²⁰², and U₁₂(1,−1)=¹²².     

On generalizations of Fermat curves over finite fields and their automorphisms

Let 𝒳 be an irreducible algebraic curve defined over a finite field 𝔽_q of characteristic p>2. Assume that the 𝔽_q-automorphism group of 𝒳 admits a subgroup isomorphic to the direct product of two cyclic groups C_m and C_n of orders m and n prime to p, such that both quotient curves 𝒳∕C_n and 𝒳∕C_m are rational. In this paper, we provide a complete classification of such curves as well as a characterization of their full automorphism groups.     

Co-calibrated G 2 structure from cuspidal cubics

We establish a twistor correspondence between a cuspidal cubic curve in a complex projective plane, and a co-calibrated homogeneous G ₂ structure on the seven-dimensional parameter space of such cubics. Imposing the Riemannian reality conditions leads to an explicit co-calibrated G ₂ structure on SU(2, 1)/U(1). This is an example of an SO(3) structure in seven dimensions. Cuspidal cubics and their higher degree analogues with constant projective curvature are characterised as integral curves of certain seventh order ODEs. Projective orbits of such curves are shown to be analytic continuations of Aloff?CWallach manifolds, and it is shown that only cubics lift to a complete family of contact rational curves in a projectivised cotangent bundle to a projective plane.     

On construction of certain CM elliptic curves

Let E be a CM elliptic curve defined over an algebraic number field F. In the previous paper [N. Murabayashi, On the field of definition for modularity of CM elliptic curves, J. Number Theory 108 (2004) 268-286], we gave necessary and sufficient conditions for E to be modular over F, i.e. there exists a normalized newform f of weight two on Γ₁(N) for some N such that HomF(E,Jf)≠{0}. We also determined the multiplicity of E as F-simple factor of Jf when HomF(E,Jf)≠{0}. In this process we separated into the three cases. In this paper we construct certain CM elliptic curves which satisfy the conditions of each case. In other words, we show that all three cases certainly occur.     

Divided powers in Chow rings and integral Fourier transforms

We prove that for any monoid scheme M over a field with proper multiplication maps M×M→M, we have a natural PD-structure on the ideal CH>0(M)⊂CH_∗(M) with regard to the Pontryagin ring structure. Further we investigate to what extent it is possible to define a Fourier transform on the motive with integral coefficients of the Jacobian of a curve. For a hyperelliptic curve of genus g with sufficiently many k-rational Weierstrass points, we construct such an integral Fourier transform with all the usual properties up to N²-torsion, where N=1+⌊log₂(3g)⌋. As a consequence we obtain, over , a PD-structure (for the intersection product) on N²⋅a, where a⊂CH(J) is the augmentation ideal. We show that a factor 2 in the properties of an integral Fourier transform cannot be eliminated even for elliptic curves over an algebraically closed field.     

Rational torsion on optimal curves and rank-one quadratic twists

When an elliptic curve E^′/Q of square-free conductor N has a rational point of odd prime order l?N, Dummigan (2005) in [Du] explicitly constructed a rational point of order l on the optimal curve E, isogenous over Q to E^′, under some conditions. In this paper, we show that his construction also works unconditionally. And applying it to Heegner points of elliptic curves, we find a family of elliptic curves E^′/Q such that a positive proportion of quadratic twists of E^′ has (analytic) rank 1. This family includes the infinite family of elliptic curves of the same property in Byeon, Jeon, and Kim (2009) [B-J-K].     

Special Points on the Product of Two Modular Curves

We prove, assuming the generalized Riemann hypothesis for imaginary quadratic fields, the following special case of a conjecture of Oort, concerning Zarsiski closures of sets of CM points in Shimura varieties. Let X be an irreducible algebraic curve in C², containing infinitely many points of which both coordinates are j-invariants of CM elliptic curves. Suppose that both projections from X to C are not constant. Then there is an integer m 1such that X is the image, under the usual map, of the modular curve Y₂0(m). The proof uses some number theory and some topological arguments.     

The modularity of some Q-curves

A Q-curve is an elliptic curve, defined over a number field, that is isogenous to each of its Galois conjugates. Ribet showed that Serre's conjectures imply that such curves should be modular. Let E be an elliptic curve defined over a quadratic field such that E is 3-isogenous to its Galois conjugate. We give an algorithm for proving any such E is modular and give an explicit example involving a quotient of J_o (169). As a by-product, we obtain a pair of 19-isogenous elliptic curves, and relate this to the existence of a rational point of order 19 on J₁ (13).     

Constructing pairing-friendly hyperelliptic curves using Weil restriction

A pairing-friendly curve is a curve over a finite field whose Jacobian has small embedding degree with respect to a large prime-order subgroup. In this paper we construct pairing-friendly genus 2 curves over finite fields Fq whose Jacobians are ordinary and simple, but not absolutely simple. We show that constructing such curves is equivalent to constructing elliptic curves over Fq that become pairing-friendly over a finite extension of Fq. Our main proof technique is Weil restriction of elliptic curves. We describe adaptations of the Cocks-Pinch and Brezing-Weng methods that produce genus 2 curves with the desired properties. Our examples include a parametric family of genus 2 curves whose Jacobians have the smallest recorded ρ-value for simple, non-supersingular abelian surfaces.