División por Prueba

Este enfoque consiste en probar todos los enteros desde 2 hasta la raíz cuadrada de n para determinar si es primo. Tiene una complejidad de O(√n) y es viable para n ≤ 1014. Una optimización común es iterar solo sobre números primos, aunque la precomputación de estos puede consumir tiempo adicional.

Test de Miller-Rabin

Es un algoritmo probabilístico para verificar primalidad. Para long long, con k iteraciones, su complejidad es O(k·(log n)3), y la probabilidad de error es menor que 4-k. Bajo la Hipótesis Generalizada de Riemann (GRH), el algoritmo puede alcanzar O((log n)5) para rangos extensos.

El principio se basa en dos condiciones: la ecuación x2 ≡ 1 (mod p) tiene solo soluciones ±1, y el Pequeño Teorema de Fermat: xp-1 ≡ 1 (mod p) para x ∈ [2, p-1]. Si un número cumple ambas condiciones para una base aleatoria, es probablemente primo. Para enteros de 32 bits, bastan las bases {2, 7, 61}, mientras que para 64 bits se pueden usar {2, 325, 9375, 28178, 450775, 9780504, 1795265022} o los primeros 12 números primos.

A continuación, un ejemplo de implementación en C++ que incluye una función auxiliar para multiplicación modular eficiente:

const long long bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

bool esPrimoMillerRabin(long long n) {
    if (n < 2 || (n % 2 == 0 && n != 2)) return false;
    if (n == 2 || n == 3) return true;
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }
    for (int i = 0; i < 7; i++) {
        long long a = bases[i] % n;
        if (a == 0) continue;
        long long x = exponenciacionModular(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool compuesto = true;
        for (int r = 1; r < s; r++) {
            x = multiplicacionModular(x, x, n);
            if (x == n - 1) {
                compuesto = false;
                break;
            }
        }
        if (compuesto) return false;
    }
    return true;
}

Método n-1

Este enfoque determinista utiliza la factorización de n-1. Si el orden multiplicativo de algún entorno a modulo n es igual a n-1, entonces n es primo. De manera más general, si n-1 = F·R, donde se conocen todos los factores primos de F, y existe un entero a tal que an-1 ≡ 1 (mod n) y gcd(a(n-1)/q - 1, n) = 1 para cada factor primo q de F, entonces n es primo, siempre que F > n1/4 + ε.

Descomposición en Factores Primos con Pollard-Rho

El algoritmo de Pollard-Rho encuentra factores no triviales de un número compuesto n de manera probabilística. Se basa en una función pseudoaleatoria, como f(x) = (x2 + c) mod n, que genera una secuencia con un ciclo en forma de ρ. Según la paradoja del cumpleaños, se espera encontrar un ciclo en O(√p) pasos, donde p es el factor primo más pequeño de n.

La detección de ciclos se implementa típicamente con el algoritmo de la tortuga y la liebre (punteros lento y rápido). Una vez que se detecta un ciclo, se calcula el gcd de n y la diferencia entre dos elementos de la secuencia para hallar un factor. El código siguiente ilustra una implementación básica:

long long pollardRho(long long n) {
    if (n % 2 == 0) return 2;
    long long x = rand() % (n - 2) + 2;
    long long y = x;
    long long c = rand() % (n - 1) + 1;
    long long d = 1;
    while (d == 1) {
        x = (multiplicacionModular(x, x, n) + c) % n;
        y = (multiplicacionModular(y, y, n) + c) % n;
        y = (multiplicacionModular(y, y, n) + c) % n;
        d = gcd(abs(x - y), n);
        if (d == n) break;
    }
    return d;
}

vector<long long=""> factorizar(long long n) {
    if (n == 1) return {};
    if (esPrimoMillerRabin(n)) return {n};
    long long factor = pollardRho(n);
    vector<long long=""> izquierda = factorizar(factor);
    vector<long long=""> derecha = factorizar(n / factor);
    izquierda.insert(izquierda.end(), derecha.begin(), derecha.end());
    return izquierda;
}
</long></long></long>

Optimizaciones clave incluyen el uso de algoritmos de multiplicación modular rápida, la detección temprana de cuadrados perfetcos, y la aplicación del test de Miller-Rabin para verifciar primalidad durante el proceso.