Why is the discrete logarithm problem in $(\mathbb{Z}_n,+)$ easy?

188 Views Asked by At

I have trouble understanding why the discrete logarithm problem in $(\mathbb{Z}_n,+)$ should be easy:

I tried it with the following example:

$$a \cdot b \equiv y \pmod {p}$$ If $a=11, b=2$ and $p=19$: $$11 \cdot 2 \equiv 3 \pmod {19}$$

If someone now has $b, y$ and $p$ how can he calculate $a$ efficiently?

$$a \cdot 2 \equiv 3 \pmod{19}$$

1

There are 1 best solutions below

0
On BEST ANSWER

Using extended Euclidean algorithm, find integers $m, n$ such that $$bm+pn = GCD(b,p) = 1$$

For instance, $$2\cdot(-9)+19\cdot1 = 1$$ which can be rewritten as $$\begin{align*} bm&\equiv1&&\pmod p\\ 2\cdot(-9)&\equiv1&&\pmod{19}\\ 2\cdot10&\equiv1&&\pmod{19}\\ \end{align*}$$

This $(m\bmod p)$ is usually called the multiplicative inverse of $b$, or $b^{-1}$. Multiply both sides of $a\cdot2 \equiv3$ by $b^{-1} = (m\bmod p)=10$, $$\begin{align*} abb^{-1}&\equiv yb^{-1}&&\pmod p\\ a\cdot1&\equiv yb^{-1}\\ a\cdot2\cdot10 &\equiv3\cdot10 &&\pmod{19}\\ a&\equiv30\equiv11 \end{align*}$$ As you can see, $b$ cannot be a multiple of $p$, unless $y = 0$.