Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@fumumue

AIと代数系を作った（パート２）

Last updated at Posted at 2025-10-10

非可換置換多項式を使った簡易代数系の実験

最近、自作の非可換代数系を実装して、置換多項式の四則演算や逆元の挙動を試してみました。
この実験では、ベクトル係数を持つ多項式に対して置換作用を組み込み、非可換な演算環を作ることを目的としています。

1. 代数系の概要

  • 係数環: $(R = (\mathbb{F}_p)^N)$ （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)$ は係数ベクトル
  • π は置換作用（非可換性の原因）

性質

  • 非可換環: πの作用により $(fg \neq gf)$ になることがある
  • 加法と乗法で閉じている
  • 一部の条件下で除法（剰余）も定義可能
    • 係数ベクトルにゼロを含まない場合、Hadamard逆元を使えば簡易的に剰余を計算可能

2. C言語での簡易実装例


// skew_poly_fixed.c
// コンパイル例: gcc -O2 skew_poly_fixed.c -o skew_fixed
// 実行: ./skew_fixed

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 4
#define P 7
#define MAX_DEG 9   // 0..64 -> degree up to 64 (32+32 の積を扱える)

/* Vec and Poly */
typedef struct { int c[N]; } Vec;
typedef struct { Vec v[MAX_DEG]; int deg; } Poly;

/* utilities */
int modp(int x){ x %= P; if(x<0) x += P; return x; }

void vec_print(Vec a){
    printf("[");
    for(int i=0;i<N;i++){ printf("%d", modp(a.c[i])); if(i+1<N) printf(" "); }
    printf("]");
}
int vec_is_zero(Vec a){ for(int i=0;i<N;i++) if(modp(a.c[i])!=0) return 0; return 1; }

Vec vec_add(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.c[i]=modp(a.c[i]+b.c[i]); return r; }
Vec vec_sub(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.c[i]=modp(a.c[i]-b.c[i]); return r; }
Vec vec_hadamard_mul(Vec a, Vec b){ Vec r; for(int i=0;i<N;i++) r.c[i]=modp(a.c[i]*b.c[i]); return r; }

/* multiplicative inverse in GF(P) */
int inv_mod(int a){
    a = modp(a);
    if(a==0){ fprintf(stderr,"inv_mod(0)\n"); exit(1); }
    for(int i=1;i<P;i++) if((a*i)%P==1) return i;
    fprintf(stderr,"inv_mod fail\n"); exit(1);
}
Vec vec_hadamard_inv(Vec a){
    Vec r;
    for(int i=0;i<N;i++){
        if(modp(a.c[i])==0){ fprintf(stderr,"vec_hadamard_inv: zero component\n"); exit(1); }
        r.c[i] = inv_mod(a.c[i]);
    }
    return r;
}

/* permutation action: pi is perm array of length N, vec_perm does r[i]=v[pi[i]] */
Vec vec_perm_once(Vec v, int pi[N]){
    Vec r;
    for(int i=0;i<N;i++) r.c[i] = v.c[pi[i]];
    return r;
}
/* apply permutation k times (sigma^k) by repeated application (N small) */
Vec vec_perm_k(Vec v, int pi[N], int k){
    Vec r = v;
    k = (k % N + N) % N;
    for(int t=0;t<k;t++) r = vec_perm_once(r, pi);
    return r;
}

/* poly normalize: reduce deg if leading terms are zero */
void poly_normalize(Poly *p){
    while(p->deg>0 && vec_is_zero(p->v[p->deg-1])) p->deg--;
}

/* poly print */
void poly_print(Poly p){
    poly_normalize(&p);
    if(p.deg==0){ printf("0\n"); return; }
    for(int i=0;i<p.deg;i++){
        vec_print(p.v[i]);
        if(i+1<p.deg) printf(" + ");
    }
    printf("\n");
}

/* addition */
Poly poly_add(Poly A, Poly B){
    Poly R;
    int maxd = (A.deg > B.deg) ? A.deg : B.deg;
    R.deg = maxd;
    for(int i=0;i<maxd;i++){
        Vec av = (i < A.deg) ? A.v[i] : (Vec){{0}};
        Vec bv = (i < B.deg) ? B.v[i] : (Vec){{0}};
        R.v[i] = vec_add(av,bv);
    }
    poly_normalize(&R);
    return R;
}

/* skew multiplication: (a_i x^i)*(b_j x^j) = a_i ⊙ sigma^i(b_j) x^{i+j} */
Poly poly_mul(Poly A, Poly B, int pi[N]){
    Poly R;
    for(int i=0;i<MAX_DEG;i++) for(int j=0;j<N;j++) R.v[i].c[j]=0;
    R.deg = A.deg + B.deg - 1;
    if(R.deg < 0) R.deg = 0;
    for(int i=0;i<A.deg;i++){
        for(int j=0;j<B.deg;j++){
            Vec bjs = vec_perm_k(B.v[j], pi, i); // sigma^i(b_j)
            Vec prod = vec_hadamard_mul(A.v[i], bjs);
            R.v[i+j] = vec_add(R.v[i+j], prod);
        }
    }
    poly_normalize(&R);
    return R;
}

/* right division: find Q such that A = Q * B + R, deg R < deg B
   requires B.deg > 0 and leading coeff of B (as element of R) is invertible after sigma^d */
void poly_divmod_right(Poly A, Poly B, int pi[N], Poly *Q_out, Poly *R_out){
    Poly R = A;
    Poly Q;
    for(int i=0;i<MAX_DEG;i++) for(int j=0;j<N;j++) Q.v[i].c[j]=0;
    Q.deg = 0;

    if(B.deg==0){ fprintf(stderr,"divmod: divisor degree 0\n"); exit(1); }

    while(R.deg >= B.deg && R.deg > 0){
        int d = R.deg - B.deg;
        Vec b_lead_shift = vec_perm_k(B.v[B.deg-1], pi, d); // sigma^d(b_lead)
        Vec b_lead_inv = vec_hadamard_inv(b_lead_shift);    // inverse (requires nonzero comps)
        Vec r_lead = R.v[R.deg-1];
        Vec qcoef = vec_hadamard_mul(r_lead, b_lead_inv);   // q_d

        Q.v[d] = qcoef;
        if(Q.deg < d+1) Q.deg = d+1;

        for(int i=0;i<B.deg;i++){
            Vec bi_shift = vec_perm_k(B.v[i], pi, d); // sigma^d(b_i)
            Vec subterm = vec_hadamard_mul(qcoef, bi_shift);
            R.v[i + d] = vec_sub(R.v[i + d], subterm);
        }
        poly_normalize(&R);
    }
    poly_normalize(&Q);
    *Q_out = Q;
    *R_out = R;
}

/* equality check (after normalization) */
int poly_equal(Poly A, Poly B){
    poly_normalize(&A);
    poly_normalize(&B);
    if(A.deg != B.deg) return 0;
    for(int i=0;i<A.deg;i++) for(int j=0;j<N;j++) if(modp(A.v[i].c[j]) != modp(B.v[i].c[j])) return 0;
    return 1;
}

/* random generators: ensure nonzero components (so hadamard inverse exists) */
Vec random_nonzero_vec(){
    Vec v;
    for(int i=0;i<N;i++) v.c[i] = 1 + rand() % (P-1);
    return v;
}
Poly random_poly_terms(int terms){ // terms = number of coefficients = degree+1
    Poly p;
    p.deg = terms;
    for(int i=0;i<terms;i++) p.v[i] = random_nonzero_vec();
    poly_normalize(&p);
    return p;
}

/* main: test with degree 32 polynomials (terms = 33) */
int main(){
    srand((unsigned)time(NULL));
    int pi[N] = {1,2,3,0}; // 巡回シフト 1-step; for general perm, put arbitrary permutation

    int terms = 4; // degree 32 => 33 terms
    if(terms > MAX_DEG){ fprintf(stderr,"increase MAX_DEG\n"); return 1; }

    // construct divisor F (must have invertible leading coeff) and Q_true (arbitrary)
    Poly F = random_poly_terms(terms);    // divisor
    Poly Q_true = random_poly_terms(terms); // quotient true (for testing)
    // Build H = Q_true * F  (so right-division H / F should return Q_true)
    Poly H = poly_mul(Q_true, F, pi);

    printf("F (divisor) degree %d:\n", F.deg-1); poly_print(F);
    printf("Q_true (to hide) degree %d:\n", Q_true.deg-1); poly_print(Q_true);
    printf("H = Q_true * F degree %d:\n", H.deg-1); poly_print(H);

    Poly Q_found, R;
    poly_divmod_right(F, Q_true, pi, &Q_found, &R);

    printf("Q_found (quotient) degree %d:\n", Q_found.deg-1); poly_print(Q_found);
    printf("R (remainder) degree %d:\n", R.deg-1); poly_print(R);

    Poly recomb = poly_add(poly_mul(Q_found, Q_true, pi), R);
    printf("Q_found*F + R:\n"); poly_print(recomb);

    if(poly_equal(recomb, F)) printf("検算: 成功 — H == Q_found*F + R\n");
    else printf("検算: 失敗 — 不一致\n");

    return 0;
}

非可換置換多項式の剰余計算と逆元

今日の実験で、非可換な置換多項式における剰余計算や逆元計算がうまく動いた条件を整理します。

1. 演算対象の限定

  • 係数ベクトルに 0 を含まない元のみを使用
    • 0 成分があると Hadamard 積の逆元が存在せず、割り算や剰余計算が無限ループになる。
  • 以前は 0 を含むベクトルも対象にしていたため、剰余計算や逆元計算が成り立たなかった。

2. 置換作用の扱い

  • 置換作用を統一的に適用
    • 係数の逆元を計算する前に、置換を正しい順序で作用させる。
    • これにより剰余計算のズレを最小化できる。
  • 以前は処理の順序が不統一で、計算結果が一致せず破綻していた。

3. 演算の単純化

  • Hadamard 積（要素ごとの掛け算） を使用
  • 巡回畳み込みより計算が局所化され、逆元が存在すれば簡単に剰余計算可能。
  • 以前は巡回畳み込みや複雑な置換作用を使っていたため、逆元が存在しても剰余計算が一致しなかった。

4. 今日成功した条件まとめ

条件 内容
対象集合 0 を含まないベクトルのみ
積の演算 Hadamard 積（要素ごとの掛け算）
置換作用 統一的に適用
逆元計算の順序 置換作用後に逆元を計算
  • これらの条件を満たすと、非可換置換多項式でも剰余計算や逆元計算が一貫して行える。

まとめ

  • 剰余や逆元の成否は 対象集合と演算の定義・順序 に強く依存する。
  • 今日の成功は「演算を変えた」のではなく、条件と順序を制約して一貫性を持たせたことによる。
  • この条件を満たすことで、非可換置換多項式でも有限次の剰余計算が可能となる。
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?