特許

J-GLOBAL ID：200903018802663961

モンゴメリ法による乗算剰余計算装置

発明者： 武仲 正彦 ,  伊藤 孝一 ,  鳥居 直哉
出願人/特許権者： 富士通株式会社
代理人 (1件)： 河野 登夫
公報種別：公開公報
出願番号（国際出願番号）：特願平10-014681
公開番号（公開出願番号）：特開平11-212456
出願日： 1998年01月27日
公開日（公表日）： 1999年08月06日
要約：

【要約】【課題】 積和回路の構成を単純化することができ、また、パイプライン処理が可能になる、モンゴメリのアルゴリズムを用いて乗算剰余計算を高速に行う計算装置を提供する。【解決手段】 積和回路21は、Aレジスタ3及びBレジスタ4の出力を乗算し、その乗算結果にc3 レジスタ26の出力及びYレジスタ5の出力を加算する。積和回路22は、Nレジスタ7及びmレジスタ8の出力を乗算し、その乗算結果にc4 レジスタ29の出力及び積和回路21の出力を加算する。2つの積和回路21,22におけるキャリー用のレジスタ26,29を各別に設けて自身の積和回路にキャリーを戻す構成とする。全ての処理を処理単位(kビット)内で行う。積和回路22の動作中に、積和回路21の次回の動作が可能である。

請求項（抜粋）：

モンゴメリのアルゴリズムを用いて乗算剰余計算を行う装置において、積和演算を行いその演算結果を上位kビットと下位kビットとに分けて出力する第1積和回路と、積和演算を行いその演算結果を上位kビットと下位kビットとに分けて出力する第2積和回路と、加算演算を行いその演算結果を上位1ビットと下位kビットとに分けて出力する加算回路と、乗算される2数を保持する第1及び第2レジスタと、前記第2積和回路の下位kビット出力を保持し、前記第2積和回路のその次の回の下位kビット出力を格納する第3レジスタと、前記加算回路の下位kビット出力を保持し、前記加算回路のその次の回の下位kビット出力を格納する第4レジスタと、剰余の法を保持する第5レジスタと、モンゴメリのアルゴリズムにおけるパラメータの値を保持する第6レジスタと、前記加算回路の上位1ビット出力を保持し、前記加算回路のその次の回の上位1ビット出力を格納する第7レジスタとを備え、前記第1積和回路は、前記第1及び第2レジスタに保持された2数の所定ビットの値を乗算し、その乗算結果に前記第3レジスタに保持された数の所定ビットの値及び前記第4レジスタに保持された値を加算する演算を行い、前記第2積和回路は、前記第5レジスタに保持された数の所定ビットの値と前記第6レジスタに保持された値とを乗算し、その乗算結果に前記第1積和回路の下位kビット出力を加算する演算を行い、前記加算回路は、前記第1積和回路の上位kビット出力と前記第2積和回路の上位kビット出力と前記第7レジスタに保持された値とを加算する演算を行うように構成したことを特徴とするモンゴメリ法による乗算剰余計算装置。

IPC (3件)：

G09C 1/00 650 ,  G06F 7/72 ,  H04L 9/30

FI (3件)：

G09C 1/00 650 A ,  G06F 7/72 ,  H04L 9/00 663 B