Hallar el orden de un elemento en un grupo denotado por un número primo

Question

Digamos que $N$ es primo y quiero encontrar el ${\rm ord}_N(a)$ para algunos $a \in \Bbb Z^*_N$ .

He leído que existe el algoritmo "paso de bebé, paso de gigante" (BSGS) de Shank que puede servir para este propósito en $\sqrt{N}$ tiempo.

Pero estaba pensando si podemos aprovechar el hecho de que $N$ es primo (por lo que el orden de $\Bbb Z^*_N$ es simplemente $N - 1$ ), y llegar a un algoritmo aún más rápido que el BSGS.

Mi primer pensamiento fue averiguar los factores de $N - 1$ y compruebe para cada factor si $a^N \equiv 1\pmod{N} $ y así deducir el orden de $a$ (ya que el orden de $a$ divide el orden del grupo). Pero pensé que podría ser tan bueno como BSGS en el mejor de los casos.

¿Alguien tiene alguna idea sobre esto, sobre cómo podemos aprovechar el hecho de que $N$ es primo para calcular el orden de un elemento?

P.D.: Es la primera vez que hago un proyecto de teoría de números.

Answer 1

Su método va por buen camino. Sí, teniendo los factores primos de $N-1$ si $N$ es primo, permite calcular el orden de $a$ mucho más rápido que BSGS. En concreto, tarda $O(\log^3 N)$ tiempo (mientras que BSGS tarda $O(\sqrt{N})$ ):

Supongamos que $N-1=\prod_{i} p_i^{b_i}$ es la factorización de $N-1$ en potencias primarias distintas. Obsérvese entonces que $\operatorname{ord}_N(a)|N-1$ así que tenemos que averiguar qué $p_i$ (y a qué poder) dividir $N-1$ . Por suerte para nosotros:

$a^{\frac{N-1}{p_i}}\not\equiv 1\mod N\Leftrightarrow p_i^{b_i}|\operatorname{ord}_N(a)$ .

Nótese que es importante para esta bicondicionalidad que utilicemos el exponente $\frac{N-1}{p_i}$ , pas sólo $p_i$ . Si $a^{\frac{N-1}{p_i}}\equiv 1\mod N$ entonces (inclusive) hasta $n=b_i$ podemos calcular sucesivamente:

$a^{\frac{N-1}{p_i^n}}\not\equiv 1\mod N, \text{ and } a^{\frac{N-1}{p_i^{n-1}}}\equiv 1\mod N \Leftrightarrow p_i^{b_i-n+1}|\operatorname{ord}_N(a)$ .

Puesto que hay como máximo $O(\log N)$ (número de factores primos de $N-1$ ), y cada comprobación es modular (y binario ) exponenciación en $\mathbb{Z}/N\mathbb{Z}$ ( $O(\log^2 N)$ tiempo), la complejidad total es $O(\log^3 N)$ .

Advertencia: Factorización real $N-1$ Sin embargo, la complejidad temporal $O(e^{(1+o(1))\sqrt{\ln(N)\ln\ln(N)}})$ que sigue siendo mejor que $O(\sqrt{N})$ pero mucho peor que $O(\log ^3 N)$ en $O(e^{(1+o(1))\sqrt{\ln(N)\ln\ln(N)}})$ sea el tiempo total de ejecución. Sin embargo, si ya conoce la factorización de $N-1$ entonces se ejecuta en $O(\log^3 N)$ tiempo.

---

Edición: para responder directamente a su otra pregunta, estamos aprovechando $N$ ser primo precisamente a través de algo que ya has mencionado: sabemos que el orden del grupo es $N-1$ que sirve como punto de partida para encontrar el orden de $a$ como se ve arriba. Si ya conocemos la factorización de $N-1$ no tenemos que perder el tiempo factorizando $N$ para encontrar el orden de los grupos.

Edita 2 por diversión: El algoritmo cuántico de Shor para encontrar el periodo puede encontrar el orden de cualquier elemento (independientemente de la factorización conocida de $N-1$ ) en $O(\log^3 N)$ pasos en un ordenador cuántico

Answer 2

Creo que se llama la forma fuerte, pero por poco Fermat, $a^p\equiv a\pmod p$ por lo que no estamos, ya que $N=p$ , va a tener $a^N\equiv 1\pmod N$ a menos que $a=1$ .

Tal vez sólo un error tipográfico de su parte, usted podría haber querido decir $a^{\color{blue}{m}}\equiv 1\pmod N$ para cada $m$ tal que $m\mid N-1$ .

Recuerda que estás hablando del orden de los elementos en $\Bbb Z_p^*$ .