Calculadora de prueba de primalidad básica rápida y precisa

Calculadora de prueba de primalidad básica: herramienta rápida para verificar si un número es primo con precisión alta.

Este artículo describe algoritmos, fórmulas, pruebas, tablas, ejemplos aplicados y guías de implementación paso a paso.

Calculadora de prueba de primalidad (rápida y precisa)

Determina si un número entero es primo usando métodos prácticos (trial division y Miller‑Rabin). Útil en criptografía ligera, verificación matemática y validación de claves públicas.

Ingrese un entero positivo (sin signos, sin separadores). Máx 500 dígitos. Para números grandes se usará Miller‑Rabin.
Auto elige el método según tamaño. Elija MR determinista solo si conoce que n < 2^64.
Número de rondas k: mayor k reduce la probabilidad de falso positivo (error ≤ 4⁻ᵏ).
Dejar en Auto para comportamiento estándar. Si especifica bases, se usarán como testigos concretos.
Ingrese los datos para ver el resultado.
Reporte errores o sugerencias: Enviar informe
Fórmulas usadas
  • Trial division: comprobar divisores p hasta floor(√n). Si existe p | n y 1 < p < n → compuesto.
  • Miller‑Rabin: escribir n−1 = 2^s · d (d impar). Para una base a, calcular x = a^d mod n. Si x = 1 o x = n−1, pasar. Repetir s−1 veces: x = x^2 mod n; si x = n−1 → pasa. Si ninguna pasa → compuesto.
  • Probabilidad de error (Miller‑Rabin): ≤ 4⁻ᵏ para k rondas independientes.
Variables:
n = número a probar.
a = testigo/base.
s,d = descomposición de n−1 en potencias de 2.
k = número de rondas (fiabilidad).
Valores típicos / referencias
ConceptoValor típico / referencia
Pruebas deterministas (32‑bit)Bases {2,7,61} garantizan exactitud para n < 2,152,302,898,747
Pruebas deterministas (64‑bit)Bases {2,3,5,7,11,13,17} suficientes para n < 2^64
Miller‑Rabin probabilísticok = 5 ≈ error ≤ 1/1024; k = 10 ≈ error ≤ 1/1,048,576
Trial division prácticoÚtil para n ≤ 10⁷; para valores mayores MR es preferible

Preguntas frecuentes

¿Cuándo usar Miller‑Rabin y cuándo trial division?
Trial division es exacta pero solo práctica para n pequeños (≤10⁷). Miller‑Rabin es mucho más rápido para enteros grandes; es probabilística salvo conjuntos deterministas de bases para rangos acotados.
¿Qué significa "probable primo"?
Significa que el número pasó las pruebas MR para k bases; la probabilidad de error es ≤ 4⁻ᵏ. Aumentar k reduce el riesgo de falsos primos.
¿Puedo verificar números mayores que 2^64?
Sí, usando Miller‑Rabin probabilístico con k adecuado. Para pruebas deterministas en tamaños arbitrarios se requieren algoritmos más complejos (p. ej. AKS o pruebas con factorización complementaria).

Visión general técnica: propósito y aplicaciones

Una calculadora de prueba de primalidad debe identificar si un entero positivo mayor que 1 es primo con eficiencia y seguridad. Sus aplicaciones incluyen criptografía, teoría de números, pruebas matemáticas, generación de claves y sistemas distribuidos.

Los requisitos críticos son tiempo de ejecución eficiente, consumo moderado de memoria y una tasa de error controlada cuando se emplean pruebas probabilísticas.

Calculadora de prueba de primalidad básica rápida y precisa para números grandes
Calculadora de prueba de primalidad básica rápida y precisa para números grandes

Principios matemáticos y límites fundamentales

Definición: un número n>1 es primo si solo tiene divisores 1 y n. La búsqueda de divisores hasta sqrt(n) es la prueba determinística clásica.

Complejidad de la verificación determinística por fuerza bruta: O(sqrt(n)) operaciones aritméticas, inaceptable para n grandes (más de 64 bits).

Algoritmos relevantes y comparativa técnica

  • Criba de Eratóstenes: eficiente para generar primos hasta N con complejidad O(N log log N).
  • Prueba de división hasta sqrt(n): determinística, adecuada para n pequeños (≤64 bits en implementaciones rápidas).
  • Pruebas probabilísticas: Miller–Rabin (rápida, configurable en iteraciones), Fermat (sencilla, susceptible a pseudoprimos), Solovay–Strassen (base en símbolos de Jacobi).
  • Pruebas determinísticas avanzadas: AKS (polinómica, compleja en práctica), versiones determinísticas de Miller–Rabin con bases fijas para enteros menores a ciertos límites.

Selección práctica: para cálculo rápido y preciso se usa Miller–Rabin con conjunto de bases determinístico según el rango de n o división hasta sqrt(n) para n pequeños.

Especificaciones funcionales de la calculadora

Entradas

  • n: entero positivo mayor que 1 a evaluar.
  • modo: "determinista" o "probabilístico".
  • k: número de iteraciones para pruebas probabilísticas (por ejemplo, Miller–Rabin).
  • tolerancia_de_error: probabilidad máxima admitida de error (ej. 2^-80).

Salida esperada: booleano is_prime y metadatos: tiempo de ejecución, número de bases usadas, evidencia de factor si existe.

Tablas de valores comunes

Las tablas siguientes recogen límites prácticos, selección de bases y tiempos de referencia en hardware típico.

La tabla es responsiva y se adapta a tamaños de pantalla: columnas claras con valores de referencia para implementadores.

Rango de n
Método recomendado
Bases (Miller–Rabin determinista)
Complejidad estimada
n < 2^16 (~65k)
Criba o división hasta sqrt(n)
N/A
O(sqrt(n)) o O(N log log N)
n < 2^32 (~4.3e9)
División hasta sqrt(n) con optimizaciones
N/A
O(sqrt(n)/log n) con cribas parciales
n < 3,474,749,660,383
Miller–Rabin determinista
bases {2,7,61}
O(k log^3 n)
n < 2^64
Miller–Rabin determinista
bases {2,3,5,7,11,13,17}
O(k log^3 n)
n grande (≥1024 bits)
Miller–Rabin probabilístico con k≥20
bases aleatorias
O(k log^3 n)

Tabla de tiempo de referencia por método (valores estimados en CPU moderna 3GHz, un solo hilo).

Tamaño de n (bits)
División hasta sqrt
Miller–Rabin (k=5)
Criba parcial
32
<0.1 ms
<0.1 ms
<0.1 ms
64
0.1–1 ms
<0.5 ms
0.2–1 ms
256
100 ms – varios s
1–10 ms (k=5)
5–50 ms
2048
no práctico
10–200 ms (k=5)
50 ms – 1 s

Fórmulas y relaciones fundamentales

Las fórmulas a continuación describen las transformaciones aritméticas necesarias para las pruebas utilizadas por la calculadora.

Cada fórmula va acompañada de su explicación y valores típicos por variable para implementación.

1) Factorización hasta la raíz

Procedimiento básico: probar divisores d desde 2 hasta floor(sqrt(n)).

d ∈ {2, 3, ..., ⌊√n⌋}
si n mod d = 0 → compuesto, factor = d
si ningún d divide n → primo

Variables: n (entero a evaluar), d (divisor candidato). Valores típicos: n hasta 2^32 para ser práctico; sqrt(n) calculado por método de punto flotante o aritmética entera.

2) Exponentiación modular (módulo n)

Necesaria para Miller–Rabin y pruebas basadas en Fermat. Se usa exponenciación por cuadrados.

modexp(a, e, n) = a^e mod n
implementación: resultado = 1; base = a mod n;
mientras e>0: si e%2==1 → resultado=(resultado*base) mod n; base=(base*base) mod n; e=floor(e/2)

Variables: a (base), e (exponente), n (módulo). Valores típicos: a en [2,n-2], e necesita hasta n-1 en Fermat; en Miller–Rabin e = d (odd) y potencias de 2.

3) Descomposición de n-1 como 2^s * d

Para Miller–Rabin se escribe n-1 = 2^s * d con d impar.

sea n impar > 2
s = 0; d = n-1;
mientras d%2==0: d /= 2; s += 1

Variables: n, s (número de factores 2), d (impar). Valores típicos: para n~2048 bits, s suele ser pequeño (depende de n).

4) Prueba de Miller–Rabin (una base a)

Paso central: comprobar si a es testigo de compositividad para n.

x = modexp(a, d, n)
si x == 1 or x == n-1 → n posiblemente primo para esta base
para r en 1..s-1: x = (x*x) mod n; si x == n-1 → pasar a siguiente base
si ningún x == n-1 → compuesto

Variables: a (base candidata), d y s de la descomposición, x variable de iteración. Valores típicos: elegir a de conjunto fijo o aleatorio; k iteraciones determinan probabilidad de error ≤ 4^-k.

5) Límite de error para Miller–Rabin

Probabilidad de que un test con base aleatoria clasifique un compuesto como probable primo ≤ 1/4 por iteración en el peor caso.

P_error(k) ≤ (1/4)^k
Para tolerancia t: elegir k ≥ ceil(-log_4(t))

Valores típicos: para t=2^-80, k ≈ 40. Para uso criptográfico k entre 20 y 64 según amenaza y optimizaciones.

Implementación: estructura modular de la calculadora

  1. Normalización de entrada: validar n entero >1, eliminar paridad simple.
  2. Detección rápida: comprobar divisibilidad por primos pequeños (2,3,5,7,11,13,... hasta un límite como 1000).
  3. Si n ≤ límite_determinista: aplicar prueba determinista adecuada (división hasta sqrt o Miller–Rabin con bases fijas).
  4. Si n grande: aplicar Miller–Rabin probabilístico con k iteraciones y registro de bases.
  5. Opcional: para factorización complementar, aplicar métodos como Pollard Rho si se desea obtener factores.

Optimización: usar tablas de primos pequeños para cribado, operaciones en aritmética entera de múltiples palabras para n>64 bits y técnicas de FFT para multiplicación si aplica.

Casos del mundo real con desarrollo completo

Caso 1: Verificación de primalidad para n = 3,215,031,751

Contexto: validar si n es primo para uso en una prueba matemática; n < 2^32 por lo que métodos deterministas son prácticos.

Paso 1: cribado por primos pequeños. Probar divisibilidad con primos hasta 100: n mod 2,3,5,... ninguno divide n.

Paso 2: dividir hasta sqrt(n). sqrt(3,215,031,751) ≈ 56,692. Probar divisores impares hasta ese límite. Sin divisores → primo. Optimización: probar solo primos hasta 56,692.

Resultado: tras pruebas con primos hasta 56,692 no se encontró divisor → n es primo. Tiempo aproximado: segundos en CPU moderna.

Caso 2: Prueba para n = 1,230,045,456,793 (13 cifras, mayor que 32 bits)

Contexto: verificación rápida para clave temporal, n impar y grande. Aplicamos Miller–Rabin probabilístico con k=10 para tolerancia baja de error.

Paso 1: cribado por primos pequeños hasta 1000 → si un primo divide n, reportar compuesto y factor.

Paso 2: descomponer n-1 = 2^s * d. Calcular s y d por división sucesiva por 2.

Paso 3: ejecutar 10 iteraciones de Miller–Rabin con bases seleccionadas pseudoaleatorias en [2, n-2]. Si alguna base detecta compositividad → compuesto. Si todas pasan → probable primo con P_error ≤ 4^-10 ≈ 9.5e-7.

Salida detallada: lista de bases probadas, valores intermedios x por iteración, tiempo por iteración. Si se requiere certeza absoluta, ejecutar prueba determinista con bases fijas conocidas para rango.

Determinismo por rangos: tablas de bases clásicas

Para garantizar determinismo hasta ciertos límites, existe un conjunto mínimo de bases para Miller–Rabin que hace la prueba determinista.

Ejemplos: {2,7,61} para n < 3,474,749,660,383; {2,3,5,7,11,13,17} para n < 2^64. Implementar según el rango objetivo.

Accesibilidad y usabilidad de la herramienta

  • Interfaz: entrada simple de n, selección de modo, k opcional y botón "evaluar".
  • Salida: is_prime booleano, explicación breve, tiempo y registros de iteraciones desplegables para auditoría.
  • Accesibilidad: etiquetas ARIA, tablas responsivas, texto con contraste alto y controles de teclado.

Documentación adicional debe incluir ejemplos reproducibles y tests unitarios para validar implementación en diferentes entornos.

Consideraciones de seguridad y criptográficas

Para generación de claves criptográficas, se exige probabilidad de error extremadamente baja y, preferiblemente, pruebas deterministas dentro del rango o k suficientemente alto.

Generación segura de bases aleatorias: usar RNG criptográfico; evitar fuentes predecibles que podrían inducir ataques dirigidos.

Extensiones: obtención de factores y pruebas compuestas

Si la prueba indica "compuesto", la calculadora puede intentar una factorización parcial con Pollard Rho para obtener factores pequeños a moderados.

Pollard Rho: método probabilístico eficiente para hallar factores no triviales; útil cuando se requiere comprobación adicional de compositividad.

Referencias, recursos y estándares

Para implementación rigurosa consultar literatura y estándares:

  • Richard Crandall, Carl Pomerance — "Prime Numbers: A Computational Perspective" (referencia técnica).
  • G. Miller — "Riemann's Hypothesis and Tests for Primality" (sobre bases y método).
  • J. M. Pollard — trabajos sobre Pollard Rho.
  • RFC 6930 y documentación de NIST sobre generación de primos y prácticas criptográficas (NIST SP 800-89, SP 800-57 para generación de claves y entropía).
  • OEIS y MathWorld para propiedades numéricas y ejemplos de pseudoprimos.

Enlaces externos de autoridad: publicaciones de NIST, artículos revisados por pares en Journal of Cryptology y capítulos de libros especializados en teoría de números.

Pruebas unitarias y verificación

  1. Cubrir casos bordes: n=2, n=3, n par mayor que 2, n cuadrado perfecto, números de Carmichael.
  2. Verificar que para conjuntos deterministas de bases se obtenga certeza dentro del rango especificado.
  3. Medir tasa de falsos positivos/negativos con conjuntos de prueba conocidos.

Registrar métricas de rendimiento: tiempo medio por n para distintos tamaños y distribución de números primos/compuestos.

Optimización avanzada para implementaciones de alto rendimiento

  • Usar aritmética de múltiples palabras (bigint) con algoritmos de multiplicación optimizados (Karatsuba, Toom–Cook, FFT) para n grandes.
  • Parallelizar pruebas de bases independientes en entornos multi-hilo.
  • Usar tablas de primos en memoria y técnica de wheel factorization para reducir candidatos de división.
  • Implementar exponenciación modular con reducción rápida (Montgomery) para aceleración sin reducción costo de división.

Estas optimizaciones reducen tiempo por iteración en Miller–Rabin y permiten evaluar primos de cientos o miles de bits en tiempos prácticos.

Buenas prácticas de implementación y mantenimiento

  • Versionar algoritmos y bibliotecas de aritmética de precisión arbitraria.
  • Proveer pruebas reproducibles y datasets con números primos y compuestos para regresión.
  • Mantener parámetros predeterminados conservadores (k, cribado) para mejorar seguridad.
  • Documentar riesgos conocidos (pseudoprimos de Fermat, números de Carmichael) y cómo se mitigan.

Auditar código criptográfico por terceros y aplicar pruebas FIPS/NIST según uso sensible.

Apéndice: ejemplos numéricos detallados

Desarrollo detallado Caso A: Miller–Rabin paso a paso para n = 2,047

n = 2047. Paso 1: n-1 = 2046 = 2 * 1023 → s=1, d=1023.

Elegimos base a=2. Calcular x = 2^1023 mod 2047 usando exponenciación por cuadrados.

Si x == 1 o x == 2046, pasa; de lo contrario, realizar bucle r en 1..s-1 (aquí s-1=0, no hay iteraciones) y concluir. Cálculo muestra x = 1? En este caso x = 1? (Resultado real: 2^1023 mod 2047 = 1) → base no detecta compositividad.

Probar con base a=3: calcular x = 3^1023 mod 2047 → se obtiene x ≠ 1 y ≠ 2046; sin iteraciones disponibles → detecta compuesto. Por tanto 2047 es compuesto (2047 = 23 * 89).

Desarrollo detallado Caso B: Divisores hasta sqrt para n = 100,003

n = 100,003. sqrt(n) ≈ 316.228. Probar primos hasta 316: 2,3,5,7,11,... 313.

Ningún primo ≤313 divide 100,003 → n es primo. Tiempo: probar ~65 primos; cálculo instantáneo en CPU moderna.

Conclusiones técnicas y recomendaciones operativas

Para implementaciones prácticas se recomienda cribado por primos pequeños seguido de Miller–Rabin con un número de iteraciones ajustado a la tolerancia de error y al tamaño de n.

Para aplicaciones criptográficas use RNGs criptográficos, bancos de pruebas y, si aplica, bases deterministas según rango para garantía adicional.