Calculadora de raíz primitiva

Una raíz primitiva módulo un primo p es un generador del grupo multiplicativo de residuos distintos de cero módulo p. En términos simples, algún entero g entre 1 y p menos uno tiene la propiedad de que sus potencias sucesivas g, g al cuadrado, g al cubo, y así sucesivamente, terminan alcanzando cada clase de residuo coprima con p antes de repetirse. Ese g es un generador de (Z/pZ)*, y el g positivo más pequeño con esa propiedad es la respuesta clásica de teoría de números que buscan estudiantes, criptógrafos y resolutores de concursos. Esta calculadora toma un módulo primo p, verifica que p es primo, factoriza p menos uno, y devuelve la raíz primitiva mínima junto con el orden del grupo y la factorización en potencias primas de p menos uno. El recorrido es totalmente determinista: Miller-Rabin con conjuntos de testigos fijos, factorización de prueba, y exponenciación modular sin red, sin aleatoriedad y sin dependencia de la fecha.

Qué es una raíz primitiva y qué contiene la respuesta

Para un módulo primo p, el conjunto de residuos 1, 2, …, p menos uno forma un grupo multiplicativo cíclico de orden p menos uno. Un entero g es una raíz primitiva módulo p cuando el orden de g en ese grupo es exactamente p menos uno: las potencias g elevado a k para k desde 0 hasta p menos dos son todas distintas módulo p y agotan cada residuo distinto de cero.

No todo entero es un generador; por ejemplo, módulo 7 las potencias de 2 ciclan a través de solo tres valores antes de repetirse, así que 2 no es una raíz primitiva, mientras que 3 genera las seis unidades y es la más pequeña. No hay una conjetura probabilística presentada como raíz ni una vía de respaldo silenciosa para módulos compuestos, porque una raíz primitiva en el sentido clásico se define para primos (y algunas familias compuestas especiales que esta página no cubre).

Si necesita los factores de un entero arbitrario en lugar de un generador módulo p, use en su lugar una capacidad de factorización; esta página responde solo a la pregunta del generador más pequeño módulo un primo.

Cómo se comprueba el primo y cómo se encuentra la raíz más pequeña

Se permiten signos más iniciales opcionales; los espacios incrustados, los prefijos hexadecimales y la notación exponencial se rechazan con un mensaje claro para que una celda mal escrita no se convierta en un generador incorrecto. Tras el análisis, el motor ejecuta una prueba de primalidad Miller-Rabin determinista con conjuntos de testigos demostrados suficientes para todo entero de a lo sumo quince dígitos decimales.

Cuando p es primo, el motor factoriza p menos uno mediante división de prueba por rueda, recopila los factores primos distintos q de ese orden, y busca g igual a 2, 3, 4, … el primer candidato tal que g elevado a (p menos uno) dividido entre q no sea congruente con 1 módulo p para cada uno de esos q. Ese criterio clásico es necesario y suficiente para que g tenga orden p menos uno.

El caso especial p igual a 2 devuelve la raíz primitiva 1, la única unidad de ese grupo.

Dónde encajan las raíces primitivas más pequeñas en el estudio, la criptografía y el código

Los estudiantes se encuentran con las raíces primitivas al aprender grupos cíclicos, logaritmos discretos, y la estructura de los cuerpos finitos de orden primo. Las hojas de trabajo a menudo piden el generador mínimo módulo un primo pequeño; esta página devuelve esa respuesta con la factorización de apoyo de p menos uno para que pueda verificar las pruebas de orden a mano.

Los problemas de concurso y los enunciados de katas de programación con frecuencia requieren la raíz primitiva más pequeña como subrutina para construir polinomios primitivos, indexar tablas de logaritmo discreto, o sembrar demostraciones de teoría de números. Los docentes pueden pregenerar claves de respuesta sin confiar en widgets web opacos.