2001 | OriginalPaper | Buchkapitel
A Memory Efficient Version of Satoh’s Algorithm
verfasst von : Frederik Vercauteren, Bart Preneel, Joos Vandewalle
Erschienen in: Advances in Cryptology — EUROCRYPT 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we present an algorithm for counting points on elliptic curves over a finite field $$ \mathbb{F}_{p^n } $$ of small characteristic, based on Satoh's algorithm. The memory requirement of our algorithm is O(n2), where Satoh's original algorithm needs O(n3) memory. Furthermore, our version has the same run time complexity of O(nn+ε) bit operations, but is faster by a constant factor. We give a detailed description of the algorithm in characteristic 2 and show that the amount of memory needed for the generation of a secure 200-bit elliptic curve is within the range of current smart card technology.