パラメータ設定装置、離散対数計算装置、事前計算装置、パラメータ設定方法、離散対数計算方法、事前計算方法、プログラム
【課題】離散対数の計算量と素因数分解の計算量の比を大きくする
【解決手段】本発明のパラメータ設定装置は、条件設定部、素数生成部、整数生成部を備える。条件設定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める。素数生成部は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから整数Ｎを求める。本発明の離散対数計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。
【解決手段】本発明のパラメータ設定装置は、条件設定部、素数生成部、整数生成部を備える。条件設定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める。素数生成部は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから整数Ｎを求める。本発明の離散対数計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、落し戸付き離散対数問題のパラメータ設定装置、離散対数計算装置、事前計算装置、パラメータ設定方法、離散対数計算方法、事前計算方法、プログラムに関する。
【背景技術】
【０００２】
ある群Ｇの要素ｇ、ｙが与えられたときに、ｙ＝ｇｘを満たす整数ｘが存在する場合には整数ｘを計算し、存在しない場合にはその旨を出力する問題を離散対数問題と呼ぶ。ここで、ｘをｇを底とするｙの離散対数と呼ぶ。離散対数問題が困難な群に対し、何かヒントが与えられた場合に離散対数が簡単に計算できるとき、そのヒントを落し戸と呼ぶ。そのようなヒントが構成できるような離散対数問題を落し戸付き離散対数問題と呼ぶ。
【０００３】
群Ｇとして、乗法群（Ｚ／ＮＺ）＊を考える。ただし、Ｎは正の整数である。乗法群（Ｚ／ＮＺ）＊とは、例えば、整数Ｎと互いに素な０以上Ｎ未満の整数の集合である。一般に、整数Ｎが十分に大きい場合には離散対数問題は困難だと考えられている。非特許文献１では、整数Ｎ＝ｐ１ｐ２として、次の条件を満たすものを選び、整数Ｎの素因数分解を落し戸としている。なお、ｐ１とｐ２は素数である。
【０００４】
＜条件１＞
ｉ＝１，２に対し、ｐｉ−１がＢ−ｓｍｏｏｔｈで、ｐｉ−１の２番目に大きな素因子はＢと同程度の大きさである
つまり、整数Ｎの素因数分解が未知の場合は離散対数問題が困難になるようにし、整数Ｎの素因数分解が既知の場合は離散対数問題が容易になるようにした。
【０００５】
ここで、既知の最適な離散対数の解法でも、落し戸がない状態では、まず整数Ｎを素因数分解し、それからその結果を用いて離散対数を計算する方法が最も高速である。＜条件１＞を満たす整数Ｎの場合、Ｂが十分に小さければ最も効率のよい整数Ｎの素因数分解法はｐ−１法であり、計算量はＯ（Ｂ）である。一方、離散対数の計算はPohlig-Hellman法とρ法の組合せが最適であり、計算量はＯ（√Ｂ）である。Ｏ（√Ｂ）の自乗のオーダーとＯ（Ｂ）のオーダーが同じなので、素因数分解の計算量は、離散対数の計算量の自乗のオーダーである。よって、整数Ｂを適切に選べば、素因数分解の計算は困難だが、離散対数の計算は容易になるように調整でき、落し戸付き離散対数問題が構成できる。つまり、落し戸である整数Ｎの素因数分解の結果を知っている場合（例えば、正規なユーザ）は離散対数の計算が容易だが、整数Ｎの素因数分解の結果を知らない場合（例えば、攻撃者）は離散対数の計算が困難になる。例えば、Ｂ＝２４０を選べばよい。なお、乗法群（Ｚ／ＮＺ）＊の離散対数を簡単に構成する具体例として、特許文献１〜３が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−００３９４６号公報
【特許文献２】特開２００７−１７１４１１号公報
【特許文献３】特開２００７−１７１４１２号公報
【非特許文献】
【０００７】
【非特許文献１】Kenneth G. Paterson and Sriramkrishnan Srinivasan, “On the Relations Between Non-Interactive Key Distribution, Identity-Based Encryption and Trapdoor Discrete Log Groups”、［平成２１年１０月１３日検索］、インターネット<URL: http://eprint.iacr.org/2007/453.pdf>．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術では、容易にしたい離散対数の計算量（落し戸ありの場合の計算量）がＯ（√Ｂ）であるのに対し、困難にしたい素因数分解の計算量（落し戸なしの場合の計算量）はＯ（Ｂ）である。また、Ｏ（√Ｂ）２のオーダーとＯ（Ｂ）のオーダーとが等しい。つまり、計算量の比は、自乗の比（Ｏ（√Ｂ）：Ｏ（Ｂ））程度に限られてしまうという課題がある。
【０００９】
本発明は、このような課題に鑑みてなされたものであり、離散対数の計算量（落し戸ありの場合の計算量）と素因数分解の計算量（落し戸なしの場合の計算量）の比を大きくできる整数Ｎを選定する方法を提供すること、およびこのような整数Ｎを用いた離散対数の計算方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の別のパラメータ設定装置は、条件設定部、素数生成部、整数生成部を備える。条件設定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める。例えば、条件設定部は、
【００１１】
【数１】
【００１２】
が成り立つように、整数Ｎのサイズと素因数の数Ｒを決めればよい。素数生成部は、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから、
【００１３】
【数２】
【００１４】
の関係が成り立つ整数Ｎを求める。
【００１５】
本発明の別のパラメータ設定装置は、素数生成部、整数生成部、パラメータ選定部を備える。素数生成部は、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから、整数Ｎを
【００１６】
【数３】
【００１７】
のように求める。パラメータ選定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定する。例えば、パラメータ選定部は、
【００１８】
【数４】
【００１９】
が成り立つ場合に、当該整数Ｎをパラメータとして選定する。なお、パラメータ設定装置は、複数の整数Ｎを生成しておき、その中からパラメータ選定部が条件を満たす整数Ｎを選定してもよいし、素数生成部と整数生成部が１つの整数Ｎを生成し、パラメータ選定部が条件を満たすかを確認する処理を、条件を満たす整数Ｎが生成されるまで繰り返してもよい。
【００２０】
本発明の離散対数計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【００２１】
【数５】
【００２２】
の関係が成り立つ整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００２３】
【数６】
【００２４】
の関係を満足する。そして、本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する。群要素計算部は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する。
【００２５】
本発明の事前計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙが与えられたときに、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を求める。本発明の別の離散対数計算装置は、あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部を備える。
【発明の効果】
【００２６】
本発明のパラメータ設定装置によって選定される整数Ｎの場合、それぞれのｐｒのサイズが近いときは、素因数分解の計算量ＰはＬＮ［１／３，（６４／９）１／３］となり、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算量ＱはＬＮ［１／３，（６４／９Ｒ）１／３］となる。したがって、ＰのオーダーとＱのＲ１／３乗のオーダーが等しい。つまり、Ｒを大きくすることで、素因数分解の計算量Ｐのオーダーを離散対数の計算量Ｑのオーダーの自乗よりも大きくできる。そして、このような整数Ｎを用いた離散対数計算装置によれば、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を大きくできる。
【図面の簡単な説明】
【００２７】
【図１】実施例１のパラメータ設定装置の機能構成例を示す図。
【図２】実施例１のパラメータ設定装置の処理フロー例を示す図。
【図３】実施例１変形例１のパラメータ設定装置の機能構成例を示す図。
【図４】実施例１変形例１のパラメータ設定装置の処理フロー例を示す図。
【図５】実施例２の離散対数計算装置の機能構成例を示す図。
【図６】実施例２の離散対数計算装置の処理フロー例を示す図。
【図７】実施例２変形例２の事前計算装置の機能構成例を示す図。
【図８】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【図９】実施例２変形例２の事前計算装置の処理フロー例を示す図。
【図１０】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２９】
実施例の説明の前に、本発明の理解に必要な内容について説明する。計算量を表す関数としてＬＮ［ｓ，ｃ］（ただし、ｓとｃは実数であり、０≦ｓ≦１）を、
【００３０】
【数７】
【００３１】
とおく。なお、ｏ（１）は整数Ｎが無限大の場合に０に近づく適当な関数である。また、
【００３２】
【数８】
【００３３】
とし、それぞれのｐｒのサイズは近いものとする。なお、必ずしもｐｒのサイズは近くなくても以下の説明は成り立つが、説明が煩雑になる上、発明の効率もサイズが近い場合の方が良い。仮にｐｒのサイズが異なるとすると、落し戸なしでの計算量は２番目に大きいｐｒもしくはＮのサイズによって決まり、落し戸ありでの離散対数の計算は最も大きなｐｒによって決まる。したがって、以下の説明ではそれぞれのｐｒのサイズは近いものとする。
【００３４】
既知の漸近的に最も高速な素因数分解法である数体篩法による整数Ｎの素因数分解の計算量は、ＬＮ［１／３，（６４／９）１／３］であることが知られている。漸近的にはCoppersmith（Don Coppersmith, “Modifications to the Number Field Sieve,” Journal of Cryptology, vol. 6, num. 3, pp.169-180, 1993.）の改良が知られているが、実用的な効果は薄いと信じられているので実施例では取り扱わない。また、楕円曲線法による素因数分解により因子ｐを見つける計算量は、Ｎのサイズがｐのサイズに比べてそれほど大きくない場合にはＬｐ［１／２，√２］であることが知られている。つまり、楕円曲線法により整数Ｎを素因数分解するためには、
【００３５】
【数９】
【００３６】
の計算が必要である。ここで、例えばｏ（１）を無視すれば、
【００３７】
【数１０】
【００３８】
が成り立つ場合には数体篩法の方が楕円曲線法より整数Ｎを素因数分解するには高速となる。なお、実際にはｏ（１）を無視できない場合や式（１）が成立しない場合にも落し戸付き離散対数問題が構成できるような整数Ｎもあるが、式（１）によって判別すれば、高い確率で数体篩法の方が楕円曲線法よりも高速となるので、整数Ｎを繰り返し設定するパラメータ設定装置の場合には十分に本発明の効果が得られる。したがって、式（１）の条件を用いても実用的には問題ない。
【実施例１】
【００３９】
図１に本発明のパラメータ設定装置の機能構成例を示す。また、図２にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１００は、条件設定部１３０、素数生成部１１０、整数生成部１２０、記録部１４０を備える。条件設定部１３０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める（Ｓ１３０）。素数生成部１１０は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１０）。このときに、前述のように各ｐｒのサイズが近くなるように設定することが望ましい。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００４０】
【数１１】
【００４１】
のように求め、記録部１４０に記録する（Ｓ１２０）。
【００４２】
本発明のパラメータ設定装置によって選定される整数Ｎの場合、素因数分解の計算量ＰはＬＮ［１／３，（６４／９）１／３］となり、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算量ＱはＬＮ［１／３，（６４／９Ｒ）１／３］となる。ここで、
【００４３】
【数１２】
【００４４】
である。したがって、ＰのオーダーとＱのＲ１／３乗のオーダーが等しい。つまり、Ｒを大きくすることで、素因数分解の計算量Ｐのオーダーを離散対数の計算量Ｑのオーダーの自乗よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００４５】
［変形例１］
図３に本発明の別のパラメータ設定装置の機能構成例を示す。また、図４にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１５０は、素数生成部１１５、整数生成部１２０、パラメータ選定部１６０、記録部１９０を備える。素数生成部１１５は、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１５）。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００４６】
【数１３】
【００４７】
のように求める（Ｓ１２０）。パラメータ選定部１６０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるかを確認する（パラメータとしての条件を満たすかを確認する）。そして、条件を満たす場合には当該整数Ｎをパラメータとして選定し、記録部１９０に記録する（Ｓ１６０）。パラメータとしての条件としては、例えば式（１）があるが、この式に限定する必要は無く、効率良く、かつ高い確率で判別できれば良い。そして、条件を満たさない場合にはステップＳ１１５に戻り、素数生成部１１５の素数の生成、整数生成部１２０の整数Ｎの生成、パラメータ選定部１６０の確認を繰り返す。なお、パラメータ設定装置１００は、複数の整数Ｎを生成しておき、その中からパラメータ選定部が条件を満たす整数Ｎを選定してもよい。この場合も、複数の整数Ｎの中に条件を満たす整数が存在しなかった場合には、ステップＳ１１５に戻ればよい。
【００４８】
このような構成なので、本変形例の場合にも、実施例１のパラメータ設定装置と同じ効果が得られる。
【００４９】
［変形例２］
変形例２のパラメータ設定装置１００’、１５０’では、素数生成部１１０’、１１５’が実施例１や実施例１変形例１と異なる。その他の構成部や処理フローは実施例１や実施例１変形例１のパラメータ設定装置１００、１５０と同じである。素数生成部１１０’、１１５’は、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算で特殊数体篩法が利用できる素数ｐｒを生成する（Ｓ１１０’、Ｓ１１５’）。具体的には、２５２１−１や２６０７−１などを選定すればよい。
【００５０】
このように素数ｐｒを生成すれば、Ｒが十分に大きいときに整数Ｎの素因数分解は、特殊数体篩法ではなく、やはり一般数体篩法が最も高速となる。このような素数ｐｒを用いた整数Ｎの場合、落し戸がある場合の離散対数の計算量Ｑは
【００５１】
【数１４】
【００５２】
となる。ここで、
【００５３】
【数１５】
【００５４】
である。したがって、ＰのオーダーとＱの（２Ｒ）１／３乗のオーダーが等しい。つまり、実施例１や実施例１変形例１のパラメータ設定装置１００、１５０が選定した整数Ｎよりもさらに計算量の比を大きくできる。
【実施例２】
【００５５】
図５に実施例２の離散対数計算装置の機能構成例を示す。また、図６に離散対数計算装置の処理フロー例を示す。離散対数計算装置２００は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を用いて
【００５６】
【数１６】
【００５７】
のように求められた整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００５８】
【数１７】
【００５９】
の関係を満足する。離散対数計算装置２００は、因子基底計算部２１０と群要素計算部２５０と記録部２９０とを備える。記録部２９０にあらかじめ上述の整数Ｎ、素数ｐ１，…，ｐＲを記録しておいてもよいし、パラメータ設定装置１００（１００’、１５０、１５０’）も備えておき、必要に応じて整数Ｎ、素数ｐ１，…，ｐＲを設定してもよい。因子基底計算部２１０は、多項式選択手段２２０、篩手段２３０、線形代数手段２４０を有し、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する（Ｓ２１０）。群要素計算部２５０は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する（Ｓ２５０）。
【００６０】
次に、ステップＳ２１０とＳ２５０の処理内容について詳細に説明する。整数Ｎとその素因数である素数ｐ１，…，ｐＲが与えられている場合、各ｍｏｄｐｒに対して離散対数を求め、中国人の剰余定理によりｍｏｄＮの離散対数に変換する。具体的には、ｙ（＝ｇｘ ｍｏｄｐ）とｇが与えられた際の、数体篩法による乗法群（Ｚ／ｐＺ）＊の離散対数ｘ（＝ｌｏｇｇｙ）は、多項式選択処理、篩処理、線形代数処理、個別の離散対数計算の手順で求められる。多項式選択手段２２０が多項式選択処理を行い、篩手段２３０が篩処理を行い、線形代数手段２４０が線形代数処理を行い、群要素計算部２５０が個別の離散対数計算を行う。
【００６１】
次に図６のフロー例に従いながら説明する。ｒを１とし（Ｓ２１１）、１つ目の素数ｐ１についての処理を始める。多項式選択手段２２０は、
【００６２】
【数１８】
【００６３】
となる多項式ｆｒ１、ｆｒ２∈Ｚ［Ｘ］、整数Ｍｒ１、Ｍｒ２∈Ｚ／ｐｒＺを求め、記録部２９０に記録する（Ｓ２２０）。多項式ｆｒ１、ｆｒ２は既約で、かつ複素数体Ｃ上の共通根を持ってはならない。また、多項式ｆｒ１、ｆｒ２の次数の和（ｄｅｇｆｒ１＋ｄｅｇｆｒ２）の最適な大きさは素数ｐｒのサイズにより決定される。多くの場合ｆｒ１、ｆｒ２の係数の絶対値が小さい方が、後続の計算が高速となる。なお、多項式ｆｒ１、ｆｒ２の選び方としては、多数の方法が知られており、それらの中から適宜選択すればよい。
【００６４】
ここで、複素数体Ｃ上でｆｒｉ（αｉ）＝０とする。因子基底ｉ＝１，２に対し、
【００６５】
【数１９】
【００６６】
と定義する。ここで最適なＢｉはｆｒ１、ｆｒ２とｐｒによって決まる。そして、ノルムを
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）
と定義する。篩手段２３０は、ｉ＝１，２のそれぞれに対して、
【００６７】
【数２０】
【００６８】
となる（ａ，ｂ）（ただし、ｇｃｄ（ａ，ｂ）＝１）を多数見つける（Ｓ２３０）。さらに、（ａ，ｂ）に対し、Shirokauer指数λを計算する。Ｋｉ＝Ｑ（αｉ）とし、その整数環ＯＫｉの部分集合Γｉを
【００６９】
【数２１】
【００７０】
と定義する。ここで、ｐｒは２以外の素数であり、（ｐｒ−１）／２が素数の場合にはｌ＝（ｐｒ−１）／２とし、（ｐｒ−１）／２が素数でない場合にはｌを素因数分解したすべての因子をそれぞれｌとして処理を行う。このとき、
λｉ：Γｉ→ｌＯＫｉ／ｌ２ＯＫｉ
の像はｄｅｇｆｒｉ個の成分で表現されるので、
【００７１】
【数２２】
【００７２】
を計算し、記録部２９０に記録する。その結果（ａｊ，ｂｊ）のノルムの素因数分解から、
【００７３】
【数２３】
【００７４】
という式が得られる。ここで、ｘ（ｉ）ｋ∈［０，ｌ）∩Ｚであり、ｘ（ｉ）ｋとｌｏｇｇ（ｑｋ，αｉ−ｔｋ）が未知数である。篩手段２３０は、この未知数の個数より多くの（ａｊ，ｂｊ）を集める。
【００７５】
式（２）の未知数を変数とみなして行列表記すると
Ａｘｒ＾≡０＾ （ｍｏｄｌ）
と書ける。ここで、ｘｒ＾は未知数を並べたベクトル、０＾は零ベクトルである。線形代数手段２４０は、このベクトルｘｒ＾の非自明な解を求め、記録部２９０に記録する（Ｓ２４０）。なお、Ａは疎行列となるので、Gaussの消去法などの一般的な方法ではなく、疎行列専用の高速な解法を利用できる。因子基底計算部２１０は、ｒ＝Ｒかを確認し（Ｓ２１２）、Ｙｅｓの場合には線形代数処理（Ｓ２５０）に進み、Ｎｏの場合にはｒの値を１つ増やした上で（Ｓ２１３）、多項式選択処理（Ｓ２２０）に戻る。ここまでの繰り返し処理（Ｓ２１０）で、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録されている。これらの情報が、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である。
【００７６】
群要素計算部２５０は、ｙｊｇｋがＢｉ−ｓｍｏｏｔｈになるようにｊ，ｋを求め、そのｊ，ｋ及び線形代数処理（Ｓ２４０）の結果であるベクトルｘ１＾，…，ｘＲ＾の値を用いて、個別の離散対数（ｙに対する離散対数）を計算する（Ｓ２５０）。
【００７７】
離散対数計算装置２００は、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００７８】
［変形例１］
実施例２で示したように、因子基底計算部２１０の処理（Ｓ２１０）によって、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録される。ステップＳ２１０の処理は、ｙの値が与えられなくても、整数Ｎ、素数ｐ１，…，ｐＲとｇの値が分かればあらかじめ計算しておくことが可能である。また、ステップＳ２１０の部分の計算量は、
【００７９】
【数２４】
【００８０】
であり、ステップＳ２５０の部分の計算量は、
【００８１】
【数２５】
【００８２】
しか必要としない。
【００８３】
そこで、変形例１の離散対数計算装置では、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。このように個別の要素ｙが与えられる前に計算量の多い因子基底の離散対数の計算（Ｓ２１０）を行ってしまえば、さらに処理速度を高めることができる。
【００８４】
［変形例２］
図７に実施例２変形例２の事前計算装置の機能構成例、図８に実施例２変形例２の離散対数計算装置の機能構成例を示す。また図９に事前計算装置の処理フロー例、図１０に離散対数計算装置の処理フロー例を示す。本変形例は、離散対数計算装置２００を２つに分けた構成であり、事前計算装置３００は、因子基底計算部２１０と記録部２９０を備えている。離散対数計算装置４００は、群要素計算部２５０と記録部４９０を備えている。因子基底計算部２１０の構成と処理フロー（Ｓ２１０）は実施例２と同じであり、変形例１と同じように、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。
【００８５】
そして、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が離散対数計算装置４００に送信され、記録部４９０に記録される。離散対数計算装置４００の群要素計算部２５０は、要素ｙが入力されると、ｙ＝ｇｘを満たす整数ｘを求める（Ｓ２５０）。この処理も実施例２と同じである。
【００８６】
このような構成であっても、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、事前計算装置３００および離散対数計算装置４００は、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。
【００８７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００８９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９３】
本発明は、ＩＤベース暗号などの落し戸付きの離散対数問題を必要とする暗号システムで利用できる。
【符号の説明】
【００９４】
１００、１００’、１５０、１５０’ パラメータ設定装置
１１０、１１０’、１１５、１１５’ 素数生成部
１２０ 整数生成部 １３０ 条件設定部
１４０、１９０、２９０、４９０ 記録部
１６０ パラメータ選定部 ２００、４００ 離散対数計算装置
２１０ 因子基底計算部 ２２０ 多項式選択手段
２３０ 篩手段 ２４０ 線形代数手段
２５０ 群要素計算部 ３００ 事前計算装置
【技術分野】
【０００１】
本発明は、落し戸付き離散対数問題のパラメータ設定装置、離散対数計算装置、事前計算装置、パラメータ設定方法、離散対数計算方法、事前計算方法、プログラムに関する。
【背景技術】
【０００２】
ある群Ｇの要素ｇ、ｙが与えられたときに、ｙ＝ｇｘを満たす整数ｘが存在する場合には整数ｘを計算し、存在しない場合にはその旨を出力する問題を離散対数問題と呼ぶ。ここで、ｘをｇを底とするｙの離散対数と呼ぶ。離散対数問題が困難な群に対し、何かヒントが与えられた場合に離散対数が簡単に計算できるとき、そのヒントを落し戸と呼ぶ。そのようなヒントが構成できるような離散対数問題を落し戸付き離散対数問題と呼ぶ。
【０００３】
群Ｇとして、乗法群（Ｚ／ＮＺ）＊を考える。ただし、Ｎは正の整数である。乗法群（Ｚ／ＮＺ）＊とは、例えば、整数Ｎと互いに素な０以上Ｎ未満の整数の集合である。一般に、整数Ｎが十分に大きい場合には離散対数問題は困難だと考えられている。非特許文献１では、整数Ｎ＝ｐ１ｐ２として、次の条件を満たすものを選び、整数Ｎの素因数分解を落し戸としている。なお、ｐ１とｐ２は素数である。
【０００４】
＜条件１＞
ｉ＝１，２に対し、ｐｉ−１がＢ−ｓｍｏｏｔｈで、ｐｉ−１の２番目に大きな素因子はＢと同程度の大きさである
つまり、整数Ｎの素因数分解が未知の場合は離散対数問題が困難になるようにし、整数Ｎの素因数分解が既知の場合は離散対数問題が容易になるようにした。
【０００５】
ここで、既知の最適な離散対数の解法でも、落し戸がない状態では、まず整数Ｎを素因数分解し、それからその結果を用いて離散対数を計算する方法が最も高速である。＜条件１＞を満たす整数Ｎの場合、Ｂが十分に小さければ最も効率のよい整数Ｎの素因数分解法はｐ−１法であり、計算量はＯ（Ｂ）である。一方、離散対数の計算はPohlig-Hellman法とρ法の組合せが最適であり、計算量はＯ（√Ｂ）である。Ｏ（√Ｂ）の自乗のオーダーとＯ（Ｂ）のオーダーが同じなので、素因数分解の計算量は、離散対数の計算量の自乗のオーダーである。よって、整数Ｂを適切に選べば、素因数分解の計算は困難だが、離散対数の計算は容易になるように調整でき、落し戸付き離散対数問題が構成できる。つまり、落し戸である整数Ｎの素因数分解の結果を知っている場合（例えば、正規なユーザ）は離散対数の計算が容易だが、整数Ｎの素因数分解の結果を知らない場合（例えば、攻撃者）は離散対数の計算が困難になる。例えば、Ｂ＝２４０を選べばよい。なお、乗法群（Ｚ／ＮＺ）＊の離散対数を簡単に構成する具体例として、特許文献１〜３が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−００３９４６号公報
【特許文献２】特開２００７−１７１４１１号公報
【特許文献３】特開２００７−１７１４１２号公報
【非特許文献】
【０００７】
【非特許文献１】Kenneth G. Paterson and Sriramkrishnan Srinivasan, “On the Relations Between Non-Interactive Key Distribution, Identity-Based Encryption and Trapdoor Discrete Log Groups”、［平成２１年１０月１３日検索］、インターネット<URL: http://eprint.iacr.org/2007/453.pdf>．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術では、容易にしたい離散対数の計算量（落し戸ありの場合の計算量）がＯ（√Ｂ）であるのに対し、困難にしたい素因数分解の計算量（落し戸なしの場合の計算量）はＯ（Ｂ）である。また、Ｏ（√Ｂ）２のオーダーとＯ（Ｂ）のオーダーとが等しい。つまり、計算量の比は、自乗の比（Ｏ（√Ｂ）：Ｏ（Ｂ））程度に限られてしまうという課題がある。
【０００９】
本発明は、このような課題に鑑みてなされたものであり、離散対数の計算量（落し戸ありの場合の計算量）と素因数分解の計算量（落し戸なしの場合の計算量）の比を大きくできる整数Ｎを選定する方法を提供すること、およびこのような整数Ｎを用いた離散対数の計算方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の別のパラメータ設定装置は、条件設定部、素数生成部、整数生成部を備える。条件設定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める。例えば、条件設定部は、
【００１１】
【数１】
【００１２】
が成り立つように、整数Ｎのサイズと素因数の数Ｒを決めればよい。素数生成部は、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから、
【００１３】
【数２】
【００１４】
の関係が成り立つ整数Ｎを求める。
【００１５】
本発明の別のパラメータ設定装置は、素数生成部、整数生成部、パラメータ選定部を備える。素数生成部は、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐｒから、整数Ｎを
【００１６】
【数３】
【００１７】
のように求める。パラメータ選定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定する。例えば、パラメータ選定部は、
【００１８】
【数４】
【００１９】
が成り立つ場合に、当該整数Ｎをパラメータとして選定する。なお、パラメータ設定装置は、複数の整数Ｎを生成しておき、その中からパラメータ選定部が条件を満たす整数Ｎを選定してもよいし、素数生成部と整数生成部が１つの整数Ｎを生成し、パラメータ選定部が条件を満たすかを確認する処理を、条件を満たす整数Ｎが生成されるまで繰り返してもよい。
【００２０】
本発明の離散対数計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【００２１】
【数５】
【００２２】
の関係が成り立つ整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００２３】
【数６】
【００２４】
の関係を満足する。そして、本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する。群要素計算部は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する。
【００２５】
本発明の事前計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙが与えられたときに、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を求める。本発明の別の離散対数計算装置は、あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部を備える。
【発明の効果】
【００２６】
本発明のパラメータ設定装置によって選定される整数Ｎの場合、それぞれのｐｒのサイズが近いときは、素因数分解の計算量ＰはＬＮ［１／３，（６４／９）１／３］となり、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算量ＱはＬＮ［１／３，（６４／９Ｒ）１／３］となる。したがって、ＰのオーダーとＱのＲ１／３乗のオーダーが等しい。つまり、Ｒを大きくすることで、素因数分解の計算量Ｐのオーダーを離散対数の計算量Ｑのオーダーの自乗よりも大きくできる。そして、このような整数Ｎを用いた離散対数計算装置によれば、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を大きくできる。
【図面の簡単な説明】
【００２７】
【図１】実施例１のパラメータ設定装置の機能構成例を示す図。
【図２】実施例１のパラメータ設定装置の処理フロー例を示す図。
【図３】実施例１変形例１のパラメータ設定装置の機能構成例を示す図。
【図４】実施例１変形例１のパラメータ設定装置の処理フロー例を示す図。
【図５】実施例２の離散対数計算装置の機能構成例を示す図。
【図６】実施例２の離散対数計算装置の処理フロー例を示す図。
【図７】実施例２変形例２の事前計算装置の機能構成例を示す図。
【図８】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【図９】実施例２変形例２の事前計算装置の処理フロー例を示す図。
【図１０】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２９】
実施例の説明の前に、本発明の理解に必要な内容について説明する。計算量を表す関数としてＬＮ［ｓ，ｃ］（ただし、ｓとｃは実数であり、０≦ｓ≦１）を、
【００３０】
【数７】
【００３１】
とおく。なお、ｏ（１）は整数Ｎが無限大の場合に０に近づく適当な関数である。また、
【００３２】
【数８】
【００３３】
とし、それぞれのｐｒのサイズは近いものとする。なお、必ずしもｐｒのサイズは近くなくても以下の説明は成り立つが、説明が煩雑になる上、発明の効率もサイズが近い場合の方が良い。仮にｐｒのサイズが異なるとすると、落し戸なしでの計算量は２番目に大きいｐｒもしくはＮのサイズによって決まり、落し戸ありでの離散対数の計算は最も大きなｐｒによって決まる。したがって、以下の説明ではそれぞれのｐｒのサイズは近いものとする。
【００３４】
既知の漸近的に最も高速な素因数分解法である数体篩法による整数Ｎの素因数分解の計算量は、ＬＮ［１／３，（６４／９）１／３］であることが知られている。漸近的にはCoppersmith（Don Coppersmith, “Modifications to the Number Field Sieve,” Journal of Cryptology, vol. 6, num. 3, pp.169-180, 1993.）の改良が知られているが、実用的な効果は薄いと信じられているので実施例では取り扱わない。また、楕円曲線法による素因数分解により因子ｐを見つける計算量は、Ｎのサイズがｐのサイズに比べてそれほど大きくない場合にはＬｐ［１／２，√２］であることが知られている。つまり、楕円曲線法により整数Ｎを素因数分解するためには、
【００３５】
【数９】
【００３６】
の計算が必要である。ここで、例えばｏ（１）を無視すれば、
【００３７】
【数１０】
【００３８】
が成り立つ場合には数体篩法の方が楕円曲線法より整数Ｎを素因数分解するには高速となる。なお、実際にはｏ（１）を無視できない場合や式（１）が成立しない場合にも落し戸付き離散対数問題が構成できるような整数Ｎもあるが、式（１）によって判別すれば、高い確率で数体篩法の方が楕円曲線法よりも高速となるので、整数Ｎを繰り返し設定するパラメータ設定装置の場合には十分に本発明の効果が得られる。したがって、式（１）の条件を用いても実用的には問題ない。
【実施例１】
【００３９】
図１に本発明のパラメータ設定装置の機能構成例を示す。また、図２にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１００は、条件設定部１３０、素数生成部１１０、整数生成部１２０、記録部１４０を備える。条件設定部１３０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める（Ｓ１３０）。素数生成部１１０は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１０）。このときに、前述のように各ｐｒのサイズが近くなるように設定することが望ましい。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００４０】
【数１１】
【００４１】
のように求め、記録部１４０に記録する（Ｓ１２０）。
【００４２】
本発明のパラメータ設定装置によって選定される整数Ｎの場合、素因数分解の計算量ＰはＬＮ［１／３，（６４／９）１／３］となり、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算量ＱはＬＮ［１／３，（６４／９Ｒ）１／３］となる。ここで、
【００４３】
【数１２】
【００４４】
である。したがって、ＰのオーダーとＱのＲ１／３乗のオーダーが等しい。つまり、Ｒを大きくすることで、素因数分解の計算量Ｐのオーダーを離散対数の計算量Ｑのオーダーの自乗よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００４５】
［変形例１］
図３に本発明の別のパラメータ設定装置の機能構成例を示す。また、図４にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１５０は、素数生成部１１５、整数生成部１２０、パラメータ選定部１６０、記録部１９０を備える。素数生成部１１５は、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１５）。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００４６】
【数１３】
【００４７】
のように求める（Ｓ１２０）。パラメータ選定部１６０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるかを確認する（パラメータとしての条件を満たすかを確認する）。そして、条件を満たす場合には当該整数Ｎをパラメータとして選定し、記録部１９０に記録する（Ｓ１６０）。パラメータとしての条件としては、例えば式（１）があるが、この式に限定する必要は無く、効率良く、かつ高い確率で判別できれば良い。そして、条件を満たさない場合にはステップＳ１１５に戻り、素数生成部１１５の素数の生成、整数生成部１２０の整数Ｎの生成、パラメータ選定部１６０の確認を繰り返す。なお、パラメータ設定装置１００は、複数の整数Ｎを生成しておき、その中からパラメータ選定部が条件を満たす整数Ｎを選定してもよい。この場合も、複数の整数Ｎの中に条件を満たす整数が存在しなかった場合には、ステップＳ１１５に戻ればよい。
【００４８】
このような構成なので、本変形例の場合にも、実施例１のパラメータ設定装置と同じ効果が得られる。
【００４９】
［変形例２］
変形例２のパラメータ設定装置１００’、１５０’では、素数生成部１１０’、１１５’が実施例１や実施例１変形例１と異なる。その他の構成部や処理フローは実施例１や実施例１変形例１のパラメータ設定装置１００、１５０と同じである。素数生成部１１０’、１１５’は、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算で特殊数体篩法が利用できる素数ｐｒを生成する（Ｓ１１０’、Ｓ１１５’）。具体的には、２５２１−１や２６０７−１などを選定すればよい。
【００５０】
このように素数ｐｒを生成すれば、Ｒが十分に大きいときに整数Ｎの素因数分解は、特殊数体篩法ではなく、やはり一般数体篩法が最も高速となる。このような素数ｐｒを用いた整数Ｎの場合、落し戸がある場合の離散対数の計算量Ｑは
【００５１】
【数１４】
【００５２】
となる。ここで、
【００５３】
【数１５】
【００５４】
である。したがって、ＰのオーダーとＱの（２Ｒ）１／３乗のオーダーが等しい。つまり、実施例１や実施例１変形例１のパラメータ設定装置１００、１５０が選定した整数Ｎよりもさらに計算量の比を大きくできる。
【実施例２】
【００５５】
図５に実施例２の離散対数計算装置の機能構成例を示す。また、図６に離散対数計算装置の処理フロー例を示す。離散対数計算装置２００は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を用いて
【００５６】
【数１６】
【００５７】
のように求められた整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００５８】
【数１７】
【００５９】
の関係を満足する。離散対数計算装置２００は、因子基底計算部２１０と群要素計算部２５０と記録部２９０とを備える。記録部２９０にあらかじめ上述の整数Ｎ、素数ｐ１，…，ｐＲを記録しておいてもよいし、パラメータ設定装置１００（１００’、１５０、１５０’）も備えておき、必要に応じて整数Ｎ、素数ｐ１，…，ｐＲを設定してもよい。因子基底計算部２１０は、多項式選択手段２２０、篩手段２３０、線形代数手段２４０を有し、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する（Ｓ２１０）。群要素計算部２５０は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する（Ｓ２５０）。
【００６０】
次に、ステップＳ２１０とＳ２５０の処理内容について詳細に説明する。整数Ｎとその素因数である素数ｐ１，…，ｐＲが与えられている場合、各ｍｏｄｐｒに対して離散対数を求め、中国人の剰余定理によりｍｏｄＮの離散対数に変換する。具体的には、ｙ（＝ｇｘ ｍｏｄｐ）とｇが与えられた際の、数体篩法による乗法群（Ｚ／ｐＺ）＊の離散対数ｘ（＝ｌｏｇｇｙ）は、多項式選択処理、篩処理、線形代数処理、個別の離散対数計算の手順で求められる。多項式選択手段２２０が多項式選択処理を行い、篩手段２３０が篩処理を行い、線形代数手段２４０が線形代数処理を行い、群要素計算部２５０が個別の離散対数計算を行う。
【００６１】
次に図６のフロー例に従いながら説明する。ｒを１とし（Ｓ２１１）、１つ目の素数ｐ１についての処理を始める。多項式選択手段２２０は、
【００６２】
【数１８】
【００６３】
となる多項式ｆｒ１、ｆｒ２∈Ｚ［Ｘ］、整数Ｍｒ１、Ｍｒ２∈Ｚ／ｐｒＺを求め、記録部２９０に記録する（Ｓ２２０）。多項式ｆｒ１、ｆｒ２は既約で、かつ複素数体Ｃ上の共通根を持ってはならない。また、多項式ｆｒ１、ｆｒ２の次数の和（ｄｅｇｆｒ１＋ｄｅｇｆｒ２）の最適な大きさは素数ｐｒのサイズにより決定される。多くの場合ｆｒ１、ｆｒ２の係数の絶対値が小さい方が、後続の計算が高速となる。なお、多項式ｆｒ１、ｆｒ２の選び方としては、多数の方法が知られており、それらの中から適宜選択すればよい。
【００６４】
ここで、複素数体Ｃ上でｆｒｉ（αｉ）＝０とする。因子基底ｉ＝１，２に対し、
【００６５】
【数１９】
【００６６】
と定義する。ここで最適なＢｉはｆｒ１、ｆｒ２とｐｒによって決まる。そして、ノルムを
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）
と定義する。篩手段２３０は、ｉ＝１，２のそれぞれに対して、
【００６７】
【数２０】
【００６８】
となる（ａ，ｂ）（ただし、ｇｃｄ（ａ，ｂ）＝１）を多数見つける（Ｓ２３０）。さらに、（ａ，ｂ）に対し、Shirokauer指数λを計算する。Ｋｉ＝Ｑ（αｉ）とし、その整数環ＯＫｉの部分集合Γｉを
【００６９】
【数２１】
【００７０】
と定義する。ここで、ｐｒは２以外の素数であり、（ｐｒ−１）／２が素数の場合にはｌ＝（ｐｒ−１）／２とし、（ｐｒ−１）／２が素数でない場合にはｌを素因数分解したすべての因子をそれぞれｌとして処理を行う。このとき、
λｉ：Γｉ→ｌＯＫｉ／ｌ２ＯＫｉ
の像はｄｅｇｆｒｉ個の成分で表現されるので、
【００７１】
【数２２】
【００７２】
を計算し、記録部２９０に記録する。その結果（ａｊ，ｂｊ）のノルムの素因数分解から、
【００７３】
【数２３】
【００７４】
という式が得られる。ここで、ｘ（ｉ）ｋ∈［０，ｌ）∩Ｚであり、ｘ（ｉ）ｋとｌｏｇｇ（ｑｋ，αｉ−ｔｋ）が未知数である。篩手段２３０は、この未知数の個数より多くの（ａｊ，ｂｊ）を集める。
【００７５】
式（２）の未知数を変数とみなして行列表記すると
Ａｘｒ＾≡０＾ （ｍｏｄｌ）
と書ける。ここで、ｘｒ＾は未知数を並べたベクトル、０＾は零ベクトルである。線形代数手段２４０は、このベクトルｘｒ＾の非自明な解を求め、記録部２９０に記録する（Ｓ２４０）。なお、Ａは疎行列となるので、Gaussの消去法などの一般的な方法ではなく、疎行列専用の高速な解法を利用できる。因子基底計算部２１０は、ｒ＝Ｒかを確認し（Ｓ２１２）、Ｙｅｓの場合には線形代数処理（Ｓ２５０）に進み、Ｎｏの場合にはｒの値を１つ増やした上で（Ｓ２１３）、多項式選択処理（Ｓ２２０）に戻る。ここまでの繰り返し処理（Ｓ２１０）で、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録されている。これらの情報が、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である。
【００７６】
群要素計算部２５０は、ｙｊｇｋがＢｉ−ｓｍｏｏｔｈになるようにｊ，ｋを求め、そのｊ，ｋ及び線形代数処理（Ｓ２４０）の結果であるベクトルｘ１＾，…，ｘＲ＾の値を用いて、個別の離散対数（ｙに対する離散対数）を計算する（Ｓ２５０）。
【００７７】
離散対数計算装置２００は、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００７８】
［変形例１］
実施例２で示したように、因子基底計算部２１０の処理（Ｓ２１０）によって、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録される。ステップＳ２１０の処理は、ｙの値が与えられなくても、整数Ｎ、素数ｐ１，…，ｐＲとｇの値が分かればあらかじめ計算しておくことが可能である。また、ステップＳ２１０の部分の計算量は、
【００７９】
【数２４】
【００８０】
であり、ステップＳ２５０の部分の計算量は、
【００８１】
【数２５】
【００８２】
しか必要としない。
【００８３】
そこで、変形例１の離散対数計算装置では、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。このように個別の要素ｙが与えられる前に計算量の多い因子基底の離散対数の計算（Ｓ２１０）を行ってしまえば、さらに処理速度を高めることができる。
【００８４】
［変形例２］
図７に実施例２変形例２の事前計算装置の機能構成例、図８に実施例２変形例２の離散対数計算装置の機能構成例を示す。また図９に事前計算装置の処理フロー例、図１０に離散対数計算装置の処理フロー例を示す。本変形例は、離散対数計算装置２００を２つに分けた構成であり、事前計算装置３００は、因子基底計算部２１０と記録部２９０を備えている。離散対数計算装置４００は、群要素計算部２５０と記録部４９０を備えている。因子基底計算部２１０の構成と処理フロー（Ｓ２１０）は実施例２と同じであり、変形例１と同じように、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。
【００８５】
そして、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が離散対数計算装置４００に送信され、記録部４９０に記録される。離散対数計算装置４００の群要素計算部２５０は、要素ｙが入力されると、ｙ＝ｇｘを満たす整数ｘを求める（Ｓ２５０）。この処理も実施例２と同じである。
【００８６】
このような構成であっても、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、事前計算装置３００および離散対数計算装置４００は、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。
【００８７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００８９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９３】
本発明は、ＩＤベース暗号などの落し戸付きの離散対数問題を必要とする暗号システムで利用できる。
【符号の説明】
【００９４】
１００、１００’、１５０、１５０’ パラメータ設定装置
１１０、１１０’、１１５、１１５’ 素数生成部
１２０ 整数生成部 １３０ 条件設定部
１４０、１９０、２９０、４９０ 記録部
１６０ パラメータ選定部 ２００、４００ 離散対数計算装置
２１０ 因子基底計算部 ２２０ 多項式選択手段
２３０ 篩手段 ２４０ 線形代数手段
２５０ 群要素計算部 ３００ 事前計算装置
【特許請求の範囲】
【請求項１】
整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める条件設定部と、
整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２６】
の関係が成り立つ整数Ｎを求める整数生成部を
有するパラメータ設定装置。
【請求項２】
整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を、
【数２７】
が成り立つように決める条件設定部と、
整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２８】
の関係が成り立つ整数Ｎを求める整数生成部を
有するパラメータ設定装置。
【請求項３】
Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２９】
の関係が成り立つ整数Ｎを求める整数生成部と、
整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定するパラメータ選定部を
有するパラメータ設定装置。
【請求項４】
Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数３０】
の関係が成り立つ整数Ｎを求める整数生成部と、
整数Ｎが、
【数３１】
が成り立つ場合に、当該整数Ｎをパラメータとして選定するパラメータ選定部を
有するパラメータ設定装置。
【請求項５】
請求項１から４のいずれかに記載のパラメータ設定装置であって、
前記素数生成部は、
乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できるように前記素数ｐｒを選定する
ことを特徴とするパラメータ設定装置。
【請求項６】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３２】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部とを備え、
整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算装置。
【請求項７】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３３】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部とを備え、
前記ＲとＮが、
【数３４】
の関係を満足する
ことを特徴とする離散対数計算装置。
【請求項８】
請求項６または７記載の離散対数計算装置であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算装置。
【請求項９】
請求項６から８のいずれかに記載の離散対数計算装置であって、
前記因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算装置。
【請求項１０】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３５】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部を備え、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする事前計算装置。
【請求項１１】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３６】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部を備え、
前記ＲとＮが、
【数３７】
の関係を満足する
ことを特徴とする事前計算装置。
【請求項１２】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３８】
の関係が成り立つ整数であり、
ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部を備え、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算装置。
【請求項１３】
条件設定部が、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める条件設定ステップと、
素数生成部が、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数３９】
の関係が成り立つ整数Ｎを求める整数生成ステップを
有するパラメータ設定方法。
【請求項１４】
条件設定部が、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を、
【数４０】
が成り立つように決める条件設定ステップと、
素数生成部が、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４１】
の関係が成り立つ整数Ｎを求める整数生成ステップを
有するパラメータ設定方法。
【請求項１５】
素数生成部が、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４２】
の関係が成り立つ整数Ｎを求める整数生成ステップと、
パラメータ選定部が、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定するパラメータ選定ステップを
有するパラメータ設定方法。
【請求項１６】
素数生成部が、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４３】
の関係が成り立つ整数Ｎを求める整数生成ステップと、
パラメータ選定部が、整数Ｎが、
【数４４】
が成り立つ場合に、当該整数Ｎをパラメータとして選定するパラメータ選定ステップを
有するパラメータ設定方法。
【請求項１７】
請求項１３または１６記載のパラメータ設定方法であって、
前記素数生成ステップは、
乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できるように前記素数ｐｒを選定する
ことを特徴とするパラメータ設定方法。
【請求項１８】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４５】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップと、
群要素計算部が、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップとを有し、
整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算方法。
【請求項１９】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４６】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップと、
群要素計算部が、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップとを有し、
前記ＲとＮが、
【数４７】
の関係を満足する
ことを特徴とする離散対数計算方法。
【請求項２０】
請求項１８または１９記載の離散対数計算方法であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算方法。
【請求項２１】
請求項１８から２０のいずれかに記載の離散対数計算方法であって、
前記因子基底計算ステップは、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算方法。
【請求項２２】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４８】
の関係が成り立つ整数であり、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップを有し、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする事前計算方法。
【請求項２３】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４９】
の関係が成り立つ整数であり、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップを有し、
前記ＲとＮが、
【数５０】
の関係を満足する
ことを特徴とする事前計算方法。
【請求項２４】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数５１】
の関係が成り立つ整数であり、
ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
群要素計算部が、あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップを有し、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算方法。
【請求項２５】
請求項１から１２のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【請求項１】
整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める条件設定部と、
整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２６】
の関係が成り立つ整数Ｎを求める整数生成部を
有するパラメータ設定装置。
【請求項２】
整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を、
【数２７】
が成り立つように決める条件設定部と、
整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２８】
の関係が成り立つ整数Ｎを求める整数生成部を
有するパラメータ設定装置。
【請求項３】
Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数２９】
の関係が成り立つ整数Ｎを求める整数生成部と、
整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定するパラメータ選定部を
有するパラメータ設定装置。
【請求項４】
Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成部と、
素数ｐｒから、
【数３０】
の関係が成り立つ整数Ｎを求める整数生成部と、
整数Ｎが、
【数３１】
が成り立つ場合に、当該整数Ｎをパラメータとして選定するパラメータ選定部を
有するパラメータ設定装置。
【請求項５】
請求項１から４のいずれかに記載のパラメータ設定装置であって、
前記素数生成部は、
乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できるように前記素数ｐｒを選定する
ことを特徴とするパラメータ設定装置。
【請求項６】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３２】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部とを備え、
整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算装置。
【請求項７】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３３】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部とを備え、
前記ＲとＮが、
【数３４】
の関係を満足する
ことを特徴とする離散対数計算装置。
【請求項８】
請求項６または７記載の離散対数計算装置であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算装置。
【請求項９】
請求項６から８のいずれかに記載の離散対数計算装置であって、
前記因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算装置。
【請求項１０】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３５】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部を備え、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする事前計算装置。
【請求項１１】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３６】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部を備え、
前記ＲとＮが、
【数３７】
の関係を満足する
ことを特徴とする事前計算装置。
【請求項１２】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３８】
の関係が成り立つ整数であり、
ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部を備え、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算装置。
【請求項１３】
条件設定部が、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める条件設定ステップと、
素数生成部が、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数３９】
の関係が成り立つ整数Ｎを求める整数生成ステップを
有するパラメータ設定方法。
【請求項１４】
条件設定部が、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を、
【数４０】
が成り立つように決める条件設定ステップと、
素数生成部が、整数Ｎのサイズと素因数の数Ｒから、素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４１】
の関係が成り立つ整数Ｎを求める整数生成ステップを
有するパラメータ設定方法。
【請求項１５】
素数生成部が、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４２】
の関係が成り立つ整数Ｎを求める整数生成ステップと、
パラメータ選定部が、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなる場合に、当該整数Ｎをパラメータとして選定するパラメータ選定ステップを
有するパラメータ設定方法。
【請求項１６】
素数生成部が、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する素数生成ステップと、
整数生成部が、素数ｐｒから、
【数４３】
の関係が成り立つ整数Ｎを求める整数生成ステップと、
パラメータ選定部が、整数Ｎが、
【数４４】
が成り立つ場合に、当該整数Ｎをパラメータとして選定するパラメータ選定ステップを
有するパラメータ設定方法。
【請求項１７】
請求項１３または１６記載のパラメータ設定方法であって、
前記素数生成ステップは、
乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できるように前記素数ｐｒを選定する
ことを特徴とするパラメータ設定方法。
【請求項１８】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４５】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップと、
群要素計算部が、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップとを有し、
整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算方法。
【請求項１９】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４６】
の関係が成り立つ整数であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップと、
群要素計算部が、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップとを有し、
前記ＲとＮが、
【数４７】
の関係を満足する
ことを特徴とする離散対数計算方法。
【請求項２０】
請求項１８または１９記載の離散対数計算方法であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算方法。
【請求項２１】
請求項１８から２０のいずれかに記載の離散対数計算方法であって、
前記因子基底計算ステップは、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算方法。
【請求項２２】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４８】
の関係が成り立つ整数であり、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップを有し、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする事前計算方法。
【請求項２３】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数４９】
の関係が成り立つ整数であり、
因子基底計算部が、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップを有し、
前記ＲとＮが、
【数５０】
の関係を満足する
ことを特徴とする事前計算方法。
【請求項２４】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数５１】
の関係が成り立つ整数であり、
ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
群要素計算部が、あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップを有し、
前記Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない
ことを特徴とする離散対数計算方法。
【請求項２５】
請求項１から１２のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−９５２８４（Ｐ２０１１−９５２８４Ａ）
【公開日】平成２３年５月１２日（２０１１．５．１２）
【国際特許分類】
【出願番号】特願２００９−２４６０２０（Ｐ２００９−２４６０２０）
【出願日】平成２１年１０月２７日（２００９．１０．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年５月１２日（２０１１．５．１２）
【国際特許分類】
【出願日】平成２１年１０月２７日（２００９．１０．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]