# How to efficiently compute $17^{23} (\mod 31)$ by hand?

I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with powers of ten ($17^2 \equiv 10 (\mod 31), (17^2)^2 \equiv 100 (\mod 31) \equiv 7 (\mod 31)$, etc.). While this makes the computation easier, I'm thinking there might be a better way to do this.

-
This question has no direct link to cryptography. It would be like tagging a question about wheels with "bicycle", "motorcycle", "car", "truck", "plane", "scooter", ... – Thomas Oct 30 '13 at 8:12

$17^2\equiv10\pmod{31}$

$17^4 \equiv 7\pmod{31}$

$17^3 \equiv 170\pmod{31}\equiv15\pmod{31}$

$17^7=17^3\times17^4\equiv15\times7\pmod{31}\equiv12\pmod{31}$

${(17^7)}^3=17^{21}\equiv23\pmod{31}$

$17^{23}=17^{21}\times17^2\equiv230\pmod{31}\equiv13\pmod{31}$

-
@FrenzYDT. Thanks for the edit. – SHOBHIT GAUTAM Oct 30 '13 at 4:34

We can do away with manipulating the powers of $17$ as follows

Observe that $17\equiv-14\pmod{31}$

$\displaystyle\implies 17^{23}\equiv(-14)^{23}\equiv-14^{23}\pmod{31}$

Now, $7^2=49\equiv18\pmod{31}, 7^3\equiv18\cdot7\equiv2\pmod{31}$

$\displaystyle\implies14^{23}=2^{23}\cdot7^{23}=2^{23}(7^3)^7\cdot7^2\equiv2^{23}\cdot2^7\cdot7^2\equiv2^{30}\cdot49\pmod{31}$

Using Fermat's Little Theorem, $2^{30}\equiv1\pmod{31}$

Alternatively, $2^5=32\equiv1\pmod{31}\implies 2^{30}=(2^5)^6\equiv1^6\pmod{31}\equiv1$

So, $\displaystyle-14^{23}\equiv-49\pmod{31}\equiv13$

-
Small mistake on the very last calculation. – Mike Oct 30 '13 at 6:53
@Mike, thanks for your observation – lab bhattacharjee Oct 30 '13 at 6:55

Modulo $31$ we have:

$$17^1 \equiv 17$$ $$17^2 \equiv 10 \text{ (because 289 mod 31 is 10)}$$ $$17^4 \equiv (10)^2 \equiv 7 \text{ (because 100 mod 31 is 7)}$$ $$17^8 \equiv (7)^2 \equiv 18 \text{ (Similar)}$$ $$17^{16} \equiv (18)^2 \equiv 14$$

And $17^{23} \equiv 17^{16} \cdot 17^4 \cdot 17^2 \cdot 17^1$.

So $17^{23} \equiv 14 \cdot 7 \cdot 10 \cdot 17$. We note that $7\cdot 10 = 70 \equiv 8 \mod 31$, so $17^{23} \equiv 14 \cdot 8 \cdot 17$, and $8\cdot 17 = 136 \equiv 12 \mod 31$, so $17^{23} \equiv 14 \cdot 12 \mod 31$, and $14 \cdot 12 = 168 \equiv 13 \mod 31$.

-

It's possible to do this in 6 multiplications. And the first couple multiplications appear to be the hardest.

$$17^2=289\equiv10\pmod{31}$$ $$17^3=17^2\times17\equiv170\equiv15\pmod{31}$$ $$17^5=17^3\times17^2\equiv150\equiv-5\pmod{31}$$ $$17^{10}=(17^5)^2\equiv25\equiv-6\pmod{31}$$ $$17^{20}=(17^{10})^2\equiv36\equiv5\pmod{31}$$ $$17^{23}=17^{20}\times17^3\equiv75\equiv13\pmod{31}$$

-

Note that $17\equiv 3/2 \pmod {31}$. We can then calculate this.

$2^5 = 1$, so $2^{23}=8$.

$3^3 = -4$, so $3^6 = 16$. We then have $3^{24} = 16^4 = 2$, and dividing through by $8$, we get $8$. Divide this by $3$ to get $31+8 = 39$, divide by 3 to get $13$.

-

Firstly sorry for my english :( It's easy to see that 〖2〗^5=〖5〗^3=1(mod 31) And 〖3〗^5=-5(mod 31). 〖17〗^23=〖48〗^23=〖3.16〗^23=〖3〗^23.〖〖2〗^4〗^23=〖3〗^23.〖2〗^92=〖3〗^23.〖〖2〗^5〗^18.4=〖3〗^23.〖1〗^18.(-27)=〖3〗^23.〖-3〗^3=-〖3〗^26=-〖〖3〗^5〗^5.3=-〖-5〗^5.3=〖5〗^3.25.3=1.25.3=75=13(mod31). Maximum we calculated 32,125,243 and get answer.

-