Discrete log modulo prime

1.7k Views Asked by At

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does

$\alpha^x \equiv 1 \mod p$

Imply that

$\alpha^a \equiv \alpha^{a \mod x} \mod p$

2

There are 2 best solutions below

0
On BEST ANSWER

It is simply being said that if $$\alpha^x \equiv 1 \pmod p,$$ and if $a = x q + r$ (where $r$ is the remainder of the division of $a$ by $x$, so that $0 \le r < x$, and one writes $r = a \mod x$), then $$\alpha^a \equiv \alpha^{x q + r} \equiv \alpha^{x q} \alpha^{r} \equiv (\alpha^{x})^{q} \alpha^{r} \equiv 1 \cdot \alpha^{r} \equiv \alpha^{r} \pmod p,$$

0
On

Let $a = kx + b$. Then $\alpha^a \equiv \alpha^{kx + b} \equiv \alpha^x \cdots \alpha^x \cdot \alpha^b \equiv 1 \cdots 1 \cdot \alpha^b \pmod p$.