How to solve fast modular exponentiations without a calculator?

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.

• Can you solve it quickly modulo $13$ and $23$? Do you know the Chinese Remainder Theorem? PS You've asked lots of questions on this site, which is good. You should accept answers that help you. – Ethan Bolker Aug 5 '17 at 12:26
• might try Euler's theorem. – user451844 Aug 5 '17 at 12:31

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$.

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.

• For computation by hand, it is unsure that this algorithm can beat iterative multiplies, because the numbers obtained by squaring can be larger (up to $298^2=88804$ vs. $3\cdot298=894$). – Yves Daoust Aug 5 '17 at 14:07
• Maybe in this question you right but in the general specially in RSA method, the Square and Multiply Algorithm can solved modular exponentiation easily. – Amin235 Aug 5 '17 at 14:42

$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$.