(57)【要約】【課題】  従来、高速に剰余演算を行うことができなかった使用環境において高速な剰余演算を実現する。【解決手段】  剰余対象ｃをc=Σi=0 cixiと表現した場合における、各係数ｃｉを入力し、縮約手段１６において、係数ｃｉと乗算係数ｐｈとを用い、Σi=0u-1 ci’xi=Σi=0 ci’ximod f(x) を満たす各係数ｃｉ’を算出する。ただし、Ｌ：ｍｏｄｎの値のビット数、ｗ：ワードのビット数、ｕ：Ｌ／ｗ以上の最小の整数、Ｑ：２以上の整数、Ｅ＝ｕｗ‐Ｌ、法n=QL-Σj=0L-1 djQj、乗算係数ph=Σk=0w-1 dwh+k-EQk(h=0,1,...,u-1)、f(x)=xu‐Σi=0u-1pixiである。  そして、全ての係数ｃｉ’の算出後、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う。  【選択図】        図１
2005208327.tif 000002
【特許請求の範囲】
【請求項１】
ｃ ｍｏｄ ｎの剰余演算を行う剰余装置であって、
【数１】
2005208327.tif 000037
各係数ｃｉの入力を受け付ける剰余対象入力手段と、
ｍｏｄ ｎの値をＬビットとし、ソフトウェアからみた処理単位であるワードのビット数をｗとし、ｕをＬ／ｗ以上の最小の整数とし、Ｑを２以上の整数とし、Ｅ＝ｕｗ‐Ｌとし、
【数２】
2005208327.tif 000038
を格納する乗算係数格納手段と、
前記係数ｃｉと前記乗算係数ｐｈとを用い、
【数３】
2005208327.tif 000039
を満たす各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する縮約手段と、
全ての前記係数ｃｉ’の算出後、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う正規化手段と、
を有することを特徴とする剰余装置。
【請求項２】
請求項１記載の剰余装置であって、
前記法ｎは、
前記縮約手段における各演算結果のビット数を、ハードウェアが一度に取り扱うことが可能なビット数未満とする値である、
ことを特徴とする剰余装置。
【請求項３】
請求項１記載の剰余装置であって、
前記Ｌは１６０であり、
前記ｕは６であり、
前記法ｎは２１６０‐２７９‐１５であり、
前記縮約手段は、
ｉ＝６，７に対して、ｃｉ←ｃｉ＋ｃｉ+３の演算を行う第１の加算手段と、
前記第１の加算手段における演算後、ｉ＝３，４，５に対して、ｃｉ←ｃｉ＋ｃｉ+３の演算を行う第２の加算手段と、
前記第１の加算手段における演算後、ｉ＝０，１，…，４に対して、２２（２４‐１）ｃｉ+６の演算を行う多倍算手段と、
前記第２の加算手段及び前記多倍算手段における演算後、ｉ＝０，１，…，４に対して、ｃｉ←ｃｉ＋２２（２４‐１）ｃｉ+６の演算を行う第３の加算手段と、を有し、
前記係数ｃｉ’（ｉ＝０，１，…，４）は、
前記第３の加算手段における演算結果ｃｉ（ｉ＝０，１，…，４）であり、
前記係数ｃ５’は、
前記第２の加算手段における演算結果ｃ５である、
ことを特徴とする剰余装置。
【請求項４】
請求項１記載の剰余装置であって、
前記Ｌは１６０であり、
前記ｕは６であり、
前記法ｎは２１６０‐２３１‐１であり、
前記縮約手段は、
ｉ＝０，１，…，４に対して、２２ｃｉ+６の演算を行う第１の多倍算手段と、
前記第１の多倍算手段における演算結果を用い、ｃｉ←ｃｉ＋２２ｃｉ+６の演算を行う第１の加算手段と、
前記第１の加算手段における演算後、ｉ＝１，２，…，５に対して、２６ｃｉ+５の演算を行う第２の多倍算手段と、
前記第２の多倍算手段における演算結果を用い、ｉ＝１，２，…，５に対して、ｃｉ←ｃｉ＋２６ｃｉ+５の演算を行う第２の加算手段と、を有し、
前記係数ｃ０’は、
前記第１の加算手段における演算結果ｃ０であり、
前記係数ｃｉ’（ｉ＝１，２，…，５）は、
前記第２の加算手段における演算結果ｃｉ’（ｉ＝１，２，…，５）である、
ことを特徴とする剰余装置。
【請求項５】
請求項１から４の何れかに記載の剰余装置であって、
【数４】
2005208327.tif 000040
各係数ａｓ及びｂｔの入力を受け付ける乗算対象入力手段と、
０≦ｓ,ｔ≦ｕ‐１の全ての整数ｓ,ｔに対しａｓｂｔの演算を行う乗算手段と、
前記乗算手段における演算結果を用い、０≦ｓ,ｔ≦ｕ‐１の全ての整数ｓ,ｔに対し、各項間の繰り上がり補正を行うことなく、ｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔの演算を行う第４の加算手段と、を有し、
前記剰余対象ｃの各係数ｃｉは、
前記第４の加算手段における最終的な演算結果ｃｓ＋ｔである、
ことを特徴とする剰余装置。
【請求項６】
ａｂ ｍｏｄ ｎの演算を行う剰余装置であって、
ｍｏｄ ｎの値は１６０ビットであり、ｎ＝２１６０‐２７９‐１５であり、ソフトウェアからみた処理単位であるワードのビット数をｗとした場合における１６０／ｗ以上の最小の整数は６であり、
【数５】
2005208327.tif 000041
各係数ａｓ及びｂｔの入力を受け付ける乗算対象入力手段と、
ｆ（ｘ）＝ｘ６‐ｘ３‐２２（２４‐１）  とした場合に、
【数６】
2005208327.tif 000042
を満たす係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する縮約手段と、
全ての前記係数ｃｉ’の算出後、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う正規化手段と、
を有し、
前記縮約手段は、
Ａ０＝ａ２ｘ２＋ａ１ｘ＋ａ０，
Ａ１＝ａ５ｘ２＋ａ４ｘ＋ａ３，
Ｂ０＝ｂ２ｘ２＋ｂ１ｘ＋ｂ０，
Ｂ１＝ｂ５ｘ２＋ｂ４ｘ＋ｂ３，
Ｘ＝ｘ３， 
とした場合における、乗算項Ａ０Ｂ０を前記係数ａｓ及びｂｔを用いて算出する乗算項算出手段と、
算出された前記乗算項Ａ０Ｂ０を格納する乗算項格納手段と、
前記係数ａｓ及びｂｔ、及び前記乗算項格納手段に格納された前記乗算項Ａ０Ｂ０を用い、
ｃ＝（（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）−Ａ０Ｂ０）Ｘ＋Ａ０Ｂ０＋２２（２４‐１）Ａ１Ｂ１
の演算を行い、当該ｃの項ｘｉに対する係数ｃｉ’を算出する係数算出手段と、
を有する、
ことを特徴とする剰余装置。
【請求項７】
ｃ ｍｏｄ ｎの剰余演算を行う剰余方法であって、
ｍｏｄ ｎの値をＬビットとし、ソフトウェアからみた処理単位であるワードのビット数をｗとし、ｕをＬ／ｗ以上の最小の整数とし、Ｑを２以上の整数とし、Ｅ＝ｕｗ‐Ｌとし、
【数７】
2005208327.tif 000043
を乗算係数格納手段に格納しておき、
剰余対象入力手段において、
【数８】
2005208327.tif 000044
各係数ｃｉの入力を受け付け、
縮約手段において、前記係数ｃｉと前記乗算係数ｐｈとを用い、
【数９】
2005208327.tif 000045
を満たす各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出し、
全ての前記係数ｃｉ’の算出後、正規化手段において、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う、
ことを特徴とする剰余方法。
【請求項８】
請求項１から６の何れかに記載の剰余装置としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項８記載のプログラムを格納したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、剰余演算を行う剰余装置、剰余方法、その機能を実現するためのプログラム及び記録媒体に関し、特に、剰余演算を高速に行うことができる剰余装置、剰余方法、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
多倍長の剰余乗算は、離散対数問題の困難性に根拠をおく公開鍵暗号や電子署名などの実装中から多数実行され、剰余乗算の速度が公開鍵暗号や電子署名などの速度を決めるといっても過言ではない。そのため従来より数多くの剰余乗算の高速化手法が考案されてきた。
多くの剰余乗算計算法では、
ｍ←ａｂ ｍｏｄ ｎ  （０≦ａ,ｂ≦ｎ）
を計算する際に、
Ｓｔｅｐ１：ｃ←ａｂを計算
Ｓｔｅｐ２：ｃ ｍｏｄ ｎを計算
という手順を踏むことが多い。
【０００３】
＜Ｓｔｅｐ１の高速化＞
このＳｔｅｐ１で必要となる多倍長乗算の高速実装法として非特許文献１の方法が知られている。以下に、Ｗビット同士の積から２Ｗビットを生成する乗算器と、２Ｗビット加算器を利用し、非特許文献１の方法によってａ,ｂの積を求める手順を説明する。なお、ａやｂはＬビット以内とする。なお、Ｌは、セキュリティパラメータ等の規格化されたデータのビット数を示す。
まず、ａ,ｂを以下のようにＱｗ進数（Ｑ≧２）表現する。
【数１０】
2005208327.tif 000003
ここで、ｕは、
【数１１】
2005208327.tif 000004
【０００４】
また、式（３）を条件とするのは、教科書法で乗算を計算した場合、（Ｑｗ‐１）２のデータをｕ回加算する場合もあるが、そのような場合であっても、演算結果が２Ｗビット乗算器の処理能力Ｑ２Ｗを超えない（溢れが生じない）ようにするためである。また、式（１）のような表現を冗長表現と呼ぶ。
このとき、ａとｂの積である
【数１２】
2005208327.tif 000005
を以下のように計算する。
Ｓｔｅｐ１−１  初期化：「ｃｉ←０」とする。
Ｓｔｅｐ１−２  語長乗算：全ての０≦ｓ,ｔ≦ｕに対し、「ｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔ」を計算する。
Ｓｔｅｐ１−３  繰り上がり補正：ｉ＝０,１,...,２ｕ-２に対し、
【数１３】
2005208327.tif 000006
【０００５】
ここで、ｗは式（３）の条件を満たすように選ばれているため、Ｓｔｅｐ１−２の加算で溢れが生じることはない。また、Ｓｔｅｐ１−２の加算では繰り上がり補正を行わず、最後のＳｔｅｐ１−３において繰り上がり補正をまとめて行うため、処理を高速化できる。
なお、ＬがＷに比べあまり大きくなく、実行すべき多倍長乗算の回数が少ない場合は、冗長表現と通常の２Ｗ進数を使った表現の変換コスト（Ｓｔｅｐ１−３）が馬鹿にならない。しかし、暗号用途のように多数の乗算を必要とする場合は、通常表現との変換コストを考えても冗長表現を使った乗算の方が有利であることが多い。
【０００６】
＜Ｓｔｅｐ２の高速化＞
また、計算に適した法ｎを選び、Ｓｔｅｐ２の剰余を高速に計算する方法がある。これは、例えば、公開鍵暗号などを構成する際に使用される方法である。このような方法の１つとして特許文献１の方法が知られている。以下に、この特許文献１の方法について説明する。
特許文献１の方法では、
【数１４】
2005208327.tif 000007
となるｎを利用する。ただし、ｋはｗｋ＝Ｌを満たす自然数である。すなわち、Ｌはｗの倍数である。
以下では、例として、
Ｑ＝２，ｗ＝６４，ｋ＝３，Ｌ＝１９２，
ｎ＝（２６４）３‐２６４‐１  …(5)
を選んだ場合のＳｔｅｐ２の処理を説明する。
【０００７】
また、剰余対象ｃは、
【数１５】
2005208327.tif 000008
と表されているとする。
このとき式（５）より、
（２６４）３≡２６４＋１（ｍｏｄ ｎ）  …(7)
であり、この合同式（７）を式（６）に複数回利用すると、
ｃ≡（ｃ０＋ｃ３＋ｃ５）＋（ｃ１＋ｃ３＋ｃ４＋ｃ５）２６４＋（ｃ２＋ｃ４＋ｃ５）（２６４）２（ｍｏｄ ｎ）  …(8)
となる。
【０００８】
ここで、式（６）のｃｉ＜２６４より、式（８）の右辺の
（ｃ０＋ｃ３＋ｃ５）＋（ｃ１＋ｃ３＋ｃ４＋ｃ５）２６４＋（ｃ２＋ｃ４＋ｃ５）（２６４）２  …(9)
は、式（５）で示されるｎの４倍以下となる。そのため、式（９）の各係数（ｃ０＋ｃ３＋ｃ５）、（ｃ１＋ｃ３＋ｃ４＋ｃ５）、（ｃ２＋ｃ４＋ｃ５）を算出し、式（９）から式（５）で示されるｎを最大３回減じることにより剰余結果ｍを求めることができる。これは、式（６）からｃのｍｏｄ ｎを直接計算する場合に比べ、計算量を大幅に低減できることを意味している。
【０００９】
なお、式（９）の各係数（ｃ０＋ｃ３＋ｃ５）、（ｃ１＋ｃ３＋ｃ４＋ｃ５）、（ｃ２＋ｃ４＋ｃ５）の加算処理は、上位項への繰り上がり補正を行いつつ実行される。すなわち、例えば、（ｃ０＋ｃ３＋ｃ５）の加算過程のｃ０＋ｃ３で加算結果が２６４以上となった場合、その時点でその項の繰り上がり補正値（ｃ０＋ｃ３）ｍｏｄ ２６４と、繰り上がり分である（ｃ０＋ｃ３）／２６４以下の最大の整数を算出する処理を行い、さらに必要な場合には、さらに上位項への繰り上がり処理を順次行う。
【非特許文献１】Intel Corporation, “ストリーミングＳＩＭＤ拡張命令２（ＳＳＥ２）を使用した大数の乗算の実行，”バージョン２．０，ＡＰ−９４１，資料番号２４８６０６Ｊ−００１，２０００
【特許文献１】松井充，“演算装置、演算方法並びにその演算方法を記録した記録媒体，”特許第３１８３６７０号，１９９９年１月２１日出願，２００１年４月２７日登録
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、従来の剰余演算方法の場合、使用環境によっては高速に剰余演算を行うことができないことがある。
つまり、式（４）の説明で示した通り、特許文献１の剰余方法は、Ｌがｗの倍数であることを前提としており、Ｌがｗの倍数でない場合には使用できない。
また、特許文献１の剰余方法では、計算量が大きい繰り上がり補正を逐一実行しつつ各係数の加算処理を実行するため、繰り上がり補正が多い場合には、たとえ特許文献１の剰余方法が使用できる場合であっても、高速に剰余演算を行うことができない。
【００１１】
本発明はこのような点に鑑みてなされたものであり、従来高速に剰余演算を行うことができなかった使用環境において高速な剰余演算を実現する剰余装置を提供することを目的とする。
また、本発明の他の目的は、従来高速に剰余演算を行うことができなかった使用環境において高速な剰余演算を実現する剰余方法を提供することである。
【課題を解決するための手段】
【００１２】
この発明では上記課題を解決するために、まず、ｍｏｄ ｎの値をＬビットとし、ソフトウェアからみた処理単位であるワードのビット数をｗとし、ｕをＬ／ｗ以上の最小の整数とし、Ｑを２以上の整数とし、Ｅ＝ｕｗ‐Ｌとし、
【数１６】
2005208327.tif 000009
を乗算係数格納手段に格納しておく。
また、剰余対象入力手段に、
【数１７】
2005208327.tif 000010
各係数ｃｉを入力する。
そして、縮約手段において、係数ｃｉと乗算係数ｐｈとを用い、
【数１８】
2005208327.tif 000011
を満たす各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。
【００１３】
そして、全ての係数ｃｉ’の算出後、正規化手段において、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う。
ここで、Ｅは、ワード単位（ｗビット）で処理可能なＬビット以上の最小ビット数とＬビットとの誤差を意味しており、乗算係数ｐｈはこの誤差Ｅを考慮して設定されるものである。従って、乗算係数ｐｈ及びこれを用いて定義されたｆ（ｘ）は、Ｌがｗの倍数でない場合をも考慮したものである。そして、この乗算係数ｐｈと各係数ｃｉとを用い、縮約手段において算出された各係数ｃｉ’を用いることにより、前述の特許文献１の剰余方法と同様、少ない計算量でｃ ｍｏｄ ｎを求めることができる。つまり、Ｌがｗの倍数でない場合であっても高速にｃ ｍｏｄ ｎを求めることができる。また同様な理由により、Ｌがｗの倍数でなくても、本発明と非特許文献１の乗算方法とを併用でき、高速な剰余乗算が実現できる。
【００１４】
また、縮約手段は、各項間における係数の繰り上がり補正を行うことなくｃ’の各係数ｃｉ’を算出する。そのため、繰り上がり補正を行いつつ各係数を算出する場合に比べ、処理が高速になる。
さらに、繰り上がり補正を最後にまとめて行うことにより、繰り上がり補正を行いつつ各係数を算出する場合に比べ、繰り上がり補正の計算量を低減することが可能となり、処理が高速になる。
【発明の効果】
【００１５】
本発明では、係数ｃｉと乗算係数ｐｈとを用い、
【数１９】
2005208327.tif 000012
を満たす各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。
この乗算係数ｐｈ及びｆ（ｘ）は、Ｌがｗの倍数でない場合をも考慮したものである。そして、その演算結果を用いることにより、少ない計算量でｃ ｍｏｄ ｎを算出することができる。また、繰り上がり補正を逐一行わないため、従来繰り上がり補正が多く計算量が多くなっていた場合であっても、高速に剰余演算処理を実行することができる。
以上より、本発明では、従来高速に剰余演算を行うことができなかった使用環境において高速な剰余演算を実現することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、この発明の実施の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明における第１の実施の形態について説明する。
＜概要＞
図１は、本形態の剰余装置１０の全体構成を例示したブロック図であり、図４は、この剰余装置１０の処理の全体を説明するためのフローチャートである。以下、これらの図を用いて本形態の概要を説明する。
【００１７】
図１に例示するように、本形態の剰余装置１０は、乗算対象入力手段１１、乗算手段１２、加算手段１３（「第４の加算手段」に相当）、剰余対象入力手段１４、乗算係数格納手段１５、縮約手段１６、正規化手段１７及び制御手段１８を有しており、制御手段１８の制御のもと、入力されたａ,ｂについての剰余乗算（ｃ←ａｂ、ｍ←ｃｍｏｄ ｎ）を行う。
なお、本形態の剰余装置１０は、語長Ｗビットを用いた剰余乗算を想定し、ハードウェアからみた処理単位を２Ｗビットとする公知のコンピュータに所定のプログラムを実行させることにより構築されたものである。つまり、Ｗビット同士から２Ｗビットを得る乗算と、２Ｗビット同士の加算が効率よく計算できる環境を想定している。
【００１８】
また、本形態では、法ｎを
【数２０】
2005208327.tif 000013
とおく。ここで、Ｌ（ビット）は出力するｍｏｄ ｎの値のビット数を意味し、例えば、セキュリティビット等が該当する。また、Ｑは２以上の整数である。
【数２１】
2005208327.tif 000014
とおく。
ここで、ｗはソフトウェアからみた処理単位であるワードを示し、ｕはＬ／ｗ以上の最小の整数を意味する。また、Ｅは、ワード単位（ｗビット）で処理可能なＬビット以上の最小ビット数と、Ｌビットとの誤差を意味する（Ｅ＝ｕｗ‐Ｌ）。また、式（１１）のｄｗｈ＋ｋ‐Ｅは、式（１０）のｄｊに対応するものであるが、ｗｈ＋ｋ‐Ｅ＜０の場合にはｄｗｈ＋ｋ‐Ｅ＝０とする。また、ｘは、正規化手段１７における正規化処理の際ｘ＝Ｑｗとして取り扱われる値である。
【００１９】
なお、式（１１）で算出されたｐｈ（以下「乗算係数」と呼ぶ。）は、乗算係数格納手段１５に格納される。ここで、乗算係数ｐｈの格納とは、乗算係数ｐｈをデータとして格納する場合の他、この乗算係数ｐｈが組み込まれたプログラムを格納する場合も含まれる。
剰余装置１０を用いて剰余乗算を行う場合、まず、乗算対象入力手段１１において、
【数２２】
2005208327.tif 000015
と表現した場合における、各係数ａｓ及びｂｔの入力を受け付ける（ステップＳ１）。なお、この例で入力されるａｓ及びｂｔは、
０≦ａｓ,ｂｔ＜Ｑｗ  （ｓ,ｔ＝０,１,...,ｕ‐２）
０≦ａｕ−１,ｂｕ−１＜Ｑｗ‐Ｅ
を満たすものとする。また、式（１３）,（１４）のような表現を「冗長表現」と呼ぶ。
【００２０】
次に、乗算手段１２において、乗算対象入力手段１１から係数ａｓ及びｂｔを受け取り、０≦ｓ,ｔ≦ｕ‐１の全ての整数ｓ,ｔに対してａｓｂｔの演算を行う。また、加算手段１３において、乗算手段１２における演算結果を用い、０≦ｓ,ｔ≦ｕ‐１の全ての整数ｓ,ｔに対し、各項間の繰り上がり補正を行うことなく、ｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔの演算を行う（乗算処理：ステップＳ２）。
なお、ｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔの演算結果は、ｉ＝ｓ＋ｔ、
【数２３】
2005208327.tif 000016
とおいた場合における各係数ｃｉを構成する。そして、ステップＳ２で示した「各項間の繰り上がり補正を行うことなく」とは、項ｘｉの係数ｃｉを構成するｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔの演算結果がｘ以上となった場合でも、この演算結果を項ｘｉ＋１の係数として繰り上げる処理を行わないことを意味する。
次に、剰余対象入力手段１４において、加算手段１３での最終的な演算結果ｃｓ＋ｔの入力を受け付ける（ステップＳ３）。なお、このｃｓ＋ｔは、ｉ＝ｓ＋ｔとし、剰余対象ｃを
【数２４】
2005208327.tif 000017
と表現した場合における各係数ｃｉに相当する。
【００２１】
次に、縮約手段１６において、剰余対象入力手段１４において入力された係数ｃｉ＝ｃｓ＋ｔと、乗算係数格納手段１５から抽出した乗算係数ｐｈとを用い、
【数２５】
2005208327.tif 000018
を満たす各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する（縮約処理：ステップＳ４）。つまり、式（１２）から導かれる合同式  
【数２６】
2005208327.tif 000019
を式（１５）に適用することにより得られる式（１６）の左辺の各係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。なお、ここでの「各項間の繰り上がり補正を行うことなく」とは、式（１７）を式（１５）に適用した場合における項ｘｉ（ｉ≦ｕ‐１）の係数ｃｉ’を算出する過程において、演算結果がｘ以上となった場合でも、この演算結果を項ｘｉ＋１の係数として繰り上げる処理を行わないことを意味する。
【００２２】
全ての前記係数ｃｉ’の算出後、各係数ｃｉ’は正規化手段１７に送られ、正規化手段１７は、ｘ＝Ｑｗとした場合における当該係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行い（ステップＳ５）、またＬビット長の縮約処理を行うことにより剰余乗算結果ｍを算出する。
ここで、前述の乗算係数ｐｈ及びこれを用いて定義されたｆ（ｘ）は、Ｌがｗの倍数でない場合をも考慮したものである。そして、この乗算係数ｐｈと各係数ｃｉとを用い、縮約手段１６において算出された各係数ｃｉ’を用いることにより、少ない計算量でｃ ｍｏｄ ｎを求めることができる。つまり、Ｌがｗの倍数でない場合であっても高速にｃ ｍｏｄ ｎを求めることができる。
【００２３】
また、縮約手段１６は、各項間の係数の繰り上がり補正を行うことなく算出されたｃ←ａｂの各係数を用い、さらに各項間における係数の繰り上がり補正を行うことなくｃ’の各係数ｃｉ’を算出し、最後に正規化手段１７において、全ての繰り上がり補正をまとめて行う。そのため、繰り上がり補正を行いつつ各係数を算出する場合に比べ、処理が高速になる。
なお、本形態における法ｎは、縮約手段１６における各演算結果のビット数を、ハードウェアが一度に取り扱うことが可能なビット数（２Ｗビット）未満とする値である。すなわち、乗算対象入力手段１１において、入力されるａｓ及びｂｔが、
０≦ａｓ,ｂｔ＜Ｑｗ  （ｓ,ｔ＝０,１,...,ｕ‐２）
０≦ａｕ−１,ｂｕ−１＜Ｑｗ‐Ｅ
であった場合、式（１５）の各係数ｃｉは、
【数２７】
2005208327.tif 000020
となるが、このようなｃｉに対して式（１６）の左辺の各係数ｃｉ’がＱ２Ｗ未満となるようなｆ（ｘ）に対応するｎを法とする。これにより、演算結果が、ハードウェアが一度に取り扱うことが可能なビット数を超え、その補正処理が必要となるという事態を防止できる。なお、一部の演算結果が、ハードウェアが一度に取り扱うことが可能なビット数を超えることになるｎであっても、他の補正処理との関係で処理が高速化できる場合には、そのようなｎを用いてもよい。
【００２４】
このようなｎは、Ｌ＝１６０、ｗ＝２７とした場合に素数だけでも２２７５１個存在する。そして、その中で縮約手段１６における計算コストが少ないものとして、例えば、
２１６０‐２２７‐２‐（２４‐１）
２１６０‐２６２２７‐２‐１
２１６０‐２３・２７‐２‐（２４‐１）
等を例示できる。
＜実施例１＞
次に、本形態における実施例１について説明する。
【００２５】
本実施例は、Ｑ＝２であり、Ｌが１６０であり、Ｗが３２であり、ｗが２７であり、ｕが６であり、法ｎが２１６０‐２７９‐１５（＝２１６０‐２３・２７‐２‐（２４‐１））である場合のものである。この場合、Ｅ＝２、ｐ０＝２２（２４‐１）、ｐ３＝１、ｐｈ＝０（ｈ＝１,２,４,５）、ｆ（ｘ）＝ｘ６‐ｘ３‐６０（＝ｘ６‐ｘ３‐２２（２４‐１））となる。
＜実施例１の構成＞
実施例１における全体構成は、前述した通りである（図１）。以下では、実施例１における縮約手段１６及び正規化手段１７の詳細構成のみを説明する。
【００２６】
図２は、本実施例における縮約手段１６の構成を示したブロック図であり、図３は、本実施例における正規化手段１７の構成を示したブロック図である。
図２に示すように、本実施例の縮約手段１６は、加算手段１６ａ、１６ｂ、１６ｄ（「第１〜３の加算手段」に相当）及び多倍算手段１６ｃを有しており、図３に示すように、本実施例の縮約手段１７は、繰り上がり補正手段１７ａａ、１７ａｂ、１７ｃ及び縮約処理手段１７ｂａ、１７ｂｂ、１７ｂｃ、１７ｂｄを有している。
また、より具体的には、例えば、本実施例の縮約手段１６及び正規化手段１７は、３２ビット同士の積６４ビットを得る乗算器と、６４ビット同士の和を得る加算器によって実現される。ここで、加算器は減算も実行でき、６４ビットの値のシフトも効率的に計算可能とする。このような環境の例としてＩｎｔｅｌ（登録商標）のＳＳＥ２がある。もちろん、６４ビット同士の加算が直接出来ない場合に、３２ビット同士の加算を組み合わせて６４ビットの加算を実行するなどの置換えがあってもよい（後述する実施例２についても同様）。
【００２７】
＜実施例１の処理＞
実施例１における処理の全体は、前述した通りである（図４）。以下では、実施例１における、ステップＳ２,Ｓ４,Ｓ５の処理（図４）の詳細のみを説明する。
＜実施例１におけるステップＳ２の処理＞
図５は、本実施例における図４のステップＳ２の処理を説明するためのフローチャートである。
図５に示すように、本処理ではまず、ｉ＝０,１,...,１０に対し、ｃｉに０を代入し、ｓ及びｔに０を代入する（ステップＳ１１）。次に、乗算手段１２（図１）においてａｓｂｔの演算を行い、その演算結果を加算手段１３に送る（ステップＳ１２）。加算手段１３は、ｃｓ＋ｔ←ｃｓ＋ｔ＋ａｓｂｔの演算を行う（ステップＳ１３）。次に、制御手段１８（図１）において、ｓ＝５（＝ｕ‐１）であるか否かを判断し（ステップＳ１４）、ｓ＝５でない場合、ｓ←ｓ＋１の演算を行ってステップＳ１２の処理に戻り、ｓ＝５である場合、ｔ＝５であるか否かを判断する（ステップＳ１５）。ここで、ｔ＝５であった場合処理を終了し、ｔ＝５でなかった場合、ｓに０を代入し、ｔ←ｔ＋１の演算を行って、ステップＳ１２の処理に戻る。
【００２８】
＜実施例１におけるステップＳ４の処理＞
前述のように、本実施例では、ｕ＝６、ｆ（ｘ）＝ｘ６‐ｘ３‐６０となるため、本実施例の縮約手段１６は、
【数２８】
2005208327.tif 000021
を満たす係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。すなわち、剰余対象入力手段１４において入力された剰余対象
【数２９】
2005208327.tif 000022
を複数回適用することにより得られる式（１８）のｃ’の係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。以下この演算を概念的に説明する。
【００２９】
図６は、剰余対象ｃの係数ｃｉとｃ’の係数ｃｉ’との関係を説明するための概念図である。ここで、図６におけるｘｉ（ｉ＝０,１,...,１０）は、ｃ及びｃ’の項ｘｉを意味し、ｃｉ（ｉ＝０,１,...,１０）は、ｃの係数ｃｉを意味し、ｃｉ’（ｉ＝０,１,...,5）は、式（１８）のｃ’の係数ｃｉ’を意味する。また、ｘｉと同一列（図６における縦方向の列）にあるｃｉ及びｃｉ’は、項ｘｉの係数に対応する。
【００３０】
図６の（ａ）は、剰余対象入力手段１４において入力された剰余対象ｃの各項ｘｉの係数ｃｉ（ｉ＝０,１,...,１０）を示している。なお、前述のように、剰余対象ｃは、式（１３）で表現される第１の乗算対象ａと、式（１４）で表現される第２の乗算対象ｂとを、項ｘｉ間の繰り上がり補正を行うことなく乗算したものである（ステップＳ２）。従って、係数ｃｉ（ｉ＝０,１,...,１０）はｘ以上となる場合もありえる。言い換えると、ｘ＝Ｑｗ＝２２７に相当するため、係数ｃｉ（ｉ＝０,１,...,１０）は２７ビット以上となっている場合もある。
【００３１】
図６の（ａ）に示される式（１９）に式（２０）を１回適用すると、
【数３０】
2005208327.tif 000023
となるため、各項ｘｉの係数ｃｉは図６の（ｂ）のようになる。なお、この図の「×６０」とは、この「×６０」と同一行（図６における横方向の行）の係数ｃｉを６０倍することを意味する。
さらに、式（２１）に式（２０）を適用すると、
【数３１】
2005208327.tif 000024
となるため、各項ｘｉの係数ｃｉは図６の（ｃ）のようになる。
そして、図６の（ｃ）に示す各係数ｃｉ或いは６０ｃｉを、各項ｘｉと同一列（図６における縦方向の列）ごとに、桁上がり補正することなく加算した値が、ｃ’における各項ｘｉの係数ｃｉ’となる（図６の（ｄ））。例えば、ｃ０’＝ｃ０＋６０ｃ６＋６０ｃ９となる。
【００３２】
この係数ｃｉ’は、順次、ｃ０’←ｃ０＋６０ｃ６＋６０ｃ９,ｃ１’←ｃ１＋６０ｃ７＋６０ｃ１０,...,ｃ５’←ｃ５＋ｃ８と演算することにより求めることも可能であるが、本実施例では、この演算方法を工夫し、さらなる処理の高速化を図る。
図７は、本実施例におけるステップＳ４の処理を説明するためのフローチャートである。以下、このフローチャートに沿って、本実施例におけるステップＳ４の処理を具体的に説明する。
図７に示すように、本処理ではまず、加算手段１６ａにおいて、剰余対象入力手段１４において入力された係数ｃｉ（ｉ＝６,７,９,１０）を取得し、ｉ＝６，７に対して、ｃｉ←ｃｉ＋ｃｉ+３の演算を行う（ステップＳ２１）。この演算結果である係数ｃｉ（ｉ＝６,７）は、加算手段１６ｂ及び多倍算手段１６ｃに送られる。
【００３３】
加算手段１６ａにおける演算後、加算手段１６ｂにおいて、剰余対象入力手段１４において入力された係数ｃｉ（ｉ＝３,４,５,８）及び加算手段１６ａから送られた係数ｃｉ（ｉ＝６,７）を取得し、ｉ＝３，４，５に対して、ｃｉ←ｃｉ＋ｃｉ+３の演算を行う（ステップＳ２２）。この演算結果である係数ｃｉ（ｉ＝３,４）は加算手段１６ｄに送られ、ｃ５はｃ５’として出力される。すなわち、係数ｃ５’は、加算手段１６ｂにおける演算結果ｃ５である。
その後、多倍算手段１６ｃにおいて、ｉ＝０，１，…，４に対して、２２（２４‐１）ｃｉ+６の演算を行い、その演算結果を加算手段１６ｄに送る。また、加算手段１６ｂ及び多倍算手段１６ｃにおける演算後、加算手段１６ｄにおいて、剰余係数格納手段１５（図１）から剰余係数ｐ０＝２２（２４‐１）を取得し、ｉ＝０，１，…，４に対して、ｃｉ←ｃｉ＋２２（２４‐１）ｃｉ+６の演算を行い、その演算結果をｃｉ’（ｉ＝０,１,...,４）として出力する（ステップＳ２３）。すなわち、係数ｃｉ’（ｉ＝０，１，…，４）は、加算手段１６ｄにおける演算結果ｃｉ（ｉ＝０，１，…，４）である。なお、多倍算手段１６ｃにおける処理は、加算手段１６ａにおける演算後であれば、加算手段１６ｂの演算前に行ってもよい。
【００３４】
なお、縮約手段１６における演算は繰り上がり補正を行うことなく行われるため、算出された各係数ｃｉ’（ｉ＝０，１，…，５）は、２７（＝ｗ）ビット以上となる場合もある。
＜実施例１におけるステップＳ５の処理＞
正規化処理では、１６０（＝Ｌ）ビット長の縮約処理を行うとともに、ｘ＝２２７とした場合における係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う。ここで、１６０ビット長の縮約処理とは、ｎを超える値に対しｍｏｄ ｎ演算を施すことをいう。本実施例では、繰り上がり補正の一部を１６０ビット長の縮約処理の前に行うことにより、正規化処理を簡略化し、処理の高速化を図る。
【００３５】
図８は、本実施例におけるステップＳ５の処理を説明するためのフローチャートである。以下、このフローチャートに沿って、本実施例におけるステップＳ５の処理を具体的に説明する。なお、このフローチャートにおけるステップＳ３１,Ｓ３２は、ｃ４からｃ５への繰り上がり処理であり、ステップＳ３３〜Ｓ３６は、１６０ビット長の縮約処理であり、ステップＳ３７は、ｃｉからｃｉ＋１（ｉ＝０,１,...,４）への繰り上がり処理であり、ステップＳ３８〜Ｓ４０は、最後の調整処理である。
【００３６】
図８に例示するように、まず、繰り上がり補正手段１７ａａにおいて、縮約手段１６から出力された係数ｃ４’、ｃ５’を取得し、
【数３２】
2005208327.tif 000025
の演算を行い、その演算結果ｃ５’を縮約処理手段１７ｂａ、１７ｂｂに送る（ステップＳ３１）。
次に、繰り上がり補正手段１７ａｂにおいて、縮約手段１６から出力された係数ｃ４’を取得してｃ４’←ｃ４’ ｍｏｄ ２２７を演算し、その演算結果ｃ４’を繰り上がり補正手段１７ｃに送る（ステップＳ３２）。
【００３７】
次に、縮約処理手段１７ｂａにおいて、
【数３３】
2005208327.tif 000026
の演算を行い、その演算結果ｚを縮約処理手段１７ｂｃ,１７ｂｄに送る（ステップＳ３３）。
次に、縮約処理手段１７ｂｂにおいて、繰り上がり補正手段１７ａａから送られた演算結果ｃ５’を用い、ｃ５’←ｃ５’ ｍｏｄ ２２５を演算し、その演算結果ｃ５’を繰り上がり補正手段１７ｃに送る（ステップＳ３４）。
【００３８】
また、縮約処理手段１７ｂｃにおいて、縮約手段１６から出力された係数ｃ０’及び縮約処理手段１７ｂａから出力されたｚを取得し、ｃ０’←ｃ０’＋（２４‐１）ｚを演算し、その演算結果ｃ０’を繰り上がり補正手段１７ｃに送る（ステップＳ３５）。
さらに、縮約処理手段１７ｂｄにおいて、縮約手段１６から出力された係数ｃ２’及び縮約処理手段１７ｂａから出力されたｚを取得し、ｃ２’←ｃ２’＋２２５ｚを演算し、その演算結果ｃ２’を繰り上がり補正手段１７ｃに送る（ステップＳ３６）。
その後、繰り上がり補正手段１７ｃにおいて、縮約手段１６から出力された係数ｃ１’, ｃ３’、繰り上がり補正手段１７ａｂから出力された係数ｃ４’、縮約処理手段１７ｂｃ、１７ｂｄから出力された係数ｃ０’, ｃ２’を取得し、
【数３４】
2005208327.tif 000027
ｃｉ’←ｃｉ’ ｍｏｄ ２２７
（ｉ＝０,１,２,３,４）
の演算を行い、その演算結果ｃｉ’（ｉ＝０,１,...,５）を減算手段１７ｄに送る（ステップＳ３７）。
次に、減算手段１７ｄにおいて、繰り上がり補正手段１７ｃから送られた演算結果ｃｉ’（ｉ＝０,１,...,５）を取得し、これらによって
【数３５】
2005208327.tif 000028
のように特定されるｃ’がｎ未満であるか否かを判断する（ステップＳ３８）。ここで、ｃ’＜ｎであった場合には、減算手段１７ｄにおいて、ｃを演算結果ｍとして出力し、処理を終了する（ステップＳ３９）。一方、ｃ’＜ｎでなかった場合には、ｍ←ｃ’‐ｎの演算を行い、その演算結果ｍを出力して処理を終了する（ステップＳ４０）。なお、ステップＳ３８〜Ｓ４０の処理は、ｃ’-nの演算を行い、ｃ’-n＜０であればｃ’を演算結果ｍとして出力し、ｃ’-n≧０であればｍ←ｃ’‐ｎとすることとしてもよい。
【００３９】
＜実施例２＞
次に、本形態における実施例２について説明する。
本実施例は、Ｑ＝２であり、Ｌが１６０であり、Ｗが３２であり、ｗが２７であり、ｕが６であり、法ｎが２１６０‐２３１‐１（＝２１６０‐２６・２７‐２‐１）である場合のものである。この場合、Ｅ＝２、ｐ０＝２２、ｐ１＝２６、ｐｈ＝０（ｈ＝２,３,４,５）、ｆ（ｘ）＝ｘ６‐６４ｘ‐４（＝ｘ６‐２６ｘ‐２２）となる。
＜実施例２の構成＞
実施例２における全体構成は、前述した通りである（図１）。以下では、実施例２における縮約手段１６及び正規化手段１７の詳細構成のみを説明する。
【００４０】
図９は、本実施例における縮約手段１６の構成を示したブロック図であり、図１０は、本実施例における正規化手段１７の構成を示したブロック図である。
図９に示すように、本実施例の縮約手段１６は、多倍算手段１１６ａ,１１６ｃ（「第１,第２の多倍算手段」に相当）及び加算手段１１６ｂ,１１６ｄ（「第１,第２の加算手段」に相当）を有しており、図１０に示すように、本実施例の縮約手段１７は、繰り上がり補正手段１１７ａａ、１１７ａｂ、１１７ｃ及び縮約処理手段１１７ｂａ、１１７ｂｂ、１１７ｂｃ、１１７ｂｄを有している。
【００４１】
＜実施例２の処理＞
実施例２における処理の全体は、前述した通りである（図４）。また、ステップＳ２の処理は実施例１と同じである。以下では、実施例２におけるステップＳ４,Ｓ５の処理（図４）の詳細のみを説明する。
＜実施例２におけるステップＳ４の処理＞
前述のように、本実施例では、ｕ＝６、ｆ（ｘ）＝ｘ６‐６４ｘ‐４となるため、本実施例の縮約手段１６は、
【数３６】
2005208327.tif 000029
を満たす係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく算出する。以下この演算を概念的に説明する。
【００４２】
図１１は、式（１９）で表現された剰余対象ｃの係数ｃｉと、式（２２）で示されるｃ’の係数ｃｉ’との関係を説明するための概念図である。ここで、図１１におけるｘｉ（ｉ＝０,１,...,１０）、ｃｉ（ｉ＝０,１,...,１０）、ｃｉ’（ｉ＝０,１,...,5）の意味は図６と同様である。
図１１の（ａ）は、剰余対象入力手段１４において入力された剰余対象ｃの各項ｘｉの係数ｃｉ（ｉ＝０,１,...,１０）を示している。
図１１の（ａ）に示される式（１９）に、
【数３７】
2005208327.tif 000030
となるため、各項ｘｉの係数ｃｉは図１１の（ｂ）のようになる。なお、この図の「×４」や「×６４」とは、この「×４」や「×６４」と同一行（図１１における横方向の行）の係数ｃｉを４倍や６４倍することを意味する。
そして、図１１の（ｂ）に示す各係数ｃｉ（ｉ＝０,１,...,５）、４ｃｉ（ｉ＝６,７,...,１０）及び６４ｃｉ（ｉ＝６,７,...,１０）を、各項ｘｉと同一列（図１１における縦方向の列）ごとに、桁上がり補正することなく加算した値が、ｃ’における各項ｘｉの係数ｃｉ’となる（図１１の（ｃ））。例えば、ｃ０’＝ｃ０＋４ｃ６となる。
【００４３】
図１２は、本実施例におけるステップＳ４の処理を説明するためのフローチャートである。以下、このフローチャートに沿って、本実施例におけるステップＳ４の処理を具体的に説明する。
図１２に示すように、本処理ではまず、多倍算手段１１６ａにおいて、剰余対象入力手段１４において入力された係数ｃｉ（ｉ＝６,７,８,９,１０）、及び乗算係数格納手段１５に格納された乗算係数ｐ０＝２２を取得し、ｉ＝０，１，…，４に対して、２２ｃｉ+６の演算を行い、その演算結果２２ｃｉ+６を加算手段１１６ｂに送る。また、加算手段１１６ｂにおいて、剰余対象入力手段１４において入力された係数ｃｉ（ｉ＝０,１,２,３,４）、及び多倍算手段１１６ａから送られた多倍算手段１１６ａにおける演算結果２２ｃｉ+６を取得し、ｃｉ←ｃｉ＋２２ｃｉ+６（ｉ＝０,１,２,３,４）の演算を行う（ステップＳ５１）。この演算結果ｃｉ（ｉ＝１,２,３,４）は加算手段１１６ｄに送られ、演算結果ｃ０は、係数ｃ０’として出力される。すなわち、係数ｃ０’は、加算手段１１６ｂにおける演算結果ｃ０である。
【００４４】
加算手段１１６ｂにおける演算後、多倍算手段１１６ｃにおいて、剰余対象入力手段１４において入力された係数ｃｉ（ｉ＝１,２,３,４,５）、及び乗算係数格納手段１５に格納された乗算係数ｐ１＝２６を取得し、ｉ＝１，２，…，５に対して、２６ｃｉ+５の演算を行い、その演算結果２６ｃｉ+５を加算手段１１６ｄに送る。また、加算手段１１６ｄにおいて、剰余対象入力手段１４において入力された係数ｃ５、多倍算手段１１６ｃから送られた演算結果２６ｃｉ+５、及び加算手段１１６ｂから送られた演算結果ｃｉ（ｉ＝１,２,３,４）を取得し、これらを用い、ｉ＝１，２，…，５に対して、ｃｉ←ｃｉ＋２６ｃｉ+５の演算を行う（ステップＳ５２）。この演算結果ｃｉ（ｉ＝１，２，…，５）は、係数ｃｉ’（ｉ＝１，２，…，５）として出力される。すなわち、係数ｃｉ’（ｉ＝１，２，…，５）は、加算手段１１６ｄにおける演算結果ｃｉ’（ｉ＝１，２，…，５）である。
【００４５】
＜実施例２におけるステップＳ５の処理＞
正規化処理では、１６０（＝Ｌ）ビット長の縮約処理を行うとともに、ｘ＝２２７とした場合における係数ｃｉ’の各項ｘｉ間の繰り上がり補正をまとめて行う。本実施例でも、繰り上がり補正の一部を１６０ビット長の縮約処理の前に行うことにより、正規化処理を簡略化し、処理の高速化を図る。
図１３は、本実施例におけるステップＳ５の処理を説明するためのフローチャートである。以下、このフローチャートに沿って、本実施例におけるステップＳ５の処理を具体的に説明する。なお、このフローチャートにおけるステップＳ６１,Ｓ６２は、ｃ４からｃ５への繰り上がり処理であり、ステップＳ６３〜Ｓ６６は、１６０ビット長の縮約処理であり、ステップＳ６７は、ｃｉからｃｉ＋１（ｉ＝０,１,...,４）への繰り上がり処理であり、ステップＳ６８〜Ｓ７０は、最後の調整処理である。
【００４６】
図１３に例示するように、まず、繰り上がり補正手段１１７ａａにおいて、縮約手段１６から出力された係数ｃ４’、ｃ５’を取得し、
【数３８】
2005208327.tif 000031
の演算を行い、その演算結果ｃ５’を縮約処理手段１１７ｂａ、１１７ｂｂに送る（ステップＳ６１）。
次に、繰り上がり補正手段１１７ａｂにおいて、縮約手段１６から出力された係数ｃ４’を取得してｃ４’←ｃ４’ ｍｏｄ ２２７を演算し、その演算結果ｃ４’を繰り上がり補正手段１１７ｃに送る（ステップＳ６２）。
【００４７】
次に、縮約処理手段１１７ｂａにおいて、
【数３９】
2005208327.tif 000032
の演算を行い、その演算結果ｚを縮約処理手段１１７ｂｃ,１１７ｂｄに送る（ステップＳ６３）。
次に、縮約処理手段１１７ｂｂにおいて、繰り上がり補正手段１１７ａａから送られた演算結果ｃ５’を用い、ｃ５’←ｃ５’ ｍｏｄ ２２５を演算し、その演算結果ｃ５’を繰り上がり補正手段１１７ｃに送る（ステップＳ６４）。
また、縮約処理手段１１７ｂｃにおいて、縮約手段１６から出力された係数ｃ０’及び縮約処理手段１１７ｂａから出力されたｚを取得し、ｃ０’←ｃ０’＋ｚを演算し、その演算結果ｃ０’を繰り上がり補正手段１１７ｃに送る（ステップＳ６５）。
【００４８】
さらに、縮約処理手段１１７ｂｄにおいて、縮約手段１６から出力された係数ｃ１’及び縮約処理手段１１７ｂａから出力されたｚを取得し、ｃ１’←ｃ１’＋２４ｚを演算し、その演算結果ｃ１’を繰り上がり補正手段１１７ｃに送る（ステップＳ６６）。
その後、繰り上がり補正手段１１７ｃにおいて、縮約手段１６から出力された係数ｃ２’, ｃ３’、繰り上がり補正手段１１７ａｂから出力された係数ｃ４’、縮約処理手段１１７ｂｂから出力された係数ｃ５’、縮約処理手段１１７ｂｃ、１１７ｂｄから出力された係数ｃ０’, ｃ１’を取得し、
【数４０】
2005208327.tif 000033
ｃｉ’←ｃｉ’ ｍｏｄ ２２７
（ｉ＝０,１,２,３,４）
の演算を行い、その演算結果ｃｉ’（ｉ＝０,１,...,５）を減算手段１１７ｄに送る（ステップＳ６７）。
【００４９】
次に、減算手段１１７ｄにおいて、繰り上がり補正手段１１７ｃから送られた演算結果ｃｉ’（ｉ＝０,１,...,５）を取得し、これらによって特定されるｃ’がｎ未満であるか否かを判断する（ステップＳ６８）。ここで、ｃ’＜ｎであった場合には、減算手段１１７ｄにおいて、ｃを演算結果ｍとして出力し、処理を終了する（ステップＳ６９）。一方、ｃ’＜ｎでなかった場合には、ｍ←ｃ’‐ｎの演算を行い、その演算結果ｍを出力して処理を終了する（ステップＳ７０）。
なお、実施例１,２における各演算を実施するにあたり、２の冪（べき）に関する乗算・切捨て除算は、多くの場合、左シフト・右シフト演算を施すことによって行うほうが高速となる。
【００５０】
また、本発明は上述の実施の形態に限定されるものではない。
例えば、上述した計算の順序は上記に限定されるものではなく、結果が矛盾しない範囲で入れ替えて、或いは同時に行うこととしてもよい。
また、ａとｂとの語長乗算（ステップＳ２）を上記の教科書的な方法ではなく、Ｋａｒａｔｓｕｂａ法、Ｔｏｏｍ−Ｃｏｏｋ法、ＦＦＴ法などの別の方法により高速に行うこととしてもよい。通常、多倍長乗算を実行する場合、Ｌ＝１６０，Ｗ＝３２といった小さな値では繰り上がり処理が繁雑になるためＫａｒａｔｓｕｂａ法は有効でない場合が多かった。しかし、本発明では繰り上がりは最後にまとめて行うため、この程度の大きさのＬ,ＷでもＫａｒａｔｓｕｂａ法が有効な場合が多い。
【００５１】
さらに、当然のことながら、ステップＳ１１におけるｃｉの初期化処理を省略し、上記のステップＳ１３において０に加算していたａｓｂｔをｃｉの初期値とし、ステップＳ１３における０との加算処理を行わないこととしてもよい。
また、本形態では、乗算手段１２及び加算手段１３において算出されたａとｂの乗算結果を剰余対象ｃとし、剰余対象入力手段１４に入力することとした。しかし、それ以外の値を剰余対象ｃとすることとしてもよい。
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。
【００５２】
本形態は、乗算のＫａｒａｔｓｕｂａ処理と、擬メルセンヌ素数を使った縮約の処理により、項を打ち消し、計算量を削減する形態である。
なお、本形態では、Ｑ＝２であり、Ｌが１６０であり、Ｗが３２であり、ｗが２７であり、ｕが６であり、法ｎが２１６０‐２７９‐１５（＝２１６０‐２３・２７‐２‐（２４‐１））であるものとする。この場合、Ｅ＝２、ｐ０＝２２（２４‐１）、ｐ３＝１、ｐｈ＝０（ｈ＝１,２,４,５）、ｆ（ｘ）＝ｘ６‐ｘ３‐６０（＝ｘ６‐ｘ３‐２２（２４‐１））となる。
【００５３】
＜原理＞
本形態では、
【数４１】
2005208327.tif 000034
と表現した場合におけるａｂｍｏｄ ｆ（ｘ）を計算する。
ここで、
Ａ０＝ａ２ｘ２＋ａ１ｘ＋ａ０，
Ａ１＝ａ５ｘ２＋ａ４ｘ＋ａ３，
Ｂ０＝ｂ２ｘ２＋ｂ１ｘ＋ｂ０，
Ｂ１＝ｂ５ｘ２＋ｂ４ｘ＋ｂ３，
Ｘ＝ｘ３，
とおくと、
ａ＝Ａ１Ｘ＋Ａ０
ｂ＝Ｂ１Ｘ＋Ｂ０
ｆ（Ｘ）＝Ｘ２‐Ｘ‐２２（２４‐１）  …(25)
となる。そのため、
ａｂ＝（Ａ１Ｘ＋Ａ０）（Ｂ１Ｘ＋Ｂ０）
＝Ａ１Ｂ１Ｘ２＋（（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）‐Ａ１Ｂ１‐Ａ０Ｂ０）Ｘ＋Ａ０Ｂ０
となり、式（２５）より導かれる合同式
【数４２】
2005208327.tif 000035
となる。ここで、第１式から第２式への変換において、第１式のＡ１Ｂ１Ｘ（下線部）の項が打ち消しあっている。これにより、演算数を削減できることが分かる。本形態では、この性質を利用し、縮約の処理の一部を乗算処理に組み込み、剰余乗算全体の演算数を低減させ高速化を図る。
【００５４】
＜構成＞
図１４は、公知のコンピュータに所定のプログラムを実行させることにより実現される、本形態における剰余装置２００の構成を例示したブロック図である。
図１４に例示するように、剰余装置２００は、乗算対象入力手段２１１、縮約手段２１２及び正規化手段２１３を有している。また、縮約手段２１２は、乗算項算出手段２１２ａ、乗算項格納手段２１２ｂ及び係数算出手段２１２ｃを有している。
また、より具体的には、本実施例の剰余装置２００は、３２ビット同士の積６４ビットを得る乗算器と、６４ビット同士の和を得る加算器によって実現される。ここで、加算器は減算も実行でき、６４ビットの値のシフトも効率的に計算可能とする。このような環境の例としてＩｎｔｅｌ（登録商標）のＳＳＥ２がある。もちろん、６４ビット同士の加算が直接出来ない場合に、３２ビット同士の加算を組み合わせて６４ビットの加算を実行するなどの置換えがあってもよい。
【００５５】
＜処理＞
図１５は、本形態における剰余乗算処理を説明するためのフローチャートである。以下、このフローチャートに沿って本形態における剰余乗算処理を説明する。
図１５に例示するように、まず、乗算対象入力手段２１１において、第１の乗算対象ａ及び第２の乗算対象ｂを式（２３）（２４）によって表現した場合における各係数ａｓ及びｂｔの入力を受け付ける（ステップＳ８１）。
入力された各係数ａｓ及びｂｔは縮約手段２１２に送られ、縮約手段２１２は、これらの係数ａｓ及びｂｔを用い、
【数４３】
2005208327.tif 000036
を満たす係数ｃｉ’を、各項ｘｉ間の繰り上がり補正を行うことなく、以下のように算出する（縮約処理）。
すなわち、まず、乗算項算出手段２１２ａにおいて、乗算対象入力手段２１１から各係数ａｓ及びｂｔを取得し、これらを用いて、乗算項Ａ０Ｂ０を算出する（ステップＳ８２）。算出された乗算項Ａ０Ｂ０は乗算項格納手段２１２ｂに送られ、そこに格納される（ステップＳ８３）。
【００５６】
その後、係数算出手段２１２ｃにおいて、乗算対象入力手段２１１から各係数ａｓ及びｂｔを取得し、さらに乗算項格納手段２１２ｂに格納された乗算項Ａ０Ｂ０を用い、ｃ＝（（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）−Ａ０Ｂ０）Ｘ＋Ａ０Ｂ０＋２２（２４‐１）Ａ１Ｂ１
の演算を行い、当該ｃの項ｘｉに対する係数ｃｉ’を算出する（ステップＳ８５）。
算出された各係数ｃｉ’は正規化手段２１３に送られ、正規化手段２１３は、この係数の各項間の繰り上がり補正をまとめて行う（ステップＳ８５）。
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５７】
また、上述の各実施の形態における構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６０】
本発明の産業上の利用分野としては、例えば、離散対数問題の困難性に根拠をおく公開鍵暗号や電子署名における多倍長剰余乗算が挙げられる。本発明をこれらに使用することにより、公開鍵暗号等の処理を高速化できる。
【図面の簡単な説明】
【００６１】
【図１】第１の実施の形態における剰余装置の全体構成を例示したブロック図。
【図２】実施例１における縮約手段の構成を示したブロック図。
【図３】実施例１における正規化手段の構成を示したブロック図。
【図４】第１の実施の形態における剰余装置の処理の全体を説明するためのフローチャート。
【図５】実施例１における図４のステップＳ２の処理を説明するためのフローチャー。
【図６】実施例１における剰余対象ｃの係数ｃｉとｃ’の係数ｃｉ’との関係を説明するための概念図。
【図７】実施例１におけるステップＳ４の処理を説明するためのフローチャート。
【図８】実施例１におけるステップＳ５の処理を説明するためのフローチャート。
【図９】実施例２における縮約手段の構成を示したブロック図。
【図１０】実施例２における正規化手段の構成を示したブロック図。
【図１１】実施例２における剰余対象ｃの係数ｃｉとｃ’の係数ｃｉ’との関係を説明するための概念図。
【図１２】実施例２におけるステップＳ４の処理を説明するためのフローチャート。
【図１３】実施例２におけるステップＳ５の処理を説明するためのフローチャート。
【図１４】第２の実施の形態における剰余装置の構成を例示したブロック図。
【図１５】第２の実施の形態における剰余乗算処理を説明するためのフローチャート。
【符号の説明】
【００６２】
１０,２００  剰余装置
１１,２１１  乗算対象入力手段
１２  乗算手段
１３  加算手段
１４  剰余対象入力手段
１５  乗算係数格納手段
１６,２１２  縮約手段
１７,２１３  正規化手段
【図１】
2005208327.tif 000046
【図２】
2005208327.tif 000047
【図３】
2005208327.tif 000048
【図４】
2005208327.tif 000049
【図５】
2005208327.tif 000050
【図６】
2005208327.tif 000051
【図７】
2005208327.tif 000052
【図８】
2005208327.tif 000053
【図９】
2005208327.tif 000054
【図１０】
2005208327.tif 000055
【図１１】
2005208327.tif 000056
【図１２】
2005208327.tif 000057
【図１３】
2005208327.tif 000058
【図１４】
2005208327.tif 000059
【図１５】
2005208327.tif 000060