|
Vol: 56(70) No: 2 / June 2011 Constructing Elliptic Curves with Predefined Parameters Tudor Bogdan Intrasoft SA Luxembourg, Bucharest, Romania, phone: (+40) 0727372488, e-mail: bogdantudor74@yahoo.com Keywords: elliptic curve, Hilbert polynomial, Java implementation, polynomial factorization, precision computing Abstract This paper presents some new algorithms that help in the generation of elliptic curves defined over prime order fields and the results of their implementation in Java language. The construction of such a curve depends on a series of factors, but the most important ones are the initial security parameters. These are being represented by the size of the prime number field order, the number of the points on that curve or the embedding degree. In this paper only the first two factors are being treated. The focus is represented by the behavior and computation time of these algorithms. There are several choices from the implementation point of view but almost all of them have only implementation in the “C” language, with dependencies on high precision mathematical routines. Java is proposed due to the portability of this language and there are many challenges in implementing high precision arithmetic in Java language, but by applying the algebraic expansions, the required precision can be controlled. The original contributions consist on the new numerical sieving method for computing the reduced quadratic form of the discriminant, new Java implementations for trigonometric functions and the new optimized algorithms in the computation of the Hilbert polynomial. References [1] A. O. L. Atkin and F. Morain, “Elliptic curves and primality proving”, Math. Comp., vol. 61, pp. 29-68, 1993. [2] F. Brezing and A. Weng, “Elliptic curves suitable for pairing based cryptography”, Design Codes and Cryptography, vol. 37, pp. 133-141, 2005. [3] P. Flajolet, X. Gourdon, and D. Panario, “The complete analysis of a polynomial factorization algorithm over finite fields”, Journal of Algorithms, vol. 40, pp. 37-81, 2001. [4] D. Freeman, M. Scott, and E. Teske, “A taxonomy of pairing-friendly elliptic curves”, Cryptography ePrint Archive, vol. 372, http://eprint.iacr.org/2006/372, 2006. [5] E. Konstantinou, A. Kontogeorgis, Y. Stamatiou, and C. Zaroliagis, “On the efficient generation of prime order elliptic curves”, Journal of cryptology, vol. 23, pp. 477-503, Springer-Verlag, New York, 2010. [6] R. Mak, “Java number cruncher: The Java programmer’s guide to numerical”, Prentice Hall, 2002. [7] L. Washington, “Elliptic curves: number theory and cryptography”, Chapman & Hall, New York, 2003. [8] H. Baier, “Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography”, Ph. D. dissertation, Darmstadt, 2002. [9] D. Hankerson, A. Menezes, and S. Vanstone, “Guide to elliptic curve cryptography”, Springer-Verlag, New York, 2004. [10] D. R. Musser, “Multivariate polynomial factorization”, J. ACM, vol. 2, pp. 291-308, 1976. [11] D. Y. Y. Yun, “On squarefree decomposition algorithms”, Proc. ACM Symp, On Symbolic and algebraic comp., pp. 26-35, 1976. [12] D. G. Cantor and H. Zassenhaus, “A new algorithm for factoring polynomials over finite fields”, Math. Comp., vol. 36, pp. 587-592, 1981. [13] B. Char, K. Gedder, and G. Gonnet, “Gcdheu: Heuristic polynomial gcd algorithm based on integer gcd computation”, Journal of Symbolic comp., vol. 7, pp. 31-48, 1989. [14] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “The design and analysis of computer algorithms”, Addison-Wesley, Reading , 1974. [15] V. Strassen, “The computational complexity of continued fractions”, SIAM J. Comput., vol. 12, pp. 1-27, 1983. [16] E. R. Berlekamp, “Factoring polynomials over large finite fields”, Math. Comp., vol. 24, pp. 713-735, 1970. [17] J. Von zur Gathen and V. Shoup, “Computing Frobenius maps and factoring polynomials”, Computational Complexity, vol. 2, pp. 187-224, 1992. |