GF(2^n) redundant representation using matrix embedding

Yongjia Wang; Xi Xiong; Haining Fan

Paper 2011/556

GF(2^n) redundant representation using matrix embedding

Yongjia Wang, Xi Xiong, and Haining Fan

Abstract

By embedding a Toeplitz matrix-vector product (MVP) of dimension $n$ into a circulant MVP of dimension $N = 2 n + δ - 1$ , where $δ$ can be any nonnegative integer, we present a $G F (2^{n})$ multiplication algorithm. This algorithm leads to a new redundant representation, and it has two merits: 1. The flexible choices of $δ$ make it possible to select a proper $N$ such that the multiplication operation in ring $G F (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 $G F (2^{n})$ redundant representations, and in fact they are approximately equal to 2 for all applicable cases.

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

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.not published
Keywords: Finite fields redundant representation matrix-vector product shifted polynomial basis FFT.
Contact author(s): fhn @ tsinghua edu cn
History: 2014-09-30: revised; 2011-10-11: received; See all versions
Short URL: https://ia.cr/2011/556
License: CC BY

BibTeX

@misc{cryptoeprint:2011/556,
      author = {Yongjia Wang and Xi Xiong and Haining Fan},
      title = {{GF}(2^n) redundant representation using matrix embedding},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/556},
      year = {2011},
      url = {https://eprint.iacr.org/2011/556}
}