A Method for Distinguishing the Two Candidate Elliptic Curves in the Complex Multiplication Method

다국어 초록 (Multilingual Abstract)

In this paper, we particularly deal with no Fp-rational
two-torsion elliptic curves, where Fp is the prime field of
the characteristic p. First we introduce a shift productbased
polynomial transform. Then, we show that the
parities of (#E − 1)/2 and (#E΄− 1)/2 are reciprocal to each
other, where #E and #E΄ are the orders of the two
candidate curves obtained at the last step of complex
multiplication (CM)-based algorithm. Based on this
property, we propose a method to check the parity by
using the shift product-based polynomial transform. For a
160 bits prime number as the characteristic, the proposed
method carries out the parity check 25 or more times
faster than the conventional checking method when 4
divides the characteristic minus 1. Finally, this paper
shows that the proposed method can make CM-based
algorithm that looks up a table of precomputed class
polynomials more than 10 percent faster.

참고문헌 (Reference)

1 "Weierstraβ Elliptic Curves and Side Channels Attacks" 335-345, 2002

2 "Speeding the Pollard and Elliptic Curve Methods of Factorization Mathematics of Computation" 243-264, 1987

3 "Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms" Paar 248-258, 2000

4 "On the Construction of Prime Order Elliptic Curves" 309-322, 2003

5 "Implementing the Asymptotically Fast Version of the Elliptic Curve Primality Proving Algorithm"

6 "Handbook of Elliptic and Hyperelliptic Curve Cryptography" 280-285, 2005

7 "Generating Elliptic Curves of Prime Order" 142-158, 2001

8 "Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curve" Univ 81-92, 1998

9 "Fast Generation of Elliptic Curves with Prime Order over Fp2c" 347-356, 2003

10 "Encyclopedia of Mathematics and Its Applications" Cambridge University Press 1984

11 "Elliptic Curves in Cryptography" Cambridge University Press -265, 1999

12 "Constructive and Destructive Facets of Weil Descent on Elliptic Curves" 2000

13 "Construction of Elliptic Curves with Prime Order and Estimation of Its Complexity" 1269-1277, 1999

14 "A Software Library for Elliptic Curve Cryptography"

15 "A Method for Distinguishing the Two Candidate Elliptic Curves in CM Method" 2004

16 "A Method for Checking the Parity of Technical Report of IEICE" 1-6, 2004

17 "A Library for doing Number Theory"

18 "A Course in Computational Algebraic Number Theory" 2000

19 "A Consideration on the Order of Genus 2 Hyperelliptic Curve" 28 (28): 889-892, 2005