PL EN
REVIEW PAPER
CONSTRUCTING ELLIPTIC CURVES WITH A SUBGROUP OF A GIVEN ORDER AND WITH A GIVEN ENDOMORPHISM RING
 
More details
Hide details
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.
 
11.
S. Lang, Elliptic functions Springer, 1987.
 
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.
 
15.
J. Silverman, The Arithmetic of Elliptic Curves Springer, 1986.
 
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
Journals System - logo
Scroll to top