### 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’s method efficiently transforms the normal-basis multiplication into a single multiplication of two size-(n¿+¿1) polynomials.
This paper speeds up Shokrollahi’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 ‘type-II optimal polynomial basis’ 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’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.

Original language | English |
---|---|

Title of host publication | Arithmetic of Finite Fields (Third International Workshop, WAIFI 2010, Istanbul, Turkey, June 27-30, 2010. Proceedings) |

Editors | M.A. Hasan, T. Helleseth |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 41-61 |

ISBN (Print) | 978-3-642-13796-9 |

DOIs | |

Publication status | Published - 2010 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 6087 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'Type-II optimal polynomial bases'. Together they form a unique fingerprint.

## Cite this

Bernstein, D. J., & Lange, T. (2010). Type-II optimal polynomial bases. In M. A. Hasan, & T. Helleseth (Eds.),

*Arithmetic of Finite Fields (Third International Workshop, WAIFI 2010, Istanbul, Turkey, June 27-30, 2010. Proceedings)*(pp. 41-61). (Lecture Notes in Computer Science; Vol. 6087). Springer. https://doi.org/10.1007/978-3-642-13797-6_4