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

El 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 ${\text{factorización }}(n)$
  si $n=1$
     devolver $n$
  sino
     $i\leftarrow 2$
     mientras $n\neq 1$ hacer
        si $i\in \mathbb {P}$ y $i\mid n$
           $\{{\text{lista factores }}n\}\leftarrow i$
           $n\leftarrow n/i$
        sino
           $i\leftarrow i+1$
  devolver $\{{\text{lista factores }}n\}$

Con respecto a la notación:

• $i\in \mathbb {P}$ significa que i pertenece al conjunto de los números primos
• $i\mid n$ significa que i divide a n.

Mejoras

Se 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

Un número compuesto $n$ 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 $p_{1}$ y $p_{2}$ a esos dos números primos y $p_{3}$, $p_{4}$,.. $p_{n}$ al resto de los números primos factores de $n$. Sean:

$a=p_{1}-{\sqrt {n}}$

$b=p_{2}-{\sqrt {n}}$

Si $p_{1}$ y $p_{2}$ ambos son mayores que ${\sqrt {n}}$, entonces $a$ y $b$ serán positivos. Desarrollando el producto se tiene que:

${\begin{aligned}n&=p_{1}\cdot p_{2}\cdot p_{3}\cdot p_{4}\cdots \\{}&=({\sqrt {n}}+a)\cdot ({\sqrt {n}}+b)\cdot p_{3}\cdot p_{4}\cdots \\{}&=(n+(a+b){\sqrt {n}}+ab)\cdot p_{3}\cdot p_{4}\cdots \\\end{aligned}}$

Como $a>0$ y $b>0$, el desarrollo $(a+b){\sqrt {n}}+ab>0$, por lo que el producto inicial debe ser mayor que $n$:

$n<(n+(a+b){\sqrt {n}}+ab)\cdot p_{3}\cdot p_{4}\cdots$

llegándose a una contradicción, por lo tanto, a lo sumo un factor puede ser mayor que ${\sqrt {n}}$.

Lema 2

Los números primos mayores que 3 cumplen con la siguiente condición:

$p\equiv 1{\pmod {6}}$

ó

$p\equiv -1{\pmod {6}}$

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

Aplicando la iteración hasta la raíz cuadrada de n [lema 1]

algoritmo ${\text{factorización }}(n)$
  si $n=1$ ó $n=2$ ó $n=3$
     devolver $n$
  sino
     $i\leftarrow 2$
     mientras $i\leq \lfloor {\sqrt {n}}\rfloor$ hacer
        si $i\in \mathbb {P}$ y $i\mid n$
           $\{{\text{lista factores }}n\}\leftarrow i$
           $n\leftarrow n/i$
        sino
           $i\leftarrow i+1$
  $\{{\text{lista factores }}n\}\leftarrow n$
  devolver $\{{\text{lista factores }}n\}$

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 ${\text{factorización }}(n)$
  si $n=1$ ó $n=2$ ó $n=3$
     devolver $n$
  sino
     $i\leftarrow 2$
     $m\leftarrow 0$
     mientras $i\leq \lfloor {\sqrt {n}}\rfloor$ hacer
        si $i\mid n$
           $\{{\text{lista factores }}n\}\leftarrow i$
           $n\leftarrow n/i$
        sino si $i<5$
           $i\leftarrow i+1$
        sino
           $i\leftarrow i+(2\cdot (-1)^{m}{\bmod {6}})$
           $m\leftarrow (m+1){\bmod {2}}$
  $\{{\text{lista factores }}n\}\leftarrow n$
  devolver $\{{\text{lista factores }}n\}$

Complejidad computacional

En 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

$\pi ({\sqrt {n}})\approx {{\sqrt {n}} \over \left({\frac {1}{2}}\right)\ln n}$

tentativas, donde $\pi (x)$ 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

${{\sqrt {n}} \over 2}$

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

C++

#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);
}