O(n)-depth modular exponentiation circuit algorithm

doi:10.1109/12.600828

O(n)-depth modular exponentiation circuit algorithm

1997-06-01

3

PRE

AI

DOI：10.1109/12.600828

Original

Original request for help

Save

Abstract

En 中文

An O(n)-depth polynomial-size combinational circuit algorithm is proposed 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 less than or equal to x, y < m. The algorithm is a generalization of the square-and-multiply method. The terms (x(2i) mod m)s for all is is an element of {0, ..., n - 1} are computed in inverted right perpendicular n-1/inverted right perpendicular alpha log n inverted left perpendicular inverted left perpendicular parallel rounds, each of which computes inverted right perpendicular alpha log n inverted left perpendicular consecutive terms, where alpha greater than or equal to 1/log n. The circuit implementing a round has depth O((1 + alpha) log n) and size O(n(2(1+alpha)) yielding a circuit for modular exponentiation of depth [GRAPHICS] and size O(n(3+2 alpha)/alpha log n).

Keywords:

circuit complexity

computer arithmetic

hardware algorithm

modular arithmetic

modular exponentiation

O(n)-depth modular exponentiation circuit algorithm

Abstract

Journal

Organization