Day 025-Q2 — 多項式 GCD・スクエアフリー分解 + Distinct Degree Factorization

問題

$\mathbb{F}_p$ 上の多項式 $f(x)$ について、Yun の SFD でスクエアフリー因子を求め、$g_1$ について次数 $d$ の既約因子の数を Cantor-Zassenhaus 流に数える。

制約

入出力例

7 1
4
1 0 0 0 1

Square-free factors:
g1 = x^4 + 1
No repeated factors.
Irreducible factors of degree 1: 2

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
input = sys.stdin.readline

def main():
    p, target_deg = map(int, input().split())
    n = int(input())
    coeffs = list(map(int, input().split()))
    MOD = p

    def normalize(f):
        while len(f) > 1 and f[-1] == 0:
            f.pop()
        return f

    def poly_sub(f, g):
        size = max(len(f), len(g))
        res = [0] * size
        for i, c in enumerate(f): res[i] = (res[i] + c) % MOD
        for i, c in enumerate(g): res[i] = (res[i] - c) % MOD
        return normalize(res)

    def poly_mul(f, g):
        if not f or not g: return [0]
        res = [0] * (len(f) + len(g) - 1)
        for i, cf in enumerate(f):
            for j, cg in enumerate(g):
                res[i+j] = (res[i+j] + cf*cg) % MOD
        return normalize(res)

    def poly_mod(f, g):
        f = list(f)
        g_lead_inv = pow(g[-1], MOD - 2, MOD)
        while len(f) >= len(g):
            while f and f[-1] == 0: f.pop()
            if len(f) < len(g): break
            coef = f[-1] * g_lead_inv % MOD
            d = len(f) - len(g)
            for i in range(len(g)):
                f[d+i] = (f[d+i] - coef * g[i]) % MOD
            while f and f[-1] == 0: f.pop()
        return f if f else [0]

    def make_monic(f):
        if not f or all(c == 0 for c in f): return [0]
        inv = pow(f[-1], MOD - 2, MOD)
        return [c * inv % MOD for c in f]

    def poly_gcd(f, g):
        f, g = list(f), list(g)
        while any(c != 0 for c in g):
            f, g = g, poly_mod(f, g)
        return make_monic(f)

    def poly_div(f, g):
        f = list(f)
        g_lead_inv = pow(g[-1], MOD - 2, MOD)
        result = []
        while len(f) >= len(g):
            while f and f[-1] == 0: f.pop()
            if len(f) < len(g): break
            coef = f[-1] * g_lead_inv % MOD
            result.append((len(f) - len(g), coef))
            for i in range(len(g)):
                f[len(f) - len(g) + i] = (f[len(f) - len(g) + i] - coef * g[i]) % MOD
            while f and f[-1] == 0: f.pop()
        if not result: return [0]
        max_deg = max(d for d, _ in result)
        res = [0] * (max_deg + 1)
        for d, c in result: res[d] = c
        return normalize(res)

    def derivative(f):
        if len(f) <= 1: return [0]
        return normalize([(i * f[i]) % MOD for i in range(1, len(f))])

    def is_one(f):
        return normalize(list(f)) == [1]

    f = normalize(list(coeffs))
    df = derivative(f)
    sqfree_factors = {}

    if all(c == 0 for c in df):
        print("Square-free factors:")
        print("(Characteristic issue)")
        return

    g = poly_gcd(f, df)
    f_div = poly_div(f, g)
    h = poly_div(df, g)
    i = 1
    while not is_one(f_div):
        dfdiv = derivative(f_div)
        diff = poly_sub(h, dfdiv)
        gi = poly_gcd(f_div, diff)
        factor = poly_div(f_div, gi)
        if not is_one(factor):
            sqfree_factors[i] = factor
        f_div = gi
        h = poly_div(diff, gi)
        i += 1

    def poly_to_str(P):
        P = normalize(list(P))
        if all(c == 0 for c in P): return "0"
        terms = []
        for deg in range(len(P) - 1, -1, -1):
            c = P[deg]
            if c == 0: continue
            if deg == 0: terms.append(str(c))
            elif deg == 1: terms.append("x" if c == 1 else f"{c}x")
            else: terms.append(f"x^{deg}" if c == 1 else f"{c}x^{deg}")
        return " + ".join(terms) if terms else "0"

    print("Square-free factors:")
    if 1 in sqfree_factors:
        print(f"g1 = {poly_to_str(sqfree_factors[1])}")
    else:
        print(f"g1 = {poly_to_str(make_monic(f))}")
    if all(k == 1 for k in sqfree_factors):
        print("No repeated factors.")
    else:
        for k, v in sorted(sqfree_factors.items()):
            if k > 1:
                print(f"g{k} = {poly_to_str(v)} (multiplicity {k})")

    g1 = sqfree_factors.get(1, make_monic(f))

    def poly_powmod(base, exp, mod_poly):
        result = [1]
        base = poly_mod(base, mod_poly)
        while exp > 0:
            if exp % 2 == 1:
                result = poly_mod(poly_mul(result, base), mod_poly)
            base = poly_mod(poly_mul(base, base), mod_poly)
            exp //= 2
        return result

    xpd = poly_powmod([0, 1], pow(p, target_deg), g1)
    xpd_minus_x = poly_sub(xpd, [0, 1])
    h_factor = poly_gcd(g1, xpd_minus_x)
    deg_h = len(normalize(h_factor)) - 1
    count = deg_h // target_deg
    print(f"Irreducible factors of degree {target_deg}: {count}")

main()

Step-by-Step 解説

よくあるミス

次のステップ

• Equal-Degree Splitting で各既約因子を確率的に分割
• 楕円曲線の位数計算（BSGS + 多項式演算）

自己評価

自分の回答

気づき・メモ