Improved method to find optimal formulae for bilinear maps

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 × 2 by 2 × 3 matrices up to the action of some group of automorphisms.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01519408
Contributeur : Svyatoslav Covanov <>
Soumis le : dimanche 7 mai 2017 - 13:59:04
Dernière modification le : jeudi 15 juin 2017 - 09:09:22
Document(s) archivé(s) le : mardi 8 août 2017 - 12:24:42

Fichiers

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

Identifiants

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

Citation

Svyatoslav Covanov. Improved method to find optimal formulae for bilinear maps. 2017. 〈hal-01519408〉

Partager

Métriques

Consultations de
la notice

185

Téléchargements du document

36