On the Efficient Generation of Prime-Order Elliptic Curves.
Saved in:
| Title: | On the Efficient Generation of Prime-Order Elliptic Curves. |
|---|---|
| Authors: | Konstantinou, Elisavet1,2 ekonstantinou@aegean.gr, Kontogeorgis, Aristides3 kontogar@aegean.gr, Stamatiou, Yannis C.2,4 istamat@cc.uoi.gr, Zaroliagis, Christos2,5 zaro@ceid.upatras.gr |
| Source: | Journal of Cryptology. Summer2010, Vol. 23 Issue 3, p477-503. 27p. 7 Charts, 7 Graphs. |
| Subjects: | Elliptic curves, Complex multiplication, Public key cryptography, Polynomials, Algebraic geometry |
| Abstract: | We consider the generation of prime-order elliptic curves (ECs) over a prime field $\mathbb{F}_{p}$ using the Complex Multiplication (CM) method. A crucial step of this method is to compute the roots of a special type of class field polynomials with the most commonly used being the Hilbert and Weber ones. These polynomials are uniquely determined by the CM discriminant D. In this paper, we consider a variant of the CM method for constructing elliptic curves (ECs) of prime order using Weber polynomials. In attempting to construct prime-order ECs using Weber polynomials, two difficulties arise (in addition to the necessary transformations of the roots of such polynomials to those of their Hilbert counterparts). The first one is that the requirement of prime order necessitates that D≡3mod8), which gives Weber polynomials with degree three times larger than the degree of their corresponding Hilbert polynomials (a fact that could affect efficiency). The second difficulty is that these Weber polynomials do not have roots in $\mathbb{F}_{p}$ . In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field $\mathbb{F}_{p^{3}}$ and present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^{3}}$ to roots of their corresponding Hilbert polynomials in $\mathbb{F}_{p}$ . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_{p}$ ), can be used in the CM method to generate prime-order ECs. We conduct an extensive experimental study comparing the efficiency of using this alternative class against the use of the aforementioned Weber polynomials. Finally, we investigate the time efficiency of the CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Cryptology is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 50034916 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: On the Efficient Generation of Prime-Order Elliptic Curves. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Konstantinou%2C+Elisavet%22">Konstantinou, Elisavet</searchLink><relatesTo>1,2</relatesTo><i> ekonstantinou@aegean.gr</i><br /><searchLink fieldCode="AR" term="%22Kontogeorgis%2C+Aristides%22">Kontogeorgis, Aristides</searchLink><relatesTo>3</relatesTo><i> kontogar@aegean.gr</i><br /><searchLink fieldCode="AR" term="%22Stamatiou%2C+Yannis+C%2E%22">Stamatiou, Yannis C.</searchLink><relatesTo>2,4</relatesTo><i> istamat@cc.uoi.gr</i><br /><searchLink fieldCode="AR" term="%22Zaroliagis%2C+Christos%22">Zaroliagis, Christos</searchLink><relatesTo>2,5</relatesTo><i> zaro@ceid.upatras.gr</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Cryptology%22">Journal of Cryptology</searchLink>. Summer2010, Vol. 23 Issue 3, p477-503. 27p. 7 Charts, 7 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Elliptic+curves%22">Elliptic curves</searchLink><br /><searchLink fieldCode="DE" term="%22Complex+multiplication%22">Complex multiplication</searchLink><br /><searchLink fieldCode="DE" term="%22Public+key+cryptography%22">Public key cryptography</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Algebraic+geometry%22">Algebraic geometry</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We consider the generation of prime-order elliptic curves (ECs) over a prime field $\mathbb{F}_{p}$ using the Complex Multiplication (CM) method. A crucial step of this method is to compute the roots of a special type of class field polynomials with the most commonly used being the Hilbert and Weber ones. These polynomials are uniquely determined by the CM discriminant D. In this paper, we consider a variant of the CM method for constructing elliptic curves (ECs) of prime order using Weber polynomials. In attempting to construct prime-order ECs using Weber polynomials, two difficulties arise (in addition to the necessary transformations of the roots of such polynomials to those of their Hilbert counterparts). The first one is that the requirement of prime order necessitates that D≡3mod8), which gives Weber polynomials with degree three times larger than the degree of their corresponding Hilbert polynomials (a fact that could affect efficiency). The second difficulty is that these Weber polynomials do not have roots in $\mathbb{F}_{p}$ . In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field $\mathbb{F}_{p^{3}}$ and present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^{3}}$ to roots of their corresponding Hilbert polynomials in $\mathbb{F}_{p}$ . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_{p}$ ), can be used in the CM method to generate prime-order ECs. We conduct an extensive experimental study comparing the efficiency of using this alternative class against the use of the aforementioned Weber polynomials. Finally, we investigate the time efficiency of the CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of Cryptology is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=50034916 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00145-009-9037-2 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 27 StartPage: 477 Subjects: – SubjectFull: Elliptic curves Type: general – SubjectFull: Complex multiplication Type: general – SubjectFull: Public key cryptography Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Algebraic geometry Type: general Titles: – TitleFull: On the Efficient Generation of Prime-Order Elliptic Curves. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Konstantinou, Elisavet – PersonEntity: Name: NameFull: Kontogeorgis, Aristides – PersonEntity: Name: NameFull: Stamatiou, Yannis C. – PersonEntity: Name: NameFull: Zaroliagis, Christos IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: Summer2010 Type: published Y: 2010 Identifiers: – Type: issn-print Value: 09332790 Numbering: – Type: volume Value: 23 – Type: issue Value: 3 Titles: – TitleFull: Journal of Cryptology Type: main |
| ResultId | 1 |
