ツェッヒの対数

ツェッヒ対数は、要素が生成元の累乗として表されるときに、有限体での加算を実装するために使用されます。 ${\displaystyle \alpha}$

ツェッヒ対数はジュリアス・ツェッヒにちなんで名付けられ、^{[1] [2] [3] [4]}、また数論的研究に使用したカール・G・J・ヤコビにちなんでヤコビ対数[ ^5]とも呼ばれる。^[6]

有限体の原始元 が与えられたとき、その底に対するツェッヒ対数は次式で定義される。 ${\displaystyle \alpha}$${\displaystyle \alpha}$

${\displaystyle \alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},}$

これは次のように書き直されることが多い。

${\displaystyle Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).}$

文脈から明らかな場合は、通常、表記から 基数の選択は省略されます。${\displaystyle \alpha }$

より正確には、はの乗法順序を法とする整数の関数であり、同じ集合内の値を取る。すべての要素を記述するために、定義とともに 新しい記号 を正式に追加すると便利である。${\displaystyle Z_{\alpha }}$ ${\displaystyle \alpha }$${\displaystyle -\infty }$

${\displaystyle \alpha ^{-\infty }=0}$

${\displaystyle n+(-\infty )=-\infty }$

${\displaystyle Z_{\alpha }(-\infty )=0}$

${\displaystyle Z_{\alpha }(e)=-\infty }$

ここで はを満たす整数であり、つまり という特性2の体に対してはであり、 という元を持つ奇数の特性を持つ体に対しては である。 ${\displaystyle e}$${\displaystyle \alpha ^{e}=-1}$${\displaystyle e=0}$${\displaystyle e={\frac {q-1}{2}}}$${\displaystyle q}$

ツェッヒ対数を使用すると、指数表現で有限体演算を行うことができます。

${\displaystyle \alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{n-m})=\alpha ^{m}\cdot \alpha ^{Z(n-m)}=\alpha ^{m+Z(n-m)}}$

${\displaystyle -\alpha ^{n}=(-1)\cdot \alpha ^{n}=\alpha ^{e}\cdot \alpha ^{n}=\alpha ^{e+n}}$

${\displaystyle \alpha ^{m}-\alpha ^{n}=\alpha ^{m}+(-\alpha ^{n})=\alpha ^{m+Z(e+n-m)}}$

${\displaystyle \alpha ^{m}\cdot \alpha ^{n}=\alpha ^{m+n}}$

${\displaystyle \left(\alpha ^{m}\right)^{-1}=\alpha ^{-m}}$

${\displaystyle \alpha ^{m}/\alpha ^{n}=\alpha ^{m}\cdot \left(\alpha ^{n}\right)^{-1}=\alpha ^{m-n}}$

これらの式は、 の減算が未定義であるという注意点を除けば、記号 の慣例に従って当てはまります。特に、加算式と減算式は特別なケースとして扱う必要があります。 ${\displaystyle -\infty }$${\displaystyle -\infty }$${\displaystyle m=-\infty }$

これは、を満たす別の記号と、必要に応じて他の規則を 導入することで、射影直線の算術に拡張できます。${\displaystyle +\infty }$${\displaystyle \alpha ^{+\infty }=\infty }$

特性2の体の場合、

${\displaystyle Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n}$。

十分に小さい有限体の場合、ツェッヒ対数表を使用すると、少数の整数加算/減算と表参照によって、すべての有限体演算を特に効率的に実装できます。

この方法の有用性は、テーブルを効率的に保存できない大きなフィールドでは低下します。また、この方法は、有限フィールドで非常に少ない操作を実行する場合にも非効率的です。これは、実際の計算よりもテーブルの計算に多くの時間がかかるためです。

α ∈ GF(2 ³ )を原始多項式x ³ + x ² + 1の根とします。この体の元の従来の表現は、α の次数2 以下 の多項式です。

この体のツェッヒ対数の表は、 Z (−∞) = 0、Z (0) = −∞、Z (1) = 5、Z (2) = 3、Z (3) = 2、Z (4) = 6、Z (5) = 1、Z (6) = 4です。 αの乗法次数は7 なので、指数表現は 7 を法とする整数で機能します。

α はx ³ + x ² + 1の根なので、 α ³ + α ² + 1 = 0となります。または、すべての係数が GF(2) にあることを思い出すと、減算は加算と同じであり、α ³ = α ² + 1となります。

指数表現から多項式表現への変換は次のように表される。

${\displaystyle \alpha ^{3}=\alpha ^{2}+1}$（上記の通り）

${\displaystyle \alpha ^{4}=\alpha ^{3}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha =\alpha ^{2}+\alpha +1}$

${\displaystyle \alpha ^{5}=\alpha ^{4}\alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2}+\alpha =\alpha +1}$

${\displaystyle \alpha ^{6}=\alpha ^{5}\alpha =(\alpha +1)\alpha =\alpha ^{2}+\alpha }$

Zech 対数を使用してα ⁶ + α ³を計算する：

${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},}$

あるいは、より効率的には、

${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},}$

これを多項式表現で検証します。

${\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.}$

• ガウス対数
• アイルランド対数、パーシー・ラドゲートが経験的に導き出した同様の手法
• 有限体演算
• 対数表

• フレッチャー、アラン;ミラー、ジェフリー・チャールズ・パーシー;ローゼンヘッド、ルイス(1946) [1943].数学表索引(第1版). Blackwell Scientific Publications Ltd.、オックスフォード/マグロウヒル、ニューヨーク。
• Conway, John Horton (1968)。Churchhouse, Robert F.、Herz, J.-C. (編)。「有限体に関するいくつかの情報の表」。Computers in Mathematical Research。アムステルダム: North-Holland Publishing Company : 37–50。MR  0237467。
• Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). 「アルゴリズム 469: 有限体上の演算 [A1]」. Communications of the ACM . Collected Algorithms of the ACM (CALGO). 16 (11). Association for Computing Machinery (ACM): 699. doi : 10.1145/355611.362544 . ISSN  0001-0782. S2CID  62794130. toms/469.[1] [2] [3]
• キューン、クラウス (2008)。 「CF Gauß und die Logarithmen」(PDF) (ドイツ語)。アリング・ビブルク、ドイツ。2018 年 7 月 14 日にオリジナルからアーカイブ(PDF)されました。2018年7月14日に取得。