Open AccessA Method for Distinguishing the Two Candidate Elliptic Curves in the Complex Multiplication Method
Author(s) -
Nogami Yasuyuki,
Obara Mayumi,
Morikawa Yoshitaka
Publication year - 2006
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.06.0106.0059
Subject(s) - mathematics , reciprocal , elliptic curve , complex multiplication , algorithm , polynomial , multiplication (music) , arithmetic , prime (order theory) , discrete mathematics , pure mathematics , combinatorics , mathematical analysis , philosophy , linguistics
In this paper, we particularly deal with no F p ‐rational two‐torsion elliptic curves, where F p is the prime field of the characteristic p. First we introduce a shift product‐based 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.