2
$\begingroup$

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. Could someone please explain the advanatge

$\endgroup$
  • 3
    $\begingroup$ Isn't "inverse exponentiation without modulo" just a logarithm? $\endgroup$ – Dan Jun 24 '13 at 1:57
8
$\begingroup$

Here's an example that might make things more clear. Suppose you want to solve $3^x=80$. You know that $3^4=81$, so the answer is a little less than 4. Using inverse exponentiation (logs) on the reals, we can find the exact answer as $3.988769\ldots$. Because the function is continuous, we can do all sorts of nice approximations like the bisection method or Taylor series to home in on the answer quickly.

Now let's try to solve $3^x\equiv 80\pmod{17}$. As it happens, $80\equiv 12\pmod{17}$, so we want to solve $3^x\equiv 12\pmod{17}$. Since we have only integers at our disposal, there's no really efficient way to figure out that the only answer is $x=13$. Knowing that $81$ is close to $80$ doesn't help at all; $4$ isn't close to $13$.

I found $13$ by trial and error. If $17$ were a much larger number, trial and error would take too long.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.