(57)【要約】【課題】  並列演算の計算量を均衡させつつ、更に、計算量を低減させる。【解決手段】  基数ｒのｓ乗の整数データＲ（いわゆるモンゴメリ定数Ｒ＝ｒs）をｘに２回乗算することにより、ステップＳＴ５４Ｈ，ＳＴ５４Ｌをいわゆるモンゴメリ乗算として並列に実行できるようにしている。ここで、両者ともモンゴメリ乗算であることから、従来のＢＭＭに比べ、計算量を低減させることができる。また、整数データＲのベキ指数ｓをｕ／２としたことから、並列演算の計算量を均衡させることができる。【選択図】      図４
2007187985.tif 000002
【特許請求の範囲】
【請求項１】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘ，ｙと、Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である整数データＲとに基づいて剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘＲ）ｙＲ-1 ｍｏｄ Ｎ）を実行し、得られた剰余乗算結果ｚを出力する剰余乗算装置であって、
前記整数データＮ，ｘ，ｙ，Ｒが記憶される記憶手段と、
前記記憶手段内の整数データｘ，Ｒ，Ｎに基づいて、整数データＸ＝ｘＲ ｍｏｄ Ｎを計算する第１の剰余乗算手段と、
この整数データＸ，Ｒ，Ｎに基づいて、整数データＸ’＝ＸＲ ｍｏｄ Ｎを計算する第２の剰余乗算手段と、
前記記憶手段内の整数データｙを、ｙHＲ＋ｙL（但し、ｙL＝ｙ ｍｏｄ Ｒ）の関係を持つ上位整数データｙH及び下位整数データｙLに分割する分割手段と、
前記整数データＸ’，Ｒ，Ｎ及び上位整数データｙHに基づいて、整数データｚH＝Ｘ’ｙHＲ-1 ｍｏｄ Ｎ を計算する第３の剰余乗算手段と、
前記第３の剰余乗算手段と並列に実行され、前記整数データＸ，Ｒ，Ｎ及び前記下位整数データｙLに基づいて、整数データｚL＝ＸｙLＲ-1 ｍｏｄ Ｎ を計算する第４の剰余乗算手段と、
前記整数データｚH，ｚL，Ｎに基づいて、剰余加算ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎを実行する剰余加算手段と、
前記剰余加算手段により得られた剰余加算結果ｚを前記剰余乗算結果ｚとして出力する出力手段と、
を備えたことを特徴とする剰余乗算装置。
【請求項２】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘと、Ｎ未満でｋビットの整数データｄに基づいてベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを実行し、得られたベキ乗剰余算結果ｚを出力するベキ乗剰余算装置であって、
前記整数データＮ，ｘ，ｄが記憶される記憶手段と、
前記Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である第１定数データＲ1を定める第１定数決定手段と、
前記Ｎ未満で且つ基数のｔ乗（但し、ｔ≧ｓ）である第２定数データＲ2を定める第２定数決定手段と、
前記記憶手段内の整数ｘ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ＝ｘＲ1 ｍｏｄ Ｎ を計算する第１の剰余乗算手段と、
この整数データＸ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ’＝ＸＲ1 ｍｏｄ Ｎ を計算する第２の剰余乗算手段と、
前記記憶手段内の整数ｘ，Ｎ及び前記第２定数データＲ2に基づいて、新たな整数データＺ＝ｘＲ2 ｍｏｄ Ｎ を計算する第３の剰余乗算手段と、
新たな整数データＺを、ＺHＲ2＋ＺL（但し、ＺL＝Ｚ ｍｏｄ Ｒ2）の関係を持つ上位整数データＺH及び下位整数データＺLに分割する第１の分割手段と、
前記整数データＺ，ＺH，Ｎに基づいて、整数データＺ1H＝ＺＺH ｍｏｄ Ｎ を計算する第４の剰余乗算手段と、
前記第４の剰余乗算手段と並列に実行され、前記整数データＺ，ＺL，Ｎに基づいて、整数データＺ1L＝ＺＺLＲ2-1 ｍｏｄ Ｎ を計算する第５の剰余乗算手段と、
前記整数データＺ1H，Ｚ1L，Ｎに基づいて、第１の剰余加算Ｚ＝（Ｚ1H＋Ｚ1L） ｍｏｄ Ｎを実行し、第１の剰余加算結果Ｚを得る第１の剰余加算手段と、
前記整数データｄのｉビット目（但し、ｉはｋ−２から０までの間で−１ずつ更新される）の値が“１”であるか否かを判定する判定手段と、
前記判定の結果が“１”の場合に、前記第１の剰余加算結果Ｚを、Ｚ2HＲ1＋Ｚ2L（但し、Ｚ2L＝Ｚ ｍｏｄ Ｒ1）の関係をもつ上位整数データＺ2H及び下位整数データＺ2Lに分割する第２の分割手段と、
前記整数データＸ’，Ｎ、前記第１定数データＲ1及び前記上位整数データＺ2Hに基づいて、整数データＺ3H＝Ｘ’Ｚ2HＲ1-1 ｍｏｄ Ｎ を計算する第６の剰余乗算手段と、
前記第６の剰余乗算手段と並列に実行され、前記整数データＸ，Ｎ、前記第１定数データＲ1及び前記下位整数データＺ2Lに基づいて、整数データＺ3L＝ＸＺ2LＲ1-1 ｍｏｄ Ｎ を計算する第７の剰余乗算手段と、
前記整数データＺ3H，Ｚ3L，Ｎに基づいて、第２の剰余加算Ｚ＝（Ｚ3H＋Ｚ3L） ｍｏｄ Ｎを実行し、第２の剰余加算結果Ｚを得る第２の剰余加算手段と、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉがｉ＞０であればｉを−１更新する更新手段と、
前記ｉを更新したとき、前記判定の結果が“１”の場合には前記第２の剰余加算結果Ｚを新たな整数データＺとし、前記判定の結果が否の場合には前記第１の剰余加算結果Ｚを新たな整数データＺとして、前記第１の分割手段から前記更新手段までを繰り返し実行する繰り返し実行手段と、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉ＝０であれば、最後の剰余加算結果Ｚ、前記第２定数データＲ2及び前記整数データＮに基づいて、剰余乗算ｚ＝Ｚ・１・Ｒ2-1 ｍｏｄ Ｎを実行する第８の剰余乗算手段と、
前記第８の剰余乗算手段により得られた剰余乗算結果ｚを前記ベキ乗剰余算結果ｚとして出力する出力手段と、
を備えたことを特徴とするベキ乗剰余算装置。
【請求項３】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘ，ｙと、Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である整数データＲとに基づいて剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘＲ）ｙＲ-1 ｍｏｄ Ｎ）を実行し、得られた剰余乗算結果ｚを出力する剰余乗算装置に用いられるプログラムであって、
前記剰余乗算装置のコンピュータを、
前記整数データＮ，ｘ，ｙ，Ｒが記憶される記憶手段、
前記記憶手段内の整数データｘ，Ｒ，Ｎに基づいて、整数データＸ＝ｘＲ ｍｏｄ Ｎを計算する第１の剰余乗算手段、
この整数データＸ，Ｒ，Ｎに基づいて、整数データＸ’＝ＸＲ ｍｏｄ Ｎを計算する第２の剰余乗算手段、
前記記憶手段内の整数データｙを、ｙHＲ＋ｙL（但し、ｙL＝ｙ ｍｏｄ Ｒ）の関係を持つ上位整数データｙH及び下位整数データｙLに分割する分割手段、
前記整数データＸ’，Ｒ，Ｎ及び上位整数データｙHに基づいて、整数データｚH＝Ｘ’ｙHＲ-1 ｍｏｄ Ｎ を計算する第３の剰余乗算手段、
前記第３の剰余乗算手段と並列に実行され、前記整数データＸ，Ｒ，Ｎ及び前記下位整数データｙLに基づいて、整数データｚL＝ＸｙLＲ-1 ｍｏｄ Ｎ を計算する第４の剰余乗算手段、
前記整数データｚH，ｚL，Ｎに基づいて、剰余加算ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎを実行する剰余加算手段、
前記剰余加算手段により得られた剰余加算結果ｚを前記剰余乗算結果ｚとして出力する出力手段、
として機能させるためのプログラム。
【請求項４】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘと、Ｎ未満でｋビットの整数データｄに基づいてベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを実行し、得られたベキ乗剰余算結果ｚを出力するベキ乗剰余算装置に用いられるプログラムであって、
前記ベキ乗剰余算装置のコンピュータを、
前記整数データＮ，ｘ，ｄが記憶される記憶手段、
前記Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である第１定数データＲ1を定める第１定数決定手段、
前記Ｎ未満で且つ基数のｔ乗（但し、ｔ≧ｓ）である第２定数データＲ2を定める第２定数決定手段、
前記記憶手段内の整数ｘ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ＝ｘＲ1 ｍｏｄ Ｎ を計算する第１の剰余乗算手段、
この整数データＸ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ’＝ＸＲ1 ｍｏｄ Ｎ を計算する第２の剰余乗算手段、
前記記憶手段内の整数ｘ，Ｎ及び前記第２定数データＲ2に基づいて、新たな整数データＺ＝ｘＲ2 ｍｏｄ Ｎ を計算する第３の剰余乗算手段、
新たな整数データＺを、ＺHＲ2＋ＺL（但し、ＺL＝Ｚ ｍｏｄ Ｒ2）の関係を持つ上位整数データＺH及び下位整数データＺLに分割する第１の分割手段、
前記整数データＺ，ＺH，Ｎに基づいて、整数データＺ1H＝ＺＺH ｍｏｄ Ｎ を計算する第４の剰余乗算手段、
前記第４の剰余乗算手段と並列に実行され、前記整数データＺ，ＺL，Ｎに基づいて、整数データＺ1L＝ＺＺLＲ2-1 ｍｏｄ Ｎ を計算する第５の剰余乗算手段、
前記整数データＺ1H，Ｚ1L，Ｎに基づいて、第１の剰余加算Ｚ＝（Ｚ1H＋Ｚ1L） ｍｏｄ Ｎを実行し、第１の剰余加算結果Ｚを得る第１の剰余加算手段、
前記整数データｄのｉビット目（但し、ｉはｋ−２から０までの間で−１ずつ更新される）の値が“１”であるか否かを判定する判定手段、
前記判定の結果が“１”の場合に、前記第１の剰余加算結果Ｚを、Ｚ2HＲ1＋Ｚ2L（但し、Ｚ2L＝Ｚ ｍｏｄ Ｒ1）の関係をもつ上位整数データＺ2H及び下位整数データＺ2Lに分割する第２の分割手段、
前記整数データＸ’，Ｎ、前記第１定数データＲ1及び前記上位整数データＺ2Hに基づいて、整数データＺ3H＝Ｘ’Ｚ2HＲ1-1 ｍｏｄ Ｎ を計算する第６の剰余乗算手段、
前記第６の剰余乗算手段と並列に実行され、前記整数データＸ，Ｎ、前記第１定数データＲ1及び前記下位整数データＺ2Lに基づいて、整数データＺ3L＝ＸＺ2LＲ1-1 ｍｏｄ Ｎ を計算する第７の剰余乗算手段、
前記整数データＺ3H，Ｚ3L，Ｎに基づいて、第２の剰余加算Ｚ＝（Ｚ3H＋Ｚ3L） ｍｏｄ Ｎを実行し、第２の剰余加算結果Ｚを得る第２の剰余加算手段、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉがｉ＞０であればｉを−１更新する更新手段、
前記ｉを更新したとき、前記判定の結果が“１”の場合には前記第２の剰余加算結果Ｚを新たな整数データＺとし、前記判定の結果が否の場合には前記第１の剰余加算結果Ｚを新たな整数データＺとして、前記第１の分割手段から前記更新手段までを繰り返し実行する繰り返し実行手段、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉ＝０であれば、最後の剰余加算結果Ｚ、前記第２定数データＲ2及び前記整数データＮに基づいて、剰余乗算ｚ＝Ｚ・１・Ｒ2-1 ｍｏｄ Ｎを実行する第８の剰余乗算手段、
前記第８の剰余乗算手段により得られた剰余乗算結果ｚを前記ベキ乗剰余算結果ｚとして出力する出力手段、
として機能させるためのプログラム。
【請求項５】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘ，ｙと、Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である整数データＲとに基づいて剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘＲ）ｙＲ-1 ｍｏｄ Ｎ）を実行し、得られた剰余乗算結果ｚを出力する剰余乗算装置が実行する剰余乗算方法であって、
前記整数データＮ，ｘ，ｙ，Ｒを前記剰余乗算装置内のメモリに記憶する記憶工程と、
前記メモリ内の整数データｘ，Ｒ，Ｎに基づいて、整数データＸ＝ｘＲ ｍｏｄ Ｎを計算する第１の剰余乗算工程と、
この整数データＸ，Ｒ，Ｎに基づいて、整数データＸ’＝ＸＲ ｍｏｄ Ｎを計算する第２の剰余乗算工程と、
前記メモリ内の整数データｙを、ｙHＲ＋ｙL（但し、ｙL＝ｙ ｍｏｄ Ｒ）の関係を持つ上位整数データｙH及び下位整数データｙLに分割する分割工程と、
前記整数データＸ’，Ｒ，Ｎ及び上位整数データｙHに基づいて、整数データｚH＝Ｘ’ｙHＲ-1 ｍｏｄ Ｎ を計算する第３の剰余乗算工程と、
前記第３の剰余乗算工程と並列に実行され、前記整数データＸ，Ｒ，Ｎ及び前記下位整数データｙLに基づいて、整数データｚL＝ＸｙLＲ-1 ｍｏｄ Ｎ を計算する第４の剰余乗算工程と、
前記整数データｚH，ｚL，Ｎに基づいて、剰余加算ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎを実行する剰余加算工程と、
前記剰余加算工程により得られた剰余加算結果ｚを前記剰余乗算結果ｚとして出力する出力工程と、
を備えたことを特徴とする剰余乗算方法。
【請求項６】
基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘと、Ｎ未満でｋビットの整数データｄに基づいてベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを実行し、得られたベキ乗剰余算結果ｚを出力するベキ乗剰余算装置が実行するベキ乗剰余算方法であって、
前記整数データＮ，ｘ，ｄを前記ベキ乗剰余算装置内のメモリに記憶する記憶工程と、
前記Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である第１定数データＲ1を定める第１定数決定工程と、
前記Ｎ未満で且つ基数のｔ乗（但し、ｔ≧ｓ）である第２定数データＲ2を定める第２定数決定工程と、
前記メモリ内の整数ｘ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ＝ｘＲ1 ｍｏｄ Ｎ を計算する第１の剰余乗算工程と、
この整数データＸ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ’＝ＸＲ1 ｍｏｄ Ｎ を計算する第２の剰余乗算工程と、
前記メモリ内の整数ｘ，Ｎ及び前記第２定数データＲ2に基づいて、新たな整数データＺ＝ｘＲ2 ｍｏｄ Ｎ を計算する第３の剰余乗算工程と、
新たな整数データＺを、ＺHＲ2＋ＺL（但し、ＺL＝Ｚ ｍｏｄ Ｒ2）の関係を持つ上位整数データＺH及び下位整数データＺLに分割する第１の分割工程と、
前記整数データＺ，ＺH，Ｎに基づいて、整数データＺ1H＝ＺＺH ｍｏｄ Ｎ を計算する第４の剰余乗算工程と、
前記第４の剰余乗算工程と並列に実行され、前記整数データＺ，ＺL，Ｎに基づいて、整数データＺ1L＝ＺＺLＲ2-1 ｍｏｄ Ｎ を計算する第５の剰余乗算工程と、
前記整数データＺ1H，Ｚ1L，Ｎに基づいて、第１の剰余加算Ｚ＝（Ｚ1H＋Ｚ1L） ｍｏｄ Ｎを実行し、第１の剰余加算結果Ｚを得る第１の剰余加算工程と、
前記整数データｄのｉビット目（但し、ｉはｋ−２から０までの間で−１ずつ更新される）の値が“１”であるか否かを判定する判定工程と、
前記判定の結果が“１”の場合に、前記第１の剰余加算結果Ｚを、Ｚ2HＲ1＋Ｚ2L（但し、Ｚ2L＝Ｚ ｍｏｄ Ｒ1）の関係をもつ上位整数データＺ2H及び下位整数データＺ2Lに分割する第２の分割工程と、
前記整数データＸ’，Ｎ、前記第１定数データＲ1及び前記上位整数データＺ2Hに基づいて、整数データＺ3H＝Ｘ’Ｚ2HＲ1-1 ｍｏｄ Ｎ を計算する第６の剰余乗算工程と、
前記第６の剰余乗算工程と並列に実行され、前記整数データＸ，Ｎ、前記第１定数データＲ1及び前記下位整数データＺ2Lに基づいて、整数データＺ3L＝ＸＺ2LＲ1-1 ｍｏｄ Ｎ を計算する第７の剰余乗算工程と、
前記整数データＺ3H，Ｚ3L，Ｎに基づいて、第２の剰余加算Ｚ＝（Ｚ3H＋Ｚ3L） ｍｏｄ Ｎを実行し、第２の剰余加算結果Ｚを得る第２の剰余加算工程と、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉがｉ＞０であればｉを−１更新する更新工程と、
前記ｉを更新したとき、前記判定の結果が“１”の場合には前記第２の剰余加算結果Ｚを新たな整数データＺとし、前記判定の結果が否の場合には前記第１の剰余加算結果Ｚを新たな整数データＺとして、前記第１の分割工程から前記更新工程までを繰り返し実行する繰り返し実行工程と、
前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉ＝０であれば、最後の剰余加算結果Ｚ、前記第２定数データＲ2及び前記整数データＮに基づいて、剰余乗算ｚ＝Ｚ・１・Ｒ2-1 ｍｏｄ Ｎを実行する第８の剰余乗算工程と、
前記第８の剰余乗算工程により得られた剰余乗算結果ｚを前記ベキ乗剰余算結果ｚとして出力する出力工程と、
を備えたことを特徴とするベキ乗剰余算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大きな整数の演算を並列処理により高速に実行する剰余乗算装置、ベキ乗剰余算装置、プログラム及び方法に係わり、例えば並列演算の計算量を均衡させつつ、更に、計算量を低減し得る剰余乗算装置、ベキ乗剰余算装置、プログラム及び方法に関する。
【背景技術】
【０００２】
近年、公開鍵暗号を利用した情報技術が広く用いられるようになってきている。例えば通信の暗号化技術であるＳＳＬ（Secure Socket Layer）や、メッセージの作成者や改ざんされていないことを検出できる電子署名などである。これらはＰＫＩ（Public Key Infrastructure）の一部として、社会の電子化を支える技術となっている。
【０００３】
このように、公開鍵暗号の重要性が増すにつれて、公開鍵暗号の高速処理の要求も高まっている。ＲＳＡ（Rivest-Shamir-Adleman）方式を始めとする多くの公開鍵暗号方式は、大きな整数（現在1,024ビット程度）の剰余付き演算の組み合わせで構成されている。その中でもベキ乗剰余算に処理の大半が費やされている。
【０００４】
ベキ乗剰余算とは、ある自然数ｘ，ｄ，Ｎに対し、ｘをｄ回乗じた結果をＮで割った剰余ｚ（＝ｘd ｍｏｄ Ｎ）を求める演算である。ベキ乗剰余算の周知の計算方法にはバイナリ法がある。バイナリ法を図１１を用いて説明する。
【０００５】
始めに、自然数ｄはｋビットであり、ｄの第ｉビット目の値をｄiとする。すなわち、自然数ｄにおいては、ＬＳＢ（Least Significant Bit：最小桁のビット）からｉ番目のビットの値がｄiである。
【０００６】
このとき、最初に中間変数ｚとしてｘを入力する（ＳＴ１）。次に、第ｉビット目を示すｉの値をｋ−２から０まで更新することにより、ステップＳＴ３からＳＴ５をループさせる（ＳＴ２）。
【０００７】
ステップＳＴ３は、中間変数ｚを２乗してＮでの剰余を求める剰余２乗算である。ステップＳＴ４は、ｉビット目の値ｄiが１か否かを判定する部分である。ｄi＝１の場合はｚにｘを乗じてＮでの剰余を求める剰余乗算を実行した後（ＳＴ５）、ループの終了判定ルーチンを行う（ＳＴ６）。ｄi＝０の場合は何もせずにループの終了判定ルーチンを行う（ＳＴ６）。ｉループを終了したときのｚの値がｘd ｍｏｄ Ｎとなる。
【０００８】
以上、バイナリ法により述べたように、ベキ乗剰余算は剰余乗算のくり返しで実現されている。このため、ベキ乗剰余算を高速化するためには、剰余乗算を高速化することが有効と考えられる。
【０００９】
剰余乗算の高速化手法としては、（１）より高速なアルゴリズムを採用する方法、又は（２）複数の装置による並列計算を行う方法、の２つの方法（１），（２）がよく知られている。
【００１０】
（１）剰余乗算の高速なアルゴリズムとして、モンゴメリ乗算が広く用いられている。モンゴメリ乗算は、整数ｘ，ｙ，Ｎに対し、ｘｙＲ-1 ｍｏｄ Ｎ を求める演算である。
【００１１】
ここで、Ｒはモンゴメリ定数と呼ばれ、Ｎと互いに素である整数である。公開鍵暗号では多くの場合、Ｎは奇数の素数であるか、いくつかの奇数の素数の積であることが多い。このため、モンゴメリ定数Ｒには、Ｎと互いに素である整数として、２をベキ乗した数が用いられる。モンゴメリ定数Ｒが２をベキ乗した数であれば、モンゴメリ乗算に必要なＲでの除算の際に、商を求めるときには被除数の上位桁を抜き出し、剰余を求めるときには下位桁を抜き出せばよいからである。
【００１２】
ここで、モンゴメリ乗算ｘｙＲ-1 ｍｏｄ Ｎを利用したベキ乗剰余算アルゴリズムを図１２を用いて説明する。ここで、ベキ指数ｄはｋビットであり、ｄの第ｉビット目の値をｄiとする。すなわち、ベキ指数ｄにおいては、ＬＳＢ（Least Significant Bit）からｉ番目のビットの値がｄiである。
【００１３】
始めに、入力ｘをモンゴメリ系での表現Ｘ＝ｘＲ ｍｏｄ Ｎに変換する（ＳＴ１１）。
【００１４】
次に、中間変数ＺとしてＸを入力する（ＳＴ１２）。その後、第ｉビット目を示すｉの値をｋ−２から０まで更新することにより、ステップＳＴ１４からＳＴ１６をループさせる（ＳＴ１３）。ステップＳＴ１４は、中間変数Ｚを２乗してＮでの剰余を求める剰余２乗算をモンゴメリ乗算で行う処理である。ステップＳＴ１５は、ｉビット目の値ｄiが１か否かを判定する部分である。ｄi＝１の場合はＺにＸを乗じてＮでの剰余を求める剰余乗算を実行してからモンゴメリ乗算を実行し（ＳＴ１６）、ループの終了判定ルーチンを行う（ＳＴ１７）。ｄi＝０の場合は何もせずにループの終了判定ルーチンを行う（ＳＴ１７）。ｉループを終了したときのＺに対し、１とのモンゴメリ乗算ＺＲ-1 ｍｏｄ Ｎを行い（ＳＴ１８）、得られた結果ｚの値がｘd ｍｏｄ Ｎとなる。
【００１５】
（２）一方、剰余乗算の並列計算では、複数の剰余乗算を複数の装置で行う場合と、１つの剰余乗算を複数の装置で行う場合とがある。図１１のステップＳＴ３，ＳＴ５から分かるように、ベキ乗剰余算においては、各剰余算が前のステップの結果を後のステップで用いる直列処理によって並列化できないため、前者の並列計算方法は不向きである。後者の並列計算方法では、剰余演算系を利用する方法と、２並列剰余乗算（Bipartite Modular Multiplication：以下、ＢＭＭという）と呼ばれる方法が知られている。
【００１６】
始めに、剰余演算系を利用する方法は、ポッシュ（Posch）ら（例えば、非特許文献１，２参照）及び川村（例えば、特許文献１参照）によって提案されている。
【００１７】
これら剰余演算系を利用する方法は、ハードウェアによる多並列計算に向いた方法であり、回路規模とのトレードオフの関係で処理の高速化を実現できる。但し、冗長な表現を利用するため、直列で処理した場合には元々の剰余乗算より計算量が増えるので、ソフトウェア実装に向いていないという不都合もある。
【００１８】
一方、ＢＭＭは、カイハラ（Kaihara）らによって提案された方法である（例えば、非特許文献３参照）。ＢＭＭは、整数ｘ，ｙ，Ｎに対し、Ｘｙｒ-t ｍｏｄ Ｎ を求める演算である（但し、Ｘ＝ｘｒt ｍｏｄ Ｎ）。ここで、ｒは装置のワード数（３２ビット等）であり、ｔは０＜ｔ＜ｕ（ｕはＮのワード数）なる整数である。この式から分かるように、ＢＭＭは、モンゴメリ定数がｒtの場合のモンゴメリ乗算である。
【００１９】
ＢＭＭは、この演算を（ＸｙH ｍｏｄ Ｎ ＋ ＸｙLｒ-t ｍｏｄ Ｎ） ｍｏｄ Ｎ として行う方法である。ここで、ｙH，ｙLは、それぞれｙを下位ｔワードで分割したときの上位ワードと下位ワードである。すなわち乗数ｙ、上位ワードｙH、下位ワードｙLは、それぞれ次式のように表される。
【００２０】
ｙ＝ｙHｒt＋ｙL 
ｙH＝ｙ／ｒtの商 
ｙL＝ｙ ｍｏｄ ｒt 
このような分割により、ＢＭＭにおいては、元々のモンゴメリ乗算Ｘｙｒ-t ｍｏｄ Ｎを、上位ビットの剰余乗算ＸｙH ｍｏｄ Ｎと、下位ビットのモンゴメリ乗算ＸｙLｒ-t ｍｏｄ Ｎとの２つの並列演算に分けて実行できる。なお、これら並列演算結果の和をｍｏｄ Ｎで表した値が、元々のモンゴメリ乗算Ｘｙｒ-t ｍｏｄ Ｎの結果となる。
【００２１】
上位ワードｙH及び下位ワードｙLは、元のｙよりワードサイズが小さいため、ｙHの剰余乗算、ｙLのモンゴメリ乗算ともに元々のモンゴメリ乗算より高速に処理できる。また、この２つの演算は独立であるため、並列に行うことができる。さらに、ＢＭＭは、計算量が元のモンゴメリ乗算から増加していないため、ソフトウェアによる直列処理をシングルＣＰＵが実行した場合も元のモンゴメリ乗算とほぼ同じ処理時間で実行できる特徴がある。
【００２２】
図１３乃至図１５はＢＭＭを実行する装置の模式図である。図１３に示したように、ＢＭＭを実行する剰余乗算装置１０は、制御部１１及び演算部１２を備えている。演算部１２は、ＲＯＭ１３、ＲＡＭ１４及びＢＭＭ演算ユニット１５から構成される。
【００２３】
ＲＯＭ１３にはＢＭＭを行うプログラム等が格納されている。ＲＡＭ１４はＢＭＭのオペランドｘ，Ｘ，ｙ，Ｎや途中結果、最終結果ｚ等が格納される。
【００２４】
ＢＭＭ演算ユニット１５は、図１４に示すように、モンゴメリ変換ユニット１６、オペランド分割ユニット１７、剰余乗算ユニット１８、モンゴメリ乗算ユニット１９、剰余加算ユニット２０から構成される。
【００２５】
モンゴメリ変換ユニット１６は、整数ｘをモンゴメリ系表現に変換した値Ｘ＝ｘｒt ｍｏｄ Ｎを得る機能を持っている。
【００２６】
オペランド分割ユニット１７は、図１５に示すように、一方のオペランドｙを下位ｔワードで上位と下位に分割し、上位ワードｙHと下位ワードｙLを作る機能を持つ。
【００２７】
剰余乗算ユニット１８は、剰余乗算ＸｙH ｍｏｄ Ｎを実行する機能をもつ。
【００２８】
モンゴメリ乗算ユニット１９はモンゴメリ乗算ＸｙLＲ-1 ｍｏｄ Ｎを実行する機能をもつ。
【００２９】
剰余加算ユニット２０は、剰余乗算ユニット７０３とモンゴメリ乗算ユニット７０４から出力された値ＸｙH ｍｏｄ Ｎ及びＸｙLＲ-1 ｍｏｄ Ｎをｍｏｄ Ｎで加算する機能を持っている。
【００３０】
以上、いくつか述べた演算は、以下のようにその計算量を見積ることができる。
【００３１】
まず各演算はワード単位（ここでは１ワード＝ｒビットとする）で行われるものとする。近年の演算器ではｒ＝３２やｒ＝６４が用いられており、ここでもそのような値であるものとする。
【００３２】
また、計算量を測るための単位演算として、積和演算ａ×ｂ＋ｃ＋ｄを採用する。この単位演算は乗算を実現するためによく用いられている。ここで、各変数ａ，ｂ，ｃ，ｄは１ワードの値である。
【００３３】
例えばｓワードの整数ｘとｔワードの整数ｙの乗算ｚ＝ｘｙは、図１６に示すように実現される。乗算は、中間変数ｚを０に初期化し（ＳＴ２１）、ｔ回のｉループ（ＳＴ２２〜ＳＴ２８）とｓ回のｊループ（ＳＴ２３〜ＳＴ２７）の中でステップＳＴ２４〜ＳＴ２６を実行する。
【００３４】
ステップＳＴ２４は、ｘ，ｙから選択した各１ワードの乗算（ｘiｙj）とその前のワードにおける演算からのくり上がり（ｚi+j）とを加算する積和演算（Ｗ＝ｘiｙj＋ｚi+j）である。ステップＳＴ２５は、ステップＳＴ２４の結果のｒでの剰余（下位ワード）をｚi+jとする演算（ｚi+j＝Ｗ ｍｏｄ ｒ）である。ステップＳＴ２６は、ｒでの商（上位ワード）を次のワードへのくり上がりｚi+j+1とする演算（ｚi+j+1＝Ｗ／ｒ）である。
【００３５】
ｒでの除算は、上位ｒワード（商）又は残りの下位ワード（剰余）の取り出しであるため、計算量としては無視できるほど小さい。従って、乗算にはｓｔ回の積和演算が必要であることが分かる。言い換えると乗算の計算量はｓｔである。
【００３６】
図１７に剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎのフローチャートを示す。ここで、ｘ，Ｎはｕワードとし、ｙはｔワードとする。剰余乗算では、中間変数ｚを０に初期化し（ＳＴ３１）、ｔ回のｉループ（ＳＴ３２〜ＳＴ３６）において、ｙの上位ワードから順にｘとの積をとり（ＳＴ３３）、その結果のｕ＋１ワードのｚに対してＮで割った商ｑを計算し（ＳＴ３４）、ｚからｑＮを減じてＮでの剰余をとる（ＳＴ３５）、という演算をくり返す。
【００３７】
ここで、ステップＳＴ３４，ＳＴ３５の除算は、図１８に示すアルゴリズムで実装されているものとする。図１８はｕ＋１ワードのｚをｕワードのＮで割ったときに、その商ｑ（１ワード）と剰余ｚ（ｕワード）を求めるものである。ここでｚのｉワード目をｚiのように表している。
【００３８】
始めに、互いの最上位ワードｚuとＮu-1とが等しいか否かを調べる（ＳＴ３４−１）。等しい場合は商ｑ＝ｒ−１とする（ＳＴ３４−２）。否の場合はｚの上位２ワード（ｚu‖ｚu-1）をＮの上位１ワードＮu-1で割り、その商をｑとする（ＳＴ３４−３）。ここで（ｚu‖ｚu-1）は、２数ｚuとｚu-1とがその順序で連結したことを意味する。
【００３９】
次に、ｚの上位３ワード（ｚu‖ｚu-1‖ｚu-2）と、ｑとＮの上位２ワードの積ｑ（Ｎu-1‖Ｎu-2）との大小を比較し（ＳＴ３５−１）、大きい場合にはｑから１を減じ（ＳＴ３５−２）、ステップＳＴ３５−１に戻る。小さい場合はｚからｑＮを減じる（ＳＴ３５−３）。
【００４０】
次に、ステップＳＴ３５−３の結果が負であるか否かを判定し（ＳＴ３５−４）、負の場合にはＮを加えて正の数とし（ＳＴ３５−５）、商ｑから１を減じて調整する（ＳＴ３５−６）。負でない場合はそれで終了とする。
【００４１】
ここで、ステップＳＴ３４−１，ＳＴ３５−４の条件分岐で、それぞれ“はい（Ｙｅｓ”に分岐する場合は非常に少ないことが知られている。従って、図１８のアルゴリズムの計算量は、ステップＳＴ３４−３の２ワードの数の１ワードの数での除算と、ステップＳＴ３５−１の１ワードの数と２ワードの数の乗算と、ステップＳＴ３５−３の１ワードの数とｕワードの数の乗算と、の和となる。ステップＳＴ３４−３の計算量を、単位とする積和演算のＱ倍とすると、図１８のアルゴリズムの計算量はＱ＋２＋ｕとなる。
【００４２】
図１７の計算量は、ＳＴ３３〜ＳＴ３５を図１８のアルゴリズムで置き換えたものであることから、ｔ（２ｕ＋Ｑ＋２）となる。
【００４３】
図１９にはモンゴメリ乗算Ｚ＝ＸＹＲ-1 ｍｏｄ Ｎのアルゴリズムを示す。ここでＸ，Ｎはｕワード、Ｙはｔワード、Ｒ＝ｒtとする。通常はｔ＝ｕと選ばれる。
【００４４】
モンゴメリ乗算では、中間変数ｚを０に初期化し（ＳＴ４１）、ｔ回のｉループ（ＳＴ４２〜ＳＴ４６）において、ステップＳＴ４３〜ＳＴ４５の演算を繰り返す。
【００４５】
ステップＳＴ４３は、ｙの下位ワードから順にｘとの積Ｚ（＝Ｚ＋ＹiＸ）を求める演算である。ステップＳＴ４４は、ＳＴ４３で得られた積Ｚの最下位１ワード（Ｚ0）と、Ｎの最下位１ワード（Ｎ0）のｍｏｄ ｒでの逆元のマイナス（−Ｎ0-1）との積の下位１ワードｑ（＝Ｚ0(−Ｎ0-1) ｍｏｄ ｒ）を計算する演算である。ステップＳＴ４５は、ＺにｑＮを加えてｒで除算して新たなＺ（＝（Ｚ＋ｑＮ）／ｒ）を求める演算である。
【００４６】
ｉループが終わった際には、Ｚ＞Ｎの可能性があるため、Ｚ＞Ｎか否かを判定し（ＳＴ４７）、Ｚ＞Ｎの場合はＺからＮを１回減じるという演算（ＳＴ４８）を実行する。
【００４７】
モンゴメリ乗算の計算量は、ＳＴ４３の１ワードの数とｕワードの数の乗算、ＳＴ４４の１ワードの数同士の乗算、ＳＴ４５の１ワードの数とｕワードの数の乗算の和をｔ倍したものとなる。従って、計算量はｔ（２ｕ＋１）となる。
【００４８】
最後に、ＢＭＭの計算量を見積る。ｕワードのｙを下位ｔワードで分割すると、上位ワードｙHの剰余乗算ＸｙH ｍｏｄ Ｎは、ｕワードと（ｕ−ｔ）ワードの剰余乗算となる。下位ワードｙLのモンゴメリ乗算ＸｙLｒ-t ｍｏｄ Ｎは、ｕワードとｔワードのモンゴメリ乗算となる。このため、それぞれの計算量は（ｕ−ｔ）（２ｕ＋Ｑ＋２）及びｔ（２ｕ＋１）となる。
【００４９】
本発明者の検討によれば、ＢＭＭの計算量は、並列に実行される剰余乗算とモンゴメリ乗算とのうち、大きい方を必要とするから、ｍａｘ｛（ｕ−ｔ）（２ｕ＋Ｑ＋２），ｔ（２ｕ＋１）｝と表せる。
【００５０】
この式から分かるように、下位ワードのワード数ｔの増加に従い、剰余乗算部分（上位ワード部分）の計算量は単調減少し、モンゴメリ乗算部分（下位ワード部分）の計算量は単調増加する。
【００５１】
従って、ＢＭＭの計算量を最適にするには、本発明者の検討によれば、剰余乗算部分とモンゴメリ乗算部分の計算量が均衡するｔを選択すればよい。２ｕ＋Ｑ＋２＞２ｕ＋１より、均衡するｔはｔ≧ｕ／２であることが分かる。
【００５２】
例えば、ｒ＝２32、ｕ＝３２（Ｎが１０２４ビット）、Ｑ＝１の場合のＢＭＭの計算量の評価結果と最適なｔの値を図２０に示す。ｔの理論的な最適値は、ｔ＝１６．２４であるが、整数ではないから分割ワード数に使用できない。このため、ｔ＝１６．２４に最も近いｔ＝１６と１７が最適値の候補となる。ｔ＝１６の場合はＢＭＭ全体の計算量は１０７２であり、ｔ＝１７の場合は計算量が１１０５である。従って、計算量が少ない方のｔ＝１６が最適値であることが分かる。また同様に、Ｑ＝５の場合は、図２１に示すように、ｔ＝１７が最適値となる。
【非特許文献１】Posch et al., “Modulo Reduction in Residue Number Systems”, IEEE Transaction on Parallel and Distributed Systems, Vol.6, No.5, May 1995, pp.449-454
【非特許文献２】Posch et al., “RNS-Modulo Reduction Upon a Restricted Base Value Set and its Applicability to RSA Cryptography”,Computer & Security, Vol.17, pp.637-650, 1998
【特許文献１】特開２００１−１９４９９３号公報
【非特許文献３】M. E. Kaihara and N. Takagi, “Bipartite Modular Multiplication”, CHES2005, Lecture Notes in Computer Sciences, Vol.3659, pp.201-210, 2005
【発明の開示】
【発明が解決しようとする課題】
【００５３】
以上説明したように、ＢＭＭの計算量は、並列に実行される剰余乗算とモンゴメリ乗算とのうち、大きい方の計算量に引きずられる。また、計算量の少ない方の演算は、他方の演算が終わるまで何もしないで待つといった不都合がある。この不都合は、本発明者の検討によれば、剰余乗算部分とモンゴメリ乗算部分の計算量が均衡するｔを選択すれば解消可能である。このようなｔを選択する方法は、簡単に言うと、計算量の多い剰余乗算部分のワード数ｕ−ｔを少なくし、計算量の少ないモンゴメリ乗算部分のワード数ｔを多くして、両者の計算量を均衡させる手法となっている。
【００５４】
この計算量を均衡させる手法には特に問題は無いが、本発明者の検討によれば、計算量を均衡させつつ、更に、計算量を低減できることが望ましいと考えられる。
【００５５】
本発明は上記実情を考慮してなされたもので、並列演算の計算量を均衡させつつ、更に、計算量を低減し得る剰余乗算装置、ベキ乗剰余算装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００５６】
第１の発明は、基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘ，ｙと、Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である整数データＲとに基づいて剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘＲ）ｙＲ-1 ｍｏｄ Ｎ）を実行し、得られた剰余乗算結果ｚを出力する剰余乗算装置であって、前記整数データＮ，ｘ，ｙ，Ｒが記憶される記憶手段と、前記記憶手段内の整数データｘ，Ｒ，Ｎに基づいて、整数データＸ＝ｘＲ ｍｏｄ Ｎを計算する第１の剰余乗算手段と、この整数データＸ，Ｒ，Ｎに基づいて、整数データＸ’＝ＸＲ ｍｏｄ Ｎを計算する第２の剰余乗算手段と、前記記憶手段内の整数データｙを、ｙHＲ＋ｙL（但し、ｙL＝ｙ ｍｏｄ Ｒ）の関係を持つ上位整数データｙH及び下位整数データｙLに分割する分割手段と、前記整数データＸ’，Ｒ，Ｎ及び上位整数データｙHに基づいて、整数データｚH＝Ｘ’ｙHＲ-1 ｍｏｄ Ｎ を計算する第３の剰余乗算手段と、前記第３の剰余乗算手段と並列に実行され、前記整数データＸ，Ｒ，Ｎ及び前記下位整数データｙLに基づいて、整数データｚL＝ＸｙLＲ-1 ｍｏｄ Ｎ を計算する第４の剰余乗算手段と、前記整数データｚH，ｚL，Ｎに基づいて、剰余加算ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎを実行する剰余加算手段と、前記剰余加算手段により得られた剰余加算結果ｚを前記剰余乗算結果ｚとして出力する出力手段と、を備えた剰余乗算装置である。
【００５７】
第２の発明は、基数ビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘと、Ｎ未満でｋビットの整数データｄに基づいてベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを実行し、得られたベキ乗剰余算結果ｚを出力するベキ乗剰余算装置であって、前記整数データＮ，ｘ，ｄが記憶される記憶手段と、前記Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である第１定数データＲ1を定める第１定数決定手段と、前記Ｎ未満で且つ基数のｔ乗（但し、ｔ≧ｓ）である第２定数データＲ2を定める第２定数決定手段と、前記記憶手段内の整数ｘ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ＝ｘＲ1 ｍｏｄ Ｎ を計算する第１の剰余乗算手段と、この整数データＸ，Ｎ及び前記第１定数データＲ1に基づいて、整数データＸ’＝ＸＲ1 ｍｏｄ Ｎ を計算する第２の剰余乗算手段と、前記記憶手段内の整数ｘ，Ｎ及び前記第２定数データＲ2に基づいて、新たな整数データＺ＝ｘＲ2 ｍｏｄ Ｎ を計算する第３の剰余乗算手段と、新たな整数データＺを、ＺHＲ2＋ＺL（但し、ＺL＝Ｚ ｍｏｄ Ｒ2）の関係を持つ上位整数データＺH及び下位整数データＺLに分割する第１の分割手段と、前記整数データＺ，ＺH，Ｎに基づいて、整数データＺ1H＝ＺＺH ｍｏｄ Ｎ を計算する第４の剰余乗算手段と、前記第４の剰余乗算手段と並列に実行され、前記整数データＺ，ＺL，Ｎに基づいて、整数データＺ1L＝ＺＺLＲ2-1 ｍｏｄ Ｎ を計算する第５の剰余乗算手段と、前記整数データＺ1H，Ｚ1L，Ｎに基づいて、第１の剰余加算Ｚ＝（Ｚ1H＋Ｚ1L） ｍｏｄ Ｎを実行し、第１の剰余加算結果Ｚを得る第１の剰余加算手段と、前記整数データｄのｉビット目（但し、ｉはｋ−２から０までの間で−１ずつ更新される）の値が“１”であるか否かを判定する判定手段と、前記判定の結果が“１”の場合に、前記第１の剰余加算結果Ｚを、Ｚ2HＲ1＋Ｚ2L（但し、Ｚ2L＝Ｚ ｍｏｄ Ｒ1）の関係をもつ上位整数データＺ2H及び下位整数データＺ2Lに分割する第２の分割手段と、前記整数データＸ’，Ｎ、前記第１定数データＲ1及び前記上位整数データＺ2Hに基づいて、整数データＺ3H＝Ｘ’Ｚ2HＲ1-1 ｍｏｄ Ｎ を計算する第６の剰余乗算手段と、前記第６の剰余乗算手段と並列に実行され、前記整数データＸ，Ｎ、前記第１定数データＲ1及び前記下位整数データＺ2Lに基づいて、整数データＺ3L＝ＸＺ2LＲ1-1 ｍｏｄ Ｎ を計算する第７の剰余乗算手段と、前記整数データＺ3H，Ｚ3L，Ｎに基づいて、第２の剰余加算Ｚ＝（Ｚ3H＋Ｚ3L） ｍｏｄ Ｎを実行し、第２の剰余加算結果Ｚを得る第２の剰余加算手段と、前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉがｉ＞０であればｉを−１更新する更新手段と、前記ｉを更新したとき、前記判定の結果が“１”の場合には前記第２の剰余加算結果Ｚを新たな整数データＺとし、前記判定の結果が否の場合には前記第１の剰余加算結果Ｚを新たな整数データＺとして、前記第１の分割手段から前記更新手段までを繰り返し実行する繰り返し実行手段と、前記判定の結果が否の場合又は前記第２の剰余加算が実行された場合に、前記ｉ＝０であれば、最後の剰余加算結果Ｚ、前記第２定数データＲ2及び前記整数データＮに基づいて、剰余乗算ｚ＝Ｚ・１・Ｒ2-1 ｍｏｄ Ｎを実��する第８の剰余乗算手段と、前記第８の剰余乗算手段により得られた剰余乗算結果ｚを前記ベキ乗剰余算結果ｚとして出力する出力手段と、を備えたベキ乗剰余算装置である。
【００５８】
なお、第１及び第２の各発明は、カテゴリーを「装置」として表現したが、これに限らず、カテゴリーを「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」に変更してもよい。このように変更しても同様の作用効果を得ることができる。
【００５９】
（作用）
第１の発明によれば、基数のｓ乗の整数データＲ（いわゆるモンゴメリ定数）をｘに２回乗算することにより、第３及び第４の剰余乗算手段をいわゆるモンゴメリ乗算として並列に実行できるようにしている。ここで、両者ともモンゴメリ乗算であることから、従来のＢＭＭに比べ、計算量を低減させることができる。また、整数データＲのベキ指数ｓをｕ／２としたことから、並列演算の計算量を均衡させることができる。
【００６０】
第２の発明によれば、基数のｓ乗の第１定数データＲ1（いわゆるモンゴメリ定数）をｘに２回乗算することにより、第６及び第７の剰余乗算手段をいわゆるモンゴメリ乗算として並列に実行できるようにしたので、第１の発明と同様の理由により、並列演算の計算量を均衡させつつ、更に、計算量を低減させることができる。
【発明の効果】
【００６１】
以上説明したように本発明によれば、並列演算の計算量を均衡させつつ、更に、計算量を低減できる。
【発明を実施するための最良の形態】
【００６２】
以下、本発明の各実施形態について図面を用いて説明する。  
（第１の実施形態）
第１の実施形態では、入力ｘ，ｙ，Ｎに対し、ｚ＝ｘｙ（ｒs）-1 ｍｏｄ Ｎを計算する形態について説明する。ここで、ｓは１＜ｓ＜ｕなる整数であり、ｘ，ｙ，Ｎはｕワードであるものとする。
【００６３】
図１は本発明の第１の実施形態に係る剰余乗算装置の構成を示す模式図である。この剰余乗算装置３０は、制御部３２及び演算部３２を備えている。演算部３２は、ＲＯＭ３３、ＲＡＭ３４、ＢＭＭ演算ユニット３５を備えている。なお、この剰余乗算装置４０は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成の場合、ハードウェアとしては、例えばマスタＣＰＵと、マスタＣＰＵに制御されるスレーブＣＰＵとの２個のＣＰＵからなるデュアルＣＰＵ構成が、並列演算を実行する観点から好ましい。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。また、具体的なソフトウェアとしては、ＢＭＭ演算ユニット３５による演算処理のうち、第２モンゴメリ乗算ユニット３９の機能をスレーブＣＰＵに実現させ、残りのユニット３６〜３８，４０の機能をマスタＣＰＵに実現させるためのプログラムが、並列演算を実行する観点から好ましい。
【００６４】
ここで、制御部３１は、ＲＯＭ３２内のプログラムに基づいて、整数データＮ，ｘ，ｙ，ｒs を用いた剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘｒs）ｙ(ｒs)-1 ｍｏｄ Ｎ）を実行するように、演算部３２を制御する機能をもっている。
【００６５】
整数データＮは、基数ｒビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データであり、法として用いられる。整数データｘ，ｙは、Ｎ未満でｕワードの整数データであり、乗数として用いられる。整数データｒsは、Ｎ未満で且つ基数ｒのｓ乗（但し、ｓ＝ｕ／２）である整数データであり、いわゆるモンゴメリ定数Ｒ（＝ｒs ）として用いられる。ここではｒは、２のベキ（例えばｒ＝２32）であるものとする。
【００６６】
演算部３２は、ＲＯＭ３３、ＲＡＭ３４、ＢＭＭ演算ユニット３５を備えている。
【００６７】
ＲＯＭ３３は、制御部３１及びＲＭＭ演算ユニット３５から読出可能なメモリであり、後述する図４乃至図６に示すように剰余乗算を実行するためのプログラム等が格納されている。
【００６８】
ＲＡＭ３４は、制御部３１及びＲＭＭ演算ユニット３５から読出／書込可能なメモリであり、ＢＭＭのオペランドｘ，ｙ，Ｎや途中結果、最終結果ｚ等が格納される。また入力値ｘのモンゴメリ系表現Ｘに対する事前計算値Ｘ’＝Ｘｒs ｍｏｄ Ｎが格納される。
【００６９】
ＢＭＭ演算ユニット３５は、制御部３１により制御され、図２に示すように、モンゴメリ変換ユニット３６、オペランド分割ユニット３７、第１モンゴメリ乗算ユニット３８、第２モンゴメリ乗算ユニット３９及び剰余加算ユニット４０を備えている。
【００７０】
モンゴメリ変換ユニット３６は、ＲＡＭ３４内の整数データ（例、ｘ）をモンゴメリ系で表現するように変換し、得られた整数データ（例、Ｘ）をＲＡＭ３４に書き込む機能をもっている。
【００７１】
オペランド分割ユニット３７は、図３に示すように、ＲＡＭ３４を参照し、一方のオペランドｙを下位ｓワードで上位整数データ（以下、上位ワードという）と下位整数データ（以下、下位ワードという）に分割し、上位ワードｙHと下位ワードｙLを作る機能と、得られたｙH，ｙLをＲＡＭ３４に書き込む機能とをもっている。ここで、ｙ，ｙH，ｙLは、ｙ＝ｙHｒs＋ｙLの関係がある。
【００７２】
第１モンゴメリ乗算ユニット３８は、ＲＡＭ３４内の整数データＸ’，ｒs，Ｎ及び上位ワードｙHに基づいて、整数データｚH＝Ｘ’ｙH(ｒs)-1 ｍｏｄ Ｎ を計算し、得られた整数データｚHをＲＡＭ３４に書き込む機能をもっている。
【００７３】
第２モンゴメリ乗算ユニット３８は、第１モンゴメリユニット３８と並列に実行され、ＲＡＭ３４内の整数データＸ，ｒs，Ｎ及び下位ワードｙLに基づいて、整数データｚL＝ＸｙL(ｒs)-1 ｍｏｄ Ｎ を計算し、得られた整数データｚLをＲＡＭ３４に書き込む機能をもっている。
【００７４】
なお、２つのモンゴメリ乗算ユニット３８，３９は、２つのモンゴメリ乗算を並列実行する場合のみ必要であり、２つのモンゴメリ乗算を直列実行する場合には、２つのモンゴメリ乗算ユニット３８，３９のうちのいずれか一方を省略してもよい。これは以下の各実施形態でも同様である。
【００７５】
剰余加算ユニット４０は、第１及び第２モンゴメリ乗算ユニット３８，３９から個別に計算された値ｚH，ｚLをｍｏｄ Ｎで加算し、得られた結果ｚをＲＡＭ３４を介して制御部３１に出力するユニットである。
【００７６】
次に、以上のように構成された剰余乗算装置による剰余乗算方法を図４乃至図６のフローチャートを用いて説明する。この剰余乗算方法は、基数ｒビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘ，ｙと、Ｎ未満で且つ基数ｒのｓ乗（但し、ｓ＝ｕ／２）である整数データＲ＝ｒs とに基づいて剰余乗算ｚ＝ｘｙ ｍｏｄ Ｎ（＝（ｘｒs）ｙ(ｒs)-1 ｍｏｄ Ｎ）を実行し、得られた剰余乗算結果ｚを出力する内容である。以下、順に説明する。
【００７７】
始めに、制御部３１は、整数データＮ，ｘ，ｙ，Ｒを演算部３２に入力する。演算部３２では、整数データＮ，ｘ，ｙ，ｒs をＲＡＭ３４に記憶する。続いて、制御部３１は、演算部３２を制御し、演算部３２におけるＢＭＭ演算ユニット３５内の各要素３６〜４０を以下のように動作させる。
【００７８】
すなわち、ＢＭＭ演算ユニット３５においては、図４に示すように、モンゴメリ変換ユニット３６が、ＲＡＭ３４内の整数データｘ，ｒs，Ｎに基づいて、整数データＸ＝ｘｒs ｍｏｄ Ｎを計算し（ＳＴ５１）、得られた整数データＸをＲＡＭ３４に書き込む。
【００７９】
続いて、モンゴメリ変換ユニット３６は、ＲＡＭ３４内の整数データＸ，ｒs，Ｎに基づいて、整数データＸ’＝Ｘｒs ｍｏｄ Ｎを事前計算し（ＳＴ５２）、得られた整数データＸ’をＲＡＭ３４に書き込む。
【００８０】
オペランド分割ユニット３７は、ＲＡＭ３４内の整数データｙを下位ｓワードを境に、ｙHｒs＋ｙL（但し、ｙL＝ｙ ｍｏｄ Ｒ）の関係を持つ上位ワードｙH及び下位ワードｙLに分割し（ＳＴ５３）、得られたｙH，ｙLをＲＡＭ３４に書き込む。
【００８１】
第１及び第２モンゴメリ乗算ユニット３８，３９は、それぞれ上位ワードｙH又は下位ワードｙLのモンゴメリ乗算を互いに並列に実行する。
【００８２】
すなわち、第１モンゴメリ乗算ユニット３８は、ＲＡＭ３４内の整数データＸ’，ｒs，Ｎ及び上位ワードｙHに基づいて、整数データｚH＝Ｘ’ｙH(ｒs)-1 ｍｏｄ Ｎ を計算し（ＳＴ５４Ｈ）、得られた整数データｚHをＲＡＭ３４に書き込む。
【００８３】
第２モンゴメリ乗算ユニット３９は、ステップＳＴ５４Ｈと並列に実行され、ＲＡＭ３４内の整数データＸ，ｒs，Ｎ及び下位ワードｙLに基づいて、整数データｚL＝ＸｙL(ｒs)-1 ｍｏｄ Ｎ を計算し（ＳＴ５４Ｌ）、得られた整数データｚLをＲＡＭ３４に書き込む。なお、ステップＳＴ５４Ｈ，ＳＴ５４Ｌは、図５のＳＴ５４Ｈ−１〜ＳＴ５４Ｈ−８及び図６のＳＴ５４Ｌ−１〜ＳＴ５４Ｌ−８に示すように、図１９のアルゴリズムと同様に実行される。
【００８４】
剰余加算ユニット４０は、ＲＡＭ３４内の整数データｚH，ｚL，Ｎに基づいて、剰余加算ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎを実行し（ＳＴ５５）、得られた剰余加算結果ｚをＲＡＭ３４に書き込む。演算部３２は、ＲＡＭ３４内の剰余加算結果ｚを剰余乗算結果ｚとして制御部３１に出力する。
【００８５】
以上のようにして計算された剰余加算結果ｚが所望の剰余乗算結果ｚであることは次の式から確認できる。
【００８６】
ｚ＝（ｚH＋ｚL） ｍｏｄ Ｎ
＝（Ｘ’ｙH(ｒs)-1 ｍｏｄ Ｎ ＋ ＸｙL(ｒs)-1 ｍｏｄ Ｎ） ｍｏｄ Ｎ
＝（ＸｙHｒs（ｒs）-1 ｍｏｄ Ｎ ＋ ＸｙL(ｒs)-1 ｍｏｄ Ｎ） ｍｏｄ Ｎ
＝Ｘ（ｙHｒs＋ｙL）(ｒs)-1 ｍｏｄ Ｎ
＝Ｘｙ(ｒs)-1 ｍｏｄ Ｎ
＝（ｘｒs）ｙ(ｒs)-1 ｍｏｄ Ｎ
＝ｘｙｒs(ｒs)-1 ｍｏｄ Ｎ
＝ｘｙ ｍｏｄ Ｎ
従って、本実施形態では、従来のＢＭＭにおける剰余乗算とモンゴメリ乗算を、２つのモンゴメリ乗算に置き換えることができる。
【００８７】
また、分割位置を定めるｓは、２つのモンゴメリ乗算の計算量が均衡するように選択すると、ｓ＝ｕ／２とするのが良い。ここで、従来のＢＭＭの計算量（＝（ｕ−ｔ）ワードの剰余乗算又はｔワードのモンゴメリ乗算の計算量）と、本実施形態の計算量（＝ｕ／２ワードのモンゴメリ乗算の計算量）とを比較する。比較の結果は、次式の通りである。
【００８８】
従来のＢＭＭの計算量
＝ max {(u-t)ワードの剰余乗算の計算量、tワードのモンゴメリ乗算の計算量}
≧ tワードのモンゴメリ乗算の計算量
≧ ｕ／２ワードのモンゴメリ乗算の計算量
従って、従来のＢＭＭでｔ＞ｕ／２の場合は、明らかに本実施形態の方が計算量が少ないことが分かる。ｔ＝ｕ／２の場合は、次式の通りである。
【００８９】
max {ｕ／２ワードの剰余乗算の計算量、ｕ／２ワードのモンゴメリ乗算の計算量}
＝ ｕ／２ワードの剰余乗算の計算量
＞ ｕ／２ワードのモンゴメリ乗算の計算量
このため、従来のＢＭＭをｔ＝ｕ／２としても、本実施形態の方が計算量が少ないことが分かる。従って、本実施形態は、従来のＢＭＭに比べ、剰余乗算を高速に実行できる。
【００９０】
上述したように本実施形態によれば、基数ｒのｓ乗の整数データＲ（いわゆるモンゴメリ定数Ｒ＝ｒs）をｘに２回乗算することにより、ステップＳＴ５４Ｈ，ＳＴ５４Ｌをいわゆるモンゴメリ乗算として並列に実行できるようにしている。ここで、ステップＳＴ５４Ｈ，ＳＴ５４Ｌの両者ともモンゴメリ乗算であることから、従来のＢＭＭに比べ、計算量を低減させることができる。また、整数データＲのベキ指数ｓをｕ／２としたことから、並列演算の計算量を均衡させることができる。
【００９１】
（第２の実施形態）
図７は本発明の第２の実施形態に係るベキ乗剰余算装置の構成を示す模式図であり、前述した図面と同一部分には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９２】
第２の実施形態は、第１の実施形態の変形例であり、入力ｘ，ｄ，Ｎに対してベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを計算する形態であり、具体的には図１に示したハードウェア構成に加え、従来のＢＭＭ演算ユニット１５をも演算部５２に備えたハードウェア構成となっている。但し、図７に示すベキ乗剰余算装置５０は、図１に示した剰余乗算装置３０とは演算内容が異なるため、図８乃至図１０に示すようにソフトウェア構成が異なっている。すなわち、制御部５１は、図８乃至図１０に示すプログラムをＲＯＭ５４から読出し、このプログラムに基づいて、ベキ乗剰余算を実行するように演算部５２を制御する。
【００９３】
次に、以上のように構成されたベキ乗剰余算装置によるベキ乗剰余算方法について、図８乃至図１０のフローチャートを用いて説明する。このベキ乗剰余算方法は、基数ｒビットを１ワードとするとき、ｕワード（但し、ｕ＞１）の整数データＮと、Ｎ未満の整数データｘと、Ｎ未満でｋビットの整数データｄに基づいてベキ乗剰余算ｚ＝ｘd ｍｏｄ Ｎを実行し、得られたベキ乗剰余算結果ｚを出力する内容である。以下、順に説明する。
【００９４】
始めに、制御部５１は、整数データＮ，ｘ，ｄを演算部５２に入力する。演算部５２では、整数データＮ，ｘ，ｄをＲＡＭ５４に記憶する。続いて、制御部５１は、演算部５２を制御し、演算部５２における第１及び第２ＢＭＭ演算ユニット３５，１５内の各要素３６〜４０，１６〜２０を以下のように動作させる。
【００９５】
すなわち、第１ＢＭＭ演算ユニット３５においては、図８に示すように、モンゴメリ変換ユニット３６が、ＲＡＭ５４内の整数データＮのワード数ｕに基づいて、Ｎ未満で且つ基数のｓ乗（但し、ｓ＝ｕ／２）である第１モンゴメリ定数データＲ1（＝ｒs ）を定める。以下、Ｒ1をｒsともいう。
【００９６】
同様に、第２モンゴメリ変換ユニット１６は、Ｎ未満で且つ基数のｔ乗（但し、ｔ≧ｓ）である第２モンゴメリ定数データＲ2（＝ｒt ）を定める。以下、Ｒ2をｒtともいう。
【００９７】
第１モンゴメリ変換ユニット３６は、ＲＡＭ３４内の整数ｘ，Ｎ及び第１モンゴメリ定数データｒsに基づいて、ｘをモンゴメリ系での表現Ｘに変換するように、整数データＸ＝ｘｒs ｍｏｄ Ｎ を計算し（ＳＴ６１）、得られた整数データＸをＲＡＭ５４に書き込む。
【００９８】
第１モンゴメリ変換ユニット３６は、この整数データＸ，Ｎ及び第１モンゴメリ定数データｒs に基づいて、Ｘをモンゴメリ系での表現Ｘに変換するように、整数データＸ’＝Ｘｒs ｍｏｄ Ｎ を事前計算し（ＳＴ６２）、得られた整数データＸ’をＲＡＭ５４に書き込む。
【００９９】
第２モンゴメリ変換ユニット１６は、ＲＡＭ５４内の整数ｘ，Ｎ及び第２モンゴメリ定数データｒt に基づいて、新たな整数データＺ＝ｘｒt ｍｏｄ Ｎ を計算し（ＳＴ６３）、得られた整数データＺをＲＡＭ５４に書き込む。なお、新たな整数データＺは、中間変数Ｚとして機能する。
【０１００】
しかる後、制御部５１は、ベキ指数ｄの桁を示すｉの値をｋ−２から０までＳＴ６５からＳＴ６８をループさせる（ＳＴ６４）。
【０１０１】
ステップＳＴ６５では、第２ＢＭＭ演算ユニット１５を用いて、整数データＺを２乗してＮでの剰余を求める剰余２乗算を行う。具体的には図９のＳＴ６５−１〜ＳＴ６５−３に示す通りである。
【０１０２】
すなわち、オペランド分割ユニット１７は、ＲＡＭ５４内の新たな整数データＺを、ＺHｒt＋ＺL（但し、ＺL＝Ｚ ｍｏｄ ｒt ）の関係を持つ上位整数データＺH及び下位整数データＺLに分割し（ＳＴ６５−１）、得られたＺH，ＺLをＲＡＭ５４に書き込む。
【０１０３】
剰余乗算ユニット１８及びモンゴメリ乗算ユニット１９においては、それぞれ上位整数データｙHの剰余乗算、又は下位整数データｙLのモンゴメリ乗算を互いに並列に実行する。
【０１０４】
剰余乗算ユニット１８は、ＲＡＭ５４内の整数データＺ，ＺH，Ｎに基づいて、整数データＺ1H＝ＺＺH ｍｏｄ Ｎ を計算し（ＳＴ６５−２Ｈ）、得られた整数データＺ1HをＲＡＭ５４に書き込む。
【０１０５】
モンゴメリ乗算ユニット１９は、ステップＳＴ６５−２Ｈと並列に実行され、ＲＡＭ５４内の整数データＺ，ＺL，Ｎに基づいて、整数データＺ1L＝ＺＺL(ｒt)-1 ｍｏｄ Ｎ を計算し（ＳＴ６５−２Ｌ）、得られた整数データＺ1LをＲＡＭ５４に書き込む。
【０１０６】
剰余加算ユニット２０は、ＲＡＭ５４内の整数データＺ1H，Ｚ1L，Ｎに基づいて、第１の剰余加算Ｚ＝（Ｚ1H＋Ｚ1L） ｍｏｄ Ｎを実行し（ＳＴ６５−３）、得られた第１の剰余加算結果ＺをＲＡＭ５４に書き込む。
【０１０７】
次に、制御部５２は、図８に示すように、ＲＡＭ５４内の整数データｄのｉビット目（但し、ｉはｋ−２から０までの間で−１ずつ更新される）の値が“１”であるか否かを判定し（ＳＴ６６）、判定の結果が“１”の場合に、第１ＢＭＭ演算ユニット３５を制御してステップＳＴ６７を実行する。
【０１０８】
ステップＳＴ６７では、第１ＢＭＭ演算ユニット３５を用いて、整数データＺにＸを乗じてＮでの剰余を求める剰余乗算を、第１の実施形態に述べた方法で実行する。ステップＳＴ６７は、ステップＳＴ６２にてＸ’を事前に計算してあるため、Ｘ’，Ｘを用いて実行できる。具体的には図１０のＳＴ６７−１〜ＳＴ６７−３に示す通りである。
【０１０９】
すなわち、第１ＢＭＭ演算ユニット３５においては、判定結果が“１”の場合に、オペランド分割ユニット３７が、ＲＡＭ５４内の第１の剰余加算結果Ｚを、Ｚ2Hｒs＋Ｚ2L（但し、Ｚ2L＝Ｚ ｍｏｄ ｒs ）の関係をもつ上位整数データＺ2H及び下位整数データＺ2Lに分割し（ＳＴ６７−１）、得られたＺ2H，Ｚ2LをＲＡＭ５４に書き込む。
【０１１０】
第１及び第２モンゴメリ乗算ユニット３８，３９においては、それぞれ上位整数データｙH又は下位整数データｙLのモンゴメリ乗算を互いに並列に実行する。
【０１１１】
第１モンゴメリ乗算ユニット３８は、ＲＡＭ５４内の整数データＸ’，Ｎ、第１モンゴメリ定数データｒs 及び上位整数データＺ2Hに基づいて、整数データＺ3H＝Ｘ’Ｚ2H(ｒs)-1 ｍｏｄ Ｎ を計算し（ＳＴ６７−２Ｈ）、得られた整数データＺ3HをＲＡＭ５４に書き込む。
【０１１２】
第２モンゴメリ乗算ユニット３９は、ステップ６７−２Ｈと並列に実行され、ＲＡＭ５４内の整数データＸ，Ｎ、第１モンゴメリ定数データｒs 及び下位整数データＺ2Lに基づいて、整数データＺ3L＝ＸＺ2L(ｒs)-1 ｍｏｄ Ｎ を計算し（ＳＴ６７−２Ｌ）、得られた整数データＺ3LをＲＡＭ５４に書き込む。
【０１１３】
剰余加算ユニット４０は、ＲＡＭ５４内の整数データＺ3H，Ｚ3L，Ｎに基づいて、第２の剰余加算Ｚ＝（Ｚ3H＋Ｚ3L） ｍｏｄ Ｎを実行し（ＳＴ６７−３）、得られた第２の剰余加算結果ＺをＲＡＭ５４に書き込む。
【０１１４】
ステップＳＴ６８においては、制御部５１は、ステップＳＴ６６の判定結果が否の場合、又はステップＳＴ６７−３が実行された場合に、ｉがｉ＞０であれば、ｉを−１更新する。また、制御部５１は、ｉを更新したとき、ステップＳＴ６６の判定の結果が“１”であった場合には前記第２の剰余加算結果Ｚを新たな整数データＺとし、ＳＴ６６の判定の結果が否であった場合には第１の剰余加算結果Ｚを新たな整数データＺとして、ステップＳＴ６５からステップＳＴ６８までを繰り返し実行するように、演算部５２を制御する。
【０１１５】
一方、制御部５１は、ステップＳＴ６６の判定結果が否の場合、又はステップＳＴ６７−３が実行された場合に、ｉ＝０であれば、ステップＳＴ６９に移行して剰余乗算ユニット１８を制御する。
【０１１６】
すなわち、剰余乗算ユニット１８は、ＲＡＭ５４内の最後の剰余加算結果Ｚ、第２モンゴメリ定数データＲ2及び整数データＮに基づいて、剰余乗算ｚ＝Ｚ・１・(ｒt)-1 ｍｏｄ Ｎを実行し（ＳＴ６９）、得られた剰余乗算結果ｚ＝ｘd ｍｏｄ Ｎ をＲＡＭ５４に書き込む。演算部５２は、ＲＡＭ５４内の剰余乗算結果ｚをベキ乗剰余算結果ｚとして制御部５１に出力する。
【０１１７】
なお、上述した動作において、ステップＳＴ６５ではモンゴメリ定数ｒtでのモンゴメリ乗算を従来のＢＭＭで実行しているのに対し、ステップＳＴ６７ではモンゴメリ定数ｒsでのモンゴメリ乗算を、第１の実施形態の方法で実行している。このため、本実施形態のアルゴリズム全体の正当性を補足的に述べておく。
【０１１８】
始めに、中間変数Ｚは、初期化時（ＳＴ６３）に、モンゴメリ定数がｒtのモンゴメリ系に変換されている。次に、ステップＳＴ６５の計算式（Ｚ＝Ｚ2(ｒt)-1 ｍｏｄ Ｎ）は、ステップＳＴ６３の変換（Ｚ＝ｚｒt ｍｏｄ Ｎ）に基づいて、次のように表現できる。
【０１１９】
Ｚ2(ｒt)-1 ｍｏｄ Ｎ
＝(ｚｒt)(ｚｒt)(ｒt)-1 ｍｏｄ Ｎ
＝ｚ2ｒt ｍｏｄ Ｎ
すなわち、ステップＳＴ６５においては、ｚ2をモンゴメリ定数ｒtでモンゴメリ系に変換した数が求められている。
【０１２０】
同様に、ステップＳＴ６７の計算式（Ｚ＝ＸＺ(ｒs)-1 ｍｏｄ Ｎ）は、ステップＳＴ６１の変換（Ｘ＝ｘｒt ｍｏｄ Ｎ）及びステップＳＴ６３の変換（Ｚ＝ｚｒt ｍｏｄ Ｎ）に基づいて、次のように表現できる。
【０１２１】
ＸＺ(ｒs)-1 ｍｏｄ Ｎ
＝(ｘｒs)(ｚｒt)(ｒs)-1 ｍｏｄ Ｎ
＝ｘｚｒt ｍｏｄ Ｎ
すなわち、ステップＳＴ６７においては、ｘｚをモンゴメリ定数ｒtでモンゴメリ系に変換した数が求められている。
【０１２２】
このように、中間変数Ｚは常にモンゴメリ定数ｒtでモンゴメリ系に変換された状態になっている。従って、最後のステップＳＴ６９において、(ｒt)-1 ｍｏｄ Ｎを乗ずることにより、モンゴメリ系の状態を解消してｚ＝ｘd ｍｏｄ Ｎを求めている。
【０１２３】
なお、第１の実施形態で述べたように、従来のＢＭＭより第１の実施形態の方が高速に処理できる。ここで、第２の実施形態では、ベキ乗剰余算における乗算（ＳＴ６７に相当）で従来のＢＭＭに代えて第１の実施形態のＢＭＭを実行しているので、全てを従来のＢＭＭで実行する場合に比べ、処理を高速化することができる。
【０１２４】
また、第２の実施形態では、ベキ指数ｄの各ビットが“１”の場合に、第１の実施形態のＢＭＭ（ＳＴ６７に相当）を実行する。よって、ベキ指数ｄの半分のビットが“１”だと仮定すると、ｋ／２回のＢＭＭにおいて、乗余乗算をモンゴメリ乗算に置き換えることができる。
【０１２５】
具体例として、ｒ＝２32、ｕ＝３２とする。ベキ指数ｄのビット数もｋ＝１０２４ビットとする。ここで、ステップＳＴ６５，ＳＴ６７を非特許文献３記載のＢＭＭで演算したとする。ステップＳＴ６５，ＳＴ６７は平均的に５１２回実行されるものとすると、例えば図２０の場合だと、1,646,592回（＝（1024＋512）×1072）の積和演算が必要である。従って、第２の実施形態の手法を用いることで乗算の部分の16,384回（＝512×（1072−1040））の積和演算を削減可能である。すなわち、ベキ乗剰余算全体のうち、１％の処理時間を削減することができる。また同様に図２１の場合には、ベキ乗剰余算全体のうち、約２％の処理時間を削減することができる。
【０１２６】
上述したように本実施形態によれば、基数ｒのｓ乗の第１モンゴメリ定数データｒs をｘに２回乗算することにより、ステップＳＴ６７−２Ｈ，ＳＴ６７−２Ｌをいわゆるモンゴメリ乗算として並列に実行できるようにしたので、第１の実施形態と同様に、並列演算の計算量を均衡させつつ、更に、計算量を低減させることができる。すなわち、ステップＳＴ６７−２Ｈ，ＳＴ６７−２Ｌの両者ともモンゴメリ乗算であることから、従来のＢＭＭに比べ、計算量を低減させることができる。また、第１モンゴメリ定数データｒsのベキ指数ｓをｕ／２としたことから、並列演算の計算量を均衡させることができる。
【０１２７】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１３０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、LＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１３１】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１３４】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１３５】
【図１】本発明の第１の実施形態に係る剰余乗算装置の構成を示す模式図である。
【図２】同実施形態におけるＢＭＭ演算ユニットの構成を示す模式図である。
【図３】同実施形態におけるオペランド分割ユニットの機能を説明するための模式図である。
【図４】同実施形態における剰余乗算方法を説明するためのフローチャートである。
【図５】同実施形態におけるモンゴメリ乗算のアルゴリズムを示すフローチャートである。
【図６】同実施形態におけるモンゴメリ乗算のアルゴリズムを示すフローチャートである。
【図７】本発明の第２の実施形態に係るベキ乗剰余算装置の構成を示す模式図である。
【図８】同実施形態におけるベキ乗剰余算方法を説明するためのフローチャートである。
【図９】同実施形態における２並列剰余乗算（ＢＭＭ）を説明するためのフローチャートである。
【図１０】同実施形態における２並列剰余乗算（ＢＭＭ）を説明するためのフローチャートである。
【図１１】一般的なベキ乗剰余算におけるバイナリ法を説明するためのフローチャートである。
【図１２】一般的なモンゴメリ乗算を利用したベキ乗剰余算を説明するためのフローチャートである。
【図１３】従来の剰余乗算装置の構成を示す模式図である。
【図１４】従来のＢＭＭ演算ユニットの構成を示す模式図である。
【図１５】従来のオペランド分割ユニットの機能を説明するための模式図である。
【図１６】一般的な乗算のアルゴリズムを示すフローチャートである。
【図１７】一般的な剰余乗算のアルゴリズムを示すフローチャートである。
【図１８】一般的な除算のアルゴリズムを示すフローチャートである。
【図１９】一般的なモンゴメリ乗算のアルゴリズムを示すフローチャートである。
【図２０】一般的なＢＭＭの計算量の評価結果及び最適なｔの値を示す図である。
【図２１】一般的なＢＭＭの計算量の評価結果及び最適なｔの値を示す図である。
【符号の説明】
【０１３６】
３０…剰余乗算装置、３１，５１…制御部、３２，５２…演算部、３３，５３…ＲＯＭ、３４，５４…ＲＡＭ、１５，３５…ＢＭＭ演算ユニット、１６，３６…モンゴメリ変換ユニット、１７，３７…オペランド分割ユニット、１８…剰余乗算ユニット、１９，３８，３９…モンゴメリ乗算ユニット、２０，４０…剰余加算ユニット。
【図１】
2007187985.tif 000003
【図２】
2007187985.tif 000004
【図３】
2007187985.tif 000005
【図４】
2007187985.tif 000006
【図５】
2007187985.tif 000007
【図６】
2007187985.tif 000008
【図７】
2007187985.tif 000009
【図８】
2007187985.tif 000010
【図９】
2007187985.tif 000011
【図１０】
2007187985.tif 000012
【図１１】
2007187985.tif 000013
【図１２】
2007187985.tif 000014
【図１３】
2007187985.tif 000015
【図１４】
2007187985.tif 000016
【図１５】
2007187985.tif 000017
【図１６】
2007187985.tif 000018
【図１７】
2007187985.tif 000019
【図１８】
2007187985.tif 000020
【図１９】
2007187985.tif 000021
【図２０】
2007187985.tif 000022
【図２１】
2007187985.tif 000023