Comprobador de primalidad

El verificador de primalidad le dice si un número entero es primo y, a diferencia de la mayoría de las calculadoras en línea, le muestra el algoritmo real que lo demostró, no una tabla de búsqueda en caché. Escriba cualquier número entero, positivo o negativo, pequeño o enorme, y la herramienta decidirá qué algoritmo real ejecutar en función de su tamaño.

Para números menores de 10¹² (un billón), ejecuta una división de prueba genuina: comenzando en 2, prueba cada candidato entero hasta el piso de √n como posible divisor, deteniéndose en el momento en que uno divide uniformemente (compuesto) o confirmando que ninguno lo hace una vez que se han verificado todos los candidatos hasta √n (primo). Para recuentos de candidatos grandes, el seguimiento que se muestra se limita a los primeros ~18 probados más el último, con una nota honesta sobre cuántos se omitieron en la pantalla, pero el código aún verifica cada candidato, ninguno se omite en el cálculo.

Para números iguales o superiores a ese umbral (el rango de tamaño utilizado en criptografía), la división de la prueba tomaría demasiado tiempo, por lo que la herramienta cambia a la prueba de primalidad de Miller-Rabin con un conjunto fijo y determinista de 13 testigos principales (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Este conjunto de testigos exactos es un resultado bien conocido: no tiene falsos positivos para ningún n inferior a 3.317.044.064.679.887.385.961.981 (aproximadamente 3,3 × 10²⁴), un límite establecido mediante verificación computacional (ver Sorenson & Webster, 2015, y la tabla de testigos deterministas ampliamente reproducida a la que pertenece). Por encima de ese límite, todavía se ejecuta la misma prueba, pero la herramienta le dice honestamente que la garantía se convierte en una certeza probabilística extremadamente fuerte en lugar de una certeza matemática.

La traza de Miller-Rabin escribe n − 1 = 2ˢ × d con d impar, luego recorre la exponenciación modular real de BigInt (elevar al cuadrado y multiplicar, reduciendo el módulo n en cada paso para que los números nunca exploten) poco a poco para el primer testigo, e informa el veredicto de cada testigo, incluido qué testigo demuestra la composición si el número resulta no ser primo. Todo se ejecuta localmente en su navegador: ningún servidor, ninguna API externa, ningún dato sale de su dispositivo.