符号 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^r全等1，n全等0。

例如，如果 r=3，则 x^4 与 x 全等。这将产生最多 r-1 次的多项式。

对多项式的系数使用 n 与 0 同余的规则。

Answer 2

此处的 X 表示我们正在处理多项式。 Mod X^r - 1 表示我们 mod 所有的多项式指数乘以 r。 Mod n 表示我们 mod 所有的系数由 n.

例如，如果我们有一个多项式 X^4 + 4 X^3 + 6 X^2 + 4 X + 1 并且我们 mod 由 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.

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

What does the notation a (mod b, n) mean?

algorithm

modulo

modular-arithmetic