In-depth comparison of the Berlekamp – Massey – Sakata and the Scalar-FGLM algorithms: the non adaptive variants

Jérémy Berthomieu 1 Jean-Charles Faugère 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We compare thoroughly the Berlekamp – Massey – Sakata algorithm and the Scalar-FGLM algorithm, which compute both the ideal of relations of a multi-dimensional linear recurrent sequence. Suprisingly, their behaviors differ. We detail in which way they do and prove that it is not possible to tweak one of the algorithms in order to mimic exactly the behavior of the other.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01516708
Contributeur : Jérémy Berthomieu <>
Soumis le : mercredi 20 septembre 2017 - 17:43:27
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Fichiers

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01516708, version 2
  • ARXIV : 1709.07168

Collections

Citation

Jérémy Berthomieu, Jean-Charles Faugère. In-depth comparison of the Berlekamp – Massey – Sakata and the Scalar-FGLM algorithms: the non adaptive variants. 2017. 〈hal-01516708v2〉

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

12