PUBLICACIONES

Sociedad Colombiana de Matemáticas:Publicaciones
Lecturas Matemáticas
Volumen 27 [1] (2006)Páginas 5--16
Artículos Matemáticos

Short solutions for a linear Diophantine equation

Hamid Esmaeili
Bu-Ali Sina University, Hamedan, Iran

Resumen.En este artículo establecemos un método, basado en el algoritmo de reducción de las bases, para obtner soluciones cortas de una ecuación diofántica lineal en tiempo polinomio. Los resultados numéricos obtenidos muestran cierta superioridad sobre otros métodos que usan generalizaciones del algoritmo euclídeo.

Abstract. It is known that finding the shortest solution for a linear Diophantine equation is a NP problem. In this paper we have devised a method, based upon the basis reduction algorithm, to obtain short solutions to a linear Diophantine equation. By this method we can obtain a short solution (not necessarily the shortest one) in a polynomial time. Numerical experiments show superiority to other methods which use generalizations of the Euclid's algorithm.

Palabras claves. Linear Diophantine Equation, Short Solution, Basis Reduction Algorithm.

Codigo AMS. 11D04.

Archivo completo : Formato [PDF] (50 K).