DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, HY | ko |
dc.contributor.author | Park, JY | ko |
dc.contributor.author | Cheon, JH | ko |
dc.contributor.author | Park, JH | ko |
dc.contributor.author | Kim, JH | ko |
dc.contributor.author | Hahn, Sang-Geun | ko |
dc.date.accessioned | 2013-03-04T18:36:49Z | - |
dc.date.available | 2013-03-04T18:36:49Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2002 | - |
dc.identifier.citation | ALGORITHMIC NUMBER THEORY BOOK SERIES: LECTURE NOTES IN COMPUTER SCIENCE, v.2369, pp.292 - 307 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10203/83656 | - |
dc.description.abstract | In this paper we present an improved algorithm for counting points on elliptic curves over finite fields. It is mainly based on Satoh-Skjernaa-Taguchi algorithm [SST01], and uses a Gaussian Normal Basis (GNB) of small type t less than or equal to 4. In practice, about 42% (36% for prime N) of fields in cryptographic context (i.e., for p = 2 and 160 < N < 600) have such bases. They can be lifted from F-pN to Z(pN) in a natural way. From the specific properties of GNBs, efficient multiplication and the Frobenius substitution axe available. Thus a fast norm computation algorithm is derived, which runs in O(N-2mu log N) with O(N-2) space, where the time complexity of multiplying two n-bit objects is O(n(mu)). As a result, for all small characteristic p, we reduced the time complexity of the SST-algorithm from O(N2mu+0.5) to O(N2mu+ 1/mu+1) and the space complexity still fits in O(N-2). Our approach is expected to be applicable to the AGM since the exhibited improvement is not restricted to only [SST01]. | - |
dc.language | English | - |
dc.publisher | SPRINGER-VERLAG BERLIN | - |
dc.subject | FINITE-FIELDS | - |
dc.title | Fast elliptic curve point counting using Gaussian normal basis | - |
dc.type | Article | - |
dc.identifier.wosid | 000180068300024 | - |
dc.type.rims | ART | - |
dc.citation.volume | 2369 | - |
dc.citation.beginningpage | 292 | - |
dc.citation.endingpage | 307 | - |
dc.citation.publicationname | ALGORITHMIC NUMBER THEORY BOOK SERIES: LECTURE NOTES IN COMPUTER SCIENCE | - |
dc.contributor.localauthor | Hahn, Sang-Geun | - |
dc.contributor.nonIdAuthor | Kim, HY | - |
dc.contributor.nonIdAuthor | Park, JY | - |
dc.contributor.nonIdAuthor | Cheon, JH | - |
dc.contributor.nonIdAuthor | Park, JH | - |
dc.contributor.nonIdAuthor | Kim, JH | - |
dc.type.journalArticle | Article; Proceedings Paper | - |
dc.subject.keywordAuthor | elliptic curve | - |
dc.subject.keywordAuthor | Gaussian normal basis | - |
dc.subject.keywordAuthor | order counting | - |
dc.subject.keywordPlus | FINITE-FIELDS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.