Rational groups of elliptic curves suitable for cryptography
This paper overviews methods for the construction of elliptic curves over finite fields containing a subgroup of large prime order, in view of their applications in cryptography. For security reasons, the elliptic curves should be chosen at random from a pool large enough to be effectively innumerable. In the random curve selection method, a finite field \(k\) is fixed, random \(E/k\) are considered and \(|E(k)|\) is computed by the SEA algorithm. From this computation one can easily deduce \(|E(k)|\) for extensions \(K/k\) and look for a large prime factor in \(|E(K)/E(k)|\). In the CM method, a negative discriminant \(D\) is fixed and solutions of \(m^2D = t^2 - 4q\) are sought such that \(q- t+1\) has a large prime factor. By the theory of complex multiplication, there exists an elliptic curve over the field with \(q\) elements, having \(t\) as trace of Frobenius. This curve is constructed from its \(j\)-invariant, which is a root of a class polynomial \(H_D(X)\). For \(D\equiv 1 \pmod 8\), \(3\nmid D\), it is suggested to use the Weber class polynomial \(W_D(x)\) introduced by \textit{N. Yui} and \textit{D. Zagier} [Math. Comput. 66, 1645-1662 (1997; Zbl 0892.11022)], which is much better for computational purposes, since it has much smaller coefficients. Finally, it is remarked that the CM method for a fixed \(q\), sieving for discriminants \(D\) of small value, according to the complexity of the computation of the class polynomial, produces only a sparse (enumerable) family of elliptic curves. For the entire collection see [Zbl 0956.00037].
- Generating Prime Order Elliptic Curves: Difficulties and Efficiency Considerations
- Constructing elliptic curves of prime order
- Efficient construction of cryptographically strong elliptic curves
- On the efficient generation of prime-order elliptic curves
- Progress in Cryptology - INDOCRYPT 2003
- scientific article; zbMATH DE number 799785
- On counting and generating curves over small finite fields
- Efficient CM-constructions of elliptic curves over finite fields
- An algorithmic construction of finite elliptic curves of order divisible by a large prime
- Constructing elliptic curves over finite fields using double eta-quotients
- Efficient construction of cryptographically strong elliptic curves
- A rapid procedure of creating elliptic curves applying to cryptography
- Constructing elliptic curves of prime order
- Choosing the correct elliptic curve in the CM method
- scientific article; zbMATH DE number 2154267 (Why is no real title available?)
- A Method for Distinguishing the Two Candidate Elliptic Curves in CM Method
- Parametric families of elliptic curves with cyclic F_p-rational points groups
This page was built for publication: Rational groups of elliptic curves suitable for cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2708613)
