🔢 mathematics

Inverses of six classes of permutation polynomials of the form $x+\gamma\operatorname{Tr}_q^{q^2}(h(x))$ over finite fields of even characteristic

この論文は、有限体 $\mathbb{F}_{q^2}$ （ $q=2^n$ ）上の多項式 $x+\gamma\operatorname{Tr}_q^{q^2}(h(x))$ の形を持つ6 種類の置換多項式について、その合成逆多項式を導出したものである。

原著者： Rajesh P. Singh, Dinesh Kumar, Jitendra Prakash

公開日 2026-04-22

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Rajesh P. Singh, Dinesh Kumar, Jitendra Prakash

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🗝️ 1. 物語の舞台：「魔法の箱」と「並べ替え」

まず、**「有限体（Finite Fields）」**というものを想像してください。これは、数字が無限に続くのではなく、決まった数（例えば 0 から 9 まで）しか存在しない、小さな「数字の箱」です。

この箱の中で、ある「魔法のルール（多項式）」を使って、箱の中の数字をすべて入れ替えることができます。

例：「1」を「5」に、「2」を「3」に……というように。
このルールが**「置換多項式（Permutation Polynomial）」**です。

重要なのは、このルールが「一対一」であること。
つまり、どの数字も必ず別の数字に変わりますが、**「元の数字に戻せる」**という性質を持っています。もし戻せなければ、それはただの「ごちゃ混ぜ」になってしまい、暗号として使えません。

🔓 2. 研究者たちが挑んだ課題：「逆鍵」の作成

この論文の著者たち（ラジェシュ・シン氏ら）は、Jiang 氏らが最近見つけた**「6 つの新しい魔法のルール（6 種類の多項式）」**に注目しました。

問題点：
新しい「並べ替えのルール（鍵）」を見つけるのは比較的簡単ですが、**「そのルールを元に戻すための『逆鍵（合成逆関数）』を見つけること」**は、非常に難しいパズルです。
- 例え話：「複雑なパズルを解いて箱を閉めるのは簡単でも、その箱をまた開けるための『正しい手順』を紙に書き起こすのは、とても大変だ」という感じです。
- 従来の方法だと、逆鍵を見つけるために膨大な計算が必要で、実用的な暗号（AES などのセキュリティ技術）に応用するのが難しかったのです。
この論文の成果：
著者たちは、この「6 つの新しいルール」すべてに対して、「逆鍵（元に戻す式）」をシンプルで明確な形で見つけ出し、公式として発表しました。

🛠️ 3. 使われた「魔法の道具」：トレース関数

彼らが使った主な道具は**「トレース関数（Trace Function）」というものです。
これを「数字の圧縮機」**と想像してみてください。

大きな箱（ $F_{q^2}$ ）の中の複雑な数字を、小さな箱（ $F_q$ ）の中に「圧縮」して持ち出す役割を果たします。
論文のルールは、**「元の数字（ $x$ ）」に「圧縮された数字（$Tr(x)$）を少し足したり掛けたりした形」**でできています。

著者たちは、この「圧縮機」の仕組みを巧みに利用して、**「圧縮された数字から、元の数字をどうやって復元するか」**という手順を、数学的に完璧に導き出しました。

🎯 4. なぜこれが重要なのか？（実生活への応用）

「数学の難しい式」がなぜ大切なのか？それは**「セキュリティ」**に関係しているからです。

暗号の世界：
銀行の送金や、スマホの通信を安全にする「暗号化」では、情報を「並べ替える（暗号化する）」ことと、「元に戻す（復号する）」ことの両方が必要です。
効率化：
この論文で見つかった「逆鍵」の式は、計算が非常に簡単で速く実行できます。
- 以前： 逆鍵を見つけるのに、スーパーコンピューターでも時間がかかるような複雑な計算が必要だった。
- 今回： 「 $x$ に $A$ を足して、 $B$ を掛ける」といった、スマホでも瞬時に計算できるシンプルな式が見つかった。

これにより、**「より安全で、かつ動作が軽い新しい暗号システム」**を作れる可能性が広がりました。

📝 まとめ

この論文を一言で言うと、以下のようになります。

「最近発見された、6 つの新しい『数字の並べ替えルール』に対して、その『元に戻すための簡単な手順（逆鍵）』をすべて見つけ出し、公式として完成させた研究です。」

彼らは、複雑な数学のパズルを解くことで、将来のセキュリティ技術の基盤となる「便利な道具」を世に送り出したのです。

論文「Inverses of six classes of permutation polynomials of the form x+γ Trq2q (h(x)) over finite fields of even characteristic」の技術的サマリー

1. 概要と背景

本論文は、有限体（特に偶数標数 $q=2^m$ の場合）における**置換多項式（Permutation Polynomials: PP）の合成逆多項式（Compositional Inverse）**の explicit な構成に関する研究である。
置換多項式は、有限体上の全単射写像を多項式で表現したものであり、ブロック暗号（AES など）、公開鍵暗号、符号理論において重要な役割を果たす。これらの応用では、暗号化（置換多項式）だけでなく、復号化（その合成逆）の効率的な計算も不可欠である。

近年、江ら（Jiang et al. [21]）によって、形式 $f(x) = x + \gamma \text{Tr}_{q^2}^q(h(x))$ を持つ置換多項式のいくつかのクラスが提案された。しかし、これらの多項式の合成逆を具体的に求めることは、ラグランジュ補間公式を用いると計算量が膨大になり、代数的構造が不明瞭になるため、困難な問題とされてきた。

本論文の目的は、江らが特定した 6 つのクラスについて、その合成逆多項式を明示的に導出することである。

2. 問題設定

対象とする有限体は $F_{q^2}$ （ $q=2^m$ ）であり、以下の形式を持つ多項式 $f(x)$ の合成逆 $g(x)$ （ $f(g(x)) = g(f(x)) = x$ ）を求める。
$f(x) = x + \gamma \text{Tr}_{q^2}^q(h(x))$
ここで、 $\text{Tr}_{q^2}^q$ は $F_{q^2}$ から $F_q$ へのトレース写像、 $\gamma \in F_{q^2}$ 、 $h(x)$ は特定の多項式である。

論文で扱われる 6 つのクラスは以下の通り（江ら [21] の結果に基づく）：

$f_1(x) = x + \gamma \text{Tr}_{q^2}^q(x^3 + x^{q+2})$
$f_2(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^2 + x^3 + x^{q+2})$
$f_3(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^3 + x^{q+2})$
$f_4(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^3 + x^{q+2})$
$f_5(x) = x + \gamma \text{Tr}_{q^2}^q(x + x^{q+2})$ （ $m$ が奇数、 $\gamma \in F_{2^2} \setminus \{1\}$ ）
$f_6(x) = x + \gamma \text{Tr}_{q^2}^q(x^2 + x^{q+2})$ （ $m$ が奇数、 $\gamma \in F_{2^2} \setminus \{1\}$ ）

3. 手法と主要な補助定理

逆多項式を導出するために、以下の補助定理と手法が用いられている。

3.1. 線形化多項式と基底の性質

$F_{q^2}$ 上の線形化多項式 $L(x) = \text{Tr}_{q^2}^q(\beta x) + \alpha \text{Tr}_{q^2}^q(\delta x)$ を考える。ここで $\alpha \in F_{q^2} \setminus F_q$ かつ $\text{Tr}_{q^2}^q(\alpha)=1$ とする。
補題 2.3において、 $\beta, \delta$ が $F_q^*$ の定数倍で関係しない場合、この $L(x)$ は置換多項式となり、その逆 $L^{-1}(x)$ が明示的に与えられることが示されている。
$L^{-1}(x) = (\beta\delta^q + \delta\beta^q)^{-1} \{ \delta^q \text{Tr}_{q^2}^q((1+\alpha)x) + \beta^q \text{Tr}_{q^2}^q(x) \}$

3.2. 変換を用いた解法（Conjugation Method）

各定理の証明では、以下の戦略が採られている：

補助定理 2.3 で得られた置換多項式 $T(x)$ （または $U(x)$ ）を導入する。
合成写像 $f \circ T(x)$ を計算し、その構造を単純化する。
方程式 $f(T(x)) = T(y)$ を解くことで、 $T^{-1} \circ f^{-1} \circ T (y)$ を求める。
これを $y = T^{-1}(x)$ に代入し、さらに $T$ と合成することで $f^{-1}(x)$ を得る。

この過程で、補題 2.4（ $T^{-1}$ を用いたトレースの性質）が頻繁に利用され、複雑な項を $\text{Tr}_{q^2}^q(x)$ や $\text{Tr}_{q^2}^q((1+\alpha)x)$ の形に整理する。

3.3. 冪乗の逆元

$m$ が奇数の場合、 $x^3$ は $F_{2^m}$ 上の置換多項式となり、その逆は $x^t$ （ $3t \equiv 1 \pmod{2^m-1}$ ）となる（補題 2.1）。この性質が、 $h(x)$ に $x^3$ が含まれる場合の逆算に利用される。

4. 主要な結果（定理 3.1 ～ 3.6）

論文は、6 つのクラスそれぞれについて合成逆多項式を明示的に導出した。

定理 3.1 ( $f_1$ の逆):
$\gamma \in F_q$ の場合、逆は $x + \gamma (\text{Tr}_{q^2}^q(x))^3$ となる。
定理 3.2 ( $f_2$ の逆):
$\gamma \in F_q$ の場合、逆は $x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$ となる。
定理 3.3 ( $f_3$ の逆):
- $\gamma \in F_q$ の場合： $x + \gamma \text{Tr}_{q^2}^q(x) + \gamma (\text{Tr}_{q^2}^q(x))^3$
- $\text{Tr}_{q^2}^q(\gamma)=1$ かつ $m$ が奇数の場合： $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma (\text{Tr}_{q^2}^q(x))^t$ （ $3t \equiv 1 \pmod{2^m-1}$ ）
定理 3.4 ( $f_4$ の逆):
- $\gamma \in F_q$ の場合： $x + \gamma (\text{Tr}_{q^2}^q(x))^2 + \gamma (\text{Tr}_{q^2}^q(x))^3$
- $\text{Tr}_{q^2}^q(\gamma)=1$ かつ $m$ が奇数の場合： $\text{Tr}_{q^2}^q((1+\gamma)x) + \gamma [(\text{Tr}_{q^2}^q(x)+1)^t + 1]$
定理 3.5 ( $f_5$ の逆):
$m$ が奇数、 $\gamma \in F_{2^2} \setminus F_2$ の場合。逆多項式は $\text{Tr}_{q^2}^q((1+\gamma)x)$ と $\gamma$ を含む複雑な項の和で表され、その中に $t$ 乗（ $3t \equiv 1$ ）が含まれる。
定理 3.6 ( $f_6$ の逆):
$m$ が奇数、 $\gamma \in F_{2^2} \setminus F_2$ の場合。同様に、 $\text{Tr}_{q^2}^q((1+\gamma)x)$ と $\gamma$ を含む項の和で表される。

5. 意義と貢献

計算の効率化:
これらの逆多項式は、ラグランジュ補間による一般的な方法（ $O(q^2)$ の項を持つ多項式）とは異なり、トレース写像と低次の多項式の組み合わせで表現されている。これにより、暗号実装における逆変換の計算コストが劇的に低下する。
代数的構造の解明:
逆多項式が「 $x$ にトレース写像を適用したものの多項式」という簡潔な形を持つことが示された。これは、元の多項式の構造が逆変換においても保たれていることを意味し、理論的な理解を深める。
応用への寄与:
偶数標数の有限体は、AES などの現代暗号や誤り訂正符号で広く使用されている。本論文で得られた結果は、これらの分野における新しい置換多項式の設計や、既存の構造の安全性評価（逆関数の解析）に直接応用可能である。
手法の一般化:
補助多項式 $T(x)$ を用いた共役（conjugation）手法と、線形代数（行列操作）を組み合わせて逆を導く手法は、他の形式の置換多項式に対しても適用可能な汎用的なアプローチとして示唆されている。

6. 結論

本論文は、有限体 $F_{q^2}$ （ $q=2^m$ ）上の特定の形式を持つ 6 つの置換多項式クラスについて、その合成逆多項式を初めて明示的に導出した。導出された逆多項式は計算的に効率的であり、暗号理論および符号理論における実用的な価値が高い。特に、パラメータ $\gamma$ の条件（ $F_q$ に属するか、トレースが 1 かなど）に応じて逆の形がどのように変化するかを体系的に整理した点が重要である。