Subquadratic space complexity digit-serial multiplier over binary extension fields using Toom-Cook algorithm

In this paper, we present a new (4,2)-way Toom-Cook algorithm using finite field interpolation. The proposed algorithm uses multi-evaluation scheme to construct a digit-serial multiplier over GF(2 m ) which involves subquadratic space-complexity. From theoretical analysis, it is found that the propo...

Full description

Saved in:
Bibliographic Details
Main Authors: Chiou-Yng Lee, Meher, Pramod Kumar, Wen-Yo Lee
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Complexity theory
Computer architecture
Delays
digit-serial multiplication
Logic gates
multi-evaluation
Polynomials
Pulse width modulation
Toom-Cook algorithm
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a new (4,2)-way Toom-Cook algorithm using finite field interpolation. The proposed algorithm uses multi-evaluation scheme to construct a digit-serial multiplier over GF(2 m ) which involves subquadratic space-complexity. From theoretical analysis, it is found that the proposed architecture has O(m log4 5 ) space complexity and O(m log4 2 ) latency, which is significantly less than traditional digit-serial multipliers.
ISSN:2325-0631
DOI:10.1109/ISICIR.2014.7029517