Cryptology ePrint Archive: Report 2012/110

Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu and Jérémie Detrey and 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.

Category / Keywords: optimal algorithms, polynomial multiplication and squaring, finite field arithmetic, tensor rank, bilinear map, bilinear rank

Date: received 28 Feb 2012

Contact author: Jeremie Detrey at loria fr

Available formats: PDF | BibTeX Citation

Version: 20120229:132806 (All versions of this report)

Discussion forum: Show discussion | Start new discussion