A new method for decomposition in the Jacobian of small genus hyperelliptic curves

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials required in Gaudry’s method. Also, the total number of additions in the Jacobian required by the new method is less than that required by Gaudry’s method. The new method itself is quite simple and we present some example decompositions and timing results of our implementation of the method using Magma.     

Constructing hyperelliptic curves of genus 2 suitable for cryptography

In this article we show how to generalize the CM-method for elliptic curves to genus two. We describe the algorithm in detail and discuss the results of our implementation.

     

A classification of unramified double coverings of hyperelliptic Riemann surfaces

Archiv der Mathematik -     

A numerical bound for small prime solutions of some binary equations

In this paper we consider the linear equation a1p1+ a2p2 = n in prime variables pi and estimate the numerical value of a relevant constant in the upper bound for small prime solutions of the above equation in terms of max ai.     

Refined Kirby calculus for three-manifolds of first homology groups of odd prime orders

Every integral homology 3-sphere is presented by a framed link with framing ±1 and without linking numbers. Restricting such presentations, Habiro arranged Kirby calculus so that it preserves framings and linkings and moreover showed that his calculus suffices to relate all links with the same results. This paper provides an extension of his result for manifolds of first homology groups of odd prime orders. After defining our set of links, we establish Habiro calculus over it, and show that, for many orders, it works on those manifolds. We further give the existence of the Casson-Walker invariant for them.     

The sum-product estimate for large subsets of prime fields

Let be the field of prime order It is known that for any integer one can construct a subset with such that

One of the results of the present paper implies that if with then

     

Arithmetical semigroups II: sieving by large and small prime elements. Sets of multiples

The quantities ψ(x, y), ϕ(x, y) which denote the number of positive integers ≤x without prime divisors >y,<y respectively as well as the concept of a set of multiples within ℕ together with many wellknown results on these have their counterpart in arithmetical semigroups.     

Conditional bounds for small prime solutions of linear equations

Leta ₁,a ₂,a ₃ be non-zero integers with gcd(a ₁ a ₂,a ₃)=1 and letb be an arbitrary integer satisfying gcd (b, a _i,a _j) =1 fori≠j andb≡a ₁+a ₂+a ₃ (mod 2). In a previous paper [3] which completely settled a problem of A. Baker, the 2nd and 3rd authors proved that ifa ₁,a ₂,a ₃ are not all of the same sign, then the equationa ₁ p ₁+a ₂ p ₂+a ₃ p ₃=b has a solution in primesp _j satisfying $$\mathop {\max }\limits_{1 \leqslant j \leqslant 3} p_j \leqslant 3\left| b \right| + (3\mathop {\max }\limits_{1 \leqslant j \leqslant 3} \left| {a_j } \right|)^A $$ whereA>0 is an absolute constant. In this paper, under the Generalized Riemann Hypothesis, the authors obtain a more precise bound for the solutionsp _j . In particular they obtainA<4+∈ for some ∈>0. An immediate consquence of the main result is that the Linnik's courtant is less than or equal to 2.     

The Sp 3 -grassmannian and duality for prime Fano threefolds of genus 9

By a result of Mukai, the non-abelian Brill-Noether locus X=M_C(2, K : 3F) of type II, defined by a stable rank 2 vector bundle F of invariant 3 over a plane quartic curve C, is a prime Fano 3-fold X=X₁₆ of degree 16. The associate ruled surface S^X=P(F) is uniquely defined by X, and we see that for the general X=X₁₆, S^X is isomorphic to the Fano surface of conics on X. The argument uses the geometry of the Sp₃-grassmannian and the double projection from a line on X₁₆.Partially supported by Grant MM-1106/2001 of the Bulgarian Foundation for Scientific Research     

An estimate for the number of integers without large prime factors

denotes the number of positive integers and free of prime factors y$">. Hildebrand and Tenenbaum provided a good approximation of . However, their method requires the solution to the equation , and therefore it needs a large amount of time for the numerical solution of the above equation for large . Hildebrand also showed approximates for , where and is the unique solution to . Let be defined by for 0$">. We show approximates , and also approximates , where . Using these approximations, we give a simple method which approximates within a factor in the range , where is any positive constant.

     

A quasi quadratic time algorithm for hyperelliptic curve point counting

We describe an algorithm to compute the cardinality of Jacobians of ordinary hyperelliptic curves of small genus over finite fields with cost . This algorithm is derived from ideas due to Mestre. More precisely, we state the mathematical background behind Mestre’s algorithm and develop from it a variant with quasi-quadratic time complexity. Among others, we present an algorithm to find roots of a system of generalized Artin-Schreier equations and give results that we obtain with an efficient implementation. Especially, we were able to obtain the cardinality of curves of genus one, two or three in finite fields of huge size. 2000 Mathematics Subject Classification Primary—11S40, 14H42, 11G20, 11G15, 94A60     

Generating pairing-friendly parameters for the CM construction of genus 2 curves over prime fields

We present two contributions in this paper. First, we give a quantitative analysis of the scarcity of pairing-friendly genus 2 curves. This result is an improvement relative to prior work which estimated the density of pairing-friendly genus 2 curves heuristically. Second, we present a method for generating pairing-friendly parameters for which ${\rho\approx 8}$ , where ρ is a measure of efficiency in pairing-based cryptography. This method works by solving a system of equations given in terms of coefficients of the Frobenius element. The algorithm is easy to understand and implement.     

A necessary and sufficient condition for lifting the hyperelliptic involution

Let denote a Riemann surface which possesses a fixed point free group of automorphisms with a hyperelliptic orbit space. A criterion is proved which determines whether the hyperelliptic involution lifts to an automorphism of Necessary and sufficient conditions are stated which determine when a lift of the hyperelliptic involution is fixed point free. A complete determination is made of the abelian groups which may arise as automorphism groups of surfaces which possess a fixed point free lift.