Introduction to δ-artithmetic : computation of integer approximate gcd and factorization.

Résumé : Cet article présente un nouveau cadre pour la définition et le calcul des pgcd approximatifs. C'est une extension de l'arithmétique classique permettant de traiter les problèmes lorsque qu'un certain ajustement des données est acceptable en vue de trouver des solutions respectant au mieux un certain nombre de contraintes. Dans ce cadre le pgcd approximatif peu se voir comme un calcul de pgcd classique ou on autorise de " petits ajustements " des données initial afin de garantir que le pgcd obtenu soit " suffisamment grand ". Depuis son introduction par Howgrave-Graham en 2001, ce sujet a fait l'objet de nombreuse publication, la plus part des articles repose sur les treillis. Notre approche se veux radicalement différente et se base sur une extension de l'arithmétique classique, nous introduisons de concept tel que la division approximative et la factorisation approximative, ce qui nous permet de poser de façon rigoureuse le problème du pgcd approximatifs. Le principal avantage de cet approche est qu'il nous permet de construire un cadre mathématique rigoureux et de définir de façon clair le pgcd approximatif recherché. Et cerise sur le gâteau, il débouche sur des algorithmes extrêmement simple à mettre en place. En particulier nous proposons ici deux algorithmes, le premier s'intéresse au pgcd approximatif, lorsque celui ci est supérieur à la racine de la plus petite des données et est d'autant plus efficace que la solution est éloignée de cette quantité. Le second s'intéresse au cas ou le pgcd est proche de la racine du plus petit des éléments et est d'autant moins performant que ce dernier en est éloigné. Nos recherches se poursuivent pour traiter le cas ou pgcd recherche est très inférieur à la racine de la plus petite des données initiales.
Type de document :
Pré-publication, Document de travail
2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00848673
Contributeur : Christian Fotso <>
Soumis le : samedi 27 juillet 2013 - 11:33:42
Dernière modification le : lundi 9 avril 2018 - 12:22:16
Document(s) archivé(s) le : mercredi 5 avril 2017 - 17:16:27

Fichier

Introduction_Delta-Arithmetiqu...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00848673, version 1

Collections

Citation

Christian Fotso. Introduction to δ-artithmetic : computation of integer approximate gcd and factorization.. 2011. 〈hal-00848673〉

Partager

Métriques

Consultations de la notice

342

Téléchargements de fichiers

186