(57)【要約】【課題】乗法群の要素である複数の被検査値すべての位数が所定の位数の約数であることを高速に検査する。【解決手段】群を定義する変数ｐ、複数の被検査値の列ｇｉ；（ｉ＝１、２、…、ｎ）、基準となる位数ｑ及び安全変数ｓを入力し（Ｓ１０１）、ステップＳ１０２〜Ｓ１０９のループを実行する。各ループでは、乱数ｒを発生し（Ｓ１０２）、この乱数に基づいて被検査値の列ｇｉの中から無作為に選択した被検査値の前記群上での積である検査積Ｑを計算し（Ｓ１０３）、検査積Ｑの位数が位数ｑの約数であるかどうかを判定する（Ｓ１０４）。検査積Ｑの位数が位数ｑの約数でないときは検査不合格の旨を出力して処理を終了する。検査積Ｑの位数が位数ｑの約数であり、且つ、安全変数ｓの回数だけループを繰り返していれば、検査合格の旨を出力して処理を終了する。【選択図】　図２
2004020984.tif 000002
【特許請求の範囲】
【請求項１】
与えられた群上で複数の被検査値が与えられたとき、これらの値すべての位数がすべて与えられた値の約数であることを確認する方法であって、
群を定義する変数と、前記群の要素である複数の被検査値と、位数と、安全変数とが入力される、入力処理と、
前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものを含む場合には、０と有意に異なる確率でこれを検出する、検査処理と、
前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれることが検出されるに至るか、あるいは前記安全変数により指定される回数実行されるに至るまで、前記検査処理を繰り返し実行する繰り返し処理と、
前記繰り返し処理において、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれることが検出された場合には「不受理」を、検出されない場合には「受理」を出力する出力処理と、
を含むことを特徴とする、複数の要素に対する確率的同時位数検査方法。
【請求項２】
前記検査処理が、
乱数生成器により乱数を生成する乱数生成処理と、
前記乱数を用いて、前記複数の被検査値の各値について選択または非選択を決定し、選択された値すべての前記群上での積である検査積を計算する、検査積生成処理と、
前記検査積の位数が前記与えられた位数の約数でなければ、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれると判断する、検査積位数判断処理と、
を含むことを特徴とする請求項１記載の複数の要素に対する確率的同時位数検査方法。
【請求項３】
複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ、
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ、
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ、
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ、
を含むことを特徴とする、複数の要素に対する確率的同時位数検査方法。
【請求項４】
複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ、
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｃ）乱数を発生するステップ、
ｄ）発生した乱数を第５の記憶手段に記憶するステップ、
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ、
ｆ）計算した検査積を第６の記憶手段に記憶するステップ、
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ、
ｈ）判定結果を第７の記憶手段に記憶するステップ、
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ、
を含むことを特徴とする、複数の要素に対する確率的同時位数検査方法。
【請求項５】
複数の被検査値すべての位数が基準となる位数の約数であることを検査するプログラムであって、コンピュータに、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ、
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ、
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ、
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ、
を実行させる位数検査プログラム。
【請求項６】
複数の被検査値すべての位数が基準となる位数の約数であることを検査するプログラムであって、コンピュータに、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ、
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｃ）乱数を発生するステップ、
ｄ）発生した乱数を第５の記憶手段に記憶するステップ、
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ、
ｆ）計算した検査積を第６の記憶手段に記憶するステップ、
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ、
ｈ）判定結果を第７の記憶手段に記憶するステップ、
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ、
を実行させる位数検査プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のデータの位数が特定の値であることを検査する方法に関し、特に複数のデータを一括して扱うことにより高速に結果を判定する方法に関する。
【０００２】
【従来の技術】
多くの公開鍵暗号系のアプリケーションでは、安全性を保証するために、暗号文を構成する数値の位数を検査することがある。ここで言う数値の位数とは、その数値が生成する巡回群の集合としての位数のことであり、数値の位数の検査とは、その数値の位数が想定されている値であるかを検査することである。位数について簡単な例を挙げて説明する。今、乗法群（Ｚ／ｐＺ）＊としてｐ＝７である（Ｚ／７Ｚ）＊を、数値として３を想定すると、数値３が生成する巡回群の集合は、３１　ｍｏｄ　７＝３、３２　ｍｏｄ　７＝２、３３　ｍｏｄ　７＝６、３４　ｍｏｄ　７＝４、３５　ｍｏｄ　７＝５、３６　ｍｏｄ　７＝１、３７　ｍｏｄ　７＝３、３８　ｍｏｄ　７＝２、３９　ｍｏｄ　７＝６、３１０　ｍｏｄ　７＝４、３１１　ｍｏｄ　７＝５、…、であり、３，２，６，４，５，１の６個の要素からなる。これを、数値３が乗法群（Ｚ／７Ｚ）＊上で生成する巡回群の集合としての位数は６であると言う。
【０００３】
ところで、近年電子投票等の暗号アプリケーション等、膨大な数の暗号文を一度に扱う機会が増えている。このため、これらのアプリケーションで数値の位数の検査を迅速に完了することが求められている。位数検査が必要となる具体的な例としては、「検証可能な　Ｍｉｘ−ｎｅｔ　」と呼ばれる暗号プロトコルを用いた電子投票システムがあげられる。ここで投票行為は、公開鍵暗号システムを用いて暗号化した投票文を集計所に送付することにより行われる。集計では、まず送付された投票暗号文を複数の集計者により共同して復号し、次に復号された投票文を集計する。一連の集計操作の終了後、「検証可能な　Ｍｉｘ−ｎｅｔ　」では、一連の操作が正しく行われたかを証明するデータを、集計者が協力して生成し出力する。このデータのことを以後「証明データ」と呼ぶことにする。ところで、もし集計結果が正しくなかったとしても、暗号投票文の集合と復号した投票文の集合のみからはその事実は簡単には分らない。しかし復号のための鍵を持っているならば、集計結果が正しいかどうかはたちどころに分る。なぜならこの鍵で全ての投票暗号文を復号して二つの集合を比較すれば良いからである。証明データとはこのように集計結果が正当であるかを知ることを可能にするデータであるが、鍵そのものでなく、証明データからは投票暗号文と復号結果の対応は分らない（つまり、投票の匿名性を破らない）データである。「検証可能な　Ｍｉｘ−ｎｅｔ　」を用いた電子投票では、投票の集計において不正がなされていないことを、投票暗号文と復号された投票文と証明データから特殊なアルゴリズムを用いて判断する。このアルゴリズムの中に、特に「検証可能な　Ｍｉｘ−ｎｅｔ　」がエルガマル暗号文を利用する場合、暗号文と復号された投票文と証明データを構成する値の位数を調べる操作が含まれることが多い。なぜなら、エルガマル暗号文では位数の異なる暗号文を識別できるため、同じ位数の暗号文だけを選んで使わないと、電子投票システムの安全性が低下するからである。
【０００４】
さて、従来の位数検査の方法には、以下のようなものがある。先ず、数値ｇの位　数がｑの約数であることを検査するためには、数値ｇをこの数値ｇが定義された群上で、数値ｇのｑ＋１乗である　ｇｑ＋１を計算する。つまり、定義された群を（Ｚ／ｐＺ）　＊とすると、ｇｑ＋１　ｍｏｄ　ｐ　を計算する。そして、この計算結果がｇに等しければ、数値ｇの位数はｑの約数であったと判定する。特に、ｑが素数の場合は、その位数は１あるいはｑである。
【０００５】
【発明が解決しようとする課題】
しかし前記従来の技術におけるｇｑ＋１の計算には、多大な計算コストがかかる場合が多いため、多数の数値の位数の検査を行うには膨大な時間がかかるという問題がある。特にＭｉｘ−ｎｅｔにより大規模な電子投票を行う場合などには、位数を検査する必要のある暗号文が膨大なため、多大な時間が必要になり、システムの運用が困難になる場合がある。
【０００６】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、多数の数値の位数をより少ない時間で検査する方法を提供することにある。
【０００７】
【課題を解決するための手段】
本発明の第１の複数の要素に対する確率的同時位数検査方法は、与えられた群上で複数の被検査値が与えられたとき、これらの値すべての位数がすべて与えられた値の約数であることを確認する方法であって、群を定義する変数と、前記群の要素である複数の被検査値と、位数と、安全変数とが入力される入力処理と、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものを含む場合には、０と有意に異なる確率でこれを検出する検査処理と、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれることが検出されるに至るか、あるいは前記安全変数により指定される回数実行されるに至るまで、前記検査処理を繰り返し実行する繰り返し処理と、前記繰り返し処理において、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれることが検出された場合には「不受理」を、検出されない場合には「受理」を出力する出力処理とを含むことを特徴とする。
【０００８】
本発明の第２の複数の要素に対する確率的同時位数検査方法は、第１の複数の要素に対する確率的同時位数検査方法において、前記検査処理が、乱数生成器により乱数を生成する乱数生成処理と、前記乱数を用いて、前記複数の被検査値の各値について選択または非選択を決定し、選択された値すべての前記群上での積である検査積を計算する検査積生成処理と、前記検査積の位数が前記与えられた位数の約数でなければ、前記複数の被検査値の中に一つでも位数が前記与えられた位数の約数でないものが含まれると判断する検査積位数判断処理と、を含むことを特徴とする。
【０００９】
本発明の第３の複数の要素に対する確率的同時位数検査方法は、複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、以下のステップを含むことを特徴とする。
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ
【００１０】
本発明の第４の複数の要素に対する確率的同時位数検査方法は、複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、以下のステップを含むことを特徴とする。
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ
ｃ）乱数を発生するステップ
ｄ）発生した乱数を第５の記憶手段に記憶するステップ
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ
ｆ）計算した検査積を第６の記憶手段に記憶するステップ
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ
ｈ）判定結果を第７の記憶手段に記憶するステップ
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ
【００１１】
【作用】
本発明にあっては、被検査値の中にその位数が与えられた位数の約数でないものがある場合には、安全変数を十分大きくとれば十分に１に近い確率で、そのようであることを確認できる。また、前記安全変数が位数のｂｉｔ数よりも十分に小さく、かつ、位数を検査する検査値の数が位数のｂｉｔ数よりも十分に大きい場合には、従来の方式による位数の検査よりも効率良く位数を検査することができる。例えば、位数のｂｉｔ数が１６０以上の数であれば、安全変数は４０ほどで十分な精度の検査が可能であり、この場合、被検査数値列が４５個以上の要素からなる場合には、計算コストが従来技術に比べて低減される。
【００１２】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００１３】
図１を参照すると、本発明を適用したコンピュータの一例は、入力装置１００、出力装置２００、プログラム記憶装置３００、メモリ４００、及びそれらに接続された中央処理装置５００で構成される。入力装置１００は、キーボード等の手動入力装置、入力データを記憶するファイル装置、通信回線を通じて送られてくるデータを受信する通信装置などで構成される。出力装置２００は、表示装置、プリンタ、出力データを記憶するファイル装置、通信回線を通じて出力データを送信する通信装置などで構成される。プログラム記憶装置３００は、当該コンピュータの基本プログラムや位数検査プログラムなどのソフトウェアを記憶するための磁気ディスク等で構成される。メモリ４００は、位数検査処理の過程で必要となる各種のデータを記憶するための記憶部で、ＲＡＭ等で構成される。本実施の形態の場合、メモリ４００には、ファイルやテーブル等で構成される第１乃至第７の記憶手段４０１〜４０７が設けられている。中央処理装置５００は、プログラム記憶装置３００に記憶されたプログラムを実行することにより、本コンピュータの全体を制御する。特に、プログラム記憶装置３００に記憶された位数検査プログラムを実行することにより、本発明にかかる位数検査方法を実行する。
【００１４】
次に図２を参照して、位数検査プログラムによる処理の流れを説明する。
【００１５】
［前提］
ｐを整数、φ（ｐ）を、ｐ未満の正整数のうちｐと互いに素な正整数の総数、ｑを、ｑ｜φ（ｐ）なる整数、つまりφ（ｐ）が割り切れる整数とする。この意味を簡単な例を挙げて説明すると、ｐ＝１５の場合、ｐ未満の正整数のうちｐと互いに素な正整数は、１，２，４，７，８，１１，１３，１４の合計８個であるから、φ（ｐ）＝８であり、８が割り切れる整数であるｑは１，２，４，８である。なお、この複数の値のｑのうち、特定の値のｑを基準となる位数として位数検査が行われる。
【００１６】
［入力処理Ｓ１０１］
中央処理装置５００は、入力装置１００から、乗法群（Ｚ／ｐＺ）＊を定義する変数ｐ、この群の要素であるｎ個の被検査値ｇ１，ｇ２，…，ｇｎ、基準となる位数ｑおよび安全変数ｓを入力し、第１の記憶手段４０１、第２の記憶手段４０２、第３の記憶手段４０３および第４の記憶手段４０４に記憶する。例えば本発明を従来技術の項で説明した「検証可能な　Ｍｉｘ−ｎｅｔ　」と呼ばれる暗号プロトコルを用いた電子投票システムに適用する場合、変数ｐは公開鍵暗号が用いる群を定義する変数に相当し、複数の被検査値は暗号化されて投票された票、復号が終了した票、集計処理が正常に行われたことを証明するデータを構成する要素に相当し、基準となる位数ｑは当該電子投票システムで用いることが定められた位数に相当する。また、安全変数ｓは検査に要求される精度に応じて事前に定められる。
【００１７】
［乱数生成処理Ｓ１０２］
中央処理装置５００は、乱数発生手段を用いて、被検査値の個数ｎと等しいｎビットの乱数ｒを生成し、第５の記憶手段４０５に記憶する。ここで、乱数ｒの各ビットの値は１または０である。
【００１８】
［検査積生成処理Ｓ１０３］
中央処理装置５００は、第１、第２、第５の記憶手段４０１、４０２、４０５から、群を定義する変数ｐ、ｎ個の被検査値ｇ１，ｇ２，…，ｇｎ、ｎビットの乱数ｒをそれぞれ取得し、ｎ個の被検査値ｇ１，ｇ２，…，ｇｎと乱数の各ビットとを１対１に対応付けた場合に、乱数ｒの対応するビットの値が予め定められた値（例えば１）である被検査値だけを選び出し、それらの被検査値の前記群上での積である検査積Ｑを計算し、第６の記憶手段４０６に記憶する。検査積Ｑの計算を簡単な例で説明すると、群を（Ｚ／７Ｚ）＊、選ばれた２つの被検査値ｇ１，ｇ２を３，４とすると、それらの被検査値の前記群上での積である検査積Ｑは、３＊４　ｍｏｄ　７　＝５　と計算する。
【００１９】
［検査積位数判定処理Ｓ１０４］
中央処理装置５００は、第１、第３、第６の記憶手段４０１、４０３、４０６から、群を定義する変数ｐ、基準となる位数ｑ、検査積Ｑをそれぞれ取得して、検査積Ｑの位数が基準となる位数ｑの約数であるかどうかを、以下の式が成立するかどうかを計算することによって判定し、その判定結果を第７の記憶手段４０７に記憶する。
Ｑｑ＋１　ｍｏｄ　ｐ　＝Ｑ
上記の式が成立するときは、当該検査積Ｑの計算の元となった全ての被検査値の位数が位数ｑの約数であるため、判定結果を「受理」とし、安全変数判断処理Ｓ１０７へ分岐する。反対に、上記の式が成立しないときは、当該検査積Ｑの計算の元となった被検査値の中に少なくとも位数が位数ｑの約数でない被検査値が含まれているため、判定結果を「不受理」とし、不受理出力処理Ｓ１０５へ分岐する。
【００２０】
［不受理出力処理Ｓ１０５］
中央処理装置５００は、「不受理」の判定結果を第７の記憶手段４０７から取り出し、出力装置２００から出力する。そして、当該被検査値に対する位数検査処理を終了する（Ｓ１０６）。
【００２１】
［安全変数判断処理Ｓ１０７］
中央処理装置５００は、第４の記憶手段４０４から安全変数ｓを取り出し、予め定められた値（本例では１）より大きいかどうかを判定し、１より大きければ繰り返し処理Ｓ１０９へ分岐し、１より大きくなければ、受理出力処理Ｓ１０８へ分岐する。
【００２２】
［受理出力処理Ｓ１０８］
中央処理装置５００は、「受理」の判定結果を第７の記憶手段４０７から取り出し、出力装置２００から出力する。そして、当該被検査値に対する位数検査処理を終了する（Ｓ１０６）。
【００２３】
［繰り返し処理Ｓ１０９］
中央処理装置５００は、第４の記憶手段４０４に記憶されている安全変数ｓを所定値（本例では１）だけ減じ、乱数生成処理Ｓ１０２に分岐する。これにより、上述した処理が繰り返される。この繰り返しは、処理Ｓ１０３で生成された検査積Ｑの位数が位数ｑの約数でないと判定されるか、処理Ｓ１０７で安全変数ｓの値が１より大きくないと判定されるまで続けられる。
【００２４】
次に、本実施例の効果を説明する。
【００２５】
全ての被検査数値列ｇｉ；（ｉ＝１、２、…、ｎ）に関して、ｇｉｑ＋１　ｍｏｄ　ｐ　＝ｇｉが成り立つならば、本実施例では必ず「受理」を出力する。これは明らかである。一つでもｇｉｑ＋１　ｍｏｄ　ｐ　≠ｇｉなるｇｉが存在する場合、各検査積Ｑがｇｉを含む確率は１／２である。なぜなら、検査積を構成するその他の要素を同じとして、検査積Ｑがｇｉを含む場合と含まない場合の両方の場合に、共にＱｑ＋１　ｍｏｄ　ｐ　＝Ｑが成り立つことは有り得ない。よって、一つでもｇｉｑ＋１　ｍｏｄ　ｐ　≠ｇｉなるｇｉが存在する場合、無作為に選ばれた乱数ｒに関して、Ｑｑ＋１　ｍｏｄ　ｐ　＝Ｑが成り立つ確立は、１／２以下であるからである。
【００２６】
本実施例において「受理」を出力した場合は、ｓ個の乱数に関して生成された検査積Ｑ全てが、Ｑｑ＋１　ｍｏｄ　ｐ　＝Ｑを満たしたと言うことであるので、一つでもｇｉｑ＋１　ｍｏｄ　ｐ≠ｇｉなるｇｉが存在する確率は１／２ｓ以下である。従って、安全変数ｓを十分に大きくとれば、ｇｉｑ＋１　ｍｏｄ　ｐ　≠ｇｉなるｇｉの存在を見逃す確率は無視できるほど小さくなる。
【００２７】
従来の方法でｎ個のｇｉに関して、ｇｉｑ＋１　ｍｏｄ　ｐ＝ｇｉを確認するには、冪乗剰余算をｎ回行わなければならなかった。そして、一回の冪乗剰余算にはおよそｑのビット数の３／２倍の乗算剰余が必要である。ｑのビット数を｜ｑ｜とすると、全体で（３／２）｜ｑ｜ｎ回の乗算剰余が必要である。
【００２８】
一方本実施例では、検査積Ｑを生成するにはｎ／２回の乗算剰余が必要で、Ｑｑ＋１　を計算するには（３／２）｜ｑ｜回の乗算剰余が必要なので、全体として、｛（１／２）ｎ　＋　（３／２）｜ｑ｜｝ｓ回の乗算剰余が必要になる。
【００２９】
従って、ｎが｜ｑ｜より十分大きい場合、すなわち多くの位数検査を行う必要がある場合で、かつｓ＜３｜ｑ｜であれば本実施例は従来の方法よりも効率が良い。現実的に、前述した電子投票システム等の場合、位数のｂｉｔ数｜ｑ｜は１６０以上の数が選ばれる場合が多く、安全変数ｓは４０ほどで十分な場合が多い。このような条件では、被検査数値列が４５個以上の要素からなる場合では、本実施例の方が効果的である。
【００３０】
【発明の効果】
以上説明したように本発明によれば、多数の数値の位数をより少ない時間で検査することが可能である。その理由は、複数のデータを一括して扱い且つ確率的に検査しているからである。
【図面の簡単な説明】
【図１】本発明を適用したコンピュータの一例を示すブロック図である。
【図２】位数検査プログラムによる処理の流れを示すフローチャートである。
【符号の説明】
１００…入力装置
２００…出力装置
３００…プログラム記憶装置
４００…メモリ
４０１〜４０７…第１〜第７の記憶手段
５００…中央処理装置
【図１】
2004020984.tif 000003
【図２】
2004020984.tif 000004