How to Calculate "M**e mod n"

This section discusses the difficulties of calculating 'M**e mod n'. The intermediate result of 'M**e' is too big for most programming languages.

If you are interested to apply the RSA encryption yourself manually, we need to learn how to calculate "M**e mod n" and "C**d mod n", which looks simple, but difficult to carry out.

First let's see how difficult is to calculate "C**d mod n" directly even with smaller numbers like "62**65 mod 133" as we saw in the previous example.

Here is a sample Perl script to calculate "62**65 mod 133":

```# PowerModTest.pl
#

print("\n");
\$c = 62**65 % 133;
print("62**65 % 133 = ".\$c."\n");

print("\n");
\$c = 62*(((62**4%133)**4%133)**4%133) % 133;
print("62*(((62**4%133)**4%133)**4%133) % 133 = ".\$c."\n");

exit(0);
```

If you run it, you will get:

```Wrong answer:
62**65 % 133 = 21

62*(((62**4%133)**4%133)**4%133) % 133 = 6
```

So, why we are getting the wrong answer, if you use the expression "62**65 % 133" that matches the formula in encryption algorithm directly? It could be integer overflow on the intermediate result. I am not sure.

You can try this in PHP script too:

```<?php
# PowerModTest.php
#
print("\n");
\$c = pow(62,65) % 133;
print("pow(62,65) % 133 = ".\$c."\n");

print("\n");
\$c = 62*(pow(pow(pow(62,4)%133,4)%133,4)%133) % 133;
print("62*(pow(pow(pow(62,4)%133,4)%133,4)%133) % 133 = ".\$c."\n");
?>
```

Here is the PHP script output. The direct expression also gives a wrong answer.

```Wrong answer:
pow(62,65) % 133 = 0