Scalable and Systolic Montgomery Multipliers over GF(2m)

Chin-Chin CHEN  Chiou-Yng LEE  Erl-Huei LU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.7   pp.1763-1771
Publication Date: 2008/07/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.7.1763
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
Keyword: 
systolic multiplier,  Toeplitz matrix-vector,  scalable architecture,  Montgomery,  

Full Text: PDF>>
Buy this Article




Summary: 
This work presents a novel scalable and systolic Montgomery's algorithm in GF(2m). The proposed algorithm is based on the Toeplitz matrix-vector representation, which obtains the scalable and systolic Montgomery multiplier in a flexible manner, and can adapt to the required precision. Analytical results indicate that the proposed multiplier over the generic field of GF(2m) has a latency of d+n(2n+1), where n = m / d , and d denotes the selected digital size. The latency is reduced to d+n(n+1) clock cycles when the field is constructed from generalized equally-spaced polynomials. Since the selected digital size is d ≥5 bits, the proposed architectures have lower time-space complexity than traditional digit-serial multipliers. Moreover, the proposed architectures have regularity, modularity and local interconnect ability, making them very suitable for VLSI implementation.