Tyler Clemons

Here is something that is pretty well documented, but I would like to take another look at it because it is so useful.  I ran across a little problem during my RSA project. Implementing the RSA equation is pretty simple… except for taking large numbers to a large power. Sure generating large prime values for p&q is somewhat easy, but without some level of care they can slow down any implementation. Thanks to my professors, Dr. Reed and Dr. Mertens, for introducing me to the powermod method, or what is commonly referred to as Modular Exponentiation.

The RSA decrypting and encrypting equations are pretty simple:

This can get pretty ugly using large values for “m” and “e” in the case of encrypting and “c” and “d” in the case of decrypting.  For programs written in C++, the value may extend the traditional datatype registers and cause those programs to malfunction, but in programs written in Python, it could drag on as Python extends its traditional register size.  The following function written in C++ can be used to solve this problem:

I originally received this code from Dr. Reed in Python and applied it to my RSA application and felt like making it in C++.  Templates are useful, overkill for the simple example above and just a sign of boredom from me, and helpful when applied to datatypes designed to hold large interger types that C++ can’t traditonally hold.  In Python, the size of any large integer is unlimited as long as you have enough memory, but in C++ it may be possible to exceed numbers that are larger than the built in datatypes.  For this method, powermod, to work, the user defined datatypes must overload the %, *, /= operators and create conversion functions.  But any good large integer datatype will have those   I wrote this in C++, but this should not be hard to port to other languages such as Python, Ruby, or Java.  Just change some of the syntax and leave the variables the same.