REVIEW PAPER
CONSTRUCTING ELLIPTIC CURVES WITH A SUBGROUP OF A GIVEN ORDER AND WITH A GIVEN ENDOMORPHISM RING
1
Szkoła Główna Handlowa w Warszawie
2
Polska Akademia Nauk w Warszawie
Publication date: 2014-12-05
SBN 2014;6(2): 81-94
KEYWORDS
ABSTRACT
The complex multiplication (CM) method allows one to construct an elliptic
curve over a finite field, whose endomorphism ring is the maximal order in an imaginary
quadratic field with a suitably small discriminant. Using CM method Lay-Zimmer and
Br¨oker-Stevenhagen gave a method to construct an elliptic curve of a given order n over
some prime field. Their method has a heuristic polynomial time if n has not too many
prime factors. In this paper we show that in an analogous way one can construct an
elliptic curve, which contains a subgroup of a given order r and has a given endomorphism ring with a suitably small discriminant. We give heuristic arguments, which show
that the method works in a polynomial time if r is prime.
REFERENCES (17)
1.
A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68.
2.
J. Belding, R. Broker, A. Enge, and K. Lauter ¨ , Computing Hilbert class polynomials, Algorithmic Number Theory Symposium-ANTS VIII (A. J. van der Poorten and A. Stein, eds.), Lecture Notes in Computer Science, vol. 5011, Springer, 2008, pp. 282–295.
3.
R. Broker ¨ , A p-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), 2417–2435.
4.
R. Broker, P. Stevenhagen ¨ , Efficient CM-constructions of elliptic curves over finite fields Math. Comp. 76 (2007), 2161–2179.
5.
H. Cohen, A course in computational algebraic number theory, Springer Graduate Texts in Mathematics, vol. 138, 1993.
6.
D. Cox, Primes of the form x 2 + ny2 . Fermat, Class Field Theory and Complex Multiplication, John Wiley & Sons (1989).
7.
A. Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089–1107.
8.
R. Gallant, R. Lambert, S. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, In: Kilian, J. (ed.) CRYPTO. LNCS, vol. 2139, pp. 190–200. Springer (2001).
9.
S. D. Galbraith, X. Lin, M. Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, J. Cryptology, 24(3):446–469, 2011.
10.
N. Koblitz, CM-curves with good cryptographic properties, Proc. Crypto’91, Springer-Verlag (1992) pp. 279–287.
12.
G. Lay, H. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic Number theory Symposium I, Springer Lecture Notes in Computer Science, 1994. MR1322728 (96a:11054).
13.
R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44, (1985), 483–494.
14.
R. Schoof, Counting points on elliptic curves over finite fields, J. Th´eorie des Nombres de Bordeaux 7 (1995). 219–254.
16.
J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Springer-Verlag, GTM 151, 1995.
17.
A. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), 501–538.
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
