An Algorithmic Construction of Finite Elliptic Curves of Order Divisible by a Large Prime

• Autorzy: Grześkowiak M.

Identyfikatory

DOI

10.3233/FI-2015-1161

• Języki publikacji: EN

Abstrakty

EN

Given a square-free integer Δ < 0, we present an algorithm constructing a pair of primes p and q such that q|p + 1 − t and 4p − t², = Δf², where |t| ≤ 2√p for some integers f, t. Together with a CM method presented in the paper, such primes p and q are used for a construction of an elliptic curve E over a finite field Fp such that the order of E is divisible by a large prime. It is shown that our algorithm works in polynomial time.

Słowa kluczowe

EN

elliptic curves over finite field; public key cryptography

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 4
• Strony: 331--343
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Grześkowiak M.

• Adam Mickiewicz University Faculty of Mathematics and Computer Science Umultowska 87, 61-614 Pozna´n, Poland

Bibliografia

• [1] Agrawal, M., Kayal, N., Saxena, N.: Primes is in P, Ann. of Math., 160(2), 2004, 781–793.
• [2] Atkin, A., Morain, F.: Elliptic curves and primality proving, Technical report, Projet ICSLA RR-1256, INRIA, 1990.
• [3] Baker, R. C., Harman, G., Pintz, J.: The difference between consecutive primes. II., Proc. London Math. Soc., 83(3), 2001, 532–562.
• [4] Borevich, Z., Shafarevich, I.: Number Theory, Academic Press, 1966, ISBN 9780121178512.
• [5] Br¨oker, R., Stevenhagen, P.: Efficient CM-constructions of elliptic curves over finite fields, Math. Comp., 76, 2007, 2161–2179.
• [6] Bröker, R., Stevenhagen, P.: Constructing elliptic curves of prime order, Contemp. Math., 463, 2008, 17–28.
• [7] Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields, J. Cryptology, 18(2), 2005, 79–89.
• [8] Enge, A.: The complexity of class polynomial computation via floating point approximations, Math. Comp., 78(266), 2009, 1089–1107.
• [9] Freeman, D., Scott, M., E.Teske: A taxonomy of pairing-friendly elliptic curves, J. Cryptology, 23(2), 2010, 224–280.
• [10] Galbraith, S., McKee, J.: The probability that the number of points on an elliptic curve over a finite field is prime, J. London Math. Soc., 62(3), 2000, 671–684.
• [11] Grześkowiak, M.: Algorithms for relatively cyclotomic primes, Fund. Inform., 125(2), 2013, 161–181.
• [12] Grześkowiak, M.: Algorithms for Pairing-Friendly Primes, Pairing-Based Cryptography 2013, LNCS 8365, 2014.
• [13] Hinz, J.: A generalization of Bombieri’s prime number theorem to algebraic number fields, Acta Arith., 51(2), 1988, 173–193.
• [14] Iwaniec, H., Urroz, J.: Orders of CM elliptic curves modulo p with at most two primes, Ann. Sc. Norm. Super. Pisa Cl. Sci., 5(9), 2010, 815832.
• [15] Koblitz, N.: Primality of the number of points on an elliptic curve over a finite field, Pacific J. Math., 131(1), 1988, 157–165.
• [16] Koblitz, N.: Algebraic Aspects of Cryptography, Springer-Verlag, 1997.
• [17] Konstantinou, E., Stamatiou, Y., Zaroliagis, C.: On the efficient generation of elliptic curves over prime fields, Cryptographic Hardware and Embedded SystemsCHES 2002, LNCS 2523, 2002.
• [18] Narkiewicz, W.: Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, 2004, ISBN 978-3-540-21902-6.
• [19] Savas¸, E., Schmidt, T., Koc¸, C. K.: Generating elliptic curves of prime order, Cryptographic Hardware and Embedded SystemsCHES 2001, LNCS 2162, 2001.
• [20] Schoof, R.: Elliptic Curves Over Finite Fields and the Computation of Square Roots (mod p), Math. Comp., 44(170), 1985, 483–494.
• [21] Silverman, J.: The Arithmetic of Elliptic Curves, Springer-Verlag, 1985.
• [22] Sutherland, A. V.: Computing Hilbert class polynomials with the chinese remainder theorem, Math. Comp., 80(273), 2011, 501–538.