符号a (mod，n)是什么意思？

Question

我正在试着为AKS primality test写一个Python程序。

第五步声明为if (X+a)^n≠ X^n+a (mod X^r − 1,n), output composite;，但当模数有两个参数时，我不确定该怎么做：Xr-1和n。在这种情况下，它应该计算什么？

我理解a(mod b)的意思是用b = a除以一个数字后的余数，但不确定这两个参数是什么意思。

Answer 1

这里的X表示我们使用的是多项式。Mod X^r - 1意味着我们用r对所有的多项式指数进行mod。Mod n意味着我们用n修改所有的系数。

例如，如果我们有一个多项式X^4 + 4 X^3 + 6 X^2 + 4 X + 1，并且我们用X^3 - 1 (即，r = 3)和n = 5进行建模，那么我们得到

X^4 + 4 X^3 + 6 X^2 + 4 X + 1 -> (mod by X^3 - 1)
X^1 + 4 X^0 + 6 X^2 + 4 X + 1 =
X   + 4     + 6 X^2 + 4 X + 1 =
6 X^2 + 5 X + 5 -> (mod by 5)
1 X^2 + 0 X + 0 =
X^2.

Answer 2

这意味着x^r同余于1，n也同余于0。

例如，如果r=3，那么我们有x^4与x同余。这产生了至多r-1次多项式。

在多项式的系数上使用n同余于0的规则。