12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95)
O(n)-depth circuit algorithm for modular exponentiation
Bath, England
July 19-July 21
ISBN: 0-8186-7089-4
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
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.
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, pp.188, 12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95), 1995
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb