On matrix-vector product based sub-quadratic arithmetic complexity schemes for field multiplication

M. A. Hasan

doi:10.1117/12.734195

12 September 2007 On matrix-vector product based sub-quadratic arithmetic complexity schemes for field multiplication

M. A. Hasan

Proceedings Volume 6697, Advanced Signal Processing Algorithms, Architectures, and Implementations XVII; 669702 (2007) https://doi.org/10.1117/12.734195
Event: Optical Engineering + Applications, 2007, San Diego, California, United States

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.

Citation Download Citation

M. A. Hasan "On matrix-vector product based sub-quadratic arithmetic complexity schemes for field multiplication", Proc. SPIE 6697, Advanced Signal Processing Algorithms, Architectures, and Implementations XVII, 669702 (12 September 2007); https://doi.org/10.1117/12.734195

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available