Logaritmo discreto cuando $\alpha$ no es una raíz primitiva

Question

Cuando un número $\alpha$ es una raíz primitiva de un número primo $n$ entonces $\beta \equiv \alpha^{x} \mod n$ puede escribirse como $x = \log_\alpha(\beta) \mod n-1 $ .
Si $n$ no es un primo, la ecuación se convierte en $x = \log_\alpha(\beta) \mod \phi(n) $ .
Pero cuando $\alpha$ no es una raíz primitiva para $n$ la ecuación se convierte en $x = \log_\alpha(\beta) \mod ord_{p}(\alpha)$ ¿cierto? ¿Pero por qué?

Answer 1

La secuencia $(\alpha^k \mod n)_k$ es periódica con un período del orden multiplicativo de $\alpha$ modulo $n$ .

Así, para cada $\beta$ que puede en absoluto se escriba como $\alpha^k$ , el respectivo $k$ se determina de forma única, modulando el orden de $\alpha$ .