@inproceedings{f66c66075e224c0db02639299032427a,

title = "Type-II optimal polynomial bases",

abstract = "In the 1990s and early 2000s several papers investigated the relative merits of polynomial-basis and normal-basis computations for F_{2^n}. Even for particularly squaring-friendly applications, such as implementations of Koblitz curves, normal bases fell behind in performance unless a type-I normal basis existed for F_{2^n}. In 2007 Shokrollahi proposed a new method of multiplying in a type-II normal basis. Shokrollahi{\textquoteright}s method efficiently transforms the normal-basis multiplication into a single multiplication of two size-(n¿+¿1) polynomials. This paper speeds up Shokrollahi{\textquoteright}s method in several ways. It first presents a simpler algorithm that uses only size-n polynomials. It then explains how to reduce the transformation cost by dynamically switching to a {\textquoteleft}type-II optimal polynomial basis{\textquoteright} and by using a new reduction strategy for multiplications that produce output in type-II polynomial basis. As an illustration of its improvements, this paper explains in detail how the multiplication overhead in Shokrollahi{\textquoteright}s original method has been reduced by a factor of 1.4 in a major cryptanalytic computation, the ongoing attack on the ECC2K-130 Certicom challenge. The resulting overhead is also considerably smaller than the overhead in a traditional low-weight-polynomial-basis approach. This is the first state-of-the-art binary-elliptic-curve computation in which type-II bases have been shown to outperform traditional low-weight polynomial bases. Keywords Optimal normal basis - ONB - polynomial basis - transformation - elliptic-curve cryptography.",

author = "D.J. Bernstein and T. Lange",

year = "2010",

doi = "10.1007/978-3-642-13797-6_4",

language = "English",

isbn = "978-3-642-13796-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "41--61",

editor = "M.A. Hasan and T. Helleseth",

booktitle = "Arithmetic of Finite Fields (Third International Workshop, WAIFI 2010, Istanbul, Turkey, June 27-30, 2010. Proceedings)",

address = "Germany",

}