如何判断多项式模(h(x),n)同余？及AKS算法Python实现问题

一、如何判断两个多项式是否模(h(x), n)同余？ #

简单来说，判断两个多项式 ( f(x) ) 和 ( g(x) ) 模 ( (h(x), n) ) 同余，你可以按这两步操作：

• 第一步：把两个多项式分别对 ( h(x) ) 做多项式除法求余，得到次数严格低于 ( h(x) ) 的余式 ( f_r(x) ) 和 ( g_r(x) )。这一步相当于把多项式“压缩”到 ( h(x) ) 的次数范围内——因为模 ( h(x) ) 意味着 ( h(x) \equiv 0 )，任何高于等于 ( h(x) ) 次数的项都可以用余式代替。
• 第二步：对比两个余式的每一项系数：如果对于每一个 ( x^i ) 的系数，( f_r(x) ) 的系数减去 ( g_r(x) ) 的结果都是 ( n ) 的整数倍（也就是 ( (coeff_{f_i} - coeff_{g_i}) \mod n = 0 )），那这两个多项式就模 ( (h(x), n) ) 同余；只要有一个系数不满足，就不同余。

举个例子：如果 ( h(x)=x^2-1 )，( n=5 )，( f(x)=x^3+2x+3 )，( g(x)=2x+4 )。先算 ( f(x) ) 模 ( h(x) ) 的余式：( x^3 = x*(x^2) = x*1 = x )，所以 ( f_r(x)=x+2x+3=3x+3 )；( g_r(x)=2x+4 )。x项系数差为 ( 3-2=1 )，( 1 \mod 5 \neq 0 )，因此两个多项式不同余。

二、AKS算法中验证 ( (x+a)^n \equiv x^n + a \mod(x^r -1, n) ) 的Python实现 #

这个验证是AKS的核心步骤之一，本质是在**模n的整数环上，同时模多项式 ( x^r-1 )**的多项式运算。我直接给你可运行的代码，再一步步拆解思路：

核心思路 #

模 ( x^r-1 ) 的关键是：( x^r \equiv 1 )，所以任何 ( x^k ) 都可以替换成 ( x^{k \mod r} )——这意味着我们只需要用长度为r的列表表示多项式（索引对应x的次数，比如索引0是常数项，索引1是x项，…，索引r-1是x^{r-1}项），所有运算都在这个长度的列表里进行，同时系数始终对n取模，避免数值过大。

Python代码实现 #

def poly_mult_mod(poly1, poly2, r, n):
    """
    计算两个多项式的乘积，模(x^r - 1)和模n
    poly1, poly2: 长度为r的列表，代表多项式系数（索引i对应x^i的系数）
    r: 对应x^r - 1中的r
    n: 模数
    返回：乘积后的多项式（长度为r的列表，系数模n）
    """
    result = [0] * r
    for i in range(r):
        if poly1[i] == 0:
            continue
        for j in range(r):
            # x^i * x^j = x^(i+j)，模x^r-1后等价于x^((i+j) % r)
            pos = (i + j) % r
            result[pos] = (result[pos] + poly1[i] * poly2[j]) % n
    return result

def poly_pow_mod(base_poly, exponent, r, n):
    """
    多项式快速幂：计算base_poly^exponent mod(x^r -1, n)
    base_poly: 底数多项式（长度r的列表）
    exponent: 指数n
    r, n: 同上
    返回：幂运算后的多项式
    """
    # 初始化结果为单位元（即多项式1，对应x^0项系数为1）
    result = [0] * r
    result[0] = 1
    current = base_poly.copy()
    while exponent > 0:
        if exponent % 2 == 1:
            result = poly_mult_mod(result, current, r, n)
        current = poly_mult_mod(current, current, r, n)
        exponent = exponent // 2
    return result

def verify_aks_condition(n, a, r):
    """
    验证(x+a)^n ≡ x^n + a mod(x^r -1, n)
    n: 待判断的数
    a: 当前选取的a（AKS中a的范围是1到某个上限）
    r: 选取的r值（AKS中r是满足特定条件的最小整数）
    返回：布尔值，True表示满足同余式，False表示不满足
    """
    # 构造左边的底数多项式(x + a)：x^1系数1，x^0系数a，其余为0
    left_base = [0] * r
    left_base[0] = a % n
    left_base[1] = 1 % n
    # 计算左边：(x+a)^n mod(x^r-1, n)
    left_poly = poly_pow_mod(left_base, n, r, n)
    
    # 构造右边的多项式x^n + a：x^(n mod r)系数1，x^0系数a，其余为0
    right_poly = [0] * r
    right_poly[0] = a % n
    right_poly[n % r] = (right_poly[n % r] + 1) % n
    
    # 对比两个多项式的所有系数是否相等
    return left_poly == right_poly

代码使用示例 #

比如判断n=11（质数），a=2，r=10的情况：

print(verify_aks_condition(11, 2, 10))  # 输出True，因为11是质数，满足条件

关键细节说明 #

1. 多项式乘法优化：因为模了x^r-1，不需要处理高于r-1次的项，直接把指数对r取模，计算量从O(k²)（k是多项式次数）降到O(r²)，而r在AKS中通常远小于n，效率很高。
2. 快速幂的作用：和整数快速幂一样，把指数运算的时间复杂度从O(n)降到O(log n)，避免直接展开高次多项式（n很大时根本不可能）。
3. 系数模n：所有运算中系数都对n取模，一是符合模n的要求，二是防止数值溢出，保持运算效率。

内容的提问来源于stack exchange，提问作者J Chapman