1. ¿Qué es una prueba de primalidad?

Una prueba de primalidad es un algoritmo que determina si un número entero n > 1 es primo (solo divisible por 1 y por sí mismo) o compuesto. En la práctica, se buscan algoritmos que ofrezcan:

• Exactitud: garantía de respuesta correcta.
• Eficiencia: tiempo y consumo de memoria adecuados, incluso para números de cientos o miles de bits.
• Escalabilidad: capacidad de ejecutarse en entornos con recursos limitados o en paralelo.

2. Algoritmos clásicos de primalidad

3. Comparativa de rendimiento (Python 3.12, CPU Intel i7‑12700K)

*Los tiempos se midieron con timeit en una única ejecución; varían según la cantidad de bases y la longitud del número.

4. Implementación práctica en Python

4.1. División trial (ejemplo didáctico)

import math
def is_prime_trial(n: int) -> bool:
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False
    limit = int(math.isqrt(n))
    for i in range(3, limit + 1, 2):
        if n % i == 0:
            return False
    return True

4.2. Miller‑Rabin (versión robusta)

import random
def _try_composite(a: int, d: int, n: int, s: int) -> bool:
    x = pow(a, d, n)
    if x == 1 or x == n - 1:
        return False
    for _ in range(s - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return False
    return True  # n es compuesto
def is_prime_miller_rabin(n: int, k: int = 5) -> bool:
    """Prueba probabilística de Miller‑Rabin.
    k = número de bases aleatorias (mayor k → menor probabilidad de error).
    """
    if n < 2:
        return False
    # Tratos rápidos para números pequeños y pares
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
    if n in small_primes:
        return True
    if any(n % p == 0 for p in small_primes):
        return False
    # Descomponer n‑1 = 2^s * d con d impar
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if _try_composite(a, d, n, s):
            return False
    return True

4.3. AKS (versión mínima, uso académico)

# Implementación compacta basada en el algoritmo de Lenstra‑Pomerance‑Wagstaff
# Nota: no recomendado para producción.
import math
def is_prime_aks(n: int) -> bool:
    if n < 2:
        return False
    # Paso 1: probar si n es una potencia perfecta
    for b in range(2, int(math.log2(n)) + 1):
        a = round(n ** (1 / b))
        if a ** b == n:
            return False
    # Paso 2: encontrar r tal que ord_r(n) > log² n
    log2n = math.log2(n)
    max_k = int(math.ceil(log2n ** 2))
    r = 2
    while True:
        if math.gcd(r, n) != 1:
            return False
        ok = True
        for k in range(1, max_k + 1):
            if pow(n, k, r) == 1:
                ok = False
                break
        if ok:
            break
        r += 1
    # Paso 3: comprobar los pequeños factores
    for a in range(2, min(r, n)):
        if (n % a) == 0:
            return False
    # Paso 4: test de polinomios (simplificado)
    # En la práctica se usa la versión de Bernstein‑Lenstra‑Pomerance‑Wagstaff.
    return True

Los dos primeros algoritmos son los que realmente se utilizan en producción. El AKS se incluye por completitud histórica.

5. Buenas prácticas y trucos de rendimiento

• Cacheo de bases pequeñas: reutiliza las primeras 12 bases primarias (2,3,5,7,11,13,17,19,23,29,31,37) para números < 2³², evitando generación aleatoria.
• Uso de pow(base, exp, mod): la función nativa de Python implementa exponenciación modular en C, garantizando velocidad y ausencia de overflow.
• Paralelismo con concurrent.futures: cuando se deben testear miles de números (p.ej., generación de primos para RSA), distribuye la carga en varios hilos o procesos.
• Tip de memoria: para números de varios megabits, emplea int.from_bytes y int.to_bytes para evitar conversiones intermedias costosas.

Ejemplo de paralelismo con ThreadPoolExecutor

from concurrent.futures import ThreadPoolExecutor, as_completed
def batch_is_prime(nums, k=5):
    results = {}
    with ThreadPoolExecutor(max_workers=8) as executor:
        future_to_num = {executor.submit(is_prime_miller_rabin, n, k): n for n in nums}
        for future in as_completed(future_to_num):
            n = future_to_num[future]
            results[n] = future.result()
    return results
# Uso
candidates = [random.getrandbits(512) | 1 for _ in range(100)]
prime_map = batch_is_prime(candidates, k=7)
print([n for n, ok in prime_map.items() if ok][:5])  # muestra los primeros 5 primos encontrados

6. Depuración y troubleshooting comunes

• Falsos positivos con Fermat: si el algoritmo devuelve True para 561, 1105, 1729, etc., es señal de que estás usando solo una base. Añade más bases o cambia a Miller‑Rabin.
• Overflow de tiempo: la división trial para números > 10⁹ es impracticable; verifica siempre la longitud del número antes de elegir el algoritmo.
• Problemas de aleatoriedad: en entornos reproducibles (tests unitarios) fija la semilla de random o pasa bases predefinidas para evitar resultados intermitentes.
• Incompatibilidad entre versiones de Python: la función math.isqrt está disponible desde Python 3.8. Para versiones anteriores usa int(n**0.5) con cuidado de redondeos.

7. Compatibilidad, rendimiento y escalabilidad

Todos los fragmentos funcionan en Python 3.8+. En entornos restringidos (p.ej., AWS Lambda con capa de Python 3.9) los algoritmos Miller‑Rabin y trial division consumen

Para generación de claves RSA de 4096 bits la práctica estándar es:

1. Generar un número aleatorio de 4096 bits.
2. Aplicar Miller‑Rabin con k=40 (error < 2⁻⁸⁰).
3. Repetir hasta obtener dos primos.

Este proceso suele completarse en ≈ 0.3 s en hardware moderno, gracias al uso de pow optimizado y a la paralelización opcional.