Efficient Algorithms for Computing Modular Exponentiation

Computing ax mod n and axby mod n for very large x, y, and n are fundamental to the efficiency of almost all public key cryp-tosystems and digital signature schemes. Efficient algorithms for computing ax mod n and axby mod n, are presented in this talk. All algorithms are simple and only a small number of additional spaces are required to store the precomputed values. These al-gorithms are suitable for devices with low computational power and limited storage, such as smart cards. Algorithm for Computing ax mod n Input: a, x, and n Output: c = ax mod n let x = (xm−1, xm−2,..., x0)2; c = 1; for (i = m − 1; i ≥ 0; i = i − 1) { c = c2 mod n; if (xi 6 = 0) c = (c × a) mod n; print c