Abstract
An O(n)-depth polynomial-size combinational circuit algorithm is proposed for n-bit modular exponentiation, i.e., for the computation of "x/sup y/ mod m" for arbitrary integers x, y and m. Represented as n-bit binary integers, within bounds 2/sup n-1//spl les/m>2/sup n/ and 0/spl les/x,y>m. The algorithm is a generalization of the square-and-multiply method. An obvious implementation of the square-and-multiply method yields a circuit of depth O(nlogn) and size O(n/sup 3/). In the proposed algorithm, the terms x/sup 2/ mod m's for all i's /spl epsiv.