(57)【要約】【課題】処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行する。【解決手段】乗算装置１０では、入出力部１２が各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を入力し、乗算装置制御部１３が入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），…，Ｂ0（ｘ）を作成し、Ｍテーブル作成部１４が、値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成する。Ｔテーブル作成部１５は、Ｍテーブルを参照し、順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する。乗算実行部１６は、Ｔテーブルの計算結果Ｔ［ｓ−１］，…，Ｔ［０］の総和を計算し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する。【選択図】図３
2009258502.tif 000002
【特許請求の範囲】
【請求項１】
第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力する乗算装置であって、
前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を入力するための入力手段と、
前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段と、
前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記値Ｂｉ（ｘ）の個数ｓとに基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成する手段と、
前記作成したＭテーブルを記憶するテーブル記憶手段と、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成するＴテーブル作成手段と、
前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段と、
前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段と、
前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する出力手段と、
を備えたことを特徴とする乗算装置。
【請求項２】
第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力する乗算装置であって、
前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切って得られるｓ個の値Ｂｉ（ｘ）の個数ｓとに基づき（但し、ｉ＝ｓ−１，ｓ−２，…，１，０）、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルが予め作成された場合、このＭテーブルと、前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）とを入力するための入力手段と、
前記入力された第２入力値Ｂ（ｘ）を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段と、
前記入力されたＭテーブルを記憶するテーブル記憶手段と、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成するＴテーブル作成手段と、
前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段と、
前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段と、
前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する出力手段と、
を備えたことを特徴とする乗算装置。
【請求項３】
請求項１又は請求項２に記載の乗算装置において、
前記Ｔテーブル作成手段及び前記出力手段に代えて、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ）の計算結果からなるＴテーブルを作成する手段と、
前記総和の計算結果を前記第３入力値Ｆ（ｘ）により剰余演算し、得られた剰余演算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段と、
を備えたことを特徴とする乗算装置。
【請求項４】
第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行して乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力し且つテーブル記憶手段を備えた乗算装置に用いられるプログラムであって、
前記乗算装置を、
前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を入力するための入力手段、
前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段と、
前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記値Ｂｉ（ｘ）の個数ｓとに基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成する手段、
前記作成したＭテーブルを前記テーブル記憶手段に書き込む手段、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する手段、
前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段、
前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段、
前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段、
として機能させるためのプログラム。
【請求項５】
第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行して乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力し且つテーブル記憶手段を備えた乗算装置に用いられるプログラムであって、
前記乗算装置を、
前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切って得られるｓ個の値Ｂｉ（ｘ）の個数ｓとに基づき（但し、ｉ＝ｓ−１，ｓ−２，…，１，０）、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルが予め作成された場合、このＭテーブルと、前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）とを入力するための入力手段、
前記入力された第２入力値Ｂ（ｘ）を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段、
前記入力されたＭテーブルを前記テーブル記憶手段に書き込む手段、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する手段、
前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段、
前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段、
前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段、
として機能させるためのプログラム。
【請求項６】
請求項４又は請求項５に記載のプログラムにおいて、
前記乗算装置を、
前記Ｔテーブル作成手段及び前記出力手段に代えて、
前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ）の計算結果からなるＴテーブルを作成する手段、
前記総和の計算結果を前記第３入力値Ｆ（ｘ）により剰余演算し、得られた剰余演算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体上の乗算を高速に実行し得る乗算装置及びプログラムに関する。
【背景技術】
【０００２】
近年、インターネットなどのオープンなネットワークを介し、文書データや画像データなどのさまざまなデータを送受信したい要望がある。これら送受信したいデータには秘密にしたいデータが多く含まれている。そのため、第三者には分からないようにデータを暗号化した状態で送受信するための暗号化技術が普及している。
【０００３】
この種の暗号化技術の一つとして、有限体上の演算を用いる方法がある。暗号化技術は、一般に暗号や署名を有限体ＧＦ(ｐm)上で定義される演算を用いて実現される。ここで、高速な暗号や署名を実現するためには、有限体上の演算を高速に実行する必要がある。高速化対象の演算には、例えば有限体上の乗算がある。
【０００４】
有限体上の乗算の高速な実行方法としては、ハサン（Hasan）のテーブル参照法が知られている（例えば、非特許文献１参照。）。
【０００５】
このテーブル参照法では、入力値Ａ（ｘ）、Ｂ（ｘ）に対し、ｍビットのＢ（ｘ）をgビット毎に区切ることにより、得られた値Ｂs-1，Ｂs-2，…Ｂｉ，…Ｂ1，Ｂ0を用いて乗算処理を実行する。この乗算処理の際に、Ｍテーブル及びＴテーブルという２種類のテーブルを参照する。ここで、ＢｉはｍビットのＢ（ｘ）をgビット毎に区切ったｉ番目の値である。ｓはｍより小さい自然数である（ｓ＝ｍ／g）。また、入力値Ｂ（ｘ）は有限体ＧＦ（ｐm）上の値であり、例えば次式で表される。
【０００６】
Ｂ(ｘ)＝ｘ(s-1)gＢs-1(ｘ)＋ｘ(s-2)gＢs-2(ｘ)＋…＋ｘgＢ1(ｘ)＋Ｂ0(ｘ)
他方の入力値Ａ（ｘ）も有限体ＧＦ（ｐm）上の値であり、例えば次式で示される。
【０００７】
Ａ(ｘ)＝ａm-1ｘm-1＋ａm-2ｘm-2＋…＋ａ1ｘ＋ａ0 
ここで、ｍ個の係数｛ａm-1，ａm-2，…，ａ1，ａ0｝は、それぞれ有限体ＧＦ（ｐ）上の要素｛０，…，ｐ−１｝のいずれかである。但し、非特許文献１では、有限体ＧＦ（ｐm），ＧＦ（ｐ）をそれぞれ有限体ＧＦ（２n），ＧＦ（２）としている。
【０００８】
このとき、ハサンのテーブル参照法のアルゴリズムは、図８の左欄に示すように、実行される。すなわち、Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）及びＭテーブルが入力されると、Ｔテーブルが作成される（step 1）。次に、入力Ｂ（ｘ）を区切って得られたｓ−１番目の値Ｂs-1に基づき、Ｔテーブルを参照してＰ（ｘ）が得られる（step 2）。更にＦｏｒ文として、ｓ−２番目から０番目までの各ｉ番目の各Ｂｉ（ｘ）について、次のτ1、τ2、τ3及びＰ（ｘ）の演算が実行される（step 3）。
【０００９】
τ1＝ｘgＰ1（ｘ）、
τ2＝Ｍ［Ｐ2（ｘ）］、
τ3＝Ｔ［Ｂi（ｘ）］、
Ｐ（ｘ）＝τ1＋τ2＋τ3 
ここで、Ｐ（ｘ）、Ｍテーブル（Ｍ−table）、Ｔテーブル（Ｔ−table）及びＦ（ｘ）は次式で表されるとする。
【数１】
2009258502.tif 000003
【００１０】
しかる後、Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果が出力される。
【００１１】
ここで、以上のようなハサンのアルゴリズムについて簡単に説明する。
【００１２】
ハサンのアルゴリズムでは、Ｂi（ｘ）の次数をｘg毎に区切って乗算処理を実行する際に、Ｂi（ｘ）とｘgの項に分けている。すなわち、途中計算結果であるＰ（ｘ）全てに対してＢi（ｘ）を掛けるのではなく、Ｐ（ｘ）で剰余演算が必要となる（ｍ−g）次以上の項のみを用いるために分けている。そのため、Ｐ（ｘ）は（ｍ−g）次未満の項（Ｐ1（ｘ））と（ｍ−g）次以上の項（Ｐ2（ｘ））に分けて処理が実行される。
【００１３】
そして、その（ｍ−g）次以上の項に対する計算結果はＭテーブルを用いてテーブル参照により求め、またＡ（ｘ）にＢi（ｘ）を掛ける処理についてはＴテーブルを参照して計算結果を求め、その処理をｘg毎に区切った全てのＢi（ｘ）に対して実行することで乗算結果を得る。
【００１４】
つまり、ハサンのアルゴリズムは、次のように式変形して説明できる。
【数２】
2009258502.tif 000004
【００１５】
前述したように、Ａ（ｘ）Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算は、Ｔテーブルを参照しながら実行される。Ｔテーブルの計算結果とｘgとの乗算は、剰余演算が必要な（ｍ−g）次以上の項に対してＭテーブルを参照しながら計算結果を得る。それら計算結果を繰り返し加えながらアルゴリズムを実行している。
【００１６】
しかしながら、ハサンのアルゴリズムは、処理単位gの値が大きくなると、各テーブルに必要なメモリサイズが指数関数的に大きくなることが知られている。ハサンのアルゴリズムに関し、Ｍテーブル及びＴテーブルに必要なメモリサイズは、次式で評価できる。
【００１７】
＜一般的な場合＞
Ｍテーブル＝（g＋ｄ）×２g、
Ｔテーブル＝ｍ×g   ［２g＜ｓのとき］又はｍ×２g  ［それ以外］
＜ｍ＝１６０、g＝１６、ｓ＝１０の場合＞
Ｍテーブル＝（１６＋ｄ）×２16、Ｔテーブル＝１６０×２16
＜ｍ＝１６０、g＝４、ｓ＝４０の場合＞
Ｍテーブル＝（４＋ｄ）×２4、Ｔテーブル＝１６０×４
【非特許文献１】M. A. Hasan, “Look-Up Table-Based Large Finite Field Multiplication in Memory Constrained Cryptosystems”, IEEE Transactions on Computers, 2000
【発明の開示】
【発明が解決しようとする課題】
【００１８】
以上説明したように、処理単位gを大きくとると、各テーブルのメモリサイズが指数関数的に増加する。特に、Ｍテーブルは、入力によらずに（g＋ｄ）×２gビットという大きいメモリ量を必要とする。
【００１９】
一方、近年のＣＰＵのビットサイズを考慮すると、処理単位gを大きくした方が計算機上で演算を効率的に実行可能である。
【００２０】
また、処理単位gを大きくすると、Ｂｉ（ｘ）の個数ｓ（＝ｍ／g）が少なくなり、ひいてはアルゴリズムのＦｏｒ文の実行回数が少なくなるので、アルゴリズムの実行効率の観点からも処理単位gを大きくした方がよい。
【００２１】
従って、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行し得る乗算手法が望まれている。
【００２２】
本発明は上記実情を考慮してなされたもので、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行し得る乗算装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明の第１の局面は、第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力する乗算装置であって、前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を入力するための入力手段と、前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段と、前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記値Ｂｉ（ｘ）の個数ｓとに基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成する手段と、前記作成したＭテーブルを記憶するテーブル記憶手段と、前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する手段と、前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段と、前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段と、前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段と、を備えた乗算装置である。
【００２４】
本発明の第２の局面は、第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力する乗算装置であって、前記第１入力値Ａ（ｘ）及び前記第３入力値Ｆ（ｘ）と、前記第２入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切って得られるｓ個の値Ｂｉ（ｘ）の個数ｓとに基づき（但し、ｉ＝ｓ−１，ｓ−２，…，１，０）、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルが予め作成された場合、このＭテーブルと、前記各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）とを入力するための入力手段と、前記入力された第２入力値Ｂ（ｘ）を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する手段と、前記入力されたＭテーブルを記憶するテーブル記憶手段と、前記テーブル記憶手段内のＭテーブルを参照しながら、前記値Ｂｉ（ｘ）及び前記第３入力値Ｆ（ｘ）に基づき、当該値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成する手段と、前記作成したＴテーブルを前記テーブル記憶手段に書き込む手段と、前記テーブル記憶手段内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する手段と、前記総和の計算結果を前記乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として出力する手段と、を備えた乗算装置である。
【００２５】
なお、第１及び第２の局面は、装置として表現したが、装置に限らず、方法、プログラム、又はプログラムを記憶したコンピュータ読み取り可能な記憶媒体、として表現することもできる。
【００２６】
また、第１及び第２の局面では、Ｔテーブルとしては、Ｔ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるものとしたが、メモリに余裕がある場合は、ＴテーブルをＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ）の計算結果からなるものとし、ｍｏｄ Ｆ（ｘ）の演算をＰ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算時にまとめて行うことによってｍｏｄ Ｆ（ｘ）の計算量をより一層削減することも可能である。この場合のフローチャートは図３および図６のステップＳＴ１３のｍｏｄ Ｆ（ｘ）を除いたものとなる。
【００２７】
（作用）
第１の局面によれば、Ｍテーブルを入力値Ａ（ｘ）に依存して順番ｉ毎に独立して計算される構成としたことにより、従来とは異なり、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。なお、従来のＭテーブルは、入力値Ａ（ｘ）とは無関係に全ての場合の値を予め用意したので、処理単位gに比例してテーブルサイズが指数関数的に増加している。
【００２８】
第２の局面によれば、一方の入力値Ａ（ｘ）が固定値の場合、入力値Ａ（ｘ）に依存して順番ｉ毎に独立して予め計算したＭテーブルを入力する構成により、従来とは異なり、一方の入力値が固定値でも、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。
【発明の効果】
【００２９】
以上説明したように本発明によれば、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行できる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の各実施形態について図面を用いて説明するが、その前に各実施形態の概要を述べる。
【００３１】
（第１の実施形態の概要）
第１の実施形態では、図８の中央欄に示すように、乗算を実行する。すなわち、Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）が入力されると、Ｍ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）に基づき、Ｍテーブルが作成される（step 0）。なお、Ｍテーブルは、入力Ｂ（ｘ）を区切って得られた値Ｂｉの順番ｉ毎に、Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の演算結果を示している。
【００３２】
次に、Ｔ［ｉ］＝Ｍ［ｉ］Ｂｉ（ｘ） ｍｏｄ Ｆ（ｘ）に基づき、Ｔテーブルが作成される（step 1）。なお、Ｔテーブルは、値Ｂｉの順番ｉ毎に、Ｍ［ｉ］Ｂｉ（ｘ） ｍｏｄ Ｆ（ｘ）の演算結果を示している。
【００３３】
続いて、途中の計算結果Ｐ（ｘ）に０を代入する（step 2）。さらに、Ｆｏｒ文として、全てのＢｉについて、順番ｉ毎のＴテーブルの参照結果Ｔ［ｉ］が累積加算される（step 3）。しかる後、Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果が出力される。
【００３４】
以上から、処理単位gを大きくとった場合におけるメモリ使用量の少ない乗算手法を提供できる。
【００３５】
第１の実施形態のアルゴリズムは次式で評価できる。
【数３】
2009258502.tif 000005
【００３６】
第１の実施形態では、入力値Ａ（ｘ），Ｆ（ｘ）の分だけ、順番ｉ毎に独立にＡ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）を計算してＭテーブルを作成することで、準備するＭテーブルのメモリサイズを削減でき、その結果、必要なメモリサイズを削減できる。例えば、Ｍテーブルにおいては、ｍビットの計算結果がｘig乗の種類だけあればよく、順番ｉが０番目からｓ−１番目まであることから、ｍビットの計算結果がｓ個だけあればよい。ここで、Ｍテーブルのメモリサイズはｍ×ｓビットである。Ｔテーブルは、ＭテーブルとＢi（ｘ）の計算結果を格納すればよく、Ｍテーブルと同様に、ｍビットの計算結果がｓ個だけあればよい。
【００３７】
一方、従来手法であるハサンのテーブル参照法は、高次の計算結果を再帰的に低次の計算結果へ反映していたが、計算可能な範囲内の全ての計算結果を含むＭテーブルを予め記憶しておく必要があるので、図９に示すように、（g＋ｄ）×２gビットのメモリサイズを必要とする。ここで、ｄは、次の多項式Ｆ（ｘ）内の２番目に大きい次数ｄを意味している。
【数４】
2009258502.tif 000006
【００３８】
また、ｍは多項式Ｆ（ｘ）の次数である。
【００３９】
メモリサイズについて、図１０に示すように、第１の実施形態は、gが小さな場合（g＜６）にはメモリサイズが大きいが、gが大きくなってもメモリサイズが多項式的にしか増加しない。一方、ハサンのテーブル参照法は、gが小さな場合（g＜６）にはメモリサイズが小さいが、gが大きくなると（６＜g）、指数関数的にメモリサイズが増加する。例えば、g＝１６の場合のメモリサイズは、明らかに第１の実施形態の方が小さい。なお、「メモリサイズ」の用語は「メモリ量」と読み替えてもよい。
【００４０】
計算量について、図９に示すように、第１の実施形態は、ＴテーブルとＭテーブルの２種類のテーブルを作成する必要があるが、各テーブルのメモリサイズがｍ×ｓビットと小さいので、テーブル作成時間が短くて済む。一方、ハサンのテーブル参照法は、g＝１６の場合、Ｔテーブルのメモリサイズがｍ×２16ビットと大きいので、テーブル作成時間が第１の実施形態と比べて長くかかる。
【００４１】
またＦｏｒ文の処理時間について、第１の実施形態とハサンのテーブル参照法とは処理内容が異なるがほぼ同等の処理時間であると考えられる。
【００４２】
以上をまとめると、第１の実施形態では、処理単位gを大きくした場合に、メモリサイズと、テーブル作成の計算量とがそれぞれ多項式的にしか増加しない。一方、ハサンのテーブル参照法では、処理単位gを大きくした場合に、メモリサイズと、テーブル作成の計算量とがそれぞれ指数関数的に増加する。
【００４３】
従って、第１の実施形態においては、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。
【００４４】
また、第１の実施形態では、ハサンのテーブル参照法とは異なり、Ｔテーブル作成後にはＭテーブルが不要となるので、Ｆｏｒ文の実行時に必要なメモリサイズを削減することができる。
【００４５】
（第２の実施形態の概要）
第２の実施形態は、第１の実施形態の変形例であり、入力値の一方が固定値でも、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行するものである。
【００４６】
第２の実施形態では、図８の右欄に示すように乗算を実行する。すなわち、Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ），Ｍテーブルが入力される。なお、Ｍテーブルは、入力値Ａ（ｘ）が固定値であるので、Ｍ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）に基づき、事前に作成されている。
【００４７】
次に、Ｔ［ｉ］＝Ｍ［ｉ］Ｂｉ（ｘ） ｍｏｄ Ｆ（ｘ）に基づき、Ｔテーブルが作成される（step 1）。なお、Ｔテーブルは、値Ｂｉの順番ｉ毎に、Ｍ［ｉ］Ｂｉ（ｘ） ｍｏｄ Ｆ（ｘ）の演算結果を示している。
【００４８】
続いて、途中の計算結果Ｐ（ｘ）に０を代入する（step 2）。さらに、Ｆｏｒ文として、全てのＢｉについて、順番ｉ毎のＴテーブルの参照結果Ｔ［ｉ］が累積加算される（step 3）。しかる後、Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果が出力される。
【００４９】
以上のような第２の実施形態では、Ｍテーブルの作成処理(step 0)が省略され、予め作成したＭテーブルが入力される点が第１の実施形態と異なる。また、Ｍテーブル入力後のアルゴリズムは第１の実施形態と同様に実行される。
【００５０】
このとき、第２の実施形態と、ハサンのテーブル参照法とをメモリサイズ及び計算量について比較した結果を図１１に示す。
【００５１】
第２の実施形態は、メモリサイズが第１の実施形態と同一であるが、Ｍテーブルの作成に必要な計算量が第１の実施形態よりも削減されている。
【００５２】
すなわち、第２の実施形態は、第１の実施形態と同様に、処理単位gを大きくした場合に、メモリサイズと、テーブル作成の計算量とが多項式的にしか増加しないことに加え、第１の実施形態とは異なり、一方の入力値を固定値とした構成により、計算量をさらに削減することができる。しかしながら、ハサンのテーブル参照法では、前述した通り、処理単位gを大きくした場合に、メモリサイズと、テーブル作成の計算量とがそれぞれ指数関数的に増加する。
【００５３】
従って、第２の実施形態においては、一方の入力値が固定値であるときにも、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。
【００５４】
以上が各実施形態の概要である。次に、本発明の各実施形態を具体的に説明する。
【００５５】
（第１の実施形態の具体的な構成）
図１は本発明の第１の実施形態に係る乗算装置の構成を示す模式図である。この乗算装置１０は、第１入力値Ａ（ｘ）、第２入力値Ｂ（ｘ）及び第３入力値Ｆ（ｘ）に基づいて有限体上の乗算処理を実行し、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を出力するものである。
【００５６】
乗算装置１０は、具体的には、テーブル記憶部１１、入出力部１２、乗算装置制御部１３、Ｍテーブル作成部１４、Ｔテーブル作成部１５及び乗算実行部１６を備えている。
【００５７】
ここで、テーブル記憶部１１は、各部１２〜１６から読出／書込可能な記憶装置であり、図２に示すように、Ｍテーブル及びＴテーブルが記憶される。
【００５８】
ここで、Ｍテーブルは、後述する値Ｂｉ（ｘ）の順番ｉ毎に、Ｍ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果を関連付けた参照テーブルである。ここで、値Ｂｉ（ｘ）は、ｍビットの入力値Ｂ（ｘ）を処理単位g毎に区切って得られる値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）である。順番ｉは、ｓ−１から０までの任意の整数である。
【００５９】
Ｔテーブルは、値Ｂｉ（ｘ）の順番ｉ毎に、Ｔ［ｉ］＝Ｍ［ｉ］Ｂｉ（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果を関連付けた参照テーブルである。
【００６０】
入出力部１２は、外部と乗算装置制御部１３との間のデータの入出力機能を有しており、例えば、各入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）を乗算装置制御部１３に入力する機能と、乗算装置制御部１３から送出された乗算結果を出力する機能とをもっている。
【００６１】
乗算装置制御部１３は、入出力部１２との間のデータの送受信機能と、各部１１，１２，１４〜１６を制御する機能とを有しており、例えば、図３のフローチャートに示す動作を実行するように、ｍビットの入力値Ｂ（ｘ）を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する機能と、入力値Ａ（ｘ），Ｆ（ｘ）と、値Ｂｉの個数ｓをＭテーブル作成部１４に送出する機能と、Ｍテーブル作成部１４から処理終了の通知を受けると、値Ｂｉ（ｘ），Ｆ（ｘ）をＴテーブル作成部１５に送出する機能と、Ｔテーブル作成部１５から処理終了の通知を受けると、乗算実行部１６を起動する機能と、乗算実行部１６から受けた乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）を入出力部１２に出力する機能とをもっている。
【００６２】
Ｍテーブル作成部１４は、乗算装置制御部１３から受けた入力値Ａ（ｘ），Ｆ（ｘ）と、値Ｂｉ（ｘ）の個数ｓとに基づき、値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルを作成してテーブル記憶部１１に書き込む機能と、この書き込みの後、処理終了を乗算装置制御部１３に通知する機能とをもっている。
【００６３】
Ｔテーブル作成部１５は、乗算装置制御部１３から値Ｂｉ（ｘ），Ｆ（ｘ）を受けると、テーブル記憶部１１内のＭテーブルを参照しながら、各Ｂｉ（ｘ），Ｆ（ｘ）に基づき、値Ｂｉ（ｘ）の順番ｉ毎のＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるＴテーブルを作成してテーブル記憶部１１に書き込む機能と、処理終了を乗算装置制御部１３に通知する機能とをもっている。
【００６４】
乗算実行部１６は、乗算装置制御部１３に起動されると、テーブル記憶部１１内のＴテーブルの全ての計算結果Ｔ［ｓ−１］，Ｔ［ｓ−２］，…，Ｔ［ｉ］，…，Ｔ［１］，Ｔ［０］の総和を計算する機能と、総和の計算結果を乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として乗算装置制御部１３に出力する機能とをもっている。具体的には、乗算実行部１６は、起動されると、途中の計算結果Ｐ（ｘ）に０を代入する機能と、順番ｉを０に初期化する機能と、現在の順番ｉに基づき、テーブル記憶部１１内のＴテーブルを参照し、得られた計算結果Ｔ［ｉ］を現在の計算結果Ｐ（ｘ）に加算する機能と、現在の順番ｉがｓ−１であるか否かを判定する機能と、判定結果が否の場合（ｉ≠ｓ−１）、現在の順番ｉを＋１だけ更新し、Ｔテーブルの参照に戻る機能と、判定の結果、順番ｉがｓ−１を示す場合（ｉ＝ｓ−１）、現在の計算結果Ｐ（ｘ）＝Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］を乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として乗算装置制御部１３に出力し、処理を終了する機能とをもっている。
【００６５】
なお、以上のような乗算装置１０は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、乗算装置１０の機能を実現させるためのプログラムが用いられる。このように、乗算装置１０がハードウェア構成又はプログラムを用いた構成で実施可能なことは、以下の各実施形態でも同様である。
【００６６】
次に、以上のように構成された乗算装置の動作について図３のフローチャートを用いて説明する。
【００６７】
（ＳＴ１１）  乗算装置１０においては、入出力部１２により、入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）が乗算装置制御部１３に入力される。乗算装置制御部１３は、ｍビットの入力値Ｂ（ｘ）を処理単位g毎に区切ってｓ個の値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する。しかる後、乗算装置制御部１３は、入力値Ａ（ｘ），Ｆ（ｘ）と、値Ｂｉの個数ｓをＭテーブル作成部１４に送出する。
【００６８】
（ＳＴ１２）  Ｍテーブル作成部１４は、入力値Ａ（ｘ），Ｆ（ｘ）と、値Ｂｉ（ｘ）の個数ｓと、次式とに基づき、値Ｂｉ（ｘ）の順番ｉ毎の次式の計算結果からなるＭテーブルを作成してテーブル記憶部１１に書き込む。
【００６９】
Ｍ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）
なお、順番ｉは、個数ｓに基づき、ｓ−１から０までの全ての整数（ｓ−１，ｓ−２，…，ｉ，…，１，０）として得られる。
【００７０】
しかる後、Ｍテーブル作成部１４は、処理終了を乗算装置制御部１３に通知する。乗算装置制御部１３は、この処理終了の通知を受ける。
【００７１】
（ＳＴ１３）  続いて、乗算装置制御部１３は、値Ｂｉ（ｘ），Ｆ（ｘ）をＴテーブル作成部１５に送出する。Ｔテーブル作成部１５は、テーブル記憶部１１内のＭテーブルを参照しながら、各Ｂｉ（ｘ），Ｆ（ｘ）と、次式とに基づき、Ｔテーブルを作成してテーブル記憶部１１に書き込む。
【００７２】
Ｔ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）
しかる後、Ｔテーブル作成部１５は、処理終了を乗算装置制御部１３に通知する。乗算装置制御部１３は、この処理終了の通知を受ける。
【００７３】
（ＳＴ１４）  乗算装置制御部１３は、乗算実行部１６を起動する。乗算実行部１６は、途中の計算結果Ｐ（ｘ）に０を代入する。
【００７４】
（ＳＴ１５）  乗算実行部１６は、順番ｉを０に初期化する。
【００７５】
（ＳＴ１６）  乗算実行部１６は、現在の順番ｉに基づき、テーブル記憶部１１内のＴテーブルを参照し、得られた計算結果Ｔ［ｉ］を次式のように現在の計算結果Ｐ（ｘ）に加算する。
【００７６】
Ｐ（ｘ）＋＝Ｔ［ｉ］
（ＳＴ１７）  乗算実行部１６は、現在の順番ｉがｓ−１であるか否かを判定する。
【００７７】
（ＳＴ１８）  乗算実行部１６は、ステップＳＴ１７の判定結果が否の場合（ｉ≠ｓ−１）、現在の順番ｉを＋１だけ更新し、ステップＳＴ１６に戻る。
【００７８】
（ＳＴ１９）  乗算実行部１６は、ステップＳＴ１７の判定の結果、順番ｉがｓ−１を示す場合（ｉ＝ｓ−１）、現在の計算結果Ｐ（ｘ）＝Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］を乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として乗算装置制御部１３に出力し、処理を終了する。
【００７９】
なお、Ｔテーブルの全ての計算結果Ｔ［ｉ］（０≦ｉ≦ｓ−１）の総和Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］は、乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）に相当している。すなわち、Ｐ（ｘ）＝Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）となっている。
【００８０】
上述したように本実施形態によれば、Ｍテーブルを入力値Ａ（ｘ）に依存して順番ｉ毎に独立して計算される構成としたことにより、従来とは異なり、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。
【００８１】
また、上述の説明では、Ｔテーブルとしては、Ｔ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるものとしたが、メモリに余裕がある場合は、ＴテーブルをＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ）の計算結果からなるものとし、ｍｏｄ Ｆ（ｘ）の演算をＰ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算時にまとめて行うことによってｍｏｄ Ｆ（ｘ）の計算量を削減してもよい。この場合のフローチャートは、図４に示すように、図３のステップＳＴ１３のｍｏｄ Ｆ（ｘ）を除いたものとなる。
【００８２】
この場合、ステップＳＴ１３，ＳＴ１９がそれぞれ次のステップＳＴ１３’，ＳＴ１９’のように実行される。
【００８３】
（ＳＴ１３’）  乗算装置制御部１３は、値Ｂｉ（ｘ），Ｆ（ｘ）をＴテーブル作成部１５に送出する。Ｔテーブル作成部１５は、テーブル記憶部１１内のＭテーブルを参照しながら、各Ｂｉ（ｘ），Ｆ（ｘ）と、次式とに基づき、Ｔテーブルを作成してテーブル記憶部１１に書き込む。
【００８４】
Ｔ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） 
（ＳＴ１９’）  乗算実行部１６は、ステップＳＴ１７の判定の結果、順番ｉがｓ−１を示す場合（ｉ＝ｓ−１）、現在の計算結果Ｐ（ｘ）＝Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］を入力値Ｆ（ｘ）により剰余演算し、得られた剰余演算結果を乗算結果Ｐ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）として乗算装置制御部１３に出力し、処理を終了する。
【００８５】
なお、図４に示す動作の場合、Ｔテーブルの全ての計算結果Ｔ［ｉ］（０≦ｉ≦ｓ−１）の総和Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］は、乗算結果Ｐ（ｘ）の一部Ｐ（ｘ）’＝Ａ（ｘ）Ｂ（ｘ）に相当している。このため、Ｐ（ｘ）＝Ｐ（ｘ）’ｍｏｄ Ｆ（ｘ）＝｛Ｔ［ｓ−１］＋Ｔ［ｓ−２］＋…＋Ｔ［ｉ］＋…＋Ｔ［１］＋Ｔ［０］｝ ｍｏｄ Ｆ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）とする必要があった。
【００８６】
（第２の実施形態の具体的な構成）
図５は本発明の第２の実施形態に係る乗算装置の構成を示す模式図であり、図１と同一機能部については同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００８７】
第２の実施形態は、第１の実施形態の変形例であり、一方の入力値Ａ（ｘ）が固定値の場合、予め作成したＭテーブルを入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ）と共に入力することにより、Ｍテーブル作成部１４を省略した構成となっている。
【００８８】
これに伴い、乗算装置制御部１３ａは、前述した乗算装置制御部１３に比べ、Ｍテーブル作成部１４に関する機能が省略されている。
【００８９】
次に、以上のように構成された乗算装置の動作を図６のフローチャートを用いて説明する。なお、本実施形態は、前述したステップＳＴ１１〜ＳＴ１９のうち、ＳＴ１１〜ＳＴ１２の変形例のため、前述したステップＳＴ１１〜ＳＴ１２に代えて、ステップＳＴ１１ａを用いて述べる。すなわち、ステップＳＴ１１ａの実行後に、前述したステップＳＴ１３〜ＳＴ５９が実行される。
【００９０】
始めに、Ｍテーブルは、入力値Ａ（ｘ）が固定値であるため、予め作成されている。すなわち、例えば図示しない外部装置において、一方の入力値Ａ（ｘ）及びＦ（ｘ）と、他方の入力値Ｂ（ｘ）（＝ｘ(s-1)gＢs-1（ｘ）＋ｘ(s-2)gＢs-2（ｘ）＋…＋ｘigＢi（ｘ）＋…＋ｘgＢ1（ｘ）＋Ｂ0（ｘ））を処理単位g毎に区切って得られるｓ個の値Ｂｉ（ｘ）の個数ｓとに基づき（但し、ｉ＝ｓ−１，ｓ−２，…，１，０）、当該値Ｂｉ（ｘ）の順番ｉ毎のＭ［ｉ］＝Ａ（ｘ）ｘig ｍｏｄ Ｆ（ｘ）の計算結果からなるＭテーブルが予め作成されているとする。
【００９１】
（ＳＴ１１ａ）  乗算装置１０ａにおいては、入出力部１２により、入力値Ａ（ｘ），Ｂ（ｘ），Ｆ（ｘ），Ｍテーブルが乗算装置制御部１３に入力される。
【００９２】
乗算装置制御部１３ａは、このＭテーブルをテーブル記憶部１１に書き込む。また、乗算装置制御部１３ａは、ｍビットの入力値Ｂ（ｘ）を処理単位g毎に区切り、得られた値Ｂs-1（ｘ），Ｂs-2（ｘ），…，Ｂｉ（ｘ），…，Ｂ1（ｘ），Ｂ0（ｘ）を作成する。
【００９３】
（ＳＴ１３〜ＳＴ１９）ステップＳＴ１１ａの実行後、乗算装置１０ａは、前述同様に、ステップＳＴ１３〜ＳＴ１９の処理を実行する。
【００９４】
上述したように本実施形態によれば、入力値Ａ（ｘ）に依存して順番ｉ毎に独立して予め計算されたＭテーブルを入力する構成としたことにより、従来とは異なり、一方の入力値が固定値でも、処理単位gが大きい場合に、小さいメモリサイズで高速に乗算を実行することができる。
【００９５】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【００９７】
また、上述の説明では、Ｔテーブルとしては、Ｔ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ） ｍｏｄ Ｆ（ｘ）の計算結果からなるものとしたが、メモリに余裕がある場合は、ＴテーブルをＴ［ｉ］＝Ｍ［ｉ］Ｂi（ｘ）の計算結果からなるものとし、ｍｏｄ Ｆ（ｘ）の演算をＰ（ｘ）＝Ａ（ｘ）Ｂ（ｘ） ｍｏｄ Ｆ（ｘ）の計算時にまとめて行うことによってｍｏｄ Ｆ（ｘ）の計算量を削減してもよい。この場合のフローチャートは、図７に示すように、図６のステップＳＴ１３のｍｏｄ Ｆ（ｘ）を除いたものとなる。この場合、乗算装置１０ａは、前述同様に、ステップＳＴ１３’、ＳＴ１４〜ＳＴ１８、ＳＴ１９’の処理を実行する。
【００９８】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【００９９】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１００】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１０１】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１０２】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１０３】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１０４】
【図１】本発明の第１の実施形態に係る乗算装置の構成を示すブロック図である。
【図２】同実施形態におけるテーブル記憶部を説明するための模式図である。
【図３】同実施形態における動作を説明するためのフローチャートである。
【図４】同実施形態における動作の変形例を説明するためのフローチャートである。
【図５】本発明の第２の実施形態に係る乗算装置の構成を示すブロック図である。
【図６】同実施形態における動作を説明するためのフローチャートである。
【図７】同実施形態における動作の変形例を説明するためのフローチャートである。
【図８】本発明の各実施形態と従来手法とのアルゴリズムを説明するための図である。
【図９】本発明の第１の実施形態と従来手法とのメモリサイズ及び計算量を説明するための図である。
【図１０】本発明の各実施形態と従来手法との間でメモリサイズと処理単位との関係を示す図である。
【図１１】本発明の第２の実施形態と従来手法とのメモリサイズ及び計算量を説明するための図である。
【符号の説明】
【０１０５】
１０，１０ａ…乗算装置、１１…テーブル記憶部、１２…入出力部、１３，１３ａ…乗算装置制御部、１４…Ｍテーブル作成部、１５…Ｔテーブル作成部、１６…乗算実行部。
【図１】
2009258502.tif 000007
【図２】
2009258502.tif 000008
【図３】
2009258502.tif 000009
【図４】
2009258502.tif 000010
【図５】
2009258502.tif 000011
【図６】
2009258502.tif 000012
【図７】
2009258502.tif 000013
【図８】
2009258502.tif 000014
【図９】
2009258502.tif 000015
【図１０】
2009258502.tif 000016
【図１１】
2009258502.tif 000017