IEEE Transactions on Computers · 1998 · 63 citations · 21 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsField-programmable Gate ArraysTheory Of ComputationGalois TheoryLookup TablesTiming AnalysisArithmetic Logic Unit ArchitectureArithmetic Of Finite FieldsComplexityFinite Field ArithmeticFinite Field ComputationModular Reduction AlgorithmsMultipliersVlsi Implementation
This contribution introduces a new class of multipliers for finite fields GF((2/sup n/)/sup 4/). The architecture is based on a modified version of the Karatsuba-Ofman algorithm (KOA). By determining optimized field polynomials of degree four, the last stage of the KOA and the module reduction can be combined. This saves computation and area in VLSI implementations. The new algorithm leads to architectures which show a considerably improved gate complexity compared to traditional approaches and reduced delay if compared with KOA-based architectures with separate module reduction. The new multipliers lead to highly modular architectures and are, thus, well suited for VLSI implementations. Three types of field polynomials are introduced and conditions for their existence are established. For the small fields, where n=2,3,...,8, which are of primary technical interest, optimized field polynomials were determined by an exhaustive search. For each field order, exact space and time complexities are provided.
21
Handbook of applied cryptography
Choice Reviews Online · 1997 · 10.5K citations · Full text
Multiplication of Multidigit Numbers on Automata
Anatolij A. Karatsuba, Yu. Ofman · Soviet physics. Doklady · 1963 · 794 citations
Neal Koblitz · Journal of Cryptology · 1989 · 452 citations · Full text