Finding Optimal Formulae for Bilinear Maps

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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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},
      note = {\url{https://eprint.iacr.org/2012/110}},
      url = {https://eprint.iacr.org/2012/110}
}