💬
AIと非可換NTRUを作ってみた
非可換置換多項式を使った簡易代数系の実験
最近、自作の非可換代数系を実装して、置換多項式の四則演算や逆元の挙動を試してみました。
この実験では、ベクトル係数を持つ多項式に対して置換作用を組み込み、非可換な演算環を作ることを目的としています。
1. 代数系の概要
-
係数環:
\(R = (\mathbb{F}_p)^N\) - 加法: ベクトルごとのmod p計算
- 乗法: Hadamard積または巡回畳み込みを利用
- 置換作用: 多項式の各係数ベクトルに $σ: ([0..N-1]\to[0..N-1]) $を作用
- 多項式:
$ f = \sum_{i=0}^{d-1} v_i \pi^i$
-
\(v_i \in R\) - π は置換作用（非可換性の原因）
性質
-
非可換環: πの作用により
\(f*g \neq g*f\) - 加法と乗法で閉じている
-
一部の条件下で除法（剰余）も定義可能
- 係数ベクトルにゼロを含まない場合、Hadamard逆元を使えば簡易的に剰余を計算可能
2. C言語での簡易実装例
非可換置換多項式の剰余計算と逆元
今日の実験で、非可換な置換多項式における剰余計算や逆元計算がうまく動いた条件を整理します。
1. 演算対象の限定
-
係数ベクトルに 0 を含まない元のみを使用
- 0 成分があると Hadamard 積の逆元が存在せず、割り算や剰余計算が無限ループになる。
- 以前は 0 を含むベクトルも対象にしていたため、剰余計算や逆元計算が成り立たなかった。
2. 置換作用の扱い
-
置換作用を統一的に適用
- 係数の逆元を計算する前に、置換を正しい順序で作用させる。
- これにより剰余計算のズレを最小化できる。
- 以前は処理の順序が不統一で、計算結果が一致せず破綻していた。
3. 演算の単純化
- Hadamard 積（要素ごとの掛け算） を使用
- 巡回畳み込みより計算が局所化され、逆元が存在すれば簡単に剰余計算可能。
- 以前は巡回畳み込みや複雑な置換作用を使っていたため、逆元が存在しても剰余計算が一致しなかった。
4. 今日成功した条件まとめ
| 条件 | 内容 |
|---|---|
| 対象集合 | 0 を含まないベクトルのみ |
| 積の演算 | Hadamard 積（要素ごとの掛け算） |
| 置換作用 | 統一的に適用 |
| 逆元計算の順序 | 置換作用後に逆元を計算 |
- これらの条件を満たすと、非可換置換多項式でも剰余計算や逆元計算が一貫して行える。
まとめ
- 剰余や逆元の成否は 対象集合と演算の定義・順序 に強く依存する。
- 今日の成功は「演算を変えた」のではなく、条件と順序を制約して一貫性を持たせたことによる。
- この条件を満たすことで、非可換置換多項式でも有限次の剰余計算が可能となる。
Discussion