(57)【要約】      （修正有）【課題】ビット長制限のある剰余乗算器を利用して４倍化ビット長の剰余乗算演算を行う。【解決手段】入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを一定ビット長以下のビット長の分割入力値に展開するビットデータ分割処理部と、ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出するｎ／２ビット専用剰余乗算器と、算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより前記入力値の剰余乗算演算結果としての商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算一時ビットデータ変換部を備えた。【選択図】図３
2011232404.tif 000002
【特許請求の範囲】
【請求項１】
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割部と、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出部と、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより前記入力値の剰余乗算演算結果としての商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換部とを備えたことを特徴とする剰余乗算演算装置。
【請求項２】
請求項１に記載の剰余乗算演算装置において、
前記入力値Ａ，Ｂ，およびＮそれぞれのビット長が４ｍである場合に、前記分割入力値はｍであることを特徴とする剰余乗算演算装置。
【請求項３】
請求項１または２に記載の剰余乗算演算装置において、
前記ビット長制限演算器は、１０２４ビット以下の入力値について剰余乗算を行うことを特徴とする剰余乗算演算装置。
【請求項４】
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開し、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出し、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出することを特徴とする剰余乗算演算方法。
【請求項５】
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割機能と、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出機能と、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換機能とをコンピュータに実行させることを特徴とした剰余乗算演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、剰余乗算を行う演算装置に関し、特に一定の制限ビット長以下について剰余乗算可能な演算器を利用して一定値より長いビット長の剰余乗算を行う剰余乗算演算装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
一般に、コンピュータシステムには暗号化処理用のコプロセッサとして１０２４ビット専用の剰余乗算器が組み込まれている。
暗号技術の標準化を行うＮＩＳＴ(米国国立標準技術研究所)では、暗号アルゴリズムの安全性基準である鍵長ビットを更に長くする必要があるという報告（暗号アルゴリズム２０１０年問題など）が行われており、具体的には、１０２４ビット専用剰余乗算コプロセッサに代わる２０４８ビット専用剰余乗算コプロセッサが必要とされている。
【０００３】
しかしながら、２０４８ビット専用剰余乗算コプロセッサは、１０２４ビット専用剰余乗算コプロセッサに比べて高価であることから、導入コストが膨大となってしまうといった不都合がある。
【０００４】
これに対する関連技術として、１０２４ビット専用剰余乗算コプロセッサを用いて、ビット長を２倍化し、２０４８ビットの剰余乗算として仮想的に演算（算出）を行うアルゴリズム（ビット長２倍化剰余乗算アルゴリズム）が開示されている（非特許文献１、２）。
【０００５】
上記関連技術における、ビット長２倍化剰余乗算アルゴリズムを利用した剰余乗算では、剰余乗算演算装置における
情報処理部が、図４に示すように、入力された２ｎビットデータを２分割し（１）、各ｎビットデータを更に２分割する（２）ことにより生成されたｎ／２ビットデータを、剰余乗算演算装置内に予め設けられたｎ／２剰余乗算器（ＭｕｌＭｏｄＤｉｖ）に入力する（３）。
【０００６】
次いで、このｎ／２剰余乗算器（ＭｕｌＭｏｄＤｉｖ）は、入力されたｎ／２ビットデータの演算を行い、ｎ／２ビット商データ、およびｎ／２ビット剰余データを出力し（４）、
出力されたｎ／２ビット商データおよびｎ／２ビット剰余データを結合することによりｎビット剰余データを生成して出力する（５）。
【０００７】
ここで、ｎビット剰余データは、予め設定されたｎビット剰余乗算器に入力され（６）、ｎビット剰余乗算器は、ｎビット商データ、およびｎビット剰余データを出力する（７）。
【０００８】
最後に、ｎビット商データおよびｎビット剰余データを結合し、２ｎビット剰余乗算データとして出力する（８）
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】W.Fischer，  J.P.Seifert，  "Increasing  the  bitlength  of  crypto-coprocessors",  CHES2002,  vol.2523  of  Lecture  Notes  in  Computer  Science,  Springer-Verlag,  pp.71-81  (2002).
【非特許文献２】B.Chevallier-Mames，  M.Joye，  P.Paillier，  "Faster  Double-Size  Modular  Multiplication  From  Euclidean  Multipliers"，  CHES2003，  vol.2779  of  Lecture  Notes  in  Computer  Science，  Springer-Verlag，  pp.214-227  (2003).
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記非特許文献１および２の関連技術では、暗号アルゴリズムをさらに長期的に利用できるように安全性を高める観点から考慮されたものではなく、例えば、安全性の基準となるビット長を２０４８ビット以上（例えば、４０９６ビット）へと切替が必要になった場合には適用することができないという不都合がある。
また、この場合、上記非特許文献１および２の関連技術では、２０４８ビット専用剰余乗算コプロセッサを利用する必要があるため、上述のように、１０２４ビット専用剰余乗算コプロセッサと比べ導入コストが膨大となってしまう不都合がある。
【００１１】
［発明の目的］
本発明は、上記関連技術の有する不都合を改善し、１０２４ビット専用剰余乗算コプロセッサを利用して、４倍化ビット長の剰余乗算演算を行う剰余乗算演算装置、剰余乗算演算方法、剰余乗算演算プログラムを提供することを、その目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明に係る剰余乗算演算装置は、一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置であって、前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割部と、前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出部と、前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより前記入力値の剰余乗算演算結果としての商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換部とを備えた構成をとっている。
【００１３】
又、本発明にかかる剰余乗算演算方法は、一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開し、前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出し、前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出すること特徴としている。
【００１４】
更に、本発明にかかる剰余乗算演算プログラムは、一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割機能と、前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出機能と、前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換機能とをコンピュータに実行させることを特徴としている。
【発明の効果】
【００１５】
本発明は、以上のように構成され機能するので、これによると、入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する手段と、ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する手段と、算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより前記入力値の剰余乗算演算結果としての商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する手段を備えた構成としたことにより、１０２４ビット専用剰余乗算コプロセッサを利用して４倍化ビット長である４０９６ビット長の剰余乗算演算を行うことが可能な剰余乗算演算装置、剰余乗算演算方法、および剰余乗算演算プログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明による剰余乗算演算装置における一実施形態を示す概略ブロック図である。
【図２】図１に開示した剰余乗算演算装置における動作を示すフローチャートである。
【図３】図１に開示した剰余乗算演算装置における演算内容を示す説明図である。
【図４】本発明の関連技術における演算動作の内容を示すフローチャートである。
【図５】本発明の関連技術における演算アルゴリズムの内容を示す説明図である。
【発明を実施するための形態】
【００１７】
［実施形態］
次に、本発明の実施形態について、その基本的構成内容を説明する。
【００１８】
本実施形態であるコンピュータ（剰余乗算演算装置）１００は、ビット長制限の剰余乗算器（ＭｕｌＭｏｄＤｉｖ）を備えたパーソナルコンピュータなどのコンピュータである。
【００１９】
コンピュータ１００は、図１に示すように、予め設定されたプログラム実行処理を行うことにより処理部１１０としての機能動作を実現するＣＰＵ２１０と、コンピュータ１００外部から処理部１１０に対する入力を受付ける入出力インタフェース部１２０と、ＣＰＵ２１０により実行されるプログラムおよびＣＰＵ２１０による実行処理によって生成されたデータを記憶する記憶部１３０を備えた構成を有する。
尚、処理部１１０は、ＣＰＵ２１０による予め設定されたプログラムの実行処理により実現されるものとする。
【００２０】
処理部１１０は、入出力インタフェース部１２０から入力された２ｎビット１０進データ（入力データ）を２進データに変換すると共にこの２進データをｎ／２ビット毎に分割（４分割）するビットデータ分割処理部２２０と、ｎ／２ビットデータを記憶する分割ビットデータ格納部２３０と、ｎ／２ビットデータに基づき上記ビット長制限の剰余乗算器（ＭｕｌＭｏｄＤｉｖ）を用いて一時ビットデータを算出するｎ／２ビット専用剰余乗算器２４０と、ｎ／２ビット専用剰余乗算器２４０により算出された一時ビットデータを記憶する剰余乗算一時ビットデータ格納部２５０と、算出された一時ビットデータに基づき入力データである２ｎビット１０進データの商データＱおよび剰余データＲを示す剰余乗算データに変換する剰余乗算一時ビットデータ変換部２６０と、変換された２ｎビット剰余乗算データを予め設定された出力装置（入出力インタフェース部１２０）に対して出力する剰余乗算データ出力部２７０を備えている。
【００２１】
また、ｎ／２ビット専用剰余乗算器２４０は、算出された一時ビットデータの一部である剰余データを出力する剰余データ出力部２４１と、前記一時ビットデータの一部としての商データを出力する商データ出力部２４２を有する。
【００２２】
処理部１１０は、入出力インタフェース部１２０からの入力値である整数Ａ，Ｂ，Ｎに対して、剰余乗算器ＭｕｌＭｏｄＤｉｖを利用した計算を行うことにより、商データＱおよび剰余データＲを算出する演算処理を行う。
【００２３】
尚、処理部１１０に対して入力される整数Ａ，Ｂ，Ｎ（０≦Ａ，Ｂ＜Ｎ）であるものとする。
ここで、剰余乗算器ＭｕｌＭｏｄＤｉｖにより算出される商データＱおよび剰余データＲと、整数Ａ，Ｂ，Ｎは、
2011232404.tif 000003
と表すことができるものとする。
【００２４】
ただし、商データＱおよび剰余データＲは、以下に示す（式１）により算出されるものとする。
（式１）
2011232404.tif 000004
【００２５】
尚、上記（式１）における記号［］は床関数を表し、小数点以下は切り捨てることをしめすものとする。
また、本実施形態の処理部１１０では、上記非特許文献1に開示されたＢａｓｉｃ  Ｄｏｕｂｌｉｎｇ  Ａｌｇｏｒｉｔｈｍ（図５）を適用した演算処理を行うものとする。
【００２６】
具体的には、Ｂａｓｉｃ  Ｄｏｕｂｌｉｎｇ  Ａｌｇｏｒｉｔｈｍ（図５）に示される、（Ｑ１，Ｒ１）＝ＭｕｌＭｏｄＤｉｖ（Ｂｔ，２ｎ，Ｎｔ）のおけるＢｔ，２ｎ，およびＮｔそれぞれの値をｎ／２ビット分割し、このｎ／２ビット値に対する剰余乗算器（ＭｕｌＭｏｄＤｉｖ）による再帰的な演算処理を行うことにより、（ｑ１，ｒ１）＝ＭｕｌＭｏｄＤｉｖ（２{n/2}，２{n/2}，Ｎ３）、（ｑ２，ｒ２）＝・・・、・・・、（ｑ７，ｒ７）＝ＭｕｌＭｏｄＤｉｖ（Ｂ２，０，２{n/2}）といった順序で一時ビットデータを算出する。
【００２７】
これにより、本実施形態では、２ｎビットデータを４分割することにより生成されたｎ／２ビットデータそれぞれを、ｎ／２ビット専用剰余乗算コプロセッサを用いて一時ビットデータを算出し、この一時ビットデータから２ｎビットデータに対する剰余乗算の演算結果を仮想的に求めることができる。
【００２８】
［実施形態の動作説明］
次に、本実施形態における、ｎ／２ビット剰余乗算器を利用して２ｎビットの剰余乗算演算を行う動作について、図２のフローチャートおよび図３に基づき説明する。
【００２９】
まず、入出力インタフェース部１２０からビットデータ分割処理部２２０に対して２ｎビット１０進データＡ，Ｂ，Ｎを入力する（ステップＳ１）。
【００３０】
ビットデータ分割処理部２２０は、入力された２ｎビット１０進データＡ，Ｂ，Ｎを２ｎビット２進データに変換し、更に、この２ｎビット２進データのビット長を４分割する処理を行う（ステップＳ２：ビット長４分割処理）。
これにより、Ａ，Ｂ，Ｎのビット長が４分割される
【００３１】
ここで、上記ビット長４分割処理の処理内容について、詳説する。
ビットデータ分割処理部２２０は、まず、２ｎビット１０進データＡを２ｎビット２進データに変換すると共に、以下に示すように、ｎ／４ビット毎にＡ３，Ａ２，Ａ１，Ａ０に分割する（ステップＳ２−１）。
ここで、２ｎビット１０進データであるＡについては、以下にしめす（式２）が成り立つものとする。
（式２）
2011232404.tif 000005
【００３２】
また、ビットデータ分割処理部２２０は、２ｎビット１０進データＢ、Ｎをそれぞれ２ｎビット２進データに変換すると共に、２ｎビット２進データＢをｎ／４ビット毎にＢ３，Ｂ２，Ｂ１，およびＢ０に、また、２ｎビット２進データＮをｎ／４ビット毎にＮ３，Ｎ２，Ｎ１，およびＮ０に、それぞれ分割する（ステップＳ２−２）。
【００３３】
ここで、２ｎビット１０進データであるＢ、Ｎについては、それぞれ以下の（式３）、および（式４）が成り立つものとする。
【００３４】
（式３）
2011232404.tif 000006
【００３５】
（式４）
2011232404.tif 000007
【００３６】
ここで、Ａ，Ｂ，およびＮは、
2011232404.tif 000008
を満たすものとする。
【００３７】
次に、ビットデータ分割処理部２２０は、上記ビット長４分割処理により生成された、ｎ／２ビットデータ（Ａ３，Ａ２，Ａ１，Ａ０，Ｂ３，Ｂ２，Ｂ１，Ｂ０，Ｎ３，Ｎ２，Ｎ１，およびＮ０）を、分割ビットデータ格納部２３０に格納する（ステップＳ３）。
【００３８】
次いで、ｎ／２ビット専用剰余乗算器２４０が、分割ビットデータ格納部２３０に格納されたｎ／２ビットデータに基づく演算を行い、剰余乗算一時ビットデータを算出する（ステップＳ４：剰余乗算一時ビットデータ演算機能）。
【００３９】
ここで、上記剰余乗算一時ビットデータ演算機能について、図４のフローチャートに基づき説明する。
【００４０】
（ステップＳ４の詳細説明：始まり）
まず、ｎ／２ビット専用剰余乗算器２４０が、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて再帰的な演算を行うことにより、商Ｑ1、剰余Ｒ１を求める（ステップＳ４−1）。
【００４１】
以下、ステップＳ４−１における計算処理の内容について詳説する。
このステップＳ４−１では、まず、ｎ／２ビット専用剰余乗算器２４０が、以下に示す（ステップＳ４−１−１）〜（ステップＳ４−１−７）に示す演算処理を行うことによりｑ１１〜１７、およびｒ１１〜１７を算出する。
【００４２】
（ステップＳ４−1−１）
2011232404.tif 000009
【００４３】
（ステップＳ４−1−２）
2011232404.tif 000010
【００４４】
（ステップＳ４−1−３）
2011232404.tif 000011
【００４５】
（ステップＳ４−1−４）
2011232404.tif 000012
【００４６】
（ステップＳ４−1−５）
2011232404.tif 000013
【００４７】
（ステップＳ４−1−６）
2011232404.tif 000014
【００４８】
（ステップＳ４−1−７）
2011232404.tif 000015
【００４９】
次いで、ｎ／２ビット専用剰余乗算器２４０は、上記（ステップＳ４−1−１）〜（ステップＳ４−1−７）で算出されたｑ１５，ｑ１６，ｑ１７，ｒ１３，ｒ１４，ｒ１５，ｒ１６，ｒ１７を用いて、以下に示す（式５）に基づく計算を行うことにより、商Ｑ１と剰余Ｒ１を得る（ステップＳ４−1−８）。
【００５０】
（式５）
2011232404.tif 000016
【００５１】
次いで、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ1と剰余Ｒ1を確定する（ステップＳ４−1−９）。
【００５２】
（条件式1)  ０  ＞  Ｑ１であるとき
2011232404.tif 000017
【００５３】
（条件式２）  Ｎ３  ＜  Ｑ１であるとき
2011232404.tif 000018
【００５４】
（条件式３）  ０  ＞  Ｒ１であるとき
2011232404.tif 000019
【００５５】
（条件式４）  ２{n/2}  ＜  Ｒ１であるとき
2011232404.tif 000020
【００５６】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ２および剰余Ｒ２を求める（ステップＳ４−２）。
ここで、上記Ｑ１は、当該Ｑ１における上位ビットＱ１Ｈおよび下位ビットＱ１Ｌを用いて、
2011232404.tif 000021
と表されるものとする。
【００５７】
以下、ステップＳ４−２における計算処理の内容について詳説する。
このステップＳ４−２において、ｎ／２ビット専用剰余乗算器２４０は、まず、以下に示す（ステップＳ４−２−１）〜（ステップＳ４−２−７）に示す演算処理を順次行うことにより、ｑ２１〜２７、およびｒ２１〜２７をそれぞれ算出する。
【００５８】
（ステップＳ４−２−１）
2011232404.tif 000022
【００５９】
（ステップＳ４−２−２）
2011232404.tif 000023
【００６０】
（ステップＳ４−２−３）
2011232404.tif 000024
【００６１】
（ステップＳ４−２−４）
2011232404.tif 000025
【００６２】
（ステップＳ４−２−５）
2011232404.tif 000026
【００６３】
（ステップＳ４−２−６）
2011232404.tif 000027
【００６４】
（ステップＳ４−２−７）
2011232404.tif 000028
【００６５】
次に、ｎ／２ビット専用剰余乗算器２４０は、上記（ステップＳ４−２−１）〜（ステップＳ４−２−７）で算出されたｑ２５，ｑ２６，ｑ２７，ｒ２３，ｒ２４，ｒ２５，ｒ２６，およびｒ２７を用いて、以下に示す（式６）に基づく計算を行うことにより、商Ｑ2および剰余Ｒ２を求める（ステップＳ４−２−８）。
【００６６】
（式６）
2011232404.tif 000029
【００６７】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ２および剰余Ｒ２を確定する（ステップＳ４−２−９）。
【００６８】
（条件式1)  ０＞Ｑ２であるとき
2011232404.tif 000030
【００６９】
（条件式２）  ２{n/2}  ＜  Ｑ２であるとき
2011232404.tif 000031
【００７０】
（条件式３）０＞Ｒ２であるとき
2011232404.tif 000032
【００７１】
（条件式４）２{n/2}＜Ｒ２であるとき
2011232404.tif 000033
【００７２】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ３および剰余Ｒ３を求める（ステップＳ４−３）。
【００７３】
以下、ステップＳ４−３における計算処理の内容について詳説する。
まず、ｎ／２ビット専用剰余乗算器２４０は、このステップＳ４−３において、以下に示す（ステップＳ４−３−１）〜（ステップＳ４−３−７）に示す演算処理を順次行うことによりｑ３１〜３７、およびｒ３１〜３７をそれぞれ算出する。
【００７４】
ここで、
2011232404.tif 000034
は、上位ビットである
2011232404.tif 000035
および、下位ビット
2011232404.tif 000036
を用いて、
2011232404.tif 000037
と表されるものとする。
【００７５】
（ステップＳ４−３−１）
2011232404.tif 000038
【００７６】
(ステップＳ４−３−２）
2011232404.tif 000039
【００７７】
(ステップＳ４−３−３)
2011232404.tif 000040
【００７８】
（ステップＳ４−３−４）
2011232404.tif 000041
【００７９】
(ステップＳ４−３−５）
2011232404.tif 000042
【００８０】
(ステップＳ４−３−６）
2011232404.tif 000043
【００８１】
(ステップＳ４−３−７）
2011232404.tif 000044
【００８２】
次に、ｎ／２ビット専用剰余乗算器２４０は、上記（ステップＳ４−３−１）〜（ステップＳ４−３−７）で算出されたｑ３５，ｑ３６，ｑ３７，ｒ３３，ｒ３４，ｒ３５，ｒ３６，およびｒ３７を用いて、以下に示す（式７）に基づく計算を行うことにより、商Ｑ３および剰余Ｒ３を求める（ステップＳ４−３−８）。
【００８３】
（式７）
2011232404.tif 000045
【００８４】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ３と剰余Ｒ３を確定する（ステップＳ４−３−９）。
【００８５】
（条件式1）  ０＞Ｑ３であるとき
2011232404.tif 000046
【００８６】
（条件式２）  ２{n/2}＜Ｑ３であるとき
2011232404.tif 000047
【００８７】
（条件式３）  ０＞Ｒ３であるとき
2011232404.tif 000048
【００８８】
（条件式４）  ２{n/2}＜Ｒ３であるとき
2011232404.tif 000049
【００８９】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ４および剰余Ｒ４を求める（ステップＳ４−４）。
【００９０】
以下、このステップＳ４−４における計算処理の内容について詳説する。
ｎ／２ビット専用剰余乗算器２４０は、このステップＳ４−４において、以下に示す（ステップＳ４−４−１）〜（ステップＳ４−４−７）に示す演算処理を順次行うことによりｑ４１〜４７、およびｒ４１〜４７をそれぞれ算出する。
【００９１】
（ステップＳ４−４−１）
2011232404.tif 000050
【００９２】
（ステップＳ４−４−２）
2011232404.tif 000051
【００９３】
（ステップＳ４−４−３）
2011232404.tif 000052
【００９４】
（ステップＳ４−４−４）
2011232404.tif 000053
【００９５】
（ステップＳ４−４−５)
2011232404.tif 000054
【００９６】
（ステップＳ４−４−６）
2011232404.tif 000055
【００９７】
（ステップＳ４−４−７）
2011232404.tif 000056
【００９８】
次に、ｎ／２ビット専用剰余乗算器２４０は、上記（ステップＳ４−４−１）〜（ステップＳ４−４−７）で算出されたｑ４５，ｑ４６，ｑ４７，ｒ４３，ｒ４４，ｒ４５，ｒ４６，およびｒ４７を用いて、以下に示す（式８）に基づく計算を行うことにより、商Ｑ４および剰余Ｒ４を算出する（ステップＳ４−４−８）。
【００９９】
（式８）
2011232404.tif 000057
【０１００】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ４と剰余Ｒ４を確定する（ステップＳ４−４−９）。
【０１０１】
（条件式１）  ０＞Ｑ４であるとき
2011232404.tif 000058
【０１０２】
（条件式２）  ２{n/2}＜Ｑ４であるとき
2011232404.tif 000059
【０１０３】
（条件式３）  ０＞Ｒ４であるとき
2011232404.tif 000060
【０１０４】
（条件式４）  ２{n/2}＜Ｒ４であるとき
2011232404.tif 000061
【０１０５】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ５および剰余Ｒ５を求める（ステップＳ４−５）。
【０１０６】
ここで、（Ｑ３＋Ｑ４）は、当該（Ｑ３＋Ｑ４）の上位ビット（Ｑ３＋Ｑ４）Ｈおよび下位ビット（Ｑ３＋Ｑ４）Ｌを用いて、
2011232404.tif 000062
と表されるものとする。
【０１０７】
以下、ステップＳ４−５における計算処理の内容について詳説する。
このステップＳ４−５において、まず、ｎ／２ビット専用剰余乗算器２４０は、以下に示す（ステップＳ４−５−１）〜（ステップＳ４−５−７）に示す演算処理を順次行うことにより、ｑ５１〜５７、およびｒ５１〜５７をそれぞれ算出する。
【０１０８】
（ステップＳ４−５−１）
2011232404.tif 000063
【０１０９】
（ステップＳ４−５−２）
2011232404.tif 000064
【０１１０】
（ステップＳ４−５−３)
2011232404.tif 000065
【０１１１】
（ステップＳ４−５−４）
2011232404.tif 000066
【０１１２】
（ステップＳ４−５−５）
2011232404.tif 000067
【０１１３】
（ステップＳ４−５−６）
2011232404.tif 000068
【０１１４】
（ステップＳ４−５−７）
2011232404.tif 000069
【０１１５】
次いで、上記（ステップＳ４−５−１）から（ステップＳ４−５−７）まで算出したｑ５５，ｑ５６，ｑ５７，ｒ５３，ｒ５４，ｒ５５，ｒ５６，ｒ５７を用いて、以下示す（式９）に基づき商Ｑ５および剰余Ｒ５を求める（ステップＳ４−５−８）。
【０１１６】
（式９）
2011232404.tif 000070
【０１１７】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ５と剰余Ｒ５を確定する（ステップＳ４−５−９）。
【０１１８】
（条件式１）０＞Ｑ５であるとき
2011232404.tif 000071
【０１１９】
（条件式２）２{n/2}＜Ｑ５であるとき
2011232404.tif 000072
【０１２０】
（条件式３）０＞Ｒ５であるとき
2011232404.tif 000073
【０１２１】
（条件式４）２{n/2}＜Ｒ５であるとき
2011232404.tif 000074
【０１２２】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ６および剰余Ｒ６を求める（ステップＳ４−６）。
【０１２３】
ここで、上記Ｒ２は、当該Ｒ２の上位ビットＲ２Ｈおよび下位ビットＲ２Ｌを用いて、
2011232404.tif 000075
と表されるものとする。
【０１２４】
以下、ステップＳ４−６における計算処理の内容について詳説する。
このステップＳ４−６において、ｎ／２ビット専用剰余乗算器２４０は、まず、以下に示す（ステップＳ４−６−１）〜（ステップＳ４−６−７）に示す演算処理を順次行うことにより、ｑ６１〜６７、およびｒ６１〜６７をそれぞれ算出する。
【０１２５】
（ステップＳ４−６−１）
2011232404.tif 000076
【０１２６】
（ステップＳ４−６−２）
2011232404.tif 000077
【０１２７】
（ステップＳ４−６−３）
2011232404.tif 000078
【０１２８】
（ステップＳ４−６−４）
2011232404.tif 000079
【０１２９】
（ステップＳ４−６−５）
2011232404.tif 000080
【０１３０】
（ステップＳ４−６−６）
2011232404.tif 000081
【０１３１】
（ステップＳ４−６−７）
2011232404.tif 000082
【０１３２】
次いで、上記（ステップＳ４−６−１）〜（ステップＳ４−６−７）で算出したｑ６５，ｑ６６，ｑ６７，ｒ６３，ｒ６４，ｒ６５，ｒ６６，およびｒ６７を用いて、以下示す（式１０）に基づき商Ｑ６および剰余Ｒ６を求める（ステップＳ４−６−８）。
（式１０）
2011232404.tif 000083
【０１３３】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ６と剰余Ｒ６を確定する（ステップＳ４−６−９）。
【０１３４】
（条件式１）０＞Ｑ６であるとき
2011232404.tif 000084
【０１３５】
（条件式２）  ２{n/2}＜Ｑ６であるとき
2011232404.tif 000085
【０１３６】
（条件式３）０＞Ｒ６であるとき
2011232404.tif 000086
【０１３７】
（条件式４）２{n/2}＜Ｒ６であるとき
2011232404.tif 000087
【０１３８】
次いで、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器ＭｕｌＭｏｄＤｉｖを用いて、再帰的な演算を行うことにより、商Ｑ７および剰余Ｒ７を求める（ステップＳ４−７）。
【０１３９】
以下、ステップＳ４−７における計算処理の内容について詳説する。
まず、ｎ／２ビット専用剰余乗算器２４０は、このステップＳ４−７において、以下に示す（ステップＳ４−７−１）〜（ステップＳ４−７−７）に示す演算処理を順次行うことによりｑ７１〜７７、およびｒ７１〜７７をそれぞれ算出する。
【０１４０】
（ステップＳ４−７−１）
2011232404.tif 000088
【０１４１】
（ステップＳ４−７−２）
2011232404.tif 000089
【０１４２】
（ステップＳ４−７−３）
2011232404.tif 000090
【０１４３】
（ステップＳ４−７−４）
2011232404.tif 000091
【０１４４】
（ステップＳ４−７−５）
2011232404.tif 000092
【０１４５】
（ステップＳ４−７−６）
2011232404.tif 000093
【０１４６】
（ステップＳ４−７−７）
2011232404.tif 000094
【０１４７】
次いで、上記（ステップＳ４−７−１）〜（ステップＳ４−７−７）で算出したｑ７５，ｑ７６，ｑ７７，ｒ７３，ｒ７４，ｒ７５，ｒ７６，およびｒ７７を用いて、以下示す（式１１）に基づき商Ｑ７および剰余Ｒ７を求める（ステップＳ４−７−８）。
【０１４８】
（式１１）
2011232404.tif 000095
【０１４９】
更に、ｎ／２ビット専用剰余乗算器２４０は、以下に示す４つの条件式（１〜４）に基づき、商Ｑ７と剰余Ｒ７を確定する（ステップＳ４−７−９）。
【０１５０】
（条件式1)
０＞Ｑ７であるとき
2011232404.tif 000096
【０１５１】
（条件式２）
２{n/2}＜Ｑ７であるとき、
2011232404.tif 000097
【０１５２】
（条件式３）
０＞Ｒ７であるとき
2011232404.tif 000098
【０１５３】
（条件式４）
２{n/2}＜Ｒ７であるとき
2011232404.tif 000099
（「ステップＳ４」終わり）
【０１５４】
次に、ｎ／２ビット専用剰余乗算器２４０は、ｎ／２ビット剰余乗算器で算出した剰余乗算一時ビットデータ（Ｑ１〜Ｑ７、Ｒ１〜Ｒ７）を剰余乗算一時ビットデータ格納部２５０に格納する（ステップＳ５）。
【０１５５】
次いで、剰余乗算一時ビットデータ変換部２６０が、剰余乗算一時ビットデータ格納部２５０に格納された剰余乗算一時ビットデータを取得すると共に「剰余乗算データ」を算出する。
剰余乗算データ出力部２７０は、算出された「剰余乗算データ」を出力する（ステップＳ６）。
【０１５６】
次いで、剰余乗算一時ビットデータ変換部２６０は、ステップＳ４で算出された剰余乗算一時ビットデータ（Ｒ３，Ｒ４，Ｒ５，Ｒ６，Ｒ７，Ｑ５，Ｑ６，およびＱ７）を用いて、以下示す（式１２）に基づき商データＱおよび剰余データＲを算出する（ステップＳ６−１）。
【０１５７】
（式１２）
2011232404.tif 000100
【０１５８】
また、剰余乗算一時ビットデータ変換部２６０は、以下に示す４つの条件式（１〜４）に基づき、商データＱと剰余データＲとを確定する（ステップＳ６−２）。
【０１５９】
（条件式１）  ０＞Ｑであるとき
2011232404.tif 000101
【０１６０】
（条件式２）  Ｎ３２＜Ｑであるとき
2011232404.tif 000102
【０１６１】
（条件式３）  ０＞Ｒであるとき
2011232404.tif 000103
【０１６２】
（条件式４）  ２ｎ＜Ｒであるとき
2011232404.tif 000104
【０１６３】
最後に、剰余乗算一時ビットデータ変換部２６０は、ステップＳ６−２で得られた商データＱおよび剰余データＲを用いて、以下に示す（式１３）の基づく計算を行うことにより、２ｎビット剰余乗算の演算結果としての、Ａ・Ｂ（ｍｏｄ  Ｎ）を得る（ステップＳ６−３）。
【０１６４】
（式１３）
2011232404.tif 000105
【０１６５】
以上のように、本実施形態では、単一の１０２４ビット剰余乗算器（ｎ／２ビット専用剰余乗算器）を用いて再帰的な演算を行うことにより、４０９６ビットの剰余乗算演算を行うことが可能となる。
【０１６６】
尚、本実施形態では、上述のように、単一のｎ／２ビット剰余乗算器を用いて再帰的な演算処理を行う。このため、異なる２つの剰余乗算器を用いたシステムと比べて実行回数が多くなる。
例えば、ｎ／２ビットおよびnビットのビット長の剰余乗算器を利用して４０９６ビットの剰余乗算演算を行う場合、剰余乗算器(ｎ／２ビット)による実行回数が１４回、剰余乗算器(nビット)による実行回数が７回となる（図４）。これに対して、本実施形態における剰余乗算器(ｎ／２ビット)の実行回数は、４９回となる。
【０１６７】
しかしながら、ｎ／２ビットおよびnビットのビット長の剰余乗算器を４０９６ビットの剰余乗算演算用に利用するには、１０２４ビット剰余乗算器に比して高価な２０４８ビット剰余乗算器を使用する必要があり、システム構築にかかるコストが膨大となってしまう。
【０１６８】
これに対して、本実施形態では、２０４８ビット剰余乗算器を使用することなく、４０９６ビットの剰余乗算演算を行うシステムを構築することができるため、４０９６ビットの剰余乗算演算用のシステム構築にかかるコストを有効に抑制することが可能となる。
【０１６９】
上述した実施形態については、その新規な技術的内容の要点をまとめると、以下のようになる。
尚、上記の実施形態の一部又は全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
【０１７０】
（付記１）
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割部と、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出部と、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより前記入力値の剰余乗算演算結果としての商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換部とを備えたことを特徴とする剰余乗算演算装置。
【０１７１】
（付記２）
付記１に記載の剰余乗算演算装置において、
前記入力値Ａ，Ｂ，およびＮそれぞれのビット長が４ｍである場合に、前記分割入力値はｍであることを特徴とする剰余乗算演算装置。
【０１７２】
（付記３）
付記１または２に記載の剰余乗算演算装置において、
前記ビット長制限演算器は、１０２４ビット以下の入力値について剰余乗算を行うことを特徴とする剰余乗算演算装置。
【０１７３】
（付記４）
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開し、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出し、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出することを特徴とする剰余乗算演算方法。
【０１７４】
（付記５）
一定ビット長以下の長さのビット長からなる入力値について剰余乗算を行う単一のビット長制限演算器を有する剰余乗算演算装置にあって、前記入力値の剰余乗算結果としての商データＱおよび剰余データＲを算出する剰余乗算演算方法であって、
前記入力値としての被乗数Ａ、乗数Ｂ、および法Ｎそれぞれを前記一定ビット長以下のビット長の分割入力値に展開する入力値ビット長分割機能と、
前記ビット長制限演算器を利用して前記分割入力値に対して予め設定された演算アルゴリズムに基づく再帰的な剰余乗算を行うことにより一時商データおよび一時剰余データからなる一時剰余乗算値を算出する一時ビットデータ算出機能と、
前記算出された一時剰余乗算値から予め設定された一時商データおよび一時剰余データを抽出し予め設定された加減演算を行うことにより、前記商データＱおよび剰余データＲ（Ａ・Ｂ（ｍｏｄＮ）＝Ｑ・２ｎ＋Ｒ）を算出する剰余乗算変換機能とをコンピュータに実行させることを特徴とした剰余乗算演算プログラム。
【産業上の利用可能性】
【０１７５】
本発明は、ビット長制限が設定された剰余乗算コプロセッサを利用して上記ビット用制限の４倍のビット長の入力値に対する剰余乗算演算を行うシステムに適用することができる。
【符号の説明】
【０１７６】
１００  コンピュータ（剰余乗算演算装置）
１１０  処理部
１２０  入出力インタフェース部
１３０  記憶部
２１０  ＣＰＵ（中央演算部）
２２０  ビットデータ分割処理部
２３０  分割ビットデータ格納部
２４０  ｎ／２ビット専用剰余乗算器
２４１  剰余データ出力部
２４２  商データ出力部
２５０  剰余乗算一時ビットデータ格納部
２６０  剰余乗算一時ビットデータ変換部
２７０  剰余乗算データ出力部
【図１】
2011232404.tif 000106
【図２】
2011232404.tif 000107
【図３】
2011232404.tif 000108
【図４】
2011232404.tif 000109
【図５】
2011232404.tif 000110