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
Résumé : Dans cet exposé, nous nous intéressons au problème du rang bilinéaire : étant donnée une application bilinéaire (par exemple, le calcul d’un produit de polynômes, d’éléments d’un corps fini, ou encore de matrices), quel est le nombre minimal de multiplications sur le corps de base nécessaires pour évaluer cette application ? Ainsi, par exemple, la méthode de Karatsuba permet de calculer le produit de deux polynômes linéaires en seulement trois multiplications au lieu de quatre. Nous donnons dans cet exposé une formalisation du problème du rang bilinéaire, connu pour être NP-dur, et proposons un algorithme général permettant de calculer efficacement des solutions exactes, qui nous permettent ainsi de prouver l’optimalité de, voire même d’améliorer certaines bornes de la littérature.
Type de document :
Documents associés à des manifestations scientifiques -- Hal-inria+
AriC Seminar, Mar 2012, Lyon, France
Liste complète des métadonnées

https://hal.inria.fr/hal-01413162
Contributeur : Jérémie Detrey <>
Soumis le : vendredi 9 décembre 2016 - 14:25:06
Dernière modification le : vendredi 16 décembre 2016 - 01:05:15
Document(s) archivé(s) le : jeudi 23 mars 2017 - 10:14:35

Fichier

talk.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de
la notice

347

Téléchargements du document

20