Discrete logarithm when $\alpha$ is not a primitve root

146 Views Asked by At

When a number $\alpha$ is a primitive root for a prime number $n$ then $\beta \equiv \alpha^{x} \mod n$ can be written as $x = \log_\alpha(\beta) \mod n-1 $.
If $n$ is not a prime, the equation becomes $x = \log_\alpha(\beta) \mod \phi(n) $.
But when $\alpha$ is not a primitive root for $n$, the equation becomes $x = \log_\alpha(\beta) \mod ord_{p}(\alpha)$, rigth? But why?

1

There are 1 best solutions below

0
On BEST ANSWER

The sequence $(\alpha^k \mod n)_k$ is periodic with period the multiplicative order of $\alpha$ modulo $n$.

Thus, for each $\beta$ that can at all be written as $\alpha^k$, the respective $k$ is uniquely determined modulo the order of $\alpha$.