A method for distinguishing the two candidate elliptic curves in CM method

Yasuyuki Nogami, Yoshitaka Morikawa

Research output: Contribution to journalConference articlepeer-review

2 Citations (Scopus)


In this paper, we first introduce a shift product-based polynomial transformation. 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 CM method algorithm. Based on this property, we propose a method to check the parity by using the shift product-based polynomial transformation. For a 160-bits prime number as the characteristic, the proposed method carries out the parity check about 20 times faster than the conventional method when 4 divides the characteristic minus 1.

Original languageEnglish
Pages (from-to)249-260
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - Jan 1 2005
Event7th International Conference on Information Security and Cryptology - ICISC 2004 - Seoul, Korea, Republic of
Duration: Dec 2 2004Dec 3 2004


  • CM method
  • Irreducible cubic polynomial
  • Quadratic power residue/non residue

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A method for distinguishing the two candidate elliptic curves in CM method'. Together they form a unique fingerprint.

Cite this