Cryptography may be utilized to protect data from unwanted access, for authentication, to generate digital signatures, etc. Current cryptographic techniques rely on intensive mathematical operations. For example, a number of public key cryptographic standards (e.g., RSA (Rivest-Shamir-Adleman), Diffie-Hellman, ElGamal, DSA (Digital Signature Algorithm), etc.) are based, at least in part, on modular exponentiation of large numbers. A binary representation of the large numbers may include on the order of thousands, e.g., 1024, 2048, 4096, 8192, etc., or more bits. Modular exponentiation involves raising a first number (base) to some power (exponent) and reducing it with respect to a third number (modulus). A reduction (i.e., modular reduction) result corresponds to a remainder left when the base raised to the exponent is divided by the modulus. Mathematically, modular exponentiation can be expressed as ge mod M where g is the base, e is the exponent and M is the modulus. Computationally, modular exponentiation includes squaring followed by a reduction and/or multiplying followed by a reduction. Such operations are performed repeatedly in cryptography. Thus, even a relatively small performance increase in a single modular reduction operation can have a significant effect over the relatively large number of modular reduction operations associated with modular exponentiation of large numbers.
Although the following Detailed Description will proceed with reference being made to illustrative embodiments, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art.