An algorithm for DLP on anomalous elliptic curves over Fp

This paper improves the method of discrete logarithm on anomalous elliptic curves, and establishes an isomorphism from E(Fp) to Fp which can be more easily implemented. Fruthermore, we give an optimized algorithm for discrete logarithm on anomalous elliptic curves E(Fp).     

Hasse invariants and anomalous primes for elliptic curves with complex multiplication

Let C be an elliptic curve defined over Q. Let p be a prime where C has good reduction. By definition, p is anomalous for C if the Hasse invariant at p is congruent to 1 modulo p. The phenomenon of anomalous primes has been shown by Mazur to be of great interest in the study of rational points in towers of number fields. This paper is devoted to discussing the Hasse invariants and the anomalous primes of elliptic curves admitting complex multiplication. The two special cases Y² = X³ + a₄X and Y² = X³ + a₆ are studied at considerable length. As corollaries, some results in elementary number theory concerning the residue classes of the binomial coefficients (_n²ⁿ) (Resp. (_n³ⁿ)) modulo a prime p = 4n + 1 (resp. p = 6n + 1) are obtained. It is shown that certain classes of elliptic curves admitting complex multiplication do not have any anomalous primes and that others admit only very few anomalous primes.     

Sequences of numbers generated by addition in formal groups and new primality and factorization tests

One can associate with an arbitrary algebroid formal group law F, defined over F_p, a sequence . These sequences for various F (multiplicative group, reduced elliptic curves and Abelian varieties) provide a variety of new primality tests like Lucas' test for Mersenne primes. Implementations and relations with factorization algorithms are presented.     

Implementing the 4-dimensional GLV method on GLS elliptic curves with <Emphasis Type="Italic">j</Emphasis>-invariant 0

The Gallant–Lambert–Vanstone (GLV) method is a very efficient technique for accelerating point multiplication on elliptic curves with efficiently computable endomorphisms. Galbraith et al. (J Cryptol 24(3):446–469, 2011) showed that point multiplication exploiting the 2-dimensional GLV method on a large class of curves over \mathbbF_p²{\mathbb{F}_{p^2}} was faster than the standard method on general elliptic curves over \mathbbF_p{\mathbb{F}_{p}} , and left as an open problem to study the case of 4-dimensional GLV on special curves (e.g., j (E) = 0) over \mathbbF_p²{\mathbb{F}_{p^2}} . We study the above problem in this paper. We show how to get the 4-dimensional GLV decomposition with proper decomposed coefficients, and thus reduce the number of doublings for point multiplication on these curves to only a quarter. The resulting implementation shows that the 4-dimensional GLV method on a GLS curve runs in about 0.78 the time of the 2-dimensional GLV method on the same curve and in between 0.78 − 0.87 the time of the 2-dimensional GLV method using the standard method over \mathbbF_p{\mathbb{F}_{p}} . In particular, our implementation reduces by up to 27% the time of the previously fastest implementation of point multiplication on x86-64 processors due to Longa and Gebotys (CHES2010).     

Signes locaux des courbes elliptiques en 2 et 3

Let p be a prime number. Associated to every elliptic curve E over Q_p there is a local root number W_p(E) = ±1, constructed from the local epsilon factors of Deligne. This sign is already known when p > 3, and also, in certain cases, when p = 2 or 3. In this Note, we give the value of W₂ or W₃ in all cases. Concerning W₃, for our results to be valid, we have to assume that a certain (finite) number of auxiliary elliptic curves over Q are Weil curves.     

An algorithm to compute the number of points on elliptic curves ofj-invariant 0 or 1728 over a finite field

We present an algorithm to compute the number ofF _q -rational points on elliptic curves defined over a finite fieldF _q , withj-invariant 0 or 1728. This algorithm takesO(log³ p) bit operations, werep is the characteristic ofF _q .     

Torsion points on elliptic curves over function fields and a theorem of Igusa

If F   is a global function field of characteristic p>3$p>3$, we employ Tate's theory of analytic uniformization to give an alternative proof of a theorem of Igusa describing the image of the natural Galois representation on torsion points of non-isotrivial elliptic curves defined over F. Along the way, using basic properties of Faltings heights of elliptic curves, we offer a detailed proof of the function field analogue of a classical theorem of Shafarevich according to which there are only finitely many F-isomorphism classes of admissible elliptic curves defined over F with good reduction outside a fixed finite set of places of F. We end the paper with an application to torsion points rational over abelian extensions of F.     

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).     

Interior a priori estimates in discreteL p norms for solutions of parabolic and elliptic difference equations

Summary We consider elliptic and parabolic difference operators and prove estimates in discrete L_p norms, 1<p<∞, which are analogues of known estimates for the corresponding differential operators. Let U be a solution in a bounded domain Ω of an elliptic or parabolic differential equation and let U_h be a solution of the discrete equation. Using the estimates, we prove under mild regularity assumptions that if U_h converges to U in some discrete L_p normp>1, then the difference quotients of U_h converge uniformly (on compact subsets of Ω) to the corresponding derivatives of U. Entrata in Redazione il 9 ottobre 1971.     

Nonsingular plane cubic curves over finite fields

We determine the number of projectively inequivalent nonsingular plane cubic curves over a finite field F_q with a fixed number of points defined over F_q. We count these curves by counting elliptic curves over F_q together with a rational point which is annihilated by 3, up to a certain equivalence relation.     

Selmer groups of elliptic curves that can be arbitrarily large

In this article, it is shown that certain kinds of Selmer groups of elliptic curves can be arbitrarily large. The main result is that if p is a prime at least 5, then p-Selmer groups of elliptic curves can be arbitrarily large if one ranges over number fields of degree at most g+1 over the rationals, where g is the genus of X₀(p). As a corollary, one sees that p-Selmer groups of elliptic curves over the rationals can be arbitrarily large for p=5,7 and 13 (the cases p?7 were already known). It is also shown that the number of elements of order N in the N-Selmer group of an elliptic curve over the rationals can be arbitrarily large for N=9,10,12,16 and 25.     

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.     

Pesenti-Szpiro inequality for optimal elliptic curves

We study Pesenti-Szpiro inequality in the case of elliptic curves over F_q(t) which occur as subvarieties of Jacobian varieties of Drinfeld modular curves. In general, we obtain an upper-bound on the degrees of minimal discriminants of such elliptic curves in terms of the degrees of their conductors and q. In the special case when the level is prime, we bound the degrees of discriminants only in terms of the degrees of conductors. As a preliminary step in the proof of this latter result we generalize a construction (due to Gekeler and Reversat) of 1-dimensional optimal quotients of Drinfeld Jacobians.     

The discrete logarithm problem from a local duality perspective

The discrete logarithm problem is analyzed from the perspective of Tate local duality. Local duality in the multiplicative case and the case of Jacobians of curves over p-adic local fields are considered. When the local field contains the necessary roots of unity, the case of curves over local fields is polynomial time reducible to the multiplicative case, and the multiplicative case is polynomial time equivalent to computing discrete logarithm in finite fields. When the local field does not contains the necessary roots of unity, similar results can be obtained at the cost of going to an extension that contains these roots of unity. There was evidence in the analysis that suggests that the minimal extension where the local duality can be rationally and algorithmically defined must contain the roots of unity. Therefore, the discrete logarithm problem appears to be well protected against an attack using local duality. These results are also of independent interest for algorithmic study of arithmetic duality as they explicitly relate local duality in the case of curves over local fields to the multiplicative case and Tate-Lichtenbaum pairing (over finite fields).     

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.     

Prime Divisors of the Number of Rational Points on Elliptic Curves with Complex Multiplication

Let E/Q be an elliptic curve. For a prime p of good reduction,let E(F_p) be the set of rational points defined over the finitefield F_p. Denote by (#E(F_p)) the number of distinct prime divisorsof #E(F_p). For an elliptic curve with complex multiplication,the normal order of (#E(F_p)) is shown to be log log p. The normalorder of the number of distinct prime factors of the exponentof E(F_p) is also studied. 2000 Mathematics Subject Classification11N37, 11G20.     

Classi di isomorfismo delle cubiche diF q

LetF _q (q=p^r) be a field of characteristicp>3 andA the set of all elliptic cubic curves overF _q having a given absolute invariantj. Furthermore let ≈be the following equivalence relation: « if and only if and F_q are isomorphic overF _q as abelian varieties». The aim of this paper is to study the equivalence classes inA, induced by ≈, and the Frobenius' traces of the cubic curves belonging to different subclasses ofA.     

Selmer Groups over p-Adic Lie Extensions I

Let E be an elliptic curve defined over a number field F. Thepaper concerns the structure of the p-Selmer group of E overp-adic Lie extensions F of F which are obtained by adjoiningto F the p-division points of an abelian variety A defined overF. The main focus of the paper is the calculation of the Gal(F_F)-Eulercharacteristic of the p-Selmer group of E. The main theory isillustrated with the example of an elliptic curve of conductor294.     

Elliptic curve analogues of a pseudorandom generator

Using the discrete logarithm in [7] and [9] a large family of pseudorandom binary sequences was constructed. Here we extend this construction. An interesting feature of this extension is that in certain special cases we get sequences involving points on elliptic curves.     

Incomplete Character Sums and Polynomial Interpolation of the Discrete Logarithm

In the first part of the paper, certain incomplete character sums over a finite field F_p^r are considered which in the case of finite prime fields F_p are of the form ∑^A+N−1_n=Aχ(g(n))ψ(f(n)), where A and N are integers with 1≤N<p, g and f are polynomials over F_p, and χ denotes a multiplicative and ψ an additive character of F_p. Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude N^1/2p^r/4. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the finite prime field F_p for N consecutive elements of F_p must have a degree at least of the order of magnitude Np^−1/2. In this paper this result is extended to arbitrary F_p^r. The proof is based on the above new bound for incomplete hybrid character sums.