Share Email Print
cover

Proceedings Paper

On matrix-vector product based sub-quadratic arithmetic complexity schemes for field multiplication
Author(s): M. A. Hasan
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Using an efficient way to compute the product of a Toeplitz matrix and a vector, a sub-quadratic arithmetic complexity scheme for field multiplication over binary extension fields has recently been proposed by Fan and Hasan. The scheme has been developed using a shifted polynomial basis for the representation of the field elements and has been stated to be applicable to the conventional polynomial basis, although with an increased gate delay for some field defining polynomials. The conventional polynomial basis is widely used in practice and is part of different recommendations and standards for cryptographic applications. In this article, we give additional details of the sub-quadratic complexity algorithm for the case of the polynomial basis by presenting efficient transformation matrices for a class of low weight field defining polynomials, namely trinomials.

Paper Details

Date Published: 12 September 2007
PDF: 11 pages
Proc. SPIE 6697, Advanced Signal Processing Algorithms, Architectures, and Implementations XVII, 669702 (12 September 2007); doi: 10.1117/12.734195
Show Author Affiliations
M. A. Hasan, Univ. of Waterloo (Canada)


Published in SPIE Proceedings Vol. 6697:
Advanced Signal Processing Algorithms, Architectures, and Implementations XVII
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top