機能フィールドふるい

このアルゴリズムには、以下のパラメータが必要です：既約関数${\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]}$発見されました。

関数の形式を考える${\displaystyle f=(rm+s)N(ry+s)}$、次に分割します${\displaystyle f}$いかなる${\displaystyle g\in S}$可能な限り何度も。${\displaystyle f}$この過程で1に縮小されるのは${\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{ はある }}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}$

ここでは、方程式の離散対数を1まで取ることができます。これは制限付き離散対数と呼ばれます。${\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)}$。