特許

J-GLOBAL ID：200903059343849214

モンゴメリ乗算装置及び方法

発明者： 小池 正修 ,  川村 信一
出願人/特許権者： 株式会社東芝
代理人 (1件)： 鈴江 武彦 (外6名)
公報種別：公開公報
出願番号（国際出願番号）：特願2000-137182
公開番号（公開出願番号）：特開2001-318785
出願日： 2000年05月10日
公開日（公表日）： 2001年11月16日
要約：

【要約】【課題】 剰余算の高速化により、少なくとも部分的な剰余演算を高速化でき、さらに全体的な演算速度の高速化を実現させる。【解決手段】 各積和回路301〜30nに配置された除算回路40において、法mでの剰余算であるにも関わらず、剰余算の実行結果h’を法mよりも大きい値2rと比較するように剰余算の終了条件を緩和している。これにより、2rという比較の容易な数の採用によるループ制御自体の高速化と、2rという大きい数の採用によるループ回数の低減化とによって剰余算を高速化させる。

請求項（抜粋）：

正の整数Nと、N未満の正の整数x,yとを入力とし、剰余演算系の基底を{a1,a2,...,ai,...,an}および{b1,b2,...,bi,...,bn}(1≦i≦n、nは正の整数)としたとき、前記基底の要素の乗積として定義された整数B(=b1b2...bn)を用いて、出力w=xyB-1mod Nを算出するためのモンゴメリ乗算装置であって、前記各基底の要素{a1,a2,...,an}および{b1,b2,...,bn}と前記出力wの算出用の事前計算結果とが記憶される第1記憶手段と、前記基底の拡張用の入力ξiを受けたとき、前記入力ξiの上位qビットを抽出すると共に、この今回の抽出値と前回の最上位ビットを除く加算結果とを加算し、得られた加算結果のうち、最上位ビットの値kiを出力する近似演算手段と、前記第1記憶手段の内容および前記近似演算手段の出力kiに基づいて、前記各基底の要素{a1,a2,...,an}および{b1,b2,...,bn}を法mとする剰余算(但し、法m=2r-μは基底の一要素、rはm≦2rを満たす整数、μは2r未満の非負整数)を実行する剰余演算手段と、前記剰余演算手段による剰余算の結果が記憶される第2記憶手段とを備え、前記剰余演算手段は、前記第1記憶手段又は前記第2記憶手段からの入力x,yの積xyと前回の剰余算の結果dと前記近似演算手段の出力kiに基づき入力される前記事前計算結果cとの和(xy+d+c)からなる入力z(但し、zは正の整数)を受けると共に、前記入力zの法mによる剰余算h=z mod mを実行する剰余算部と、前記剰余算部による実行結果h’と前記法mの上限値2rとを比較し、前記実行結果h’が2r以上のときには当該実行結果h’を前記入力zとして前記剰余算部に戻し、前記実行結果h’が2r未満のときには当該実行結果h’を前記剰余算の結果hとして前記第2記憶手段に出力するループ制御部と、を備えたことを特徴とするモンゴメリ乗算装置。

IPC (2件)：

G06F 7/72 ,  G09C 1/00 650

FI (2件)：

G06F 7/72 ,  G09C 1/00 650 A

Fターム (6件)：

5J104AA22 ,  5J104JA23 ,  5J104NA18 ,  9A001BB02 ,  9A001EE03 ,  9A001GG01

引用特許：

出願人引用 (2件)

• データ処理装置及びマイクロコンピュータ
  公報種別：公開公報   出願番号：特願平8-169322   出願人：株式会社日立製作所
• 剰余演算装置及び方法
  公報種別：公開公報   出願番号：特願2000-334978   出願人：株式会社東芝