Algoritmos eficientes para raíces primitivas donde la complejidad temporal es $\leq O(\sqrt{n})$

Question

Tengo un algoritmo para las raíces primitivas para el número de entrada $n$ que creo que es $O(n)$ actualmente. También tengo algoritmos separados para $\varphi(n)$ y $factorise(n)$ que creo que son ambos $O(\sqrt{n})$ cuyos resultados se utilizan en mi algoritmo de raíz primitiva.

La raíz primitiva alg se basa en esta entrada de Wikipedia :

En primer lugar, calcule $\varphi(n)$ . A continuación, determine los diferentes factores primos de $\varphi(n)$ , digamos que $p_1, \cdots, p_k$ . Ahora, para cada elemento m de $\mathbb{Z}_n^*$ , computa $$m^{\varphi(n)/p_i}\pmod{n}$$ para $i=1, \cdots,k$ Utilizando un algoritmo rápido de exponenciación modular, como la exponenciación por cuadratura.

Un número $m$ para los que estos $k$ resultados son todos diferentes de $1$ es una raíz primitiva.

Pregunta:

Estoy buscando ejemplos de algoritmos eficientes para las raíces primitivas donde la complejidad del tiempo es $\leq O(\sqrt{n})$ .

He encontrado muchos ejemplos de algoritmos que encuentran raíces primitivas en línea, sin embargo no tienen la complejidad de tiempo señalada.

Answer 1

Tenga cuidado con el significado de "n" en su análisis. Típicamente en este uso debe representar el tamaño de la entrada, por lo tanto esto es subexponencial ya que tenemos que factorizar.

Ver Encontrar una raíz primitiva de un número primo para una buena respuesta sobre el proceso de encontrar una raíz primitiva.

Ver Algoritmos eficientes de tiempo polinómico para el cálculo de raíces primitivas industriales para un artículo sobre un método de tiempo polinómico para las raíces primitivas probabilísticas.

Añadir: Ver Encontrar raíces primitivas de forma pseudodeterminista para otra discusión. Esto muestra las complejidades basadas en la factorización (tanto determinista como utilizando los métodos de factorización más conocidos). También señala una respuesta a las preguntas de abajo sobre hasta dónde tenemos que buscar para encontrar una raíz primitiva: asumiendo el GRH, $O(\log^6 p)$ que es polinómico en el tamaño de $p$ , por lo que el tiempo de factorización domina.

Para ello, hallar phi consiste en encontrar una potencia que es bastante rápida. Después, factorizarla, que es la mayor parte del tiempo empleado. La incógnita es buscar la primera raíz (que requiere una o más exponencias modulares cada una), y no veo inmediatamente un límite duro en el número que tendremos que buscar. En mi experiencia, la factorización domina el tiempo.

En la práctica, hay algunas formas de omitir algunos valores, pero no afectan al número asintótico.

Suponiendo que se busque en orden, podemos ver cómo la secuencia http://oeis.org/A046145 crece. Parece que encontramos uno bajo $\log^2(n)$ pero eso son sólo unos pocos miles de millones de ejemplos, e incluso si eso es correcto necesitamos más análisis para convertirlo en un término adecuado.