### Polynomial multiplication over binary finite fields: new upper bounds

Alessandro De Piccoli, Andrea Visconti, and Ottavio Giulio Rizzo

##### Abstract

When implementing a cryptographic algorithm, efficient operations have high relevance both in hardware and software. Since a number of operations can be performed via polynomial multiplication, the arithmetic of polynomials over finite fields plays a key role in real-life implementations. One of the most interesting paper that addressed the problem has been published in 2009. In [5], Bernstein suggests to split polynomials into parts and presents a new recursive multiplication technique which is faster than those commonly used. In order to further reduce the number of bit operations [6] required to multiply n-bit polynomials, researchers adopt different approaches. In [18] a greedy heuristic has been applied to linear straight-line sequences listed in [6]. In 2013, D'angella, Schiavo and Visconti [20] skip some redundant operations of the multiplication algorithms described in [5]. In 2015, Cenk, Negre and Hasan [12] suggest new multiplication algorithms. In this paper, (a) we present a "k-1"-level Recursion algorithm that can be used to reduce the effective number of bit operations required to multiply n-bit polynomials; and (b) we use algebraic extensions of F_2 combined with Lagrange interpolation to improve the asymptotic complexity.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Polynomial multiplicationKaratsubaTwo-level Seven-way Recursion algorithmbinary fieldsfast software implementations.
Contact author(s)
andrea visconti @ unimi it
History
Short URL
https://ia.cr/2018/091

CC BY

BibTeX

@misc{cryptoeprint:2018/091,
author = {Alessandro De Piccoli and Andrea Visconti and Ottavio Giulio Rizzo},
title = {Polynomial multiplication over binary finite fields: new upper bounds},
howpublished = {Cryptology ePrint Archive, Paper 2018/091},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/091}},
url = {https://eprint.iacr.org/2018/091}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.