O(N)-DEPTH MODULAR EXPONENTIATION CIRCUIT ALGORITHM

An O(n)-depth polynomial-size combinational circuit algorithm is propo sed for n-bit modular exponentiation, i.e., for the computation of x(y ) mod m for arbitrary integers x, y, and m represented as n-bit binary integers, within bounds 2(n-1) less than or equal to m < 2(n) and 0 l ess than or equal to x, y < m. The algorithm is a generalization of th e square-and-multiply method. The terms (x(2i) mod m)s for all is is a n element of {0, ..., n - 1} are computed in inverted right perpendicu lar n-1/inverted right perpendicular alpha log n inverted left perpend icular inverted left perpendicular parallel rounds, each of which comp utes inverted right perpendicular alpha log n inverted left perpendicu lar consecutive terms, where alpha greater than or equal to 1/log n. T he circuit implementing a round has depth O((1 + alpha) log n) and siz e O(n(2(1+alpha)) yielding a circuit for modular exponentiation of dep th [GRAPHICS] and size O(n(3+2 alpha)/alpha log n).