|
Published Articles >> Table of Contents >> Abstract
12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95)
p. 188
O(n)-depth circuit algorithm for modular exponentiation
T. Hamano, Dept. of Inf. Sci., Kyoto Univ., Japan
N. Takagi, Dept. of Inf. Sci., Kyoto Univ., Japan
S. Yajima, Dept. of Inf. Sci., Kyoto Univ., Japan
F.P. Preparata, Dept. of Inf. Sci., Kyoto Univ., Japan
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.1995.465360
Send link to a friend
| 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.
|
 Additional Information
|
Index Terms- public key cryptography; digital arithmetic; combinational circuits; O(n)-depth circuit algorithm; modular exponentiation; polynomial-size combinational circuit algorithm; n-bit modular exponentiation; n-bit binary integers; square-and-multiply method
Citation:
T. Hamano, N. Takagi, S. Yajima, F.P. Preparata,
"O(n)-depth circuit algorithm for modular exponentiation,"
arith,
p. 188,
12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95),
1995
|
|
