Fast arithmetic for polynomials over F>inf<2>/inf<in hardware

Abstract

We study different possibilities of implementing Karatsuba multipliers for polynomials over F <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> on Field Programmable Gate Arrays (FPGAs). This is a core task for implementing finite fields of characteristic 2. Algorithmic and platform dependent optimizations yield efficient hardware designs. The resulting structure is hybrid in two different aspects. On the one hand, a combination of various methods decreases the number of bit operations. On the other hand, a mixture of sequential and combinational circuit design techniques including pipelining is used to design a circuit which can be adapted flexibly to time-area constraints. The approach—both theory and implementation—can be viewed as a further step towards taming the machinery of fast algorithmics for hardware applications.