(57)【特許請求の範囲】
【請求項１】
数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算装置であって、
ｐ、ｑ、ｇ及びｙを保持する入力保持手段と、
数体ふるい法で用いる複数の多項式を生成する多項式生成手段と、
数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理手段と、
前記ふるい処理手段が生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持手段と、
数体ふるい法で用いられる指標を演算する指標演算手段と、
数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算手段と、
前記ふるい処理を行うか否かを制御する演算制御手段と、
を具え、
前記演算制御手段は、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持手段に格納されたｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持手段にて格納した整数の対（ａ，ｂ）を取得し、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持手段に格納し、前記多項式生成手段、前記ふるい処理手段、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力する演算制御手段と
を具えることを特徴とする離散対数演算装置。
【請求項２】
前記指標演算手段が演算した指標を複数保持する指標保持手段を更に具え、
前記演算制御手段は、前記条件が成立する場合には、前記ふるいデータ保持手段にて格納した整数の対（ａ，ｂ）及び前記指標保持手段にて格納した指標を取得し、前記対数演算手段を用いてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持手段に格納し、前記多項式生成手段、前記ふるい処理手段、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力することを特徴とする請求項１記載の離散対数演算装置。
【請求項３】
前記多項式生成手段が生成する多項式を保持する多項式保持手段を更に具え、
前記条件は、前記演算制御手段が取得したｐと、前記入力保持手段に格納されたｐとが一致し、かつ、前記演算制御手段が取得したｑが前記多項式保持手段に格納された多項式の根を添加した有理数体上の拡大体において分岐しない条件であることを特徴とする請求項１又は２記載の離散対数演算装置。
【請求項４】
複数の多項式を取得する多項式取得手段を更に具え、
前記演算制御手段は、前記多項式取得手段が取得した多項式を前記多項式保持手段に格納し、前記多項式保持手段に格納された多項式のみを用いて数体ふるい法を行うことを特徴とする請求項３に記載の離散対数演算装置。
【請求項５】
ｐ−１を割る異なる素数冪ｑ（１），ｑ（２），ｑ（ｋ）を法とする複数の入力値に対して、複数の離散対数計算を行い、
複数の（ｐ，ｑ（１），ｇ（１），ｙ（１）），（ｐ，ｑ（２），ｇ（２），ｙ（２）），．．．，（ｐ，ｑ（ｋ），ｇ（ｋ），ｙ（ｋ））を取得する手段と、
ｑ（１），ｑ（２），．．．，ｑ（ｋ）が分岐しない有理体上の拡大体を定義する複数の規約多項式を生成する手段と、
ｇ（ｉ）ｘ（ｉ）＝ｙ（ｉ）を満たすｘ（ｉ） ｍｏｄ ｑ（ｉ）を出力する手段とを更に具えることを特徴とする請求項４記載の離散対数演算装置。
【請求項６】
入力保持手段、多項式生成手段、ふるい処理手段、ふるいデータ保持手段、指標演算手段、対数演算手段、及び演算制御手段を備える離散対数演算装置にて、数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算方法であって、
前記ふるいデータ保持手段により、ｐ、ｑ、ｇ及びｙを保持する入力保持ステップと、
前記多項式生成手段により、数体ふるい法で用いる複数の多項式を生成する多項式生成ステップと
前記ふるい処理手段により、数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理ステップと、
前記ふるいデータ保持手段により、前記ふるい処理ステップにて生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持ステップと、
前記指標演算手段により、数体ふるい法で用いられる指標を演算する指標演算ステップと、
前記対数演算手段により、数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算ステップと、
前記演算制御手段により、前記ふるい処理を行うか否かを制御する演算制御ステップと、
を含み、
前記演算制御ステップは、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持ステップにて格納したｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップで格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップをにてｘ ｍｏｄ ｑを出力するステップを含むことを特徴とする離散対数演算方法。
【請求項７】
指標保持手段を更に備える離散対数演算装置にて、
前記指標保持手段により、前記指標演算手段が演算した指標を複数保持する指標保持ステップを更に含み、
前記演算制御ステップは、前記条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）及び前記指標保持ステップにて格納した指標を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップにて格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力することを特徴とする請求項６記載の離散対数演算方法。
【請求項８】
数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算を実行する離散対数演算装置としてのコンピュータに、
ｐ、ｑ、ｇ及びｙを保持する入力保持ステップと、
数体ふるい法で用いる複数の多項式を生成する多項式生成ステップと、
数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理ステップと、
前記ふるい処理ステップにて生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持ステップと、
数体ふるい法で用いられる指標を演算する指標演算ステップと、
数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算ステップと、
前記ふるい処理を行うか否かを制御する演算制御ステップと、
を実行させるためのプログラムであって、
演算制御ステップは、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持ステップにて格納したｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップにて格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力するステップを含むことを特徴とする離散対数演算プログラム。
【請求項９】
前記指標演算ステップにて演算した指標を複数保持する指標保持ステップを更に実行させ、
前記演算制御ステップは、前記条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）及び前記指標保持ステップにて格納した指標を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップにて格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力することを特徴とする請求項８記載の離散対数演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散対数問題の困難性を安全性の根拠とするセキュリティ技術に多く応用されている情報セキュリティの分野において、離散対数問題を計算機上で解く離散対数演算装置、方法及びプログラムに関する。
【背景技術】
【０００２】
「有限体上の離散対数」とは、位数ｐ（但し、ｐは素数又は素数べき）の有限体ＧＦ（ｐ）と、ＧＦ（ｐ）の元ｙとｇに対して、ｙ＝ｇｘを満たす０以上ｐ−２以下の整数を指し、ｐが非常に大きな素数の場合には、離散対数の計算が困難であることが知られている。（以下、ｐ，ｇ，ｙからｘを求める計算問題を「離散対数問題」と呼ぶことにする。）そのために、離散対数問題の計算困難性は、暗号の鍵を交換するために用いられるDiffie−Hellman方式や、デジタル署名方式の一つであるＤＳＡの安全性を保証する仮定として利用されている。
【０００３】
一方、離散対数問題を高速に解くためのアルゴリズムの発明や高速化は、離散対数問題の計算の困難性を仮定とした暗号の安全性を図る上で重要な技術分野であり、現在でも活発に研究がなされている。
【０００４】
現在、最も早く離散対数問題を解くアルゴリズムは、D.Gordonが発明し、O.Schirokauerが理論的な改良を加えた「数体ふるい法」である。数体ふるい法の計算量は、ｐの大きさに依存し、Lｐ（1/3，（64/9）1/3）＝exp（（64/9）1/3＋o（1））（1og p）1/3（loglog p）2/3)と評価されている（例えば、非特許文献１）。
【０００５】
有理数体上の代数体Ｋと、Ｋで分岐しない素数ｑに対して以下の写像を導入した。
λ1:Ｕｑ→ｑＯ／ｑ２Ｏ、λ1（ξ）＝ξ２  ｍｏｄ  ｑ２Ｏ
（但し、Ｏは、Ｋの整数環、Ｕｑは、ｑと素なＯの元の集合、εは、ｑを割るＫの全ての素イデアルＱに対して（Ｏ／Ｑの要素数−１）の最小公倍数で定義される整数）
λｉ：kernel（λｉ−１）→ｒｉ−１Ｏ／ｒｉＯ，λ１（ξ）＝ξε  ｍｏｄ  ｒｉＯ
（但し、i＞1のときで、kernel（λｉ−１）は写像λｉ−１の核を表す。）
この写像λｉは次の性質を持っている。
「ｑと互いに素であるＫの元ξに対して、単項イデアル（ξ）が、あるイデアルのｑ冪元と一致し、２σ＞ｅを満たす整数σに対して、λσ（ξ）＝０であれば、ξはＫの元のｑｅ冪元である。」
この性質を持つλを導入することによって、計算量をＬｐ（１／３，（６４／９）１／３）に抑えることに成功した
また、Schirokauerの提案したアルゴリズムを実装した数値実験が複数報告されている。
【非特許文献１】O.Schirokauer,”Discrete logarithms and local units”，Phil．Trans.Soc．LondonSer.A，Vol.345，Royal Society London，pp409-424，1993．
【非特許文献２】D.Weber，”An Implementation of the General Number Field Sieve to Compute Discrete Logarithms mod p”, Advanced in Cryptology-EUROCRYPT’95, LNCS921, pp.95-106, Springer-Verlag Berlin Heidelberg 1995
【非特許文献３】A.Joux,R.Lercier“Discrete Logarithm in GF(p)”Apr.17 2001，NMBRTHRY Mailing Listhttp://www.medicis.polytech.fr/〜lericier/francais/dlog.html
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記非特許文献２は、上記非特許文献１で示された数体ふるい法を初めて実装した例を報告している。上記非特許文献３では、一般の１２０桁の素数に対して、５２５ＭＨｚのＣＰＵを備えた１台のＰＣを使って７２日間かけて離散対数計算に成功した例が報告されており、２００５年６月現在世界最高記録である。
【０００７】
数体ふるい法は、（１）多項式選択、（２）ふるい処理、（３）線形代数処理及び（４）離散対数計算の処理から構成されており、その中でも、ふるい処理に多くの時間がかかることがわかっている。例えば、上記非特許文献３では、１２０桁のｐに対する離散対数を計算するために５２５ＭＨｚのマシンを使って、約７２日間かけているが、ふるい処理には約４０日の時間を要している。
【０００８】
ここで、複数の離散対数を計算しようとすると、複数回の数体ふるい法の処理が必要となる。そのため、数体ふるい法を高速に行なうためにはふるい処理にかかる時間を減らすことが要求される。
【０００９】
また、数体ふるい法を用いて正確な離散対数を計算するためには、複数回の数体ふるい法を処理する必要がある場合がある。数体ふるい法は、ｐ−１を割る素数冪ｑに対して、ｇｘ≡ｙ（ｍｏｄ  ｐ）を満たす整数ｘ  ｍｏｄ  ｑｉｅｉを計算する。したがって、正確な離散対数ｘを求めるためには、ｐ−１の素因数分解がｐ−１＝ｑ１ｅ１×ｑ２ｅ２×．．．ｑｎｅｎとなるときに、各ｑｉｅｉごとに、ｘ  ｍｏｄ  ｑを全て求める必要がある。上記特許文献２によれば、ｑｉの大きさが１０１２以下であれば、Pollig- Hellman方式の方がｘ  ｍｏｄ  ｑｉｅｉを短時間で計算できるという見積もりがあるため、全てのｑｉｅｉに対して数体ふるい法を用いる必要はない。しかしｐが大きい場合には、１０１２を超えるｑｉが複数現れる可能性も十分にありうるため、複数回数体ふるい法を適用する必要がある。
【００１０】
上記非特許文献２，３では、１０１２を超えるｑｉが一つしか出てこない特殊な場合のｐを扱っているため、同一のｐを用いて複数回数体ふるい法を行なうことについては説明されていない。
【００１１】
本発明の目的は、離散対数計算を計算する際に、複数回数体ふるい法を行う必要があるときにふるい処理の処理回数を減らし、効率的に複数の離散対数を解く離散対数演算装置、方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１２】
本発明による離散対数演算装置は、
数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算装置であって、
ｐ、ｑ、ｇ及びｙを保持する入力保持手段と、
数体ふるい法で用いる複数の多項式を生成する多項式生成手段と、
数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理手段と、
前記ふるい処理手段が生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持手段と、
数体ふるい法で用いられる指標を演算する指標演算手段と、
数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算手段と、
前記ふるい処理を行うか否かを制御する演算制御手段と、
を具え、
前記演算制御手段は、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持手段に格納されたｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持手段にて格納した整数の対（ａ，ｂ）を取得し、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持手段に格納し、前記多項式生成手段、前記ふるい処理手段、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力する演算制御手段と
を具えることを特徴とする。
【００１３】
本発明による離散対数演算方法は、
入力保持手段、多項式生成手段、ふるい処理手段、ふるいデータ保持手段、指標演算手段、対数演算手段、及び演算制御手段を備える離散対数演算装置にて、数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算方法であって、
前記ふるいデータ保持手段により、ｐ、ｑ、ｇ及びｙを保持する入力保持ステップと、
前記多項式生成手段により、数体ふるい法で用いる複数の多項式を生成する多項式生成ステップと
前記ふるい処理手段により、数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理ステップと、
前記ふるいデータ保持手段により、前記ふるい処理ステップにて生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持ステップと、
前記指標演算手段により、数体ふるい法で用いられる指標を演算する指標演算ステップと、
前記対数演算手段により、数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算ステップと、
前記演算制御手段により、前記ふるい処理を行うか否かを制御する演算制御ステップと、
を含み、
前記演算制御ステップは、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持ステップにて格納したｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップで格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップをにてｘ ｍｏｄ ｑを出力するステップを含むことを特徴とする。
【００１４】
本発明による離散対数演算プログラムは、
数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）、ｐ−１を割る素数べきｑ、ＧＦ（ｐ）の元ｇ及びｙから、ｇｘ＝ｙを満たすｘ ｍｏｄ ｑを出力する離散対数演算を実行する離散対数演算装置としてのコンピュータに、
ｐ、ｑ、ｇ及びｙを保持する入力保持ステップと、
数体ふるい法で用いる複数の多項式を生成する多項式生成ステップと、
数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）を生成するふるい処理ステップと、
前記ふるい処理ステップにて生成した複数の整数の対（ａ，ｂ）を格納するふるいデータ保持ステップと、
数体ふるい法で用いられる指標を演算する指標演算ステップと、
数体ふるい法の線形代数処理を演算し、ｘ ｍｏｄ ｑを出力する対数演算ステップと、
前記ふるい処理を行うか否かを制御する演算制御ステップと、
を実行させるためのプログラムであって、
演算制御ステップは、ｐ，ｑ，ｇ，ｙを取得し、取得したｐ及びｑと、前記入力保持ステップにて格納したｐ及びｑとが一致する条件が成立する場合には、前記ふるいデータ保持ステップにて格納した整数の対（ａ，ｂ）を取得し、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力し、
前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持ステップにて格納し、前記多項式生成ステップ、前記ふるい処理ステップ、前記指標演算ステップ及び前記対数演算ステップにてｘ ｍｏｄ ｑを出力するステップを含むことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、有限体上の離散対数を計算する数体ふるい法において、入力値のひとつであるｐが同一である複数個の離散対数を計算する場合に、ふるいデータの再利用をすることによって、ふるい処理の時間を削減し、効率的に行うことが可能となる。
【００１６】
ｐ，ｑが一致しているときに指標処理回数を減らすために、前記指標演算手段が演算した指標を複数保持する指標保持手段を更に具え、前記演算制御手段は、前記条件が成立する場合には、前記ふるいデータ保持手段にて格納した整数の対（ａ，ｂ）及び前記指標保持手段にて格納した指標を取得し、前記対数演算手段を用いてｘ ｍｏｄ ｑを出力し、前記条件が成立しない場合には、取得したｐ，ｑ，ｇ，ｙを前記入力保持手段に格納し、前記ふるい処理手段、前記指標演算手段及び前記対数演算手段を用いてｘ ｍｏｄ ｑを出力する。
【００１７】
ｐが一致している複数の入力に対して、ふるいの回数を減らすために、前記多項式生成手段が生成する多項式を保持する多項式保持手段を更に具え、前記条件は、前記演算制御手段が取得したｐと、前記入力保持手段に格納されたｐとが一致し、かつ、前記演算制御手段が取得したｑが前記多項式保持手段に格納された多項式の根を添加した有理数体上の拡大体において分岐しない条件とする。
【００１８】
複数の入力に対して、効率的にふるいデータを活用するために、多項式を設定することを可能にするには、複数の多項式を取得する多項式取得手段を更に具え、前記演算制御手段は、前記多項式取得手段が取得した多項式を前記多項式保持手段に格納し、前記多項式保持手段に格納された多項式のみを用いて数体ふるい法を行う。
【００１９】
複数の入力に対して、効率的にふるいデータを活用するための多項式設定に際し、ｐ−１を割る異なる素数冪ｑ（１），ｑ（２），・・・，ｑ（ｋ）を法とする複数の入力値に対して、複数の離散対数計算を行い、複数の（ｐ，ｑ（１），ｇ（１），ｙ（１）），（ｐ，ｑ（２），ｇ（２），ｙ（２）），．．．，（ｐ，ｑ（ｋ），ｇ（ｋ），ｙ（ｋ））を取得する手段と、ｑ（１），ｑ（２），．．．，ｑ（ｋ）が分岐しない有理体上の拡大体を定義する複数の規約多項式を生成する手段と、ｇ（ｉ）ｘ（ｉ）＝ｙ（ｉ）を満たすｘ（ｉ） ｍｏｄ ｑ（ｉ）を出力する手段とを更に具える。
【発明を実施するための最良の形態】
【００２０】
本発明による離散対数演算装置、方法及びプログラムの実施の形態を、図面を参照して詳細に説明する。以下、ｐを「位数」と呼ぶこともあれば、ｑを「法」と呼ぶこともある。
図１は、本発明による離散対数演算装置の実施の形態を示す図である。離散対数演算装置１は、数対ふるい法を利用して、有限体ＧＦ（ｐ）（ｐは素数又は素数べき）と、ｐ−１を割る素数べきｑと、ＧＦ（ｐ）の元ｇと、ｙとからｇｘ＝ｙを満たすｘ  ｍｏｄ  ｑを出力する装置である。離散対数演算装置１は、後に説明するように、可能な限り、ふるいデータを再利用することによって、ふるい処理時間を削減するものであり、入力保持投１１と、多項式生成段１２と、ふるい処理段１３と、ふるいデータ保持段１４と、指標演算段１５と、対数演算段１６と、演算制御段１７とを具える。
【００２１】
入力保持投１１は、入力で与えられるｐ、ｑ、ｇ及びｙを保持する。多項式生成段１２は、数体ふるい法で用いる複数の多項式を出力する。ふるい処理段１３は、数体ふるい法におけるふるい処理を行い、ふるい処理で特定された複数の整数の対（ａ，ｂ）（以下，「ふるいデータ」と呼ぶ。）を出力する。ふるいデータ保持段１４は、ふるい処理段１３によって出力されたふるいデータを全て格納する。指標演算段１５は、数体ふるい法で用いられる指標を演算する。対数演算段１６は、数体ふるい法の線形代数処理を演算し、ｘ  ｍｏｄ  ｑを出力する。
【００２２】
図２は、演算制御段の一例を示す図である。この場合、演算制御段１７は、入力ｐ，ｇ，ｑ，ｙを受信する入力受信部２１と、受信した入力に対して数体ふるいを制御する数体ふるい制御部２２と、演算によって特定されたｘ  ｍｏｄ  ｑを出力するデータ送信部２３を有する。
【００２３】
図３は、図１の離散対数演算装置の動作のフローチャートである。
本ルーチンでは、先ず、ステップＳ１において、演算制御段１７が、位数ｐ、法ｑ、ｇ及びｙを受信する。次いで、ステップＳ２において、演算制御段１７は、入力保持段１１を参照し、入力受信部２１が受信した位数ｐと入力保持段１１に格納された位数とが一致するか否か判定する。入力受信部２１が受信した位数ｐと、入力保持段１１に格納された位数とが一致する場合、演算制御段１７０は、入力保持段１１を参照し、入力受信部２１が受信した法ｑと入力保持段１１に格納された法とが一致しないか否かを判定する（ステップＳ３）。それに対して、入力受信部２１が受信した位数ｐと、入力保持段１１に格納された位数とが一致しない場合、演算制御段１７０は、ｐ，ｑ，ｇ，ｙを入力保持段１１に格納する（ステップＳ４）。
【００２４】
ステップＳ３において、入力受信部２１が受信した法ｑと入力保持段１１に格納された法とが一致しない場合、ステップＳ４に進み、それに対して、入力受信部２１が受信した法ｑと入力保持段１１に格納された法とが一致する場合、演算制御段１７は、入力保持段１１及びふるいデータ保持段１４を参照し、指標処理段１５及び対数演算段１６を利用してｘ  ｍｏｄ  ｑを出力する（ステップＳ５）。
【００２５】
ステップＳ４の後、演算制御段１７は、入力保持段１１を参照し、ｐ及びｑを多項式生成段１２に送信し、多項式生成段１２は、数体ふるい法で用いる複数の多項式を出力する（ステップＳ６）。次いで、演算制御段１７は、多項式生成段１２の生成した多項式をふるい処理手段１３に送信し、ふるい処理段１３は、複数のふるいデータを生成し、ふるいデータ保持段１４に格納する（ステップＳ７）。
【００２６】
図４は、本発明による離散対数演算装置の他の実施の形態を示す図である。以下では、説明を簡単にするために、ｐ、ｑが素数であることを前提とする。
離散対数演算装置１００は、入力保持段１０１と、素数導出段１０２と、素数保持段１０３と、多項式生成段１０４と、多項式保持段１０５と、Ｋα素イデアル生成段１０６と、Ｋα素イデアル保持段１０７と、ふるい処理段１０８と、ふるいデータ保持段１０９と、指標演算段１１０と、指標データ保持段１１１と、対数演算段１１２と、演算制御段１１３とを具える。
【００２７】
入力保持段１０１は、入力で与えられる位数ｐ、法ｑ、位数ｇ，ｙを保持する。素数導出段１０２は、ｇ及びｙを入力とし、ｙとｇのいずれかを割る素数を全て含む複数の素数を出力する。例えば、最大値Ｂ１を設定して、Ｂ１以下の全ての素数を出力する。素数保持段１０３は、素数導出段１０２の出力を全て保持する。素数保持段の一例を図５に示す。多項式生成段１０４は、ｐ及びｑを受信し、ｑが分岐しない有理数体上の拡大体Ｋαを生成する複素数αを根に持つ規約多項式ｆ（Ｘ）を算出し、式ｆ（ｍ）＝０（ｍｏｄ  ｐ）を満たす整数ｍを算出して、ｆ（Ｘ）及びＸ−ｍを出力する。
【００２８】
多項式保持段１０５は、多項式生成段１０４の出力を全て格納する。Ｋα素イデアル生成段１０６は、ｑ及び多項式式ｆ（ｘ）を入力とし、ｑを割る素イデアルを除いたＫαの素イデアル（Ｋα素イデアル）を複数出力する。例えば、最大値Ｂ２を設定して、ノルムがｑで割れず、かつ、Ｂ２以下の１次の素イデアルを全て出力する。Ｋα素イデアル保持段１０７は、Ｋαの素イデアルを複数保持する。例えば、ノルムの最大値Ｂを設定して、ノルムがＢ２以下の１次のＫα素イデアルを全て格納する。Ｋα素イデアル保持段の一例を図６に示す。各Ｋα素イデアルには、識別番号を付与している。
【００２９】
ふるい処理段１０８は、複数の素数と複数のＫα素イデアルを受信し、（１）Ｋαのイデアル（ａ＋ｂα）がＫα素イデアル保持段１０７に格納された素イデアルのみで割れ、（２）ａ＋ｂｍが素数保持段１０３に格納された素数のみで割れ、かつ、（３）ａとｂが互いに素である整数の対（ａ，ｂ）（ふるいデータ）を、（受信した素数の数Ｎ１）＋（受信したＫα素イデアルの数Ｎ２）＋（ｆ（ｘ）の次数ｄ）−１個以上出力する。ふるいデータ保持段１０９は、ふるい処理段１０８によって出力されたふるいデータを全て格納する。
【００３０】
図７は、ふるいデータ保持段の一例を示す図である。各（ａ，ｂ）には、識別番号を付与している。また、あわせて、（ａ＋ｂｍ）の「素因数分解情報」と、（ａ＋ｂα）の素イデアル分解情報も付与されている。例えば、識別番号ｉのふるいデータ（ａｉ，ｂｉ）にする素因数分解情報は、式
ａｊ＋ｂｊｍ＝Πｐｊ＾{ｅｉ，ｊ}
（但し、ｐｊは、素数保持段に格納されている識別番号ｊの素数）
で表されるときの、ｅｉ，１，ｅｉ，２，．．．，ｅｉ，Ｎ１であり、素イデアル分解情報は
（ａｊ＋ｂｊα）＝ΠＰｊ＾{ｅ’ｉ，ｊ}
（但し、Ｐｊは、Ｋα素イデアル保持段１０７に格納されている識別番号ｊの素イデアル）で表されるときの、ｅ’ｉ，１，．．．，ｅ’ｉ，Ｎ２）である。
【００３１】
指標処理段１１０は、素数ｑ及び複数の整数の対（ａ，ｂ）を受信して、式
λ（ａ＋ｂα）＝（ａ＋ｂα）ε＝λ０（ａ，ｂ）ｑ＋λ１（ａ，ｂ）ｑα＋
・・・＋λｄ−１（ａ，ｂ）ｑαｄ−１  ｍｏｄ  ｒ２
を計算し、データ（ａ，ｂ，λ０（ａ，ｂ）ｒ，λ１（ａ，ｂ），λｄ−１（ａ，ｂ））（指標データ）を出力する。なお、λｉ（ａ，ｂ）（ｉは０以上ｄ−１以下）はｍｏｄ  ｒで一意に決まる。また、λ及びλｉは、以下の性質を有する（以下、上記性質をΛと表す。）。
λ（（ａ＋ｂα）（ａ’＋ｂ’α））＝λ（ａ＋ｂα）＋λ（ａ’＋ｂ’α）
λｉ（（ａ＋ｂα）（ａ’＋ｂ’α））＝λｉ（ａ＋ｂα）＋λｉ（ａ’＋ｂ’α）
【００３２】
指標データ保持段１１１は、指標処理段１１０が出力する指標データを全て保持する。指標データ保持段の一例を図８に示す。本例では、ふるいデータの識別番号ｉと（λ１（ａｉ＋ｂｉα），．．．，λｊ（ａｉ＋ｂｉα），．．．，λｄ−１（ａｉ＋ｂｉα））を結び付ける。対数演算段１１２は、複数のふるいデータ、それに対応する指標データ及びqを受信して、次の条件
(1)  ｇＳｙΠ（ａ＋ｂｍ）ｅ（ａ，ｂ）がある整数のｑ冪
(2)  Π（ａ＋ｂα）ｅ（ａ，ｂ）があるイデアルのｑ冪
(3)  λ（Π（ａ＋ｂα）ｅ（ａ，ｂ））＝０  ｍｏｄ  ｒ２
により、整数Ｓを計算し、ｘ≡−ｓ（ｍｏｄ  ｑ）を計算し、ｘ  ｍｏｄ  ｑを出力する。
【００３３】
図９は、ｘ  ｍｏｄ  ｑの算出例のフローチャートである。本ルーチンでは、先ず、ステップＳ１１において、１以上（Ｎ１＋Ｎ２＋ｄ−１）以下の各ｉについて、識別番号ｉのふるいデータ及び指標データから、図１０に示すベクトルｖ（ｉ）を作成する。次いで、ステップＳ１２において、ｇとｙとを素因数分解し、図１１に示すベクトルｖ（ｇ），ｖ（ｙ）を作成する。次いで、ステップＳ１３において、ベクトルｖ（ｇ）及びｖ（ｉ）を利用し、図１２に示す行列Ａを作成する。
【００３４】
次いで、ステップＳ１４において、行列の方程式ｗＡ＝−ｖ（ｙ）（ｍｏｄ  ｑ）を解き、その解をｚとする。次いで、ステップＳ１５において、ｚの一番目の成分をＳとすると、ｘ＝−Ｓ  ｍｏｄ  ｑを出力する。
【００３５】
ｚ＝（ｅ（ｇ），ｅ（１），ｅ（２），．．．，ｅ（Ｎ１＋Ｎ２＋ｄ−１））とすると、次の条件が満たされている。
(1)’ｇｅ（ｇ）ｙΠ（ａｉ＋ｂｉｍ）ｅ（ｉ）がある整数のｑ冪
(2)’Π（ａｉ＋ｂｉα）ｅ（ｉ）があるＫαのイデアルのｑ冪
(3)’０以上ｄ−１以下の各ｊについてΣλｊ（ａｉ，ｂｉ）ｅ（ｉ）＝０  ｍｏｄ  ｑ
条件(3)’が条件(2)に一致していることは、性質Λから確認できる。
【００３６】
図１３は、演算制御段の一例を示す図である。演算制御段１１３は、入力受信部１２１と、数体ふるい制御部１２２と、データ送信部１２３とを有する。入力受信部１２１は、入力ｐ，ｇ，ｑ，ｙを受信する。数対ふるい制御部１２２は、受信した入力に対して、入力保持段１０１と、素数導出段１０２と、素数保持段１０３と、多項式生成段１０４と、多項式保持段１０５と、Ｋα素イデアル生成段１０６と、Ｋα素イデアル保持段１０７と、ふるい処理段１０８と、ふるいデータ保持段１０９と、指標演算段１１０と、指標データ保持段１１１と、対数演算段１１２とを制御する。データ送信部１２３は、演算によって特定されたｘ  ｍｏｄ  ｑを出力する。
【００３７】
図１４は、図４の離散対数演算装置の動作のフローチャートである。
本ルーチンでは、先ず、ステップＳ２１において、演算制御段１１３が位数ｐ、法ｑ、ｇ，ｙを受信する。次いで、ステップＳ２２において、演算制御段１１３は、入力保持段１０１を参照し、入力受信部１２１が受信した位数ｐと、入力保持段１０１に格納された位数とが一致するか否か判定する。
【００３８】
入力受信部１２１が受信した位数ｐと入力保持段１０１に格納された位数とが一致する場合、ステップＳ２３において、演算制御段１１３は、入力保持段１０１を参照し、入力受信部１２１が受信した法ｑと、入力保持段１０１に格納された法とが一致するか否か判定する。入力保持段１０１を参照し、入力受信部１２１が受信した法ｑと、入力保持段１０１に格納された法とが一致しない場合、ステップＳ２４において、演算制御段１１３は、多項式保持段１０５を参照し、入力受信部１２１が受信した法ｑが、多項式保持段１０５に格納された多項式の根を添加した有理数体上の拡大体において分岐するか否か判定する。
【００３９】
入力受信部１２１が受信した法ｑが、多項式保持段１０５に格納された多項式の根を添加した有理数体上の拡大体において分岐する場合、演算制御段１１３は、ｐ，ｑ，ｇ，ｙを入力保持段１０１に格納する（ステップＳ２５）。次いで、演算制御段１１３は、入力保持段１０１を参照して、ｇ，ｙを素数導出段１０２に送信し、素数導出段１０２は、ｇ，ｙのいずれかを割る素数を全て含んだ複数の素数を素数保持段１０３に格納する（ステップＳ２６）。
【００４０】
次いで、演算制御段１１３は、入力保持段１０１を参照して、ｐとｑを多項式生成段１０４に送信し、多項式生成段１０４は、規約多項式ｆ（Ｘ）及びＸ−ｍを生成し、多項式保持段１０５に格納する（ステップＳ２７）。次いで、演算制御段１１３は、入力保持段１０１及び多項式保持段１０５を参照して、ｆ（Ｘ）をＫα素イデアル生成段１０６に送信し、Ｋα素イデアル生成段１０６は、体Ｋαの素イデアルを複数生成し、Ｋα素イデアル保持段１０７に格納する（ステップＳ２８）。
【００４１】
次いで、演算制御段１１３は、入力保持段１０１、素数保持段１０３及びＫα素イデアル保持段１０７を参照して、素数保持段１０３に格納された素数の全てと、Ｋα素イデアル保持段１０７に格納されたＫα素イデアルの全てとを、ふるい処理段１０８に送信し、ふるい処理段１０８は、複数のふるいデータを生成し、これらふるいデータをふるいデータ保持段１０９に格納する（ステップＳ２９）。
【００４２】
次いで、演算制御段１１３は、入力保持段１０１及びふるいデータ保持段１０９を参照し、ふるいデータ保持段１０９に格納された全てのふるいデータを指標処理段１１０に送信し、指標処理段１１０は、複数の指標データを生成し、これら指標データを指標データ保持段１１１に格納する（ステップＳ３０）。次いで、演算制御段１１３は、入力保持段１０１及び指標データ保持段１１１を参照し、ｑ，ｇ，ｙを対数演算段１１２に送信し、対数演算段１１２は、ｘ  ｍｏｄ  ｑを演算制御段１１３に送信し（ステップＳ３１），演算制御段１１３は、ｘ  ｍｏｄ  ｑを出力する（ステップＳ３２）。
【００４３】
ステップＳ２２において、入力受信部１２１が受信した位数ｐと入力保持段１０１に格納された位数とが一致しない場合、ステップＳ２５に進む。ステップＳ２３において、入力受信部１２１が受信した法ｑと入力保持段１０１に格納された法とが一致する場合、及び、ステップＳ２４において、入力受信部１２１が受信した法ｑが、多項式保持段１０５に格納された多項式の根を添加した有理数体上の拡大体において分岐しない場合、ステップＳ３０に進む。
【００４４】
本実施の形態によれば、同一のｐ，ｑを含んだ異なる入力に対して、以前にふるい処理段が出力したふるいデータを再利用することによって、ふるい処理の軽減を図ることができる。また、同一のｐを含んだ異なる入力に対して、一定の条件がそろえば算出したふるいデータを再利用することが可能である。さらに、本実施の形態では、同一のｐ，ｑ，ｇを含んだ異なる入力に対して、対数処理段で生成した行列Ａも再利用することが可能であるため、効率的に複数の離散対数計算を行なうことが可能となる。
【００４５】
本発明を用いた例として、計算機上で動作プログラムが考えられる。図１５は、本発明を用いた計算機を示す図である。計算機２００は、入出力装置２０１、ＣＰＵ２０２、データメモリ２０３、プログラム格納媒体２０４及びデータ格納媒体２０５を具える。上記入力保持段１０１、素数保持段１０３、多項式保持段１０５、Ｋα素イデアル保持段１０７、ふるいデータ保持段１０９及び指標データ保持段１１１は、データ格納媒体２０５に格納されるファイルとして実現され、上記素数導出段１０２、多項式生成段１０４、Ｋα素イデアル生成段１０６、ふるい処理段１０８、指標処理段１１０、対数演算段１１２及び演算制御段１１３は、プログラム格納媒体２０４に格納される実行ファイルとして実現される。
【００４６】
本発明は、上記実施の形態に限定されるものではなく、幾多の変更及び変形が可能である。
【図面の簡単な説明】
【００４７】
【図１】本発明による離散対数演算装置の実施の形態を示す図である。
【図２】演算制御段の一例を示す図である。
【図３】図１の離散対数演算装置の動作のフローチャートである。
【図４】本発明による離散対数演算装置の他の実施の形態を示す図である。
【図５】素数保持段の一例を示す図である。
【図６】Ｋα素イデアル保持段の一例を示す図である。
【図７】ふるいデータ保持段の一例を示す図である。
【図８】指標データ保持段の一例を示す図である。
【図９】ｘ  ｍｏｄ  ｑの算出例のフローチャートである。
【図１０】ベクトルｖ（ｉ）の一例を示す図である。
【図１１】ベクトルｖ（ｇ）及びベクトルｖ（ｙ）の一例を示す図である。
【図１２】行列Ａの一例を示す図である。
【図１３】演算制御段の一例を示す図である。
【図１４】図４の離散対数演算装置の動作のフローチャートである。
【図１５】本発明を用いた計算機を示す図である。
【符号の説明】
【００４８】
１，１００  離散対数演算装置
１１，１０１  入力保持投
１２，１０４  多項式生成段
１３，１０８  ふるい処理段
１４，１０９  ふるいデータ保持段
１５，１１０  指標演算段
１６，１１２  対数演算段
１７  演算制御段
２１，１２１  入力受信部
２２，１２２  数体ふるい制御部
２３，１２３  データ送信部
１０２  素数導出段
１０３  素数保持段
１０５  多項式保持段
１０６  Ｋα素イデアル生成段
１０７  Ｋα素イデアル保持段
１１１  指標データ保持段
１１３  演算制御段
２００  計算機
２０１  入出力装置
２０２  ＣＰＵ
２０３  データメモリ
２０４  プログラム格納媒体
２０５  データ格納媒体
【図１】
0004663421.tif 000002
【図２】
0004663421.tif 000003
【図３】
0004663421.tif 000004
【図４】
0004663421.tif 000005
【図５】
0004663421.tif 000006
【図６】
0004663421.tif 000007
【図７】
0004663421.tif 000008
【図８】
0004663421.tif 000009
【図９】
0004663421.tif 000010
【図１０】
0004663421.tif 000011
【図１１】
0004663421.tif 000012
【図１２】
0004663421.tif 000013
【図１３】
0004663421.tif 000014
【図１４】
0004663421.tif 000015
【図１５】
0004663421.tif 000016