0

I need to solve the following equation:

$$x\equiv 17^{-1} \pmod{83}$$

Using...some "fast exponential algorithm". Well, that's the only information I have. Do you maybe know some fast exponential algorithm that could be helpful? ;)

Ayman Hourieh
  • 39,603
khernik
  • 1,369
  • 1
    $83$ is prime, and for primes $p$ you have $a^{p-1} \equiv 1 \pmod{p}$ when $p$ doesn't divide $a$, hence the modular inverse of $a$ is given by $a^{p-2}$ (modulo $p$). But here, it's faster to note that $5\cdot 17 = 85 \equiv 2 \pmod{83}$, hence $17^{-1} = 5\cdot 2^{-1}$ and that becomes $(5+83)/2 = 44$. – Daniel Fischer Aug 07 '13 at 22:08

3 Answers3

4

Exponentiation by squaring takes $O(log(n))$ time, where $n$ is the exponent.

Because $83$ is a prime number, you can use the fact that $x^{-1}\equiv x^{p-2} (mod \space p)$ where $p$ is a prime number.

ILikeMath
  • 1,514
  • More accurately, it takes $O(\log n)$ modular multiplies. For a fixed modulus that means $O(\log n)$ time, but if we let the modulus vary, then the time depends on the modulus as well! –  Aug 08 '13 at 00:00
4

As Diego mentions, because $83$ is prime, Fermat's Little Theorem yields $$ 17^{81}\equiv17^{-1}\pmod{83} $$ Since $81=1010001_{\text{two}}$, we can compute $17^{81}\pmod{83}$ by repeated squaring and multiplication: $$ \begin{align} 17^0&\equiv1&&\text{initial}&&0000000\\ 17^1&\equiv17&&\times17&&0000001&&\text{add $1$ to the exponent}\\ 17^2&\equiv40&&\text{square}&&0000010&&\text{double the exponent}\\ 17^4&\equiv23&&\text{square}&&0000100&&\text{double the exponent}\\ 17^5&\equiv59&&\times17&&0000101&&\text{add $1$ to the exponent}\\ 17^{10}&\equiv78&&\text{square}&&0001010&&\text{double the exponent}\\ 17^{20}&\equiv25&&\text{square}&&0010100&&\text{double the exponent}\\ 17^{40}&\equiv44&&\text{square}&&0101000&&\text{double the exponent}\\ 17^{80}&\equiv27&&\text{square}&&1010000&&\text{double the exponent}\\ 17^{81}&\equiv44&&\times17&&1010001&&\text{add $1$ to the exponent}\\ \end{align} $$ To check $$ 17\times44\equiv1\pmod{83} $$

robjohn
  • 345,667
1

You already have answers, let us now try another approach. All the following is done via arithmetic modulo $\;83\;$:

$$17=-66=(-11)\cdot 6$$

$$\begin{align*}6\cdot 14&=84=1\implies 6^{-1}=14\\{}\\ 11\cdot7&=77=-6\implies 11^{-1}=-6^{-1}\cdot7=-14\cdot7=-98=-15=68\end{align*}$$

So finally

$$17^{-1}=(-11)^{-1}\cdot 6^{-1}=15\cdot14=15\cdot7\cdot2=22\cdot2=44$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287