Introduction to δ-artithmetic : computation of integer approximate gcd and factorization.
Résumé
In this article we present a new framework to define and compute integer approximate gcd computation. It is an extension of the classical arithmetic to solve problem where data can be " ajust " to obtain " better " solution. Basically the problem of approximate gcd computation consist on searching a kind of gcd when input are not exact multiple of the real gcd. Our approach to solve this problem is totally different from the classical approach of this topic that rely on lattice. The main advantage of our solution is that it led to a clear definition of the notion of approximate Gcd and build a rigorous new mathematical framework to solve the problem. And " cerise sur le gâteau " we end up with algorithms that are very simple to understand and to implement. This paper start with an introduction to δ-artithmetic and we deduce natural and clean definition of approximates gcd. We then present two algorithms to find this quantity. The first one work well when the approximate gcd is greater than the square root of the smallest element (the pivot). It rely on the notion of approximate divisor and it is as efficient as the gcd is greater than this value. The second algorithm rely on the notion of approximate factorization, and work well when the gcd is close to the square root of the pivot. We are still working on the case where the gcd is very small compare to that value.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...