**GF(2^n) redundant representation using matrix embedding**

*Yongjia Wang and Xi Xiong and Haining Fan*

**Abstract: **By embedding a Toeplitz matrix-vector product (MVP) of dimension $n$ into a circulant MVP of dimension $N=2n+\delta -1$, where $\delta $ can be any nonnegative integer, we present a $GF(2^n)$ multiplication algorithm. This algorithm leads to a new redundant representation, and it has two merits: 1. The flexible choices of $\delta$ make it possible to select a proper $N$ such that the multiplication operation in ring $GF(2)[x]/(x^N+1$) can be performed using some asymptotically faster algorithms, e.g. the Fast Fourier Transformation (FFT)-based multiplication algorithm; 2. The redundant degrees, which are defined as $N/n$, are smaller than those of most previous $GF(2^n)$ redundant representations, and in fact they are approximately equal to 2 for all applicable cases.

**Category / Keywords: **Finite fields, redundant representation, matrix-vector product, shifted polynomial basis, FFT.

**Date: **received 9 Oct 2011, last revised 29 Sep 2014

**Contact author: **fhn at tsinghua edu cn

**Available format(s): **PDF | BibTeX Citation

**Note: **We move the result in the work of IACR eprint 2011/606 (Xi Xiong and Haining Fan) into this work, see Section VI.

**Version: **20140930:012819 (All versions of this report)

**Short URL: **ia.cr/2011/556

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]