Implementación de algoritmos de teoría de números/Algoritmo de factorización en números primos
Un algoritmo de factorización en números primos es un algoritmo que dado un número natural mayor que 1 genera la lista de números primos que componen la factorización del mismo. El más sencillo de entender e implementar en una computadora es el algoritmo de división por tentativa y sus variantes.
División por tentativa
editarEl algoritmo más sencillo y común para la factorización de enteros es la división por tentativa. Consiste en intentar dividir n entre todo número primo menor o igual a n. Si se encuentra un primo que es divisor de n, en división entera, ese número es un factor de n.
Si n es el número a factorizar, el algoritmo devuelve una lista de números primos factores de n. Si n = 1, entonces el número no es factorizable por ningún número primo (es 1).
algoritmo si devolver sino mientras hacer si y sino devolver
Con respecto a la notación:
- significa que i pertenece al conjunto de los números primos
- significa que i divide a n.
Mejoras
editarSe pueden realizar mejoras sobre el algoritmo dependiendo de sus variantes para ganar algo en velocidad de cálculo utilizando los siguientes lemas. Hay que tener en cuenta que también se necesita verificar si un determinado número i es primo y eso supone una sobrecarga de hacer un test de primalidad, o utilizar una tabla precalculada de números primos hasta cierto n, con lo que este paso para implementaciones sencillas se obvia, ganando en sencillez a costa de rendimiendo computacional. Siempre se puede ganar algo de rendimiendo descartando ciertos números utilizando el lema 2 descrito abajo.
Lema 1
editarUn número compuesto no puede tener más de un factor primo que sea mayor a su raíz cuadrada.
Demostración: Supongamos que sí puede haber más de uno, por ejemplo dos. Llamemos y a esos dos números primos y , ,.. al resto de los números primos factores de . Sean:
Si y ambos son mayores que , entonces y serán positivos. Desarrollando el producto se tiene que:
Como y , el desarrollo , por lo que el producto inicial debe ser mayor que :
llegándose a una contradicción, por lo tanto, a lo sumo un factor puede ser mayor que .
Lema 2
editarLos números primos mayores que 3 cumplen con la siguiente condición:
ó
siendo esta la más eficiente para soluciones iterativas de programación.
Demostración:
Todo número natural puede expresarse como 6n±r, para algún n, r variará solo entre 0 y 5.
- 6n+0 es divisible por 6
- 6n+2 es divisible por 2
- 6n+3 es divisible por 3
- 6n+4 es divisible por 2
6n+1 y 6n-1 (o lo que es lo mismo a efectos del análisis, 6n+5), no proporcionan ninguna garantía de divisibilidad entre 6, por lo tanto los números primos solo pueden encontrarse entre ellos.
Pseudocódigo
editarAplicando la iteración hasta la raíz cuadrada de n [lema 1]
algoritmo si ó ó devolver sino mientras hacer si y sino devolver
Para las variantes del algoritmo que no utilicen una tabla de primos precalculada o un test de primalidad para obtener los números primos candidatos a ser factores, se pueden combinar ambos lemas, de manera que se va incrementando i en 2, 4, 2, 4.. a partir de 5 [lema 1][lema 2]
algoritmo si ó ó devolver sino mientras hacer si sino si sino devolver
Complejidad computacional
editarEn el peor caso, la división por tentativa es un algoritmo costoso. Si se empieza en 2 y se va subiendo hasta la raíz cuadrada de n, el algoritmo requiere
tentativas, donde es la función contador de primos, el número de primos menores que x. En lo anterior no se ha tenido en cuenta la sobrecarga del test de primalidad para obtener los números primos candidatos a ser factores. Si se utiliza una variante sin el test de primalidad, sencillamente dividiendo por todo número impar menor que la raíz cuadrada de n, ya sea primo o no, puede llegar a necesitarse alrededor de
tentativas, que para un n grande es peor.
Esto significa que para un n con factores primos grandes de tamaños similares (como aquellos empleados en la criptografía asimétrica), la división por tentativa es computacionalmente impracticable.
Sin embargo, para un n con al menos un factor pequeño, la división por tentativa puede ser un método rápido para encontrar ese factor pequeño. Vale la pena percatarse de que para un n aleatorio, existe un 50% de probabilidad de que 2 sea un factor de n, un 33% de probabilidad de que 3 sea un factor, y así sucesivamente. Se puede observar que el 88% de todos los enteros positivos tiene un factor menor que 100, y que el 91% tiene un factor menor que 1000.
Implementación en distintos lenguajes de programación
editarC++
editar#include <iostream>
#include <cmath>
using namespace std;
template <class tipo>
tipo potencia(tipo base, tipo exponente)
{
return pow(base,exponente);
}
template <class tipo1, class tipo2>
tipo2 modulo(tipo1 a, tipo2 b)
{
return (a % b + b) % b;
}
void factorizacion(unsigned long long n)
{
const long long b = -1;
if (n == 1 || n == 2 || n == 3)
{
cout << n << endl;
return;
}
unsigned long long i = 2;
long long m = 0;
while (i <= static_cast<unsigned long long>(sqrt(n)))
{
if (n % i == 0)
{
cout << i << "--";
n /= i;
}
else if (i < 5)
{
++i;
}
else
{
i = i + modulo(2 * potencia(b,m), 6);
m = (m + 1) % 2;
}
}
cout << n << endl;
}
int main()
{
cout << "Factorizando el numero 100895598169:\n";
factorizacion(100895598169);
}