乗除べき乗算のための段数 O((1-α)/α n)) 素子数 O((n^<3+2α>)/(αlogn))回路
スポンサーリンク
概要
- 論文の詳細を見る
nビットの任意の自然数x,y,m(2^<n-1>≦m<2^n,0≦x,y<m)に対して剰余べき乗算x^y mod mをnビット2進数の形で計算する段数O(n)素子数n^<O>の組合せ回路アルゴリズムを提案する。このアルゴリズムはsquare-and-multiplyアルゴリズムの一般化である。square-and-multiplyアルゴリズムに基づき単純に組合せ回路を構成すれば、その回路は段数O(n log n)素子数O(n^3)である。提案するアルゴリズムでは、剰余数表示法を用いて累乗演算を行うことにより、任意の正数αをパラメータとして、段数((1-α)/α n)、素子数O((n^<3+2α>)/(αlogn))の組合せ回路が得られる。
- 社団法人電子情報通信学会の論文
- 1995-11-17
著者
-
高木 直史
名古屋大学大学院情報科学研究科
-
矢島 脩三
京都大学工学部情報工学教室
-
矢島 脩三
京都大学工学部
-
矢島 脩三
京都大学大学院工学研究科情報工学教室
-
矢島 脩三
京都大学 工学部
-
高木 直史
名古屋大学
-
濱野 貴文
京都大学 工学部 情報工学科
-
プレパラータ フランコ
Dept. of Computer Science, Brown University
-
プレパラータ フランコ
Dept. Of Computer Science Brown University
関連論文
- 超伝導単一磁束量子集積回路の技術動向と超伝導コンピュータの展望
- 複合算術演算の減算シフト型ハードウェアアルゴリズムの設計支援(VLSI設計技術とCAD)
- Nbアドバンストプロセスを用いた単一磁束量子浮動小数点演算器の設計(ディジタル,一般)
- テスト容易な並列プレフィックス加算器の設計手法(設計/テスト/検証,設計/テスト/検証)
- SFQ半精度浮動小数点乗算器の設計と試作(デジタル,一般)
- 投票無衝突化手法を用いた小面積画素並列ハフ変換回路(応用,組込技術とネットワークに関するワークショップETNET2009)
- SFQ半精度浮動小数点加算器の設計と試作(デジタル,一般)
- C-8-10 SFQ浮動小数点乗算器の同期化および動作実証(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-13 Nb多層プロセスを用いて試作したシフトレジスタの測定評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-7 超伝導SFQ回路のための新Nb多層プロセス(C-8. 超伝導エレクトロニクス,一般セッション)
- オペランドの和を用いた並列乗算器の消費エネルギー評価 (ディペンダブルコンピューティング)
- オペランドの和を利用した小面積乗算器(演算器最適化,デザインガイア2008-VLSI設計の新しい大地)
- オペランドの和を利用した小面積乗算器(演算器最適化,デザインガイア2008-VLSI設計の新しい大地-)
- 全加算器で構成したマルチオペランド加算器のテスト生成(設計/テスト/検証)
- Nb多層デバイス構造用セルライブラリに向けた最適なモート構造の検討(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- パイプライン動作を考慮した単一磁束量子回路のための論理設計検証手法(ディジタル,一般)
- ハードウェアサポートによるガロア体上の演算の高速化(情報通信基礎サブソサイエティ合同研究会)
- テスト容易な並列プレフィックス加算器の自動合成手法の検討(ディペンダブルシステム,組込み技術とネットワークに関するワークショップ ETNET2010)
- オペランドの和を用いた並列乗算器の消費エネルギー評価(論理設計,デザインガイア2009-VLSI設計の新しい大地-)
- A-3-1 Sequential SATの高速化のためのm-Trieを用いた時間フレームを跨いだ状態併合(A-3.VLSI設計技術,一般セッション)
- C-8-14 可変遅延素子を用いた単一磁束量子可変長シフトレジスタ(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-6 10kA/cm^2Nbプロセス用単一磁束量子セルライブラリの構築(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-7 単一磁束量子回路を用いた2並列3段の再構成可能なデータパスの検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-9 A^*アルゴリズムに基づく単一磁束量子回路受動線路配線ツールの実装と評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-10 2並列4段の再構成可能なデータパスを有する単一磁束量子回路の検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-12 SFQ半精度浮動小数点乗算器の試作と動作実証(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-21 単一磁束量子回路における2並列2段の再構成可能なデータパスの動作実証(C-8. 超伝導エレクトロニクス,一般セッション)
- C-8-18 SFQ半精度浮動小数点乗算器の設計と試作(C-8. 超伝導エレクトロニクス,一般セッション)
- 超伝導単一磁束量子集積回路の技術動向と超伝導コンピュータの展望
- C-8-16 アドバンストプロセス2.1を用いた2並列2段のSFQ-RDPの検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-15 10kA/cm^2Nbアドバンスドプロセスを用いたSFQ半精度浮動小数点乗算器の設計(C-8.超伝導エレクトロニクス,一般セッション)
- A-20-20 TLDP法の並列化による省メモリな連続単語音声認識回路(A-20. スマートインフォメディアシステム,一般セッション)
- A-3-11 テスト容易な並列プレフィックス加算器の設計(A-3. VLSI設計技術,一般セッション)
- C-8-5 10kA/cm^2Nbプロセスを用いたSFQ半精度浮動小数点加算器のコンポーネント回路の設計(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-2 単一磁束量子回路による冗長2進表現を用いたシストリックシリアル指数計算回路(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-1 単一磁束量子回路のためのパイプライン検証手法(C-8.超伝導エレクトロニクス,一般セッション)
- けた上げ保存加算器で構成された部分積加算部をもつ乗算器のテスト(ディペンダブルコンピューティング)
- C-8-13 SFQ回路のためのレイアウトを考慮したスキューのあるクロック木の構成法(C-8.超伝導エレクトロニクス,一般セッション)
- 平方根の逆数計算回路の設計と評価
- 平方根の逆数計算回路の設計と評価
- 平方根の逆数計算回路の設計と評価
- Steinのアルゴリズムに基づく有限体上の除算アルゴリズム
- Steinのアルゴリズムに基づく有限体上の除算アルゴリズム
- Steinのアルゴリズムに基づく有限体上の除算アルゴリズム
- 再構成可能なデータパスに向けた単一磁束量浮動小数点除算器の実証(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- C-8-22 単一磁束量子回路のフロアプラン設計支援に向けた配線遅延時間の推定(C-8. 超伝導エレクトロニクス,一般セッション)
- C-8-11 パイプライン導入による単一磁束量子浮動小数点加算器の性能向上(C-8.超伝導エレクトロニクス,一般講演)
- C-8-10 シストリックアーキテクチャに基づく高スループットSFQビットシリアル浮動小数点乗算器(C-8.超伝導エレクトロニクス,一般講演)
- C-8-9 単一磁束量子回路による冗長2進表現を用いたシストリック開平器の設計(C-8.超伝導エレクトロニクス,一般講演)
- C-8-11 冗長2進表現を用いたシストリックSFQ除算器(C-8.超伝導エレクトロニクス,一般講演)
- A-3-10 単一磁束量子ディジタル回路のためのone-hot状態割り当てを用いた順序回路の構成法(A-3.VLSI設計技術,一般講演)
- C-8-15 トルネードアーキテクチャに基づく単一磁束量子マイクロプロセッサのALUの改善(C-8.超伝導エレクトロニクス,一般講演)
- C-8-12 トルネードアーキテクチャにおけるSFQマイクロプロセッサのデータパスの動作実証(C-8.超伝導エレクトロニクス,一般講演)
- C-8-10 トルネードアーキテクチャにおけるSFQマイクロプロセッサのデータパスの設計(C-8.超伝導エレクトロニクス,エレクトロニクス2)
- C-8-9 クロック同期式SFQ回路のクロック木合成(C-8.超伝導エレクトロニクス,エレクトロニクス2)
- C-8-5 SFQマイクロプロセッサに向けたレジスタファイルの実証(C-8. 超伝導エレクトロニクス, エレクトロニクス2)
- C-8-12 SFQマイクロプロセッサに向けたトルネードアーキテクチャの提案(C-8.超伝導エレクトロニクス)
- 順序回路の形式的検証におけるフォールスネガティブ削減のための回路変換(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- C-8-4 SFQ回路実現に向いた直並列型2の補数乗算器(C-8. 超伝導エレクトロニクス, エレクトロニクス2)
- C-8-10 SFQマイクロプロセッサに用いるコンパレータの設計(C-8.超伝導エレクトロニクス)
- 多層配線単一磁束量子回路のための自動配線手法(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 再構成可能部を持つJavaプロセッサにおけるハードウェアJIT機構の検討
- 再構成可能部を持つJavaプロセッサにおけるハードウェアJIT機構の検討
- A-3-16 再構成可能部を持つJavaプロセッサにおける高速化方式およびハードウェアJIT方式の検討
- D-10-10 乗算器の種々の部分積加算部の順序故障テスト(D-10. ディペンダブルコンピューティング,一般セッション)
- 5H-8 立方根計算のハードウェアアルゴリズムについて
- 機能メモリを用いた動画像圧縮のための動きベクトル検出アルゴリズム
- 乗算型除算および開平のためのハードウェアによる初期近似手法
- 除算と開平のための積和演算を用いた初期近似手法
- 連分数展開に基づく高速開平アルゴリズム
- A-3-11 パリティ検査符号を用いたオンライン誤り検出可能な高速加算器(A-3. VLSI設計技術)
- 加算器の平均スイッチングエネルギーの解析的評価(低電力設計と回路設計技術,システムオンシリコンを支える設計技術)
- GF (2^m) 上の繰り返し乗算の高速化のための冗長基底とそれを用いた並列乗算器
- A-7-12 Fast addition for elliptic curve arithmetic in GF(2^n) using projective coordinates
- 剰余除算用ハードウェアアルゴリズムについて
- 乗算器および除算器IPの開発
- 乗算器および除算器IPの開発
- 乗算器および除算器IPの開発
- 算術演算のための減算シプト型ハードウェアアルゴリズムの自動合成(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 算術演算のための減算シフト型ハードウェアアルゴリズムの自動合成(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 算術演算のための減算シフト型ハードウェアアルゴリズムの自動合成(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 算術演算のための減算シフト型ハードウェアアルゴリズムの自動合成(アルゴリズム)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 浮動小数点ユークリッドノルム計算回路
- A-3-1 3D ユークリッドノルムの逆数計算のハードウェアアルゴリズム
- LC-2 浮動小数点3Dユークリッドノルム計算回路の設計と評価(C. アーキテクチャ・ハードウェア)
- 浮動小数点3Dユークリッドノルム計算回路
- 浮動小数点3Dユークリッドノルム計算回路
- 浮動少数点3Dユークリッドノルム計算回路
- 冗長2進表現を用いた右シフト剰余除算のハードウェアアルゴリズム
- BDDに基づくSFQ論理回路の新しい実現方法(エレクトロニクス・一般)
- 専用回路を用いたマイクロプロセッサにおけるパーミュテーションの高速化(コデザイン及びアーキテクチャ)
- 専用回路を用いたマイクロプロセッサにおけるパーミュテーションの高速化(コデザイン及びアーキテクチャ)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 専用回路を用いたマイクロプロセッサにおけるパーミュテーションの高速化(コデザイン及びアーキテクチャ)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 専用回路を用いたマイクロプロセッサにおけるパーミュテーションの高速化(コデザイン及びアーキテクチャ)(デザインガイア2003 -VLSI設計の新しい大地を考える研究会-)
- 専用回路を用いたマイクロプロセッサにおけるパーミュテーションの高速化
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法