A new architecture for a parallel finite field multiplier with low complexity based on composite fields
- 1 July 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 45 (7) , 856-861
- https://doi.org/10.1109/12.508323
Abstract
A bit parallel structure for a multiplier with low complexity in Galois fields is introduced. The multiplier operates over composite fields GF((2/sup n/)/sup m/), with k=nm. The Karatsuba-Ofman algorithm (A. Karatsuba and Y. Ofmanis, 1963) is investigated and applied to the multiplication of polynomials over GF(2/sup n/). It is shown that this operation has a complexity of order O(k/sup log23/) under certain constraints regarding k. A complete set of primitive field polynomials for composite fields is provided which perform module reduction with low complexity. As a result, multipliers for fields GF(2/sup k/) up to k=32 with low gate counts and low delays are listed. The architectures are highly modular and thus well suited for VLSI implementation.Keywords
This publication has 9 references indexed in Scilit:
- Discrete logarithms in finite fields and their cryptographic significancePublished by Springer Nature ,2000
- Primitive polynomials and m-sequences over GF(q/sup m/)IEEE Transactions on Information Theory, 1993
- Modular construction of low complexity parallel multipliers for a class of finite fields GF(2/sup m/)IEEE Transactions on Computers, 1992
- Structure of parallel multipliers for a class of fields GF(2m)Information and Computation, 1989
- A new algorithm for multiplication in finite fieldsIEEE Transactions on Computers, 1989
- Vlsi designs for multiplication over finite fields GF(2m)Published by Springer Nature ,1989
- VLSI Architectures for Computing Multiplications and Inverses in GF(2m)IEEE Transactions on Computers, 1985
- Polynomial Multiplication, Powers and Asymptotic Analysis: Some CommentsSIAM Journal on Computing, 1974
- Irreducible polynomials over composite Galois fields and their applications in coding techniquesProceedings of the Institution of Electrical Engineers, 1974