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

Yasuyuki Nogami; Yoshitaka Morikawa

doi:10.1007/11496618_19

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

Yasuyuki Nogami, Yoshitaka Morikawa

Research output: Contribution to journal › Conference article › peer-review

2 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	249-260
Number of pages	12
Journal	Lecture Notes in Computer Science
Volume	3506
DOIs	https://doi.org/10.1007/11496618_19
Publication status	Published - Jan 1 2005
Event	7th International Conference on Information Security and Cryptology - ICISC 2004 - Seoul, Korea, Republic of Duration: Dec 2 2004 → Dec 3 2004

Keywords

CM method
Irreducible cubic polynomial
Quadratic power residue/non residue

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11496618_19

Cite this

@article{2a592c436d2d48e5a1cb2e1494ab15a7,

title = "A method for distinguishing the two candidate elliptic curves in CM method",

abstract = "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.",

keywords = "CM method, Irreducible cubic polynomial, Quadratic power residue/non residue",

author = "Yasuyuki Nogami and Yoshitaka Morikawa",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/11496618_19",

language = "English",

volume = "3506",

pages = "249--260",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Verlag",

note = "7th International Conference on Information Security and Cryptology - ICISC 2004 ; Conference date: 02-12-2004 Through 03-12-2004",

}

TY - JOUR

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

AU - Nogami, Yasuyuki

AU - Morikawa, Yoshitaka

PY - 2005/1/1

Y1 - 2005/1/1

N2 - 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.

AB - 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.

KW - CM method

KW - Irreducible cubic polynomial

KW - Quadratic power residue/non residue

UR - http://www.scopus.com/inward/record.url?scp=24944469469&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24944469469&partnerID=8YFLogxK

U2 - 10.1007/11496618_19

DO - 10.1007/11496618_19

M3 - Conference article

AN - SCOPUS:24944469469

SN - 0302-9743

VL - 3506

SP - 249

EP - 260

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 7th International Conference on Information Security and Cryptology - ICISC 2004

Y2 - 2 December 2004 through 3 December 2004

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this