Impact of Intel's New Instruction Sets on Software Implementation of $GF(2)[x]$ Multiplication

Chen Su; Haining Fan

Paper 2011/589

Impact of Intel's New Instruction Sets on Software Implementation of $GF(2)[x]$ Multiplication

Chen Su and Haining Fan

Abstract

PCLMULQDQ, a new instruction that supports $GF(2)[x]$ multiplication, was introduced by Intel in 2010. This instruction brings dramatic change to software implementation of multiplication in $GF(2^m)$ fields. In this paper, we present improved Karatsuba formulae for multiplying two small binary polynomials, compare different strategies for PCLMULQDQ-based multiplication in the five $GF(2^m)$ fields recommended by NIST and conclude the best design approaches to software implementation of $GF(2)[x]$ multiplication.

Note: Source code appended

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. Unknown where it was published
Keywords: $GF(2)[x]$ multiplication Karatsuba Algorithm SSE AVX PCLMULQDQ
Contact author(s): sochat88 @ gmail com
History: 2012-03-22: last of 4 revisions; 2011-11-03: received; See all versions
Short URL: https://ia.cr/2011/589
License: CC BY

BibTeX

@misc{cryptoeprint:2011/589,
      author = {Chen Su and Haining Fan},
      title = {Impact of Intel's New Instruction Sets on Software Implementation of ${GF}(2)[x]$ Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/589},
      year = {2011},
      url = {https://eprint.iacr.org/2011/589}
}