1

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}$$

libjup
  • 313
  • 2
    modular division. –  Nov 23 '14 at 13:31
  • Thanks for your answer, @Hurkyl If I look into this topic: (for instance on SO: http://stackoverflow.com/questions/2664301/how-does-modulus-divison-work) I only find how I can calculate the remainder but not the integer which led to that remainder. Is it because I could have multiple answers leading to the same remainder? – libjup Nov 23 '14 at 13:41

1 Answers1

2

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$.

peterwhy
  • 22,256