Skip to Main content Skip to Navigation
Documents associated with scientific events

Finding Optimal Formulae for Bilinear Maps

Razvan Barbulescu 1 Jérémie Detrey 1 Nicolas Estibals 1 Paul Zimmermann 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : This talk will focus on the bilinear rank problem: given a bilinear map (e.g., the product of polynomials, of finite-field elements, or of matrices), what is the smallest number of multiplications over the coefficient ring required to evaluate this function? For instance, Karatsuba's method allows one to compute the product of two linear polynomials using only three multiplications instead of four. In this talk, we give a formalization of the bilinear rank problem, which is known to be NP-hard, and propose a generic algorithm to efficiently compute exact solutions, thus proving the optimality of (or even improving) known complexity bounds from the literature.
Document type :
Documents associated with scientific events
Complete list of metadatas
Contributor : Jérémie Detrey <>
Submitted on : Friday, December 9, 2016 - 2:25:06 PM
Last modification on : Friday, October 16, 2020 - 4:02:04 PM
Long-term archiving on: : Thursday, March 23, 2017 - 10:14:35 AM


Files produced by the author(s)


  • HAL Id : hal-01413162, version 1




Razvan Barbulescu, Jérémie Detrey, Nicolas Estibals, Paul Zimmermann. Finding Optimal Formulae for Bilinear Maps. AriC Seminar, Mar 2012, Lyon, France. ⟨hal-01413162⟩



Record views


Files downloads