Search

In this paper we derive formulas for the scalar multiplication by n map, denoted [n], on the Hessian model of elliptic curve. This enables to characterize n-torsion points on this curve. The computation involves three families of polynomials $$P_n$$ , $$Q_n$$ and $$V_n$$ and we show some properties on the coefficients and degrees of these polynomials. We also show some functional equations satisfied by these polynomials. As application we provide a type of mean-value theorem for the Hessian elliptic curve.

Выводятся формулы для многочленов деления класса гиперэллиптических кривых рода $2$, задаваемых многочленами Диксона. В случае $\ell = 3$ формулы представлены в явном виде.

According to the P conjecture by Gh. Păun, polarizationless P systems with active membranes cannot solve $${\mathbf {NP}}$$NP-complete problems in polynomial time. The conjecture is proved only in special cases yet. In this paper we consider the case where only elementary membrane division and dissolution rules are used and the initial membrane structure consists of one elementary membrane besides the skin membrane. We give a new approach based on the concept of object division polynomials introduced in this paper to simulate certain computations of these P systems. Moreover, we show how to compute efficiently the result of these computations using these polynomials.

Here, the authors provide a derivation of an improvement to Kanayama's elliptic curve scalar multiplication algorithm using division polynomials. In addition, they also provide experimental results and show that the improvement is useful when the elliptic curve under consideration is defined over large prime fields.

3 Brill–Noether Varieties 6 3.1 The canonical involution v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Basic Brill–Noether varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 The Basic Brill–Noether variety attached to X1(N) . . . . . . . . . . . . . . . . . . 9 3.4 Basic Brill–Noether curves attached to algebraic curves of genus 5 and gonality 4 . 9 3.5 Loci of singular quadrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6 The canonical representation of the Basic Brill–Noether curve . . . . . . . . . . . . . 11 3.7 Elliptic components and new components . . . . . . . . . . . . . . . . . . . . . . . . 12

Scalar multiplication is the most important and expensive operation in elliptic curve cryptosystems. In this study, the authors improve the efficiency of the elliptic net algorithm to compute scalar multiplication by using the equivalence of elliptic nets. The proposed method saves four multiplications by a constant in each iteration loop. Experimental results also indicate that the proposed algorithm will be more efficient than the previously known results on this line while it is still slower than the state-of-the-art algorithm to compute scalar multiplication.

In this paper, the randomness of binary sequences generated from elliptic curves over a finite field of characteristic 2 is studied. A scheme of construction based on the Chaos-Driven Elliptic Curve Pseudo-random Number Generator (C-D ECPRNG) is proposed. The generators based of this scheme are verified by using tests from the NIST Statistical Test Suite to analyze their statistical properties. An elliptic curve used in the numerical example is defined over F 2 8. The investigations which made for the generated series of two output sequences of the lengths of 210 and 220 bits shown that 14 generators working according to our general scheme exhibit good randomness properties. Next, the binary sequences generated by these 14 schemes were used for encrypting a 256×256 grayscale Lena image as an application example and the security analysis of the ciphered images was carried out.

Assuming Lang's conjectured lower bound on the heights of non-torsion points on an elliptic curve, we show that there exists an absolute constant C such that for any elliptic curve E/Q and non-torsion point P in E(Q), there is at most one integral multiple [n]P such that n > C. The proof is a modification of a proof of Ingram giving an unconditional but not uniform bound. The new ingredient is a collection of explicit formulae for the sequence of valuations of the division polynomials. For P of non-singular reduction, such sequences are already well described in most cases, but for P of singular reduction, we are led to define a new class of sequences called elliptic troublemaker sequences, which measure the failure of the Neron local height to be quadratic. As a corollary in the spirit of a conjecture of Lang and Hall, we obtain a uniform upper bound on h(P)/h(E) for integer points having two large integral multiples., 41 pages; minor corrections and improvements to exposition

In this paper we propose a modified Elliptic Net algorithm to compute pairings. By reducing the number of the intermediate variables which should be updated in the iteration loop of the Elliptic Net algorithm, we speed up the computation of pairings. Experimental results show that the proposed method is more efficient than the original Elliptic Net algorithm on Barreto-Naehrig (BN) curves which are the best choice for implementing pairings at 128-bit security level.

We use Masser’s counting theorem to prove a lower bound for the canonical height in powers of elliptic curves. We also prove the Galois case of the elliptic Lehmer problem, combining Kummer theory and Masser’s result with bounds on the rank and torsion of some groups of rational points on an elliptic curve.

Point compression is an essential technique to save bandwidth and memory when deploying elliptic curve based security solutions in wireless communication systems. In this contribution, we provide new linear algebra (LA) based compression algorithms for multiple points on elliptic curves, that are compression algorithms which only make use of LA (with a constant number of field multiplications and at most one inversion, with no quadratic or higher degree polynomial root finding). In particular, we extend the results of Khabbazian et al. (IEEE Trans Comput 56(3):305---313, 2007) to four (resp. five) points on elliptic curves by generically storing five (resp. six) field elements and provide an asymptotic generalization to any number n of points on a curve $$y^2=f(x)$$y2=f(x) by generically storing $$n+1$$n+1 values.

Given two elliptic curves, each of which is associated with a projection map that identifies opposite elements with respect to the natural group structure, we investigate how their corresponding projective images of torsion points intersect.

Let $E$ be an elliptic curve defined over $K$ given by a Weierstrass equation and let $P=(x,y)\in E(K)$ be a point. Then for each $n$ $\geq 1$ we can write the $x$- and $y$-coordinates of the point $[n]P$ as\[ [n]P=\left( \frac{G_{n}(P)}{F_{n}^{2}(P)},\frac{H_{n}(P)}{F_{n}^{3}(P)}\right)\]where $F_{n}$, $G_{n}$, and $H_{n}\in K[x,y]$ are division polynomials of $E$. In this work we give explicit formulas for sequences\[(F_{n}(P))_{n\geq 0},\,(G_{n}(P))_{n\geq 0},\,\text{and}\,(H_{n}(P))_{n\geq 0}\]associated to an elliptic curve $E$ defined over $\mathbb{Q}$ with non-cyclic torsion subgroup. As applications we give similar formulas for elliptic divisibility sequences associated to elliptic curves with non-cyclic torsion subgroup and determine square terms in these sequences.

We fi nd the number of elliptic curves with a cyclic isogeny of degree n over various number fields by studying the modular curves X_0(n). We show that for n=14, 15, 20, 21, 49 there exist infinitely many quartic fields K such that # Y0(n)(Q)≠ # Y0(n)(K)< ∞ . In the case n=27 we prove that there are infinitely many sextic fields such that # Y0(n)(Q)≠ # Y0(n)(K)< ∞.

Let F be the cubic field of discriminant −23 and its ring of integers. Let Γ be the arithmetic group , and for every ideal , let be the congruence subgroup of level . In [Gunnells and Yasaki 13], the cohomology of various was computed, along with the action of the Hecke operators. The goal of that work was to test the modularity of elliptic curves over F. In the present article, we complement and extend those results in two ways. First, we tabulate more elliptic curves than were found earlier using various heuristics (“old and new” cohomology classes, dimensions of Eisenstein subspaces) to predict the existence of elliptic curves of various conductors, and then using more sophisticated search techniques (for instance, torsion subgroups, twisting, and the Cremona–Lingham algorithm) to find them. We then compute further invariants of these curves, such as their rank and representatives of all isogeny classes. Our enumeration includes conjecturally the first elliptic curves of ranks 1 and 2 over this field, ...

In this paper, we investigate the elliptic analogues of the Apostol-Bernoulli and Apostol-Euler polynomials and obtain the closed expressions of sums of products for these elliptic type polynomials. Some interesting special cases are also shown.

We give an algorithm to compute the generalized division polynomials for elliptic curves with complex multiplication. These polynomials can be used to generate the ray class fields of imaginary quadratic fields over the Hilbert class field with no restriction on the conductor.

In this note we extend the theory of twists of elliptic curves as presented in various standard texts for characteristic not equal to two or three to the remaining characteristics. For this, we make explicit use of the correspondence between the twists and the Galois cohomology set $H^1\big(\operatorname{G}_{\overline{K}/K}, \operatorname{Aut}_{\overline{K}}(E)\big)$. The results are illustrated by examples.

We show that for Dirichlet characters $\chi_1,\ldots ,\chi_s$ mod $p^m$ the sum $$ \mathop{\sum_{x_1=1}^{p^m} \dots \sum_{x_s=1}^{p^m}}_{ A_1x_1^{k_1}+\dots+ A_sx_s^{k_s}\equiv B \text{ mod } p^m}\chi_1(x_1)\cdots \chi_s(x_s), $$ has a simple evaluation when $m$ is sufficiently large.

It is proved in this paper that, for any point on an elliptic curve, the mean value of x-coordinates of its n-division points is the same as its x-coordinate and that of y-coordinates of its n-division points is n times that of its y-coordinate.

The Complex Multiplication (CM) method is a widely used technique for constructing elliptic curves over finite fields. The key point in this method is parameter generation of the elliptic curve and root compution of a special type of class polynomials. However, there are several class polynomials which can be used in the CM method, having much smaller coefficients, and fulfilling the prerequisite that their roots can be easily transformed to the roots of the corresponding Hilbert polynomials.In this paper, we provide a method which can construct elliptic curves by Ramanujan's class invariants. We described the algorithm for the construction of elliptic curves (ECs) over imaginary quadratic field and given the transformation from their roots to the roots of the corresponding Hilbert polynomials. We compared the efficiency in the use of this method and other methods.

Given an elliptic curve E defined over a number field K, an integer m and let E [ m ] ( F ℘ ) be the set of m-torsion points of E that are rational over F ℘ where F ℘ denotes the residue field at ℘. Our main goal is to compute the asymptotic average number of E [ m ] ( F ℘ ) as the prime ℘ varies. The average number N ( m ) as a function of m agrees with a divisor function. For the elliptic curves E D : Y 2 = X 3 − D X , with D ∈ Z − { 0 } , we compute the average number N ( m ) for all odd integers m.

Let E: y^2 = x^3 + Ax + B be an elliptic curve defined over a finite field of characteristic p\geq 3. In this paper we prove that the coefficient at x^{p(p-1)/2} in the p-th division polynomial \psi_p(x) of E equals the coefficient at x^{p-1} in (x^3 + Ax + B)^{(p-1)/2}. The first coefficient is zero if and only if the division polynomial has no roots, which is equivalent to E being supersingular. Deuring (1941) proved that this supersingularity is also equivalent to the vanishing of the second coefficient. So the zero loci of the coefficients (as functions of A and B) are equal; the main result in this paper is clearly stronger than this last statement., Comment: 8 pages

Using a multi-dimensional large sieve inequality, we prove that, for almost all pairs (or indeed almost all k -tuples) of elliptic curves, the associated Galois representation on their torsion has maximal image. This generalizes the authorʼs previous work and provides evidence for an affirmative answer to a higher-dimensional analogue of Serreʼs uniformity question for single elliptic curves. Furthermore, as a consequence of our main theorem, one deduces the triviality of the Brauer group of the Kummer surface attached to almost all pairs of elliptic curves.

We consider models for genus one curves of degree 5, which arise in explicit 5-descent on elliptic curves. We prove a theorem on the existence of minimal models with the same invariants as the minimal model of the Jacobian elliptic curve and give an algorithm for computing such models. Finally we describe how to reduce genus one models of degree 5 defined over Q., Comment: 27 pages

We provide a precise description of the integer points on elliptic curves of the shape y2 = x3 - N2x, where N = 2apb for prime p. By way of example, if p ≡ ±3 (mod 8) and p > 29, we show that all such points necessarily have y = 0. Our proofs rely upon lower bounds for linear forms in logarithms, a variety of old and new results on quartic and other Diophantine equations, and a large amount of (non-trivial) computation.

This paper concerns elliptic curves defined over real quadratic fields with everywhere good reduction and a torsion point of order 3 over the same field. We characterize all such elliptic curves by using Tateʼs algorithm. A corollary is that there are infinitely many such elliptic curves. We also calculate all such elliptic curves over real quadratic fields with discriminants 10 000 up to Galois conjugation.

In this paper, we use elliptic nets to implement the optimized Ate pairings and optimal pairings on the Barreto-Naehrig curves with embedding degree 12. In order to do the arithmetic of elliptic curves over finite fields with elliptic nets, we first give some basic properties of elliptic nets associated to elliptic curves over finite fields and the expression of Miller function in terms of elliptic nets. Then we give formulae to compute some optimized pairings with elliptic nets, which is a new method to implement pairings. This method with elliptic nets has time complexity comparable to Miller’s algorithm and it can be optimized.

We consider a specific family of elliptic curves with rational 3-torsion subgroup. We arithmetically define 3-Selmer groups through isogeny and 3-descent maps, then associate the image of the 3-descent maps to solutions of homogeneous cubic polynomials affiliated with the elliptic curve E and an isogenous curve E′. Thanks to the work of Cohen and Pazuki, we have solubility conditions for the homogeneous polynomials. Using these conditions, we give a graphical approach to computing the size of 3-Selmer groups. Finally, we translate the conditions on graphs into a question concerning ranks of matrices and give an upper bound for the rank of the elliptic curve E by calculating the size of the Selmer groups.

International audience; We provide a new family of elliptic curves that results in a one to two percent performance improvement of the elliptic curve integer factoriza-tion method. The speedup is confirmed by extensive tests for factors ranging from 15 to 63 bits.

Schoof's classic algorithm allows point-counting for elliptic curves over finite fields in polynomial time. This algorithm was subsequently improved by Atkin, using factorizations of modular polynomials, and by Elkies, using a theory of explicit isogenies. Moving to Jacobians of genus-2 curves, the current state of the art for point counting is a generalization of Schoof's algorithm. While we are currently missing the tools we need to generalize Elkies' methods to genus 2, recently Martindale and Milio have computed analogues of modular polynomials for genus-2 curves whose Jacobians have real multiplication by maximal orders of small discriminant. In this article, we prove Atkin-style results for genus-2 Jacobians with real multiplication by maximal orders, with a view to using these new modular polynomials to improve the practicality of point-counting algorithms for these curves., Comment: 31 pages

We construct pairs of elliptic curves over number fields with large intersection of projective torsion points.

M. Toda in 1967 (\textit{J. Phys. Soc. Japan}, \textbf{22} and \textbf{23}) considered a lattice model with exponential interaction and proved, as suggested by the Fermi-Pasta-Ulam experiments in the 1950s, that it has exact periodic and soliton solutions. The Toda lattice, as it came to be known, was then extensively studied as one of the completely integrable (differential-difference) non-linear equations which admit exact solutions in terms of theta functions of hyperelliptic curves. In this paper, we extend Toda's original approach to give hyperelliptic solutions of the Toda lattice in terms of hyperelliptic Kleinian (sigma) functions for arbitrary genus. The key identities are given by generalized addition formulae for the hyperelliptic sigma functions (J.C. Eilbeck \textit{et al.}, {\it J. reine angew. Math.} {\bf 619}, 2008). We then show that periodic (in the discrete variable, a standard term in the Toda lattice theory) solutions of the Toda lattice correspond to the zeros of Kiepert-Brioschi's division polynomials, and note these are related to solutions of Poncelet's closure problem. One feature of our solution is that the hyperelliptic curve is related in a non-trivial way to the one previously used., Comment: pages 30, to appear in Annales de l'Institut Fourier