Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu; Jérémie Detrey; Nicolas Estibals; Paul Zimmermann

Paper 2012/110

Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu, Jérémie Detrey, Nicolas Estibals, and Paul Zimmermann

Abstract

We describe a unified framework to search for optimal formulae evaluating bilinear --- or quadratic --- maps. This framework applies to polynomial multiplication and squaring, finite field arithmetic, matrix multiplication, etc. We then propose a new algorithm to solve problems in this unified framework. With an implementation of this algorithm, we prove the optimality of various published upper bounds, and find improved upper bounds.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: optimal algorithms polynomial multiplication and squaring finite field arithmetic tensor rank bilinear map bilinear rank
Contact author(s): Jeremie Detrey @ loria fr
History: 2012-02-29: received
Short URL: https://ia.cr/2012/110
License: CC BY

BibTeX

@misc{cryptoeprint:2012/110,
      author = {Razvan Barbulescu and Jérémie Detrey and Nicolas Estibals and Paul Zimmermann},
      title = {Finding Optimal Formulae for Bilinear Maps},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/110},
      year = {2012},
      url = {https://eprint.iacr.org/2012/110}
}