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

https://hal.inria.fr/hal-01413162
Contributor : Jérémie Detrey <>
Submitted on : Friday, December 9, 2016 - 2:25:06 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Long-term archiving on : Thursday, March 23, 2017 - 10:14:35 AM

File

talk.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01413162, version 1

Collections

Relations

Citation

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

Share

Metrics

Record views

487

Files downloads

81