Implementación de algoritmos de teoría de números/Algoritmos básicos en teoría de números

Podemos decir informalmente, que los algoritmos son procedimientos paso-a-paso para resolver problemas. Se puede pensar en ellos como simples programas de computadora, escritos en un lenguaje artificial específico.

Se dice que un algoritmo resuelve un problema A, si dicho algoritmo se puede aplicar a cualquier instancia I de A, y se garantiza que siempre produce una solución para dicha instancia. De manera general, nos interesa encontrar el algoritmo más «eficiente» para resolver cierto problema. En su sentido más amplio, la noción de eficiencia involucra a todos los recursos computacionales necesarios para la ejecución de un algoritmo.

Por algoritmo «más eficiente» usalmente nos referimos al más rápido. Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este recurso.

En teoría de números, hay una serie de métodos y algoritmos básicos, usados para el cálculo de ciertas cantidades o números (salida), que cumplen una serie de propiedades dentro de un conjunto mayor de números, que se utiliza, generalmente, como entrada.

Famosos son el algoritmo de Euclides, que es un método antiguo y eficaz para calcular el máximo común divisor (MCD) o la criba de Eratóstenes, que permite hallar todos los números primos menores que un número natural dado n. El primero fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. El segundo (la criba), fue descrito y atribuído a Eratóstenes en el (Introducción a la Aritmética, gr. Ἀριθμητικὴ εἰσαγωγή), de Nicómaco de Gerasa.

Uno de los algoritmos más importantes en teoría de números es el de factorización en números primos, ya que tener un algoritmo para este problema con un tiempo de ejecución suficientemente pequeño tendría gran repercusión en criptografía, puesto que la mayoría de criptosistemas utilizados en el sector financiero o gubernamental (a alto nivel) dependen de su imposibilidad.

---