Dec, 2006
A method for distinguishing the two candidate elliptic curves in the complex multiplication method
ETRI JOURNAL
- ,
- ,
- Volume
- 28
- Number
- 6
- First page
- 745
- Last page
- 760
- Language
- English
- Publishing type
- DOI
- 10.4218/etrij.06.0106.0059
- Publisher
- ELECTRONICS TELECOMMUNICATIONS RESEARCH INST
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.
- Link information
-
- DOI
- https://doi.org/10.4218/etrij.06.0106.0059
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000242809400006&DestApp=WOS_CPL
- Scopus
- https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33845396854&origin=inward Open access
- Scopus Citedby
- https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=33845396854&origin=inward
- ID information
-
- DOI : 10.4218/etrij.06.0106.0059
- ISSN : 1225-6463
- eISSN : 2233-7326
- SCOPUS ID : 33845396854
- Web of Science ID : WOS:000242809400006