(57)【要約】【課題】高速化な乗算剰余演算方法を提供する。【解決手段】本発明の乗算剰余演算方法は，奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；Ａ×Ｂ×Ｒ−１ｍｏｄＮを求める演算方法であって，Ｎ，Ａ，Ｂ，および，ＡとＮとの加算値ＡＮ＝Ａ＋Ｎを入力する段階，演算の中間結果Ｔを記憶する段階，各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する段階，中間結果Ｔと選択結果Ｘとを加算シフトした値；（Ｔ＋Ｘ）／２を演算する段階，この演算を繰り返し実行する段階を含むことを特徴とする。【選択図】  図１
2004170642.tif 000002
【特許請求の範囲】
【請求項１】
奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，前記法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める演算方法であって，
Ｎ，Ａ，Ｂ，および，ＡとＮとの加算値ＡＮ＝Ａ＋Ｎを入力する段階と，
演算の中間結果Ｔを記憶する段階と，
各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する段階と，
前記中間結果Ｔと前記選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する段階と，
前記演算を繰り返し制御する段階と，
を含むことを特徴とする，乗算剰余演算方法。
【請求項２】
奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，前記法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める演算方法であって，
Ｎ，Ａ，Ｂ，および，ＡとＮとの減算値ＡＮ＝Ａ−Ｎを入力する段階と，
演算の中間結果Ｔを記憶する段階と，
各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する段階と，
前記中間結果Ｔと前記選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する段階と，
前記演算を繰り返し制御する段階と，
を含むことを特徴とする，乗算剰余演算方法。
【請求項３】
前記入力段階では，Ｎ，Ａ，および，Ｂのみを入力し，
ＡとＮからＡＮを演算する段階をさらに含むことを特徴とする，請求項１または２のいずれか１項に記載の乗算剰余演算方法。
【請求項４】
前記選択段階は，前記選択処理に加えてさらに，Ｂの状態のみに依存して０もしくはＡを選択する処理を行い，
前記演算段階は，前記演算処理に加えてさらに，前記演算処理のシフトにより切り捨てられる最下位桁を取り出す処理を行い，
前記演算段階より順次取り出された下位桁を出力する段階をさらに含むことを特徴とする，請求項１，２，または３のうちのいずれか１項に記載の乗算剰余演算方法。
【請求項５】
複数の前記選択段階と，複数の前記演算段階とを含み，
１つ目の選択段階は，前記記憶段階で保持するＴを中間結果として選択処理し，かつ，１つ目の演算段階は，前記記憶段階で保持するＴを中間結果として演算処理し，
２つ目以降の選択段階は，その１つ前の演算段階の演算結果を中間結果として選択処理し，かつ，２つ目以降の演算段階は，その１つ前の演算段階の演算結果を中間結果として演算処理することを特徴とする，請求項１，２，３，または４のうちのいずれか１項に記載の乗算剰余演算方法。
【請求項６】
前記演算段階の加算シフト演算処理前の加算結果を出力する出力段階をさらに含み，
前記選択段階は，前記選択処理に加えてさらに，前記中間結果の符号の状態に応じて０もしくはＮを選択する処理を行うことを特徴とする，請求項２，３，４，または５のうちのいずれか１項に記載の乗算剰余演算方法。
【請求項７】
前記演算段階は，前記演算処理の前に，演算モードを選択する処理を行い，
前記演算モードの選択の結果，整数演算モードでは通常の前記演算処理を行い，多項式演算モードでは，前記各演算段階の加減算処理における各桁から上位桁への桁上がりまたは桁下がりを抑制した状態で前記演算処理を行うことを特徴とする，請求項１，２，３，４，５，または６のうちのいずれか１項に記載の乗算剰余演算方法。
【請求項８】
前記記憶段階は，複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果を保持する分割記憶処理を行い，
前記演算段階は，前記複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果と，前記選択段階の選択結果から新たな追加の桁上がりビットを含む中間結果とを演算する分割演算処理を行うことを特徴とする，請求項１，２，３，４，５，６，または７のうちのいずれか１項に記載の乗算剰余演算方法。
【請求項９】
前記演算段階は，ＡとＮからＡＮを演算する前記ＡＮ演算処理を複数のブロックに分割し，追加の桁上がりビットを含むＡＮ値を演算する分割ＡＮ演算処理を行い，
前記選択段階は，ＡＮの追加の桁上がりビットを含めて選択する分割選択処理を行うことを特徴とする，請求項３または８のいずれか１項に記載の乗算剰余演算方法。
【請求項１０】
前記入力段階は，入力値Ａを複数のブロックに分割して，追加の桁上がりビットを含む入力値Ａが入力可能な分割入力処理を行い，
前記演算段階は，追加の桁上がりビットを含む入力値Ａを用いてＡＮを演算する分割ＡＮ演算処理を行い，
前記選択手段は，追加の桁上がりビットを含む入力値Ａを用いた分割選択処理を行うことを特徴とする，請求項９に記載の乗算剰余演算方法。
【請求項１１】
奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，前記法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める演算装置であって，
Ｎ，Ａ，Ｂ，および，ＡとＮとの加算値ＡＮ＝Ａ＋Ｎを入力する手段と，
演算の中間結果Ｔを記憶する手段と，
各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する手段と，
前記中間結果Ｔと前記選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する手段と，
前記演算手段を繰り返し制御する手段と，
を含むことを特徴とする，乗算剰余演算装置。
【請求項１２】
奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，前記法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める演算装置であって，
Ｎ，Ａ，Ｂ，および，ＡとＮとの減算値ＡＮ＝Ａ−Ｎを入力する手段と，
演算の中間結果Ｔを記憶する手段と，
各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する手段と，
前記中間結果Ｔと前記選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する手段と，
前記演算手段を繰り返し制御する手段と，
を含むことを特徴とする，乗算剰余演算装置。
【請求項１３】
前記入力手段では，Ｎ，Ａ，および，Ｂのみを入力し，
ＡとＮからＡＮを演算する手段をさらに含むことを特徴とする，請求項１１または１２のいずれか１項に記載の乗算剰余演算装置。
【請求項１４】
前記選択手段は，前記選択処理に加えてさらに，Ｂの状態のみに依存して０もしくはＡを選択する処理を行い，
前記演算手段は，前記演算処理に加えてさらに，前記演算処理のシフトにより切り捨てられる最下位桁を取り出す処理を行い，
前記演算手段より順次取り出された下位桁を出力する手段をさらに含むことを特徴とする，請求項１１，１２，または１３のうちのいずれか１項に記載の乗算剰余演算装置。
【請求項１５】
前記選択手段は複数の選択処理を行い，１つ目の選択処理は，前記記憶手段で保持するＴを中間結果として選択処理し，２つ目以降の選択処理は，その１つ前の演算処理の演算結果を中間結果として選択処理し，
前記演算手段は複数の演算処理を行い，１つ目の演算処理は，前記記憶手段で保持するＴを中間結果として演算処理し，２つ目以降の演算処理は，その１つ前の演算処理の演算結果を中間結果として演算処理することを特徴とする，請求項１１，１２，１３，または１４のうちのいずれか１項に記載の乗算剰余演算装置。
【請求項１６】
前記演算手段の加算シフト演算処理前の加算結果を出力する出力手段をさらに含み，
前記選択手段は，前記選択処理に加えてさらに，前記中間結果の符号の状態に応じて０もしくはＮを選択する処理を行うことを特徴とする，請求項１２，１３，１４，または１５のうちのいずれか１項に記載の乗算剰余演算装置。
【請求項１７】
前記演算手段は，前記演算処理の前に，演算モードを選択する処理を行い，
前記演算モードの選択の結果，整数演算モードでは通常の前記演算処理を行い，多項式演算モードでは，前記各演算手段の加減算処理における各桁から上位桁への桁上がりまたは桁下がりを抑制した状態で前記演算処理を行うことを特徴とする，請求項１１，１２，１３，１４，１５，または１６のうちのいずれか１項に記載の乗算剰余演算装置。
【請求項１８】
前記記憶手段は複数のブロックに分割され，前記複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果を保持する分割記憶処理を行い，
前記演算手段は，前記複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果と，前記選択手段の選択結果から新たな追加の桁上がりビットを含む中間結果とを演算する分割演算処理を行うことを特徴とする，請求項１１，１２，１３，１４，１５，１６，または１７のうちのいずれか１項に記載の乗算剰余演算装置。
【請求項１９】
前記演算手段は，ＡとＮからＡＮを演算する前記ＡＮ演算処理が複数のブロックに分割され，追加の桁上がりビットを含むＡＮ値を演算する分割ＡＮ演算処理を行い，
前記選択手段は，ＡＮの追加の桁上がりビットを含めて選択する分割選択処理を行うことを特徴とする，請求項１３または１８のいずれか１項に記載の乗算剰余演算装置。
【請求項２０】
前記入力手段は，入力値Ａを複数のブロックに分割して，追加の桁上がりビットを含む入力値Ａが入力可能な分割入力処理を行い，
前記演算手段は，追加の桁上がりビットを含む入力値Ａを用いてＡＮを演算する分割ＡＮ演算処理を行い，
前記選択手段は，追加の桁上がりビットを含む入力値Ａを用いた分割選択処理を行うことを特徴とする，請求項１９に記載の乗算剰余演算装置。
【請求項２１】
請求項１，２，３，４，５，６，７，８，９，または１０のうちのいずれか１項に記載の乗算剰余演算方法を行うためのコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，公開鍵暗号の演算処理等で用いられる剰余演算，特に乗算剰余演算の演算処理を行う方法および装置に関する。
【０００２】
【従来の技術】
従来，乗算剰余演算を処理する演算方法としては，非特許文献１に示される，「モンゴメリ乗算」と呼ばれる方法があった。このモンゴメリ乗算は，公開鍵暗号のように剰余系における乗算等の演算を繰り返し行う処理において有効な乗算剰余演算方法である。
【０００３】
モンゴメリ乗算では，法Ｎに対して，Ｎと互いに素な基数をＲとして，
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める。この演算は，通常の剰余系における乗算剰余ａ×ｂｍｏｄＮに対して，Ａ＝ａＲ，Ｂ＝ｂＲとすると，
Ａ×Ｂ×Ｒ−１ｍｏｄＮ＝（ａ×ｂ）ＲｍｏｄＮ
となり，Ｒ倍に写像された領域での乗算に対応する。
【０００４】
Ａ×Ｂ×Ｒ−１ｍｏｄＮを求める手順は，法Ｎおよび，法Ｎと互いに素な基数Ｒに対して，
Ｎ’＝−Ｎ−１ｍｏｄＲ
として，以下のようなアルゴリズムである。
【０００５】
Ｓｔｅｐ１：Ｔ＝Ａ×Ｂ
Ｓｔｅｐ２：ｍ＝（ＴｍｏｄＲ）×Ｎ’ｍｏｄＲ
Ｓｔｅｐ３：ｔ＝（Ｔ＋ｍ×Ｎ）／Ｒ
Ｓｔｅｐ４：Ｉｆ（ｔ≧Ｎ）  ｔｈｅｎ  ｒｅｔｕｒｎ  ｔ−Ｎ  ｅｌｓｅ  ｒｅｔｕｒｎ  ｔ
【０００６】
ここで，Ｓｔｅｐ３のＴ＋ｍ×Ｎは，Ｒの倍数となることが証明できるため，Ｒによる除算が実行可能である。従って，モンゴメリ乗算は，この除算が簡単な処理で実行可能な場合には有効である。特に奇数のＮに対してＲ＝２ｎなるＲを選ぶ場合，Ｒによる除算は下位ｎビットを破棄した上位ビットを取り出すだけの演算となる。
【０００７】
このようにモンゴメリ乗算は，上記アルゴリズムにより，乗算処理に比べて処理コストが比較的高価なＮによる剰余算を回避することができる。
【０００８】
【非特許文献１】
Ｐｅｔｅｒ  Ｌ．  Ｍｏｎｔｇｏｍｅｒｙ，  ”Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｗｉｔｈｏｕｔ  Ｔｒｉａｌ  Ｄｉｖｉｓｉｏｎ”，  Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ，  ｖｏｌ．４４，  Ａｐｒ．  １９８５，  ｐｐ．  ５１９−５２１
【０００９】
【発明が解決しようとする課題】
しかしながら，上記従来のモンゴメリ乗算のアルゴリズムでは，Ｎと同程度のサイズの数の乗算が３回必要である。特に，ＲＳＡ暗号等において１０２４ビットというような大きなサイズの法Ｎを用いる場合，処理に非常に長い時間を要するため，更なる高速化が望まれていた。
【００１０】
【課題を解決するための手段】
本発明は，上記課題を解決するためになされた乗算剰余演算方法であり，次のような構成を採用する。
【００１１】
即ち，奇数の法Ｎ，入力値Ａ，入力値Ｂ，および，法Ｎと互いに素な基数Ｒ（但し，Ｒ＝２ｎ，ｎは整数）に対して乗算剰余；Ａ×Ｂ×Ｒ−１ｍｏｄＮを求めるにあたり，まず，Ｎ，Ａ，Ｂ，および，ＡとＮとの加算値ＡＮ＝Ａ＋Ｎを入力する。次に，演算の中間結果Ｔを記憶し，各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。次に，中間結果Ｔと選択結果Ｘとを加算シフトした値；（Ｔ＋Ｘ）／２を演算する。そしてこの演算を繰り返し実行する。
【００１２】
【発明の実施の形態】
以下に，本発明のいくつかの実施の形態を，図面を用いて説明する。本実施の形態では，法Ｎ，入力値Ａ，入力値Ｂ，法Ｎと互いに素な基数Ｒに対して，
Ａ×Ｂ×Ｒ−１ｍｏｄＮ
を求める。ここで，法Ｎは奇数，基数Ｒは，Ｒ＝２ｎ，ｎは整数とする。
【００１３】
［第１の実施形態］
本発明の第１の実施形態の乗算剰余演算方法は，Ｎ，Ａ，Ｂ，および，ＡとＮとの加算値ＡＮ＝Ａ＋Ｎを入力する段階と，演算の中間結果Ｔを記憶する段階と，各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する段階と，中間結果Ｔと選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する段階と，演算を繰り返し制御する段階とを含む。
【００１４】
図１は，本発明の第１の実施形態の乗算剰余演算装置の構成図である。入力部１０１では，法Ｎ，入力値Ａ，Ｂ，および，予め計算したＡＮ＝Ａ＋Ｎを，入力する。記憶部１０４は，演算の中間結果Ｔを保持する記憶部であり，０に初期化された後，演算途中の中間結果を順次保持する。また，最終結果の保持場所ともなる。制御部１０５は，演算の繰り返し状態等を制御する。
【００１５】
選択部１０２は，ＴおよびＡのそれぞれの最下位ビットｔ０，ａ０と，Ｂのあるビットｂｉの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。
【００１６】
演算部１０３は，選択部１０２の選択結果Ｘと中間結果Ｔから
（Ｔ＋Ｘ）／２
を演算し，これを新たなＴとして記憶部１０４に記憶させる。
【００１７】
以上のような構成を用いて，以下の処理手順アルゴリズムを実行する。
Ｔ＝０
ｆｏｒ  ｉ＝０  ｔｏ  ｎ−１
Ｘ＝ｓｅｌｅｃｔ（Ａ，Ｎ，ＡＮ；ｔ０，ａ０，ｂｉ）
Ｔ＝（Ｔ＋Ｘ）／２
【００１８】
ここで，選択部１０２の処理ｓｅｌｅｃｔは，ｂｉ，ｔ０，ａ０の状態に応じて，表１のように０，Ａ，Ｎ，ＡＮのいずれかを選択する。
【００１９】
【表１】
2004170642.tif 000003
【００２０】
以上の処理により，Ａ×Ｂ×Ｒ−１（ｍｏｄＮ）が，Ｔに求まる。このとき，Ｔの値の範囲は，
０≦Ｔ＜Ａ＋Ｎ
となり，従来技術のＳｔｅｐ４と同様な処理によって，Ｔ＜Ｎなる値を求めることもできる。
【００２１】
以上説明したように，本発明の第１の実施形態によれば，従来，法Ｎと同程度のサイズの数の乗算処理が３回必要であった乗算剰余演算が，乗算処理１回と同程度の処理コストで演算を実行することが可能になり，高速化が達成できる。また，従来の方法では，演算途中で法Ｎのサイズの２倍のサイズの中間結果を保持する必要があったが，本実施形態では，法Ｎのサイズ＋１ビット程度の中間結果を保持するのみでよい。
【００２２】
［第２の実施形態］
本発明の第２の実施形態の乗算剰余演算方法は，Ｎ，Ａ，Ｂ，および，ＡとＮとの減算値ＡＮ＝Ａ−Ｎを入力する段階と，演算の中間結果Ｔを記憶する段階と，各入力およびＴの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する段階と，中間結果Ｔと選択結果Ｘとを加算シフトした値（Ｔ＋Ｘ）／２を演算する段階と，演算を繰り返し制御する段階とを含む。
【００２３】
図２は，本発明の第２の実施形態の乗算剰余演算装置の構成図である。第１の実施形態とは，入力部２０１において，ＡＮとして，Ａ−Ｎを入力する点が異なる。処理手順アルゴリズムは第１の実施形態と同様であるが，選択部２０２で選択されるＡＮは，ＡＮ＝Ａ−Ｎであり，これは負の値となることがある。したがって，演算部２０３，記憶部２０４等は，符号付きの値を処理できる機能が必要となる。以上を制御部２０５が制御する。
【００２４】
以上の処理により，Ａ×Ｂ×Ｒ−１（ｍｏｄＮ）が，Ｔに求まる。このとき，Ｔの値の範囲は，−Ｎ≦Ｔ＜ｍａｘ（Ａ，Ｎ）となる。Ｔ＜０の場合には，Ｔに，Ｎを加算した値を求めることにより，非負の演算結果を求めることもできる。
【００２５】
また，選択部２０２へはＮを入力する形態を記載したが，−Ｎを入力する形態も可能である。
【００２６】
以上説明したように，本発明の第２の実施形態によれば，上記第１の実施形態と同様に高速化が達成されるとともに，演算結果の補正処理の判定が，Ｎとの比較ではなく，単純に符号判定のみで可能となる。
【００２７】
［第３の実施形態］
本発明の第３の実施形態の乗算剰余演算方法は，上記第１または第２の実施形態において，入力段階では，Ｎ，Ａ，および，Ｂのみを入力し，ＡとＮからＡＮを演算する段階をさらに含む。
【００２８】
図３は，本発明の第３の実施形態の乗算剰余演算装置の構成図である。第３の実施形態では，第１の実施形態もしくは第２の実施形態において，入力として事前に計算が必要であったＡＮ＝Ａ＋Ｎ，もしくは，ＡＮ＝Ａ−Ｎを，入力Ａ，Ｎから演算して求めるＡＮ演算部３０６を設けている。したがって，入力部３０１は，Ｎ，Ａ，Ｂのみを入力する。選択部３０２は，ＡＮ演算部３０６の演算結果を選択候補のＡＮとして参照する。演算部３０３，記憶部３０４，制御部３０５の機能は，第１の実施形態もしくは第２の実施形態と同様である。
【００２９】
処理手順は，ＡＮを求める演算手順の後に，第１の実施形態もしくは第２の実施形態と同様の処理を行う。
【００３０】
以上説明したように，本発明の第３の実施形態によれば，第１の実施形態，もしくは第２の実施形態のように，ＡＮ＝Ａ＋Ｎ，もしくはＡＮ＝Ａ−Ｎを事前に計算しておく必要がなく，Ｎ，Ａ，Ｂのみを入力とすることが可能になる。
【００３１】
［第４の実施形態］
本発明の第４の実施形態の乗算剰余演算方法は，上記第１，第２，または第３の実施形態において，選択段階は，上記の選択処理に加えてさらに，Ｂの状態のみに依存して０もしくはＡを選択する処理を行い，演算段階は，上記の演算処理に加えてさらに，演算処理のシフトにより切り捨てられる最下位桁を取り出す処理を行い，演算段階より順次取り出された下位桁を出力する段階をさらに含む。
【００３２】
図４は，本発明の第４の実施形態の乗算剰余演算装置の構成図である。第１の実施形態，第２の実施形態，もしくは第３の実施形態において，剰余乗算に加えて，通常の乗算を処理する機能を追加する。本実施形態では，入力部４０１において，ＡＮとしての入力は特定せずに記載するが，第１の実施形態と同様に，ＡＮ＝Ａ＋Ｎを入力するか，第２の実施形態と同様に，ＡＮ＝Ａ−Ｎを入力するか，または，第３の実施形態と同様に，ＡＮ演算部を設ける，等の構成が可能である。
【００３３】
選択部４０２は，剰余乗算時には表１に従った選択を行うが，通常の乗算時には，Ｂのあるビットｂｉの状態に応じて，０，Ａのうちのいずれかを選択する。例えば，演算モードを表す値を
ｍｏｄｅ（１：剰余乗算，０：通常乗算）
とすると，表２に示すような選択を行う。
【００３４】
【表２】
2004170642.tif 000004
【００３５】
演算部４０３は，加算シフト処理により加算値の最下位桁は破棄していたが，これを取り出すことが可能となるようにする。演算部４０３より順次取り出される加算値の最下位桁を，下位桁出力部４０６で出力する。記憶部４０４は，演算部４０３の演算結果を記憶する。以上を制御部４０５で制御する。
【００３６】
以上の処理により，剰余乗算処理時には，第１，第２，または第３の実施形態と同様の結果がＴに得られ，通常乗算時には，乗算結果の下位桁が下位桁出力部４０６から出力され，上位桁がＴに得られる。
【００３７】
以上説明したように，本発明の第４の実施形態によれば，第１の実施形態，第２の実施形態，または第３の実施形態の効果に加えて，通常の乗算を処理することが可能となる。
【００３８】
［第５の実施形態］
本発明の第５の実施形態の乗算剰余演算方法は，上記第１，第２，第３，または第４の実施形態において，複数の選択段階と，複数の演算段階とを含む。そして，１つ目の選択段階は，記憶段階で保持するＴを中間結果として選択処理し，１つ目の演算段階は，記憶段階で保持するＴを中間結果として演算処理する。そして，２つ目以降の選択段階は，その１つ前の演算段階の演算結果を中間結果として選択処理し，２つ目以降の演算段階は，その１つ前の演算段階の演算結果を中間結果として演算処理する。
【００３９】
図５は，本発明の第５の実施形態の乗算剰余演算装置の構成図である。第５の実施形態では，第１，第２，第３，もしくは第４の実施形態における，選択部，演算部相当の処理手段を複数段設ける。本実施形態では，それぞれ２つ設けた２段の構成例について説明するが，２段よりも多く設ける構成とすることも可能である。また，本実施形態では，入力部５０１において，ＡＮとしての入力を特定せずに記載するが，第１の実施形態と同様に，ＡＮ＝Ａ＋Ｎを入力するか，第２の実施形態と同様に，ＡＮ＝Ａ−Ｎを入力するか，または第３の実施形態と同様に，ＡＮ演算部を設ける，等の構成が可能である。
【００４０】
選択部１（５０２）は，ＴおよびＡのそれぞれの最下位ビットｔ０，ａ０と，Ｂのあるビットｂｉの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。演算部１（５０３）は，選択部１（５０２）の選択結果Ｘ１と中間結果Ｔから
（Ｔ＋Ｘ１）／２
を演算し，これを１段目の演算結果Ｙ１とする。
【００４１】
選択部２（５１２）は，演算部１（５０３）の演算結果であるＹ１およびＡのそれぞれの最下位ビットｙ１０，ａ０と，Ｂの別のビットｂｉ＋１の状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。
【００４２】
演算部２（５１３）は，選択部２（５１２）の選択結果Ｘ２と，１段前の演算部である演算部１（５０３）の演算結果Ｙ１から
（Ｙ１＋Ｘ２）／２
を演算し，これを２段目の演算結果Ｙ２とする。そして，最終段の演算結果である２段目の演算結果Ｙ２を新たなＴとして記憶部５０４に記憶させる。以上を制御部５０５が制御する。
【００４３】
以上のような構成を用いて，以下の処理手順アルゴリズムを実行する。
Ｔ＝０
ｆｏｒ  ｉ＝０  ｔｏ  ｎ−１  ｓｔｅｐ  ２
Ｘ１＝ｓｅｌｅｃｔ（Ａ，Ｎ，ＡＮ；ｔ０，ａ０，ｂｉ）
Ｙ１＝（Ｔ＋Ｘ１）／２
Ｘ２＝ｓｅｌｅｃｔ（Ａ，Ｎ，ＡＮ；ｙ１０，ａ０，ｂｉ＋１）
Ｙ２＝（Ｙ１＋Ｘ２）／２
Ｔ＝Ｙ２
【００４４】
ここで，選択部１（５０２）および選択部２（５１２）の処理ｓｅｌｅｃｔは，ｂｉ，ｔ０，ａ０，もしくはｂｉ＋１，ｙ１０，ａ０の状態に応じて，表１もしくは表２のように，０，Ａ，Ｎ，ＡＮのいずれかを選択する。１回の繰り返し当たり，Ｂの２つのビットに関して処理するので，ｉは２ずつ増加させる。
【００４５】
以上の処理により，Ａ×Ｂ×Ｒ−１（ｍｏｄＮ）が，Ｔに求まる。得られた値の範囲等は，第１もしくは第２の実施形態と同様である。
【００４６】
また，第４の実施形態と同様に通常の演算機能を追加する場合は，各選択部の選択処理を表２のような選択とし，各演算部から各加算値の最下位ビットをそれぞれ取り出すという実施形態とすることも可能である。
【００４７】
以上説明したように，本発明の第５の実施形態によれば，１回の繰り返し当たりに複数段の演算処理を行うように構成したので，構成する段数に反比例して繰り返し回数を少なくすることが可能となり，第１，第２，第３，もしくは第４の実施形態と比べてさらに高速に処理することが可能となる。
【００４８】
［第６の実施形態］
本発明の第６の実施形態の乗算剰余演算方法は，上記第２，第３，第４，または第５の実施形態において，演算段階の加算シフト演算処理前の加算結果を出力する出力段階をさらに含む，そして，選択段階は，選択処理に加えてさらに，中間結果の符号の状態に応じて０もしくはＮを選択する処理を行う。
【００４９】
図６は，本発明の第６の実施形態の乗算剰余演算装置の構成図である。第６の実施形態では，第２，第３，第４，または第５の実施形態における選択部，演算部の機能を拡張することにより，従来技術のＳｔｅｐ４相当の補正処理を可能とする機能を設ける。
【００５０】
本実施形態では，第５の実施形態における選択部１，演算部１に対して機能を拡張する構成例について説明するが，第２，第３，第４の実施形態における選択部，演算部に対して機能を拡張する構成とすることも可能である。また，第５の実施形態と同様，２段以上の構成とすることも可能である。
【００５１】
入力部６０１は，ＡＮ＝Ａ−Ｎを入力する形態で記載するが，第３の実施形態と同様に，ＡＮ演算部を設ける構成も可能である。拡張選択部６０２は，通常時は第５の実施形態と同様，ＴおよびＡのそれぞれの最下位ビットｔ０，ａ０と，Ｂのあるビットｂｉの状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。補正処理時は，Ｔの符号に応じてＴ＜０ならばＮを，それ以外は０を選択する。
【００５２】
拡張演算部６０３は，拡張演算部６０２の選択結果Ｘ１と中間結果Ｔから
Ｔ＋Ｘ１
を演算し，これを補正出力部６０６に出力するとともに，
（Ｔ＋Ｘ１）／２
を１段目の演算結果Ｙ１とする。
【００５３】
選択部２（６１２）は，拡張演算部６０３の演算結果であるＹ１およびＡのそれぞれの最下位ビットｙ１０，ａ０と，Ｂの別のビットｂｉ＋１の状態に応じて，０，Ａ，Ｎ，ＡＮのうちのいずれかを選択する。
【００５４】
演算部２（６１３）は，選択部２（６１２）の選択結果Ｘ２と，１段前の演算部である拡張演算部６０３の演算結果Ｙ１から
（Ｙ１＋Ｘ２）／２
を演算し，これを２段目の演算結果Ｙ２とする。そして，最終段の演算結果である２段目の演算結果Ｙ２を新たなＴとして記憶部６０４に記憶させる。以上を制御部６０５が制御する。
【００５５】
以上のような構成を用いて，第５の実施形態と同様の処理手順アルゴリズムを実行する。その後，拡張選択部６０２，拡張演算部６０３を用いて以下の処理と同等な処理を行う。
【００５６】
ｉｆ（Ｔ＜０）
ｔｈｅｎ  Ｚ＝Ｔ＋Ｎ
ｅｌｓｅ  Ｚ＝Ｔ＋０
【００５７】
このとき，拡張選択部６０２は，通常の表１もしくは表２に従った選択ではなく，表３に従った選択を行う。拡張演算部６０３は，シフト処理前の加算結果Ｚを補正出力部６０６へ出力する。
【００５８】
【表３】
2004170642.tif 000005
【００５９】
以上の処理により，Ａ×Ｂ×Ｒ−１（ｍｏｄＮ）が，Ｚとして補正出力部６０６へ出力される。得られた値Ｚの範囲は，
９≦Ｚ＜ｍａｘ（Ａ，Ｎ）
となり，従来技術のＳｔｅｐ４の補正処理と同等な処理を施した値を求めることができる。
【００６０】
以上説明したように，本発明の第６の実施形態によれば，第２，第３，第４，または第５の実施形態において，得られた結果が負となった場合にＮを加算する処理を，選択部，演算部へのわずかな機能追加で実現することが可能となり，従来技術のＳｔｅｐ４相当の演算結果の補正処理も含めて処理することが可能となる。
【００６１】
本発明の第７の実施形態の乗算剰余演算方法は，上記第１，第２，第３，第４，第５，または第６の実施形態において，演算段階は，演算処理の前に，演算モードを選択する処理を行う。そして，演算モードの選択の結果，整数演算モードでは通常の演算処理を行い，多項式演算モードでは，各演算段階の加減算処理における各桁から上位桁への桁上がりまたは桁下がりを抑制した状態で演算処理を行う。
【００６２】
本実施形態では，上記第１，第２，第３，第４，第５，または第６の実施形態の乗算剰余処理に対して，ＧＦ（２）上の多項式の剰余環上の乗算処理機能を追加する。ここで，ＧＦ（２）上の多項式の剰余環上の乗算は，以下のようなものである。
【００６３】
ＧＦ（２）の元を係数にもつ多項式で，０次の係数が０でない多項式Ｎ（ｘ）を法とし，入力多項式Ａ（ｘ），Ｂ（ｘ），および，Ｒ（ｘ）＝ｘｎに対して，
Ａ（ｘ）×Ｂ（ｘ）×Ｒ（ｘ）−１ｍｏｄＮ（ｘ）
を求める。
【００６４】
上記各実施形態における，整数上の各値の表現，
Ａ＝Σａｉ２ｉ
に対応して，ＧＦ（２）上多項式の表現を，
Ａ（ｘ）＝Σａｉｘｉ
として，入出力する。
【００６５】
整数上の加減算とＧＦ（２）上多項式の加減算の違いは，整数上では各桁での加減算において桁上がりおよび桁下がりが発生するのに対して，ＧＦ（２）上多項式では，桁上がりおよび桁下がりが発生しない。
【００６６】
したがって，上記各実施形態中の構成要素で加減算処理を含む構成要素に対してモード選択入力を与え，整数演算モードでは桁上がりおよび桁下がりを処理し，多項式演算モードでは桁上がりおよび桁下がり処理を抑制することにより，上記各実施形態のそれぞれと同様の構成，同様の処理手順で，ＧＦ（２）上の多項式の剰余環上の乗算処理機能を追加することができる。
【００６７】
図７は，本発明の第７の実施形態の乗算剰余演算装置の構成図である。本実施形態では，例として，第３の実施形態に対してＧＦ（２）上の多項式の剰余環上の乗算処理機能を追加する場合の構成を示す。その他の第１，第２，第４から第６の各実施形態に対しても，各構成要素のうち加減算処理を含む構成要素に対してモード選択入力を与え，整数演算モードでは桁上がりおよび桁下がりを処理し，多項式演算モードでは桁上がりおよび桁下がり処理を抑制する機能を追加した演算部とする実施形態とすることも可能である。
【００６８】
第３の実施形態から拡張された機能は，モード選択入力７０７であり，整数演算モードで処理するか，多項式演算モードで処理するかの選択情報を入力する。演算部７０３では，整数演算モードでは通常の加算シフト処理を行い，多項式演算モードでは，整数演算モードでの加算の桁上がりを抑制した処理，すなわち，排他的論理和シフト処理を行う。
【００６９】
ＡＮ演算部７０６では，第１の実施形態同様に，ＡＮ＝Ａ＋Ｎを用いる形態では桁上がりを，第２の実施形態同様に，ＡＮ＝Ａ−Ｎを用いる形態では桁下がりを，モード選択入力により抑制し，多項式演算モードでは，排他的論理和処理を行う。その他の構成要素の機能は，第３の実施形態と同様である。
【００７０】
入出力は，整数演算モードでは数値で，多項式演算モードでは対応する上記の表現の係数で入出力する。
【００７１】
処理手順も，モード選択入力を与えた後，同様に処理する。このとき，多項式演算モードでは，演算部７０３において
（Ｔ（ｘ）＋Ｘ（ｘ））／ｘ
を求めていることに相当し，ＡＮ演算部において，
ＡＮ（ｘ）＝Ａ（ｘ）＋Ｎ（ｘ）
を求めていることに相当する。
【００７２】
以上の処理により，整数演算モードにおいては，第１，第２，第３，第４，第５，または第６の実施形態と同様の乗算剰余処理がなされ，多項式演算モードにおいては，
Ａ（ｘ）×Ｂ（ｘ）×Ｒ（ｘ）−１ｍｏｄＮ（ｘ）
を求める処理がなされる。
【００７３】
また，本実施形態において，上記第１，第２，第３，第４，第５，または第６の実施形態の各演算部の整数演算機能をすべて排除し，多項式演算専用とする実施形態も可能である。
【００７４】
以上説明したように，本発明の第７の実施形態によれば，第１，第２，第３，第４，第５，もしくは第６の実施形態における乗算剰余処理に加えて，ＧＦ（２）上の多項式の剰余環上の乗算処理も処理することが可能となる。
【００７５】
本発明の第８の実施形態の乗算剰余演算方法は，上記第１，第２，第３，第４，第５，第６，または第７の実施形態において，記憶段階は，複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果を保持する分割記憶処理を行う。そして，演算段階は，複数のブロックに分割された記憶手段の各ブロックにおいて，追加の桁上がりビットを含む中間結果と，選択段階の選択結果から新たな追加の桁上がりビットを含む中間結果とを演算する分割演算処理を行う。
【００７６】
本実施形態では，上記第１，第２，第３，第４，第５，第６，または第７の実施形態の演算処理において，例えば１０２４ビットというような非常に大きな桁数の演算処理を行う場合に，各実施形態において加算シフト処理を行うそれぞれの演算部相当の構成要素の加算処理に伴う桁上がりの伝播の遅延が，処理速度の低下に影響を与えるような場合に対する解決方法を提供する。
【００７７】
図８は，本発明の第８の実施形態の乗算剰余演算装置の構成図である。本実施形態では，例として，上記第１もしくは第２の実施形態における演算部と記憶部に対して本実施形態を適用する形態について説明するが，その他の実施形態においても同様に，加算シフト処理を行う演算部相当の構成要素部と，中間結果を保持する記憶部に対して本実施形態を適用する形態とすることも可能である。
【００７８】
本実施形態のように，上記第１もしくは第２の実施形態相当の構成に対して実施する場合は，演算部，記憶部が，それぞれブロックに分割された分割演算部８０３，分割記憶部８０４となる。
【００７９】
本実施形態では，中間結果を複数のいくつかのブロックに分割し，各ブロックにおいて追加の桁上がりビットを含む形で中間結果を表現する。ここでは，説明を簡単にするため，入力Ｎ，Ａのサイズをｎビットとし，これをｗビットずつのｍ個のブロックに分割し，ｎ＝ｍ×ｗであるものとして説明する。但し，各ブロックがすべて同じとは限らず，異なるビット幅をもつ複数のブロックに分割するような実施形態とすることも可能である。
【００８０】
ＡＮはｎ＋１ビットで表現されているものとし，第２の実施形態のようにＡＮ＝Ａ−Ｎの場合は，ｎ＋１ビットの２補数で表現されているものとする。
【００８１】
選択部８０２の選択結果Ｘは，ｎ＋１ビット必要である。これを複数のブロックに分割された演算要素を持つ分割演算部８０３に入力するため，便宜的に以下のように表現する。
Ｘ＝ΣＸｊ２ｗｊ
【００８２】
ここで，和は，ｊ＝０，・・・，ｍ−１にわたる。各Ｘｊはそれぞれｗビットで，最上位のＸｍ−１のみｗ＋１ビットとする。
【００８３】
分割演算部に入力される中間結果をＹ，出力される新たな中間結果をＺとする。本実施形態の場合は，記憶部８０４のＴが中間結果として入力され，出力される新たな中間結果は記憶部８０４に記憶させる。第５の実施形態のように複数段で構成する場合は，前の段から出力される中間結果を次の段へ入方する。
【００８４】
中間結果Ｙ，Ｚは，ブロックに分割された以下のような表現とする。
Ｙ＝ΣＹｊ２ｗｊ
Ｚ＝ΣＺｊ２ｗｊ
【００８５】
ここで，和は，ｊ＝０，・・・，ｍ−１にわたる。各ＹｊとＺｊはそれぞれブロックの幅ｗより１ビット大きいｗ＋１ビットで表現する。ＡＮ＝Ａ−Ｎの場合は，それぞれ最上位の，Ｙｍ−１とＺｍ−１のみが２の補数表現されているものとする。したがって，分割記憶部８０４は，ｍ×（ｗ＋１）ビット分のデータが記憶できる記憶部とする。
【００８６】
図９は，分割演算部８０３で行われる演算の説明図である。図９では，３ブロックに分割している場合を例示している。図９中，ＦＡは全加算器，ＨＡは半加算器である。まず，各ブロックにおいてＸｊとＹｊの下位ｗビット同士の加算を，Ｙの一つ下位のブロックＹｊ−１の桁上がりビットとともに加算する。この結果，Ｕとして図に示したように，ｗ＋１ビットずつの加算結果Ｕｊが得られる。
【００８７】
これを１ビット下位ヘシフトした値を，次のように求める。Ｕｊのそれぞれのブロックにおけるｗ＋１ビットのうち，最上位と最下位のビットを除くビットは普通にシフトする。これにより，Ｚｊの下位ｗ−１ビットが得られる。
【００８８】
あるブロックの最上位ビットと，１つ上位のブロックの最下位ビットは同じ桁であるので，半加算器ＨＡを用いて加算し，得られた加算結果２ビットをＺｊの上位２ビットとする。
【００８９】
最下位のブロックでは，Ｕの最下位ビットはシフト処理により破棄される。あるいは，最下位ブロックのＸ０とＹ０の加算処理のうち，最下位ビットを算出する処理を省略してもよい。但し，第４の実施形態のように通常の乗算機能を追加する場合は，この最下位ビットを下位桁出力部へ取り出す。
【００９０】
最上位のブロックでは，Ｘ，Ｙ，およびＵの最上位ビットが同じ桁であるので，これを全加算器ＦＡを用いて加算し，得られた結果２ビットをＺの最上位ブロックＺｍ−１の上位２ビットとする。
【００９１】
また，ＡＮ＝Ａ−Ｎの場合は，Ｘ，Ｙ，Ｚの最上位ブロックは２の補数表現であるので，Ｘ，Ｙ，およびＵの最上位ビットをそれぞれｘ，ｙ，ｕで表すと，ｕ−ｘ−ｙの２の補数表現２ビットをＺｍ−１の上位２ビットとする。
【００９２】
あるいは，最上位ブロックは桁上がりビットを別に処理することはせず，Ｘｍ−１とＹｍ−１を，それぞれｗ＋１ビットのまま加算したｗ＋２ビットの加算値をＵｍ−１とし，Ｕｍ−１をシフトすることにより，Ｚｍ−１を得ているとみなすこともできる。ＡＮ＝Ａ−Ｎの場合も，この加算が２の補数表現の加算としたものと同じである。
【００９３】
以上のような演算処理により，Ｘ，Ｙをブロックに分割した表現Ｘｊ，ＹｊからＺ＝（Ｘ＋Ｙ）／２をブロックに分割した表現Ｚｊとして求めることができる。
【００９４】
なお，第６の実施形態のように，最終的にＴ＜０となった場合に，Ｔ＋Ｎと補正出力する機能を持たせる場合，上記のＵを補正出力として取り出すことができる。
【００９５】
また，第５の実施形態のように複数段で構成する場合は，図９の分割演算処理を複数段設ける構成とすることも可能である。しかしこの場合，２段目以降に入力されるＹの各ブロックの桁上がりビットに相当する最上位ビットは，前の段の演算におけるｗビット程度の桁上がり伝播遅延の影響を受けてしまう。
【００９６】
そこで，２段目以降の分割演算処理を，図１０に示すような演算処理を行うように構成するとこにより，この問題を回避することも可能である。図１０中，ＦＡは全加算器である。図１０に示す構成のように，前の段の桁上がりビットであるＹｊ−１の桁上がりビットをＵｊの演算時に足しこむことはせずに，シフト処理結果の上位２ビットを求める加算を全加算器ＦＡを用いてＹｊの桁上がりビットとともに加算するように構成する。これにより，前の段の桁上がり伝播遅延の影響を最小限にとどめることが可能となる。
【００９７】
以上説明したように，本発明の第８の実施形態によれば，第１，第２，第３，第４，第５，第６，もしくは第７の実施形態の構成にさらに，分割演算手段における加算処理の桁上がりの影響をブロツク内にとどめることができるように構成したので，例えば１０２４ビットといったような非常に大きな桁数の処理においても，桁上がりの伝播遅延による処理速度の低下を最小限にとどめることが可能となる。
【００９８】
本発明の第９の実施形態の乗算剰余演算方法は，上記第３または第８の実施形態において，演算段階は，ＡとＮからＡＮを演算するＡＮ演算処理を複数のブロックに分割し，追加の桁上がりビットを含むＡＮ値を演算する分割ＡＮ演算処理を行う。そして，選択段階は，ＡＮの追加の桁上がりビットを含めて選択する分割選択処理を行う。
【００９９】
本実施形態では，上記第３の実施形態および第８の実施形態に記載の演算処理において，例えば１０２４ビットというような非常に大きな桁数の演算処理を行う場合に，各実施形態のＡとＮからＡＮを演算するＡＮ演算部の加減算処理にともなる桁上がりもしくは桁下がりの伝播の遅延が，処理速度の低下に影響を与えるような場合に対する解決方法を提供する。
【０１００】
このため，第８の実施形態の分割演算部と同様に，上記ＡＮ演算部もブロック化して，追加の桁上がりビットを含むようなＡＮ値を演算する構成とする。これに伴って，上記選択部も，ＡＮの追加の桁上がりビットを含めて選択する構成とする。
【０１０１】
図１１は，本発明の第９の実施形態の乗算剰余演算装置の構成図である。本実施形態では，例として，上記第３の実施形態と第８の実施形態を参照して説明するが，その他の上記各実施形態に対して，第８の実施形態のような分割演算を実施する形態で，第３の実施形態のようにＡＮ演算部を持たせるような構成に対して，本実施形態を適用することも可能である。
【０１０２】
分割演算部９０３，分割記憶部９０４に加えて，分割ＡＮ演算部９０６，分割選択部９０２もブロックに分割された構成となる。
【０１０３】
図１２は，ＡＮ＝Ａ＋Ｎの場合に分割ＡＮ演算部９０６で行われる演算の説明図である。図１２では，３ブロックに分割している場合を例示している。ＡとＮをそれぞれブロック幅ｗビットずつＡｊとＮｊとして参照し，それぞれのブロックにおいて，ＡｊとＮｊの和ＡＮｊを求める。
【０１０４】
図１３は，ＡＮ＝Ａ−Ｎの場合に分割ＡＮ演算部９０６で行われる演算の説明図である。図１３では，３ブロックに分割している場合を例示している。ＡとＮをそれぞれブロック幅ｗビットずつＡｊとＮｊとして参照し，それぞれのブロックにおいて，ＡｊとＮｊの論理否定ｎｏｔ（Ｎｊ）の和ＡＮｊを求める。また，最下位のブロックでは，Ａ０とＮ０の論理否定ｎｏｔ（Ｎ０）と１の和ＡＮ０を求める。最上位ブロックでは，Ａｍ−１とＮｍ−１の論理否定ｎｏｔ（Ｎｍ−１）の和を求め，得られた和の桁上がりビットを反転したものをＡＮｍ−１とする。図１３では，Ｎｍ−１の論理否定ｎｏｔ（Ｎｍ−１）の桁上がりビットを１としたものとＡｍ−１の和として示してあるように，同様の結果が得られるさまざまな実施形態が可能である。
【０１０５】
以上によって，ＡＮとして，追加の桁上がりビットを含む表現が得られる。
【０１０６】
分割選択部９０２では，上記追加の桁上がりビットを含むＡＮも選択可能とする。Ａ，Ｎは追加の桁上がりビットを含まないので，Ａ，Ｎの追加の桁上がりビット相当の値として０を入力して選択するか，あるいは，ＡＮを選択するときのみＡＮの追加の桁上がりビットを選択し，それ以外は０を選択結果の追加の桁上がりビットとするような構成としてもよい。
【０１０７】
分割選択部９０２の選択結果Ｘは，したがって，第８の実施形態とは異なって，最上位ブロック以外のブロックも追加の桁上がりビットを含む形となる。
【０１０８】
図１４，図１５は，本実施形態における，上記第８の実施形態の図９，図１０に相当する分割演算部９０３の演算処理，および複数段の構成としたときの分割演算部の演算処理の説明図である。図中，ＦＡは全加算器である。第８の実施形態とは，選択部の選択結果Ｘが追加の桁上がりビットを含んでいる点で異なっている。
【０１０９】
したがって，図１４では，Ｕの演算時には加算されていないＸの桁上がりビットを，シフト処理時に，Ｕの最上位，最下位ビットとともに，全加算器ＦＡを用いて加算している。
【０１１０】
図１５では，図１０と同様に前の段の桁上がり伝播遅延の影響を受けるＹの桁上がりビットをＵの演算時に加算しない代わりに，Ｘの桁上がりビットをＵの演算時に加算する。
【０１１１】
また，第６の実施形態と同様な補正出力手段を設ける場合は，図１４のＵを取り出して，補正出力に用いる。このとき，Ｘの桁上がりビットが，加算されていないが，補正演算時には，Ｘは０もしくはＮであるので，桁上がりビットは０であり，加算する必要はない。
【０１１２】
以上のように，ＡＮ値の演算をブロック化して，桁上がりの影響をブロック内にとどめることが可能となる。
【０１１３】
以上説明したように，本発明の第９の実施形態によれば，第３の実施形態または第８の実施形態の構成でさらに，分割ＡＮ演算手段における加減算処理の桁上がりもしくは桁下がりの影響をブロック内にとどめることができるよう構成したので，例えば１０２４ビットといったような非常に大きな桁数の処理においても，桁上がりの伝播遅延によるＡＮの事前演算処理部分の処理速度の低下を，最小限にとどめることが可能となる。
【０１１４】
［第１０の実施形態］
本発明の第１０の実施形態の乗算剰余演算方法は，上記第９の実施形態において，入力段階は，入力値Ａを複数のブロックに分割して，追加の桁上がりビットを含む入力値Ａが入力可能な分割入力処理を行う。そして，演算段階は，追加の桁上がりビットを含む入力値Ａを用いてＡＮを演算する分割ＡＮ演算処理を行う。そして，選択手段は，追加の桁上がりビットを含む入力値Ａを用いた分割選択処理を行う。
【０１１５】
本実施形態では，上記第９の実施形態に記載の演算処理において，例えば，べき乗剰余演算処理を行うなど，乗算剰余演算の演算結果を繰り返し乗算剰余演算処理するような用途において，上記実施形態のように追加の桁上がりビットを含む形で求まっている演算結果をそのままの形で，次の演算の入力として与えることができる方法を提供する。
【０１１６】
このため，入力Ａを複数のいくつかのブロックに分割し，各ブロックにおいて追加の桁上がりビットを含むような入力Ａを入力可能とする。
【０１１７】
図１６は，本発明の第１０の実施形態の乗算剰余演算装置の構成図である。本実施形態では，例として，上記第９の実施形態を参照して説明するが，その他の上記各実施形態の構成に対しても，同様に本実施形態を適用することも可能である。
【０１１８】
入力部１００１では，入力Ａとして，複数のいくつかのブロックに分割され各プロックにおいて，追加の桁上がりビットを含むような入力Ａを入力する。
【０１１９】
分割ＡＮ演算部１００６では，Ｎと追加の桁上がりビットを含むＡからＡＮを演算する。
【０１２０】
図１７，図１８は，それぞれＡＮ＝Ａ＋Ｎと，ＡＮ＝Ａ−Ｎの場合の，分割ＡＮ演算部１００６で行われる演算の説明図である。図１７，図１８では，それぞれ３ブロックに分割している場合を例示している。第９の実施形態の図１２，図１３との違いは，入力Ａが追加の桁上がりビットを含むことである。これらのビットは，一つ上位のブロックにおける加算演算時に同時に加算する。
【０１２１】
分割選択部１００２では，ＡＮに加えて，Ａも追加の桁上がりビットを含む表現となっているので，これらを選択可能とする。これにより，分割選択部１００２の選択結果Ｘとして，追加の桁上がりビットを含む表現のＸを，分割演算部１００３に供給する。
【０１２２】
その他，分割演算部１００３，分割記憶部１００４等は，第９の実施形態と同様である。
【０１２３】
以上によって，入力Ａとして，追加の桁上がりビットを含む表現の入力を与えることが可能となる。
【０１２４】
以上説明したように，本発明の第１０の実施形態によれば，第９の実施形態の構成でさらに，入力Ａとして，追加の桁上がりビットを含むような入力を与えることが可能となるように構成したので，例えば，乗算剰余演算を繰り返して行うべき乗剰余演算等を本実施形態の演算方法を用いて行う場合に，追加の桁上がりビットを含む形で求まっている乗算剰余結果を，そのままの形で再度入力として与えて繰り返し演算を行わせることが可能となる。
【０１２５】
なお，上記本発明の実施形態の乗算剰余演算方法は，コンピュータプログラムの形態として電子記憶媒体などに記憶される他，ネットワークを介しても配信されうる。
【０１２６】
以上，添付図面を参照しながら本発明の乗算剰余演算方法および乗算剰余演算装置の好適な実施形態について説明したが，本発明はこれらの例に限定されない。いわゆる当業者であれば，特許請求の範囲に記載された技術的思想の範疇内において各種の変更例または修正例に想到し得ることは明らかであり，それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１２７】
【発明の効果】
本発明により，さらなる高速化が達成できる，乗算剰余演算方法および乗算剰余演算装置が提供できた。
【図面の簡単な説明】
【図１】図１は，本発明の第１の実施形態の構成図である。
【図２】図２は，本発明の第２の実施形態の構成図である。
【図３】図３は，本発明の第３の実施形態の構成図である。
【図４】図４は，本発明の第４の実施形態の構成図である。
【図５】図５は，本発明の第５の実施形態の構成図である。
【図６】図６は，本発明の第６の実施形態の構成図である。
【図７】図７は，本発明の第７の実施形態の構成図である。
【図８】図８は，本発明の第８の実施形態の構成図である。
【図９】図９は，図８の分割演算部で行われる演算の説明図である。
【図１０】図１０は，図８の分割演算部で行われる２段目以降の分割演算処理の説明図である。
【図１１】図１１は，本発明の第９の実施形態の構成図である。
【図１２】図１２は，図１１でＡＮ＝Ａ＋Ｎの場合に分割ＡＮ演算部で行われる演算の説明図である。
【図１３】図１３は，図１１でＡＮ＝Ａ−Ｎの場合に分割ＡＮ演算部で行われる演算の説明図である。
【図１４】図１４は，図１１の分割演算部で行われる演算の説明図である。
【図１５】図１５は，図１１の分割演算部で行われる２段目以降の分割演算処理の説明図である。
【図１６】図１６は，本発明の第１０の実施形態の構成図である。
【図１７】図１７は，図１６でＡＮ＝Ａ＋Ｎの場合の分割ＡＮ演算部で行われる演算の説明図である。
【図１８】図１８は，図１６でＡＮ＝Ａ−Ｎの場合の分割ＡＮ演算部で行われる演算の説明図である。
【符号の説明】
１０１，２０１，３０１，４０１，５０１，６０１，７０１，８０１，９０１，１００１  ・・・  入力部
１０２，２０２，３０２，４０２，７０２，８０２  ・・・  選択部
１０３，２０３，３０３，４０３，７０３  ・・・  演算部
１０４，２０４，３０４，４０４，５０４，６０４，７０４  ・・・  記憶部
１０５，２０５，３０５，４０５，５０５，６０５，７０５，８０５，９０５，１００５  ・・・  制御部
３０６，７０６  ・・・  ＡＮ演算部
４０６  ・・・  下位桁出力部
５０２  ・・・  選択部１
５０３  ・・・  演算部１
５１２，６１２  ・・・  選択部２
５１３，６１３  ・・・  演算部２
６０２  ・・・  拡張選択部
６０３  ・・・  拡張演算部
６０６  ・・・  補正出力部
７０７  ・・・  モード選択入力
８０３，９０３，１００３  ・・・  分割演算部
８０４，９０４，１００４  ・・・  分割記憶部
９０２，１００２  ・・・  分割選択部
９０６，１００６  ・・・  分割ＡＮ演算部
ＦＡ  ・・・  全加算器
ＨＡ  ・・・  半加算器
【図１】
2004170642.tif 000006
【図２】
2004170642.tif 000007
【図３】
2004170642.tif 000008
【図４】
2004170642.tif 000009
【図５】
2004170642.tif 000010
【図６】
2004170642.tif 000011
【図７】
2004170642.tif 000012
【図８】
2004170642.tif 000013
【図９】
2004170642.tif 000014
【図１０】
2004170642.tif 000015
【図１１】
2004170642.tif 000016
【図１２】
2004170642.tif 000017
【図１３】
2004170642.tif 000018
【図１４】
2004170642.tif 000019
【図１５】
2004170642.tif 000020
【図１６】
2004170642.tif 000021
【図１７】
2004170642.tif 000022
【図１８】
2004170642.tif 000023