A VLSI Algorithm for Division in GF(2m) Based on Extended Binary GCD Algorithm

Yasuaki WATANABE  Naofumi TAKAGI  Kazuyoshi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.994-999
Publication Date: 2002/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
finite field arithmetic,  division in finite field,  hardware algorithm,  VLSI algorithm,  

Full Text: PDF(234.2KB)
>>Buy this Article

A VLSI algorithm for division in GF(2m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.