Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-00848673
Contributor : Christian Fotso <>
Submitted on : Saturday, July 27, 2013 - 11:33:42 AM
Last modification on : Thursday, March 5, 2020 - 3:16:45 PM
Long-term archiving on: : Wednesday, April 5, 2017 - 5:16:27 PM

File

Introduction_Delta-Arithmetiqu...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00848673, version 1

Collections

Citation

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

Share

Metrics

Record views

443

Files downloads

277