Método práctico de cálculo de raíces primitivas módulo primo

Question

¿Cómo se calculan los generadores de un conjunto (primo grande) en programas populares como pgp y bibliotecas como bouncycastle de java? no me los imagino simplemente revolviendo cada valor entre 2 y p hasta que salga algo, pero no parece haber ninguna descripción de algún otro método que los programadores utilicen para encontrarlos.

incluso si prueban todos los números entre 2 y p, ¿cuál es la prueba? ¿se está comprobando si el conjunto generado es {1,2,...p-1} que parece que ocuparía demasiada memoria.

¿alguien me puede dar algún pseudocódigo sobre cómo hacerlo? estoy tratando de algo que probablemente increíblemente ingenuo y el programa está utilizando 1,5gb ram después de unos segundos, con sólo un valor de 32 bits

Answer 1

El algoritmo básico para comprobar si $a$ es una raíz primitiva mod $p$ es factorizar $p-1$ identificar todos los factores primos $q \mid p-1$ (hay como máximo $(1+o(1))\log p$ tales factores). Si $a$ no es primitivo, entonces su orden multiplicativo debe dividir correctamente a $p-1$ y por lo tanto debe dividir algunos $(p-1)/q$ .

Por lo tanto, sólo tiene que comprobar si $a^{(p-1)/q} \not\equiv 1 \pmod p$ para todos los primos $q \mid p-1$ . Si es así $a$ es primitivo. No hay absolutamente ninguna necesidad de utilizar gigabytes de RAM para almacenar todas las potencias de $a$ .

Como señala Qiaochu Yuan, no hay que esperar comprobar muchos valores de $a$ antes de encontrar uno que sea primitivo. De hecho, no es necesario basarse en GRH si la muestra es puramente aleatoria: hay $\phi(p-1)$ raíces primitivas entre $2$ y $p-1$ por lo que se puede esperar encontrar uno al azar después de aproximadamente $p/\phi(p-1)$ lo intenta. Este número suele ser muy pequeño y no puede ser mucho mayor que $1.78 \log \log p$ incluso para valores excepcionales de $p$ . Por lo tanto, en la práctica, nunca llegará al $O(\log^6 p)$ antes de encontrar una raíz primitiva.

Answer 2

Como otros han mencionado, no conocemos métodos eficientes para encontrar generadores de $(ℤ/pℤ)^∗$ sin conocer la factorización de $p-1$ . Sin embargo, se puede generar eficientemente un número aleatorio factorizado $n$ a continuación, compruebe si $n+1$ es primo, y luego calcular las raíces primitivas módulo $n+1$ . Véase Victor Shoup -- Introducción computacional a la teoría de números y al álgebra capítulo 11. (En realidad necesitas las secciones 11.1 sobre la búsqueda de generadores, 9.6 para generar números aleatorios factorizados y 9.5, para generar una secuencia aleatoria no creciente).

Answer 3

Este es, como usted sabe, un problema muy difícil. Estrictamente hablando, no es necesario comprobar todo el conjunto, ya que se sabe si $2$ no es una raíz primitiva, entonces $4$ tampoco lo es y así sucesivamente. Así que puede buscar entre los "sospechosos habituales" (es decir $2,3,5,$ etc) y utilizar exponenciación binaria para reducir la complejidad temporal

William Stein tiene un página web sobre el problema de encontrar generadores para $(\mathbb{Z}/p\mathbb{Z})^*$ . Sin embargo, el método dado no es muy útil ya que requiere conocer la factorización de $p-1$ que, actualmente, es un problema en $NP$ .

Hay algunos algoritmos probabilísticos de poltiempo para encontrar raíces primitivas que mucho más rápido que los métodos deterministas y mediante pruebas repetidas se puede reducir la posibilidad de error. También suponiendo la Hipótesis de Riemann Extendida, hay son algoritmos politemporales deterministas .

Sin embargo, en general no se conoce ningún algoritmo determinista eficiente (rápido).

Answer 4

No sé cuál es el algoritmo exacto, pero quizá tengan rutinas y subrutinas con las que trabajar. Por ejemplo, hay que descartar claramente los residuos cuadráticos, así que nos quedamos sólo con la mitad de los elementos en $\,\left(\mathbb{F}_p\right)^*\,$ .

A continuación, quizá comprueben si $\,\displaystyle{a^{\frac{p-1}{2}}}=-1\,$ de los elementos restantes, ya que las raíces primitivas surgirán de estos elementos...