关于有限域上多项式同余式$f(Y^q) \equiv f(gY) \bmod(Y^{q-1} -g)$的证明问询

架构老林

2026-4-20

嗨，我来帮你拆解这个同余式的证明逻辑，其实核心就是利用模$E(Y)$下的关键等价关系，一步步推导就很清晰了~

首先，先明确模$E(Y)$的核心条件：因为$E(Y) = Y^{q-1} - g$，所以在模$E(Y)$的意义下，我们有$Y^{q-1} \equiv g$。给这个等式两边同时乘以$Y$，就能得到一个关键的等价式：
$$Y^q \equiv gY \pmod{E(Y)}$$

接下来我们分两步证明：

第一步：先验证单项式的情况
假设$f(Y)$是一个单项式，也就是$f(Y) = Y^{k$（$k$是非负整数）。那么$f(Y}q) = (Y^q)k$，根据上面的关键等价式，$(Y^q)k \equiv (gY)^k$。而$f(gY) = (gY)^k$，所以显然有：
$$f(Y^q) \equiv f(gY) \pmod{E(Y)}$$
单项式的情况就成立了。
第二步：推广到任意多项式
任何$\mathbb{F}q[Y]$中的多项式$f(Y)$都可以写成单项式的线性组合，也就是：
$$f(Y) = \sum{k=0}^n a_k Y^k \quad (a_k \in \mathbb{F}q)$$
那对应的$f(Y^q)$和$f(gY)$分别是：
$$f(Y^q) = \sum{k=0}^n a_k (Y^q)k, \quad f(gY) = \sum_{k=0}^n a_k (gY)^k$$
因为模运算保持加法和数乘的等价性，既然每个单项式项都满足$(Y^q)k \equiv (gY)^k \pmod{E(Y)}$，那么给每个项乘以系数$a_k$再相加，自然就有：
$$\sum_{k=0}^n a_k (Y^q)k \equiv \sum_{k=0}^n a_k (gY)^k \pmod{E(Y)}$$
也就是$f(Y^q) \equiv f(gY) \pmod{E(Y)}$。