講演名	1995/11/17 乗除べき乗算のための段数 O((1-α)/α n)) 素子数 O((n^<3+2α>)/(αlogn))回路 濱野 貴文, 高木 直史, 矢島 脩三, プレパラータ フランコ P.,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	nビットの任意の自然数x,y,m(2^≦m<2^n,0≦x,yの組合せ回路アルゴリズムを提案する。このアルゴリズムはsquare-and-multiplyアルゴリズムの一般化である。square-and-multiplyアルゴリズムに基づき単純に組合せ回路を構成すれば、その回路は段数O(n log n)素子数O(n^3)である。提案するアルゴリズムでは、剰余数表示法を用いて累乗演算を行うことにより、任意の正数αをパラメータとして、段数((1-α)/α n)、素子数O((n^<3+2α>)/(αlogn))の組合せ回路が得られる。
抄録(英)	An O((1-α)/α 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^≦m < 2^n and 0≦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(n log n) and size O(n^3). In the proposed algorithm, using residue number system for powering operations, a circuit for modular exponentiation of depth O((1-α)/α n) and size O((n^<3+2α>)/(αlog n)), where α is an arbitrary Chosen positive integer, is achieved.
キーワード(和)	剰余べき乗算 / 回路計算複雑さ / ハードウェアアルゴリズム
キーワード(英)	modular exponentiation / circuit complexity / hardware algorithm
資料番号	COMP95-60
発行日

研究会情報
研究会	COMP
開催期間	1995/11/17(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Theoretical Foundations of Computing (COMP)
本文の言語	ENG
タイトル（和）	乗除べき乗算のための段数 O((1-α)/α n)) 素子数 O((n^<3+2α>)/(αlogn))回路
サブタイトル（和）
タイトル（英）	An O((1-α)/α n) -depth O((n^<3+2α>)/(α log n)) -size circuit for modular exponentiation
サブタイトル（和）
キーワード(1)（和/英）	剰余べき乗算 / modular exponentiation
キーワード(2)（和/英）	回路計算複雑さ / circuit complexity
キーワード(3)（和/英）	ハードウェアアルゴリズム / hardware algorithm
第 1 著者 氏名（和/英）	濱野 貴文 / Takafumi Hamano
第 1 著者 所属（和/英）	京都大学 工学部 情報工学科 Department of Information Science, Kyoto University
第 2 著者 氏名（和/英）	高木 直史 / Naofumi Takagi
第 2 著者 所属（和/英）	名古屋大学 工学部 情報工学科 Department of Information Engineering, Nagoya University
第 3 著者 氏名（和/英）	矢島 脩三 / Shuzo Yajima
第 3 著者 所属（和/英）	京都大学 工学部 情報工学科 Department of Information Science, Kyoto University
第 4 著者 氏名（和/英）	プレパラータ フランコ P. / Franco P. Preparata
第 4 著者 所属（和/英）	Dept. of Computer Science, Brown University Department of Computer Science, Brown University
発表年月日	1995/11/17
資料番号	COMP95-60
巻番号（vol）	vol.95
号番号（no）	374
ページ範囲	pp.-
ページ数	6
発行日