algorithm - 符号 a (mod b, n) 是什么意思？

Question

我正在尝试为 AKS primality test 编写一个 Python 程序.

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

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

Answer 1

此处的 X 表示我们正在处理多项式。 Mod X^r - 1 表示我们用 r 对所有多项式指数进行模数。 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.