[Math] Calculating $1819^{13} \pmod{2537}$ using Fermat’s little theorem

Question

Can anyone make me understand how to calculate $1819^{13} \pmod{2537}$ using Fermat's little theorem? Here $p=2537$ and $p-1=2537-1=2536$.

I am unable to understand how to express $1819^{13}$ in terms of $1819^{2536}$.

Answer 1

If you check description of RSA in wikipedia you will find that for the modulus $n = 2537 = 43\cdot 59$ we first calculate $\phi(n) = 42\cdot 58 = 2436$. Now from the problem you have mentioned it seems that $e = 13$ is encryption key and $m = 1819$ is the message.

The modular exponentiation is simple by squaring and we can write

$\displaystyle \begin{aligned}1819^{13}\pmod{2537} &= 1819^{8 + 4 + 1}\pmod{2537}\\ &= 1819^{8}\cdot 1819^{4}\cdot 1819\pmod{2537}\\ &= 1819^{2^{3}}\cdot 1819^{2^{2}}\cdot 1819\pmod{2537}\\ &= 513^{2^{2}}\cdot 513^{2}\cdot 1819\pmod{2537}\\ &= 1858^{2}\cdot 1858\cdot 1819\pmod{2537}\\ &= 1844 \cdot 1858 \cdot 1819 \pmod{2537}\\ &= 2081 \pmod{2537}\end{aligned}$

You also need to find the decryption key $d$ such that $ed = 1 \pmod{\phi(n)}$. This requires you to find HCF of $e = 13$ and $\phi(n) = 2436$ which is clearly $1$, but we need to express this HCF in form $13x + 2436y = 1$ and then $x$ will be your decryption key $d$. For this we proceed as below.

$\displaystyle \begin{aligned}1 &= 3 - 2\\ &= 3 - (5 - 3)\\ &= 2 \cdot 3 - 1\cdot 5\\ &= 2\cdot(13 - 2\cdot 5) - 1\cdot 5\\ &= 2\cdot 13 - 5\cdot 5\\ &= 2\cdot 13 - 5\cdot(2436 - 187 \cdot 13)\\ &= 937\cdot 13 - 5\cdot 2436\end{aligned}$

so that $d = 937$. It will take time (again by modular exponentiation) to verify that from the ciphertext $c = 2081$ we can get $m = 1819$ by calculating $c^{d}\pmod{2537} = 2081^{937}\pmod{2537}$