Konstruowanie krzywych eliptycznych z podgrupą danego rzędu i z danym pierścieniem endomorfizmów

• Autorzy: Dryło R. , Jelonek Z.

Warianty tytułu

EN

Constructing elliptic curves with a subgroup of a given order and with a given endomorphism rin

• Języki publikacji: PL

Abstrakty

PL

Metoda mnożeń zespolonych (CM metoda) pozwala skonstruować krzywą eliptyczną nad ciałem skończonych, której pierścień endomorfizmów jest ordynkiem maksymalnym w ciele urojonym kwadratowym o odpowiednio małym wyróżniku. Stosując CM metodę Lay i Zimmer oraz Bröker i Stevenhagen podali metodę konstruowania krzywej eliptycznej danego rzędu n nad pewnym ciałem prostym. Ich metoda ma heurystycznie wielomianowy czas działania, jeśli n nie ma zbyt wielu dzielników pierwszych. W tym opracowaniu pokażemy, że w analogiczny sposób można skonstruować krzywą eliptyczną, która zawiera podgrupę danego rzędu r i ma dany pierścień endomorfizmów o odpowiednio małym wyróżniku. Przy pewnych heurystycznych założeniach metoda ma wielomianowy czas działania, jeśli r jest liczbą pierwszą.

EN

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öker-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.

Słowa kluczowe

PL

krzywe eliptyczne danego rzędu; metoda CM; algorytm Cornacchii; pierścień endomorfizmów

EN

elliptic curves with given order; CM method; Cornacchia's algorithm; endomorphism ring

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Studia Bezpieczeństwa Narodowego
• Rocznik: 2014
• Tom: R. 4, Nr 6
• Strony: 81--94
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Dryło R.

• Szkoła Główna Handlowa, Aleja Niepodległości 162, 02-554 Warszawa

autor

Jelonek Z.

• Instytut Matematyczny PAN, ul. Śniadeckich 8, 00-950 Warszawa

Bibliografia

• [1] A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68.
• [2] J. Belding, R. Bröker, 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. Bröker, A p-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), 2417–2435.
• [4] R. Bröker, 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 x2 + 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 modp. Math. Comp. 44, (1985), 483–494.
• [14] R. Schoof, Counting points on elliptic curves over finite fields, J. Théorie 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).