Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Improved method for finding optimal formulae for bilinear maps in a finite field

Svyatoslav Covanov 1 
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In 2012, Barbulescu, Detrey, Estibals and Zimmermann proposed a new framework to exhaustively search for optimal formulae for evaluating bilinear maps, such as Strassen or Karatsuba formulae. The main contribution of this work is a new criterion to aggressively prune useless branches in the exhaustive search, thus leading to the computation of new optimal formulae, in particular for the short product modulo X 5 and the circulant product modulo (X 5 − 1). Moreover , we are able to prove that there is essentially only one optimal decomposition of the product of 3 x 2 by 2 x 3 matrices up to the action of some group of automorphisms.
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Svyatoslav Covanov Connect in order to contact the contributor
Submitted on : Friday, November 30, 2018 - 11:20:51 PM
Last modification on : Friday, February 4, 2022 - 3:30:19 AM
Long-term archiving on: : Friday, March 1, 2019 - 4:09:20 PM


Files produced by the author(s)


  • HAL Id : hal-01519408, version 3
  • ARXIV : 1705.07728


Svyatoslav Covanov. Improved method for finding optimal formulae for bilinear maps in a finite field. 2018. ⟨hal-01519408v3⟩



Record views


Files downloads