関数フィールドふるい

Algorithm to solve the discrete logarithm problem

数学において、関数体ふるいは有限体における離散対数問題（DLP）を解く最も効率的なアルゴリズムの一つである。これは、ヒューリスティックな指数以下の計算量を持つ。Leonard Adlemanは1994年にこれを開発し^[1]、その後1999年にMD Huangと共同で改良を加えた^[2]。それ以前の研究としては、D. Coppersmithによる標数2の体におけるDLPに関する研究^{[3]がある。}

有限体における離散対数問題は、 、 素数、整数 について方程式を解くことから成ります。固定された に対する関数は、暗号技術で使用される一方向性関数です。Diffie -Hellman鍵交換、El Gamal暗号システム、デジタル署名アルゴリズムなど、いくつかの暗号手法はDLPに基づいています。 ${\displaystyle a^{x}=b}$ ${\displaystyle a,b\in \mathbb {F} _{p^{n}}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}$ ${\displaystyle x\in \mathbb {N} }$

数論的背景

機能フィールド

を有限体 上の代数曲線を定義する多項式とする。関数体 は、アフィン座標環 の分数体と見なすことができ、 はによって生成されるイデアルを表す。これは代数関数体の特殊な場合である。これは有限体 上に定義され、超越次数は1である。超越元は で表される。 ${\displaystyle C(x,y)}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle \mathbb {F} _{p}[x,y]/(C(x,y))}$ ${\displaystyle (C(x,y))}$ ${\displaystyle C(x,y)}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle x}$

関数体における付値環と場所の同値類の間、および付値環と付値の同値類の間には一対一対応が存在する。^[4]この対応は関数体ふるいアルゴリズムで頻繁に使用される。

約数

関数体 の離散値、すなわち離散値環 は、関数体の素数と呼ばれる唯一の最大イデアルを持ちます。 の次数は であり、 も定義します。 ${\displaystyle K/\mathbb {F} _{p}}$ ${\displaystyle \mathbb {F} _{p}\subset O\subset K}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle deg(P)=[O/P:\mathbb {F} _{p}]}$ ${\displaystyle f_{O}=[O/P:\mathbb {F} _{p}]}$

約数はすべての素数上の -線型結合であるため、となり、和の有限個の元のみが非ゼロとなります。 元の約数はと定義されます。ここでは素数 に対応する付値です。約数の次数は です。 ${\displaystyle \mathbb {Z} }$ ${\textstyle d=\sum \alpha _{P}P}$ ${\displaystyle \alpha _{P}\in \mathbb {Z} }$ ${\displaystyle x\in K}$ ${\textstyle {\text{div}}(x)=\sum v_{P}(x)P}$ ${\displaystyle v_{P}}$ ${\displaystyle P}$ ${\textstyle \deg(d)=\sum \alpha _{P}\deg(P)}$

方法

関数体ふるいアルゴリズムは、小さい次数の既約多項式の離散対数を求める事前計算と、それらを の対数に結合する簡約ステップで構成されます。 ${\displaystyle b}$

ある境界よりも小さい次数の既約関数に分解される関数は、 -滑らかな関数と呼ばれます。これは滑らかな数の定義に類似しており、そのような関数は分解が比較的速く求められるため有用です。これらの関数の集合は因子基底と呼ばれます。関数のペアが二重に滑らかな場合、およびは上のの元のノルム、は何らかのパラメータ、は の関数体の元として見なされます 。 ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle S=\{g(x)\in \mathbb {F} _{p}[x]\mid {\text{ irreductible with }}\deg(g)<B\}}$ ${\displaystyle (r,s)}$ ${\displaystyle rm+s}$ ${\displaystyle N(ry+s)}$ ${\displaystyle N(\cdot ,\cdot )}$ ${\displaystyle K}$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle m\in \mathbb {F} _{p}[x]}$ ${\displaystyle ry+s}$ ${\displaystyle C}$

アルゴリズムのふるい分けステップは、二重に滑らかな関数のペアを見つけることです。次のステップでは、それらを用いて、分解された関数の対数を含む線形関係を求めます。線形連立方程式を解くことで、対数を計算します。縮約ステップでは、先に求めた対数の組み合わせとして表現し、DLPを解きます。 ${\displaystyle \log _{a}(b)}$

事前計算

パラメータ選択

このアルゴリズムには、次数 の既約関数、関数、および となる次数 の曲線というパラメータが必要です。ここで、 は基底体 の位数におけるべき乗です。は で定義される関数体を表します。 ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle m\in \mathbb {F} _{p}[x]}$ ${\displaystyle C(x,y)}$ ${\displaystyle d}$ ${\displaystyle C(x,m)\equiv 0{\text{ mod }}f}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle K}$ ${\displaystyle C}$

これにより、同型性と準同型性が導かれます。同型性を使用すると、 の各要素はの多項式として考えることができます。 ${\displaystyle \mathbb {F} _{p^{n}}\simeq \mathbb {F} _{p}[x]/f}$ $${\displaystyle \phi :\mathbb {F} _{p}[x,y]/C\to \mathbb {F} _{p}[x]/f,y\mapsto m.}$$ ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle \mathbb {F} _{p}[x]/f}$

また、因子基数の滑らかさの境界を設定する必要もあります。 ${\displaystyle B}$ ${\displaystyle S}$

ふるい分け

このステップでは、二重に滑らかな関数のペアが見つかります。 ${\displaystyle (r,s)\in \mathbb {F} _{p}[x]\times \mathbb {F} _{p}[x]}$

の形をした関数を考え、任意の で可能な限り何度も割ります。この過程で 1 に約分されるものはどれも-滑らかです。これを実装するために、グレイコードを用いることで、与えられた多項式の倍数を効率的に処理することができます。 ${\displaystyle f=(rm+s)N(ry+s)}$ ${\displaystyle f}$ ${\displaystyle g\in S}$ ${\displaystyle f}$ ${\displaystyle B}$

これは、数体ふるいや指数計算アルゴリズムといった他のふるい分けアルゴリズムにおけるふるい分けステップと完全に類似しています。数値の代わりに関数を用いてふるい分けを行いますが、数値が素数に因数分解できるのと同様に、これらの関数も既約多項式に因数分解できます。 ${\displaystyle \mathbb {F} _{p}[x]}$

線形関係を見つける

これはアルゴリズムの中で最も難しい部分であり、上で定義した関数体、位数、および因子が関係します。目標は、二重滑らかな関数のペアを用いて、因数底の元の離散対数を含む線形関係を見つけることです。

因子基底の各既約関数に対して、その上にある の位と、それらの位に対応する代理関数を求める。位に対応する代理関数はを満たす。ここでは の類数であり、は を満たす任意の固定離散値である。このように定義された関数は、 における定数を除いて一意である 。 ${\displaystyle v_{1},v_{2},...}$ ${\displaystyle K}$ ${\displaystyle \alpha _{1},\alpha _{2},...}$ ${\displaystyle \alpha _{i}\in K}$ ${\displaystyle v_{i}}$ ${\displaystyle {\text{div}}(\alpha _{i})=h(v_{i}-f_{v_{i}}u)}$ ${\displaystyle h}$ ${\displaystyle K}$ ${\displaystyle u}$ ${\displaystyle f_{u}=1}$ ${\displaystyle \mathbb {F} _{p}}$

の約数の定義により、これと という事実を用いると、次の式が得られます。 ${\textstyle {\text{div}}(ry+s)=\sum a_{i}v_{i}}$ ${\displaystyle a_{i}=v_{i}(ry+s)}$ ${\textstyle \sum a_{i}f_{v_{i}}=\deg({\text{div}}(ry+s))=0}$

${\displaystyle {\text{div}}((ry+s)^{h})=\sum ha_{i}v_{i}=\sum ha_{i}v_{i}-\sum ha_{i}f_{v_{i}}v+hv\sum a_{i}f_{v_{i}}=\sum a_{i}h(v_{i}-f_{v_{i}}v))={\text{div}}(\prod \alpha _{i}^{a_{i}})}$

ここでは任意の値である。そして、代理関数の約数が定数を除いて一意であるという事実を用いて、次を得る。 ${\displaystyle v}$ ${\displaystyle f_{v}=1}$

${\displaystyle (ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}{\text{ for some }}c\in F_{p}^{*}}$

${\displaystyle \implies \phi ((ry+s)^{h})=\phi (c)\prod \phi (\alpha _{i})^{a_{i}}}$

ここで、この式を既約多項式に分解する既知の事実と、この分解におけるのべき乗を とします。すると、 ${\displaystyle \phi (ry+s)=rm+s}$ ${\displaystyle e_{g}}$ ${\displaystyle g\in S}$

${\displaystyle \prod _{g\in S}g^{he_{g}}\equiv \phi (c)\prod \phi (\alpha _{i})^{a_{i}}{\text{ mod }}f}$

ここで、方程式の離散対数を単位まで取ることができます。これは制限離散対数と呼ばれます。これは、ある単位 に対する方程式によって定義されます。 ${\displaystyle \log _{*}(x)}$ ${\displaystyle a^{\log _{*}(x)}=ux}$ ${\displaystyle u\in \mathbb {F} _{p}}$

${\displaystyle \sum _{g\in S}e_{g}\log _{*}g\equiv \sum a_{i}h_{1}\log _{*}(\phi (\alpha _{i})){\text{ mod }}(p^{n}-1)/(p-1),}$

ここで、は を法とする逆数です。 ${\displaystyle h_{1}}$ ${\displaystyle h}$ ${\displaystyle (p^{n}-1)/(p-1)}$

式と対数は未知です。この形式の方程式が十分に見つかれば、線形連立方程式を解いてすべてのについて を求めることができます。式全体を未知数とすることで、 、 、 を計算する必要がなくなるため、時間を節約できます。最終的には、 それぞれについて、制限された離散対数に対応する単位を計算し、 を得ることができます。 ${\displaystyle h_{1}\log _{*}(\phi (\alpha _{i}))}$ ${\displaystyle \log _{*}(g)}$ ${\displaystyle \log _{*}(g)}$ ${\displaystyle g\in S}$ ${\displaystyle h_{1}log_{*}(\phi (\alpha _{i}))}$ ${\displaystyle h}$ ${\displaystyle h_{1}}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \phi (\alpha _{i})}$ ${\displaystyle g\in S}$ ${\displaystyle \log _{a}(g)=\log _{*}(g)-\log _{a}(u)}$

削減ステップ

まず、 ランダムな に対してmodを計算します。十分に高い確率でこれは-滑らかなので、 について のように因数分解できます。これらの多項式はそれぞれ、コッパースミス法の一般化を用いて、より次数の低い多項式に簡約できます。^{[2] -}滑らかな多項式の積が得られるまで次数を簡約できます。次に、 を底とする対数をとると、最終的に次のように計算できます。 ${\displaystyle a^{l}b}$ ${\displaystyle f}$ ${\displaystyle l<n}$ ${\displaystyle {\sqrt {nB}}}$ ${\displaystyle a^{l}b=\prod b_{i}}$ ${\displaystyle b_{i}\in \mathbb {F} _{p}[x]}$ ${\displaystyle \deg(b_{i})<{\sqrt {nB}}}$ ${\displaystyle b_{i}}$ ${\displaystyle B}$ ${\displaystyle a}$

${\displaystyle \log _{a}(b)=\sum _{g_{i}\in S}\log _{a}(g_{i})-l}$、DLP を解決します。

複雑

関数体ふるいは、指数関数以下の時間で実行されると考えられている。

${\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {32}{9}}}+o(1)\right)(\ln p)^{\frac {1}{3}}(\ln \ln p)^{\frac {2}{3}}\right)=L_{p}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {32}{9}}}\right]}$

L記法を用いて。この複雑さはいくつかの経験的仮定に依存しているため、厳密な証明は存在しない。例えば、ふるい分けのステップでは、 という形式の数は与えられた範囲内で乱数のように振舞うと仮定する。 ${\displaystyle (rm+s)N(ry+s)}$

他の方法との比較

離散対数問題を指数時間未満で解くアルゴリズムとして、他に2つのよく知られたアルゴリズムがあります。指数計算アルゴリズムと数体ふるいの一種です。^{[5]どちらも最も簡単な形では素数位数の}有限体におけるDLPを解きますが、同様にDLPを解くように拡張することもできます。 ${\displaystyle \mathbb {F} _{p^{n}}}$

におけるDLPの数体ふるいの計算量は^[6]であり、関数体ふるいの最高性能よりもわずかに遅い。しかし、の場合には関数体ふるいよりも高速である。数体と関数体を扱う2つの類似したアルゴリズムが存在することは驚くべきことではない。実際、これら2種類のグローバル体の間には広範な類似性がある。 ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle L_{p}[1/3,(64/9)^{1/3}+o(1)]}$ ${\displaystyle n<<(\log(p))^{1/2}}$

指数計算アルゴリズムは、高度な代数構造を必要としないため、関数体ふるいや数体ふるいよりもはるかに簡単に記述できます。計算量は で、漸近的に遅くなります。数体ふるいや関数体ふるいが高速である主な理由は、これらのアルゴリズムはより小さな平滑性境界 で実行できるため、ほとんどの計算をより小さな数値で実行できることです。 ${\displaystyle L_{p}[1/2,{\sqrt {2}}]}$ ${\displaystyle B}$

参照

• 代数関数体
• 数体ふるい
• 指数計算アルゴリズム

参考文献

1. L. Adleman. 「関数体ふるい」. アルゴリズム的数論（ANTS-I）. コンピュータサイエンス講義ノート. Springer (1994), pp.108-121.
2. L. Adleman, MD Huang. 「有限体上の離散対数に対する関数体ふるい法」In: Inf. Comput. 151 (1999年5月), pp. 5-16. DOI: 10.1006/inco.1998.2761.
3. D. Coppersmith. (1984), 「特性2の体における離散対数の高速評価」IEEE Trans. Inform. Theory IT-39 (1984), pp. 587-594.
4. M. FriedとM. Jarden. 「Field Arithmetic」第11巻（2005年1月）第2章1節。DOI: 10.1007/b138352。
5. D. Gordon. 「数体ふるいを用いたGF(P)における離散対数」. Siam Journal on Discrete Mathematics - SIAMDM 6 (1993年2月), pp. 124-138. DOI: 10.1137/0406010.
6. R. Barbulescu, P. Gaudry, T. Kleinjung. 「タワー数体ふるい」. Advances in Cryptology – Asiacrypt 2015. Vol. 9453. Springer, 2015年5月. pp. 31-58

Retrieved from "https://en.wikipedia.org/w/index.php?title=Function_field_sieve&oldid=1310386710"