How to solve fast modular exponentiations without a calculator?

Question

I am currently preparing for my math exam and the RSA encryption system will be a part of it. But the decryption is quite hard without WolframAlpha or a calculator.

For example I have to decrypt the message $a=3$ which is already encrypted by $e$

The parameter are

• $p=13$
• $q=23$
• $N=pq=13\cdot23=299$
• $\phi(299)=264$
• encryption key $e = 151 $
• decryption key $d=7$

To decrypt $a$ you need to solve the following equation

$$3^7\equiv x \ (mod \ 299)$$

According to Wolfram Alpha the solution is 94. Which theorem can I use for this problem. Little Fermat will not work because 299 isn't a prime number. Calculators aren't allowed in the exam.

Answer 1

By heart, $3^5=243$.

Then mentally $3^6=3\cdot243=729=131\mod299$ (subtract $300$ twice and add $2$).

And $3\cdot131=393=94\mod299$.

Answer 2

One of the best method for calculating power in the Cryptography is Square and Multiply Algorithm for Modular Exponentiation. The algorithm is in the following form. For example.

Please solve your question with this nice algorithm to find how it is useful for large numbers.

Answer 3

$3$ is a relatively easy case (and $7$ is a low exponent), and the modulus is convenient close to $300$. So in this case repeatedly multiplying by $3$ is simple, given that (for example)
$3\times 243 \equiv 2\times 300 +3\times 43 \equiv 2+129\equiv 131 \bmod 299$
$3\times 131 \equiv 1\times 300 +3\times 31 \equiv 1+93\equiv 94 \bmod 299$

For the general case, since you know the component primes, you could solve those individually, first reducing the base by the modulus and the exponent by the totient as necessary, and then recombine due to the Chinese Remainder Theorem.

$\bmod 13 : \quad 3^3\equiv 1 \implies 3^7\equiv 3$
$\bmod 23 : \quad 3^3\equiv 4 \implies 3^7\equiv 48 \equiv 2$

$13j+3=23k+2 \implies 23k\equiv 10k\equiv 1 \bmod 13 \implies k\equiv 4 \bmod 13$

$\implies 3^7\equiv 23\cdot 4+2\equiv 94\bmod 299$.