PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 6 February 2004

Area Efficient Multiplier based on LFSR Architecture

Jae-Hyung Jung
Kyungpook Nat$¡¯$l University, Computer Engineering
702-701, Daegu, Korea
email: dolp0@hanmail.net

In this paper, we propose a new LFSR multiplier for modular multiplication over $GF(2m)$. The multiplier is based on an all one polynomial (AOP). Fenn et al. proposed two efficient LFSR multipliers, AOPM and MAOPM, using the property of AOP. AOPM is a multiplier for a result with one dimensional extended fields. Thereby, to reduce the result with the ordinary fields element MAOPM is proposed. They just focused on time efficiency to derive AOPM to MAOPM. Therefore, they resulted about twice of the hardware requirement from AOPM. Our main idea is contrast with Fenn et al.$¡¯s$ idea. Since there are lots of applications with strict hardware requirements, we focused on area efficiency to derive a multiplier with the ordinary fields result. Therefore, we get a multiplier with almost same hardware requirements with AOPM but additional just two time clock cycles. The additional time clock cycles is not depends on the size of fields but it is just constant. Also, it can be generalized.

Our architectures could be used as a basic architecture for error-control coding, digital signal processing and cryptography. Especially, the finite field $GF(2m)$ is suitable for implementing hardware architecture. Finite field $GF(2m)$ arithmetic is fundamental to the implementation of a number of modern cryptographic systems and schemes of certain cryptographic systems. Most arithmetic operations, such as exponentiation, inversion, and division operations, can be carried out using just a modular multiplier or using power-sum architecture. Therefore, to reduce the complexity of these arithmetic architectures, an efficient architecture for multiplication over $GF(2m)$ is necessary.

Home page