algorithm - 对米勒拉宾感到困惑

Question

作为我自己的练习，我正在实施 Miller-Rabin 测试。（通过 SICP 工作）。我理解费马的小定理，并且能够成功地实现它。我在 Miller-Rabin 测试中被绊倒的部分是这个“1 mod n”业务。1 mod n（n是一些随机整数）不是总是1吗？所以我对“1 模 n 的非平凡平方根”可能是什么感到困惑，因为在我看来，“1 mod n”在处理整数值时始终为 1。我错过了什么？

Answer 1

1 与 9 mod 8 全等，因此 3 是 1 mod 8 的非平凡平方根。

您正在使用的不是单个数字，而是等价集。[m]n是与mod一致的所有数字的集合。任何与这个集合的任何元素平方的东西都是模的平方根。xxmnmn

给定任何n，我们有一组整数模 n ，我们可以写成Zn。这是集合（集合）[1]n, [2]n, ... , [n]n. 每个整数都位于这些集合中的一个且只有一个。我们可以在这个集合上定义加法和乘法，乘法[a]n + [b]n = [a + b]n同样如此。所以 的平方根[1]n是一个(n 的元素)[b]n使得[b*b]n = [1]n。

但在实践中，我们可以m合并[m]n并通常选择独特的元素，m'例如[m]n我们0 <= m' < n的“代表性”元素：这就是我们通常认为的m mod n. 但重要的是要记住，正如数学家所说，我们正在“滥用符号”。

这是一些（非惯用的）python代码，因为我没有方案解释器ATM：

>>> def roots_of_unity(n):
...      roots = []
...      for i in range(n):
...          if i**2 % n == 1:
...               roots.append(i)
...      return roots
... 
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]

所以，特别是（看最后一个例子），17 是单位模 9 的根。实际上，17^2 = 289 和 289 % 9 = 1。回到我们之前的符号[8]9 = [17]9和([17]9)^2 = [1]9

Answer 2

我相信误解来自本书给出的关于非平凡根的定义：

“1 模 n 的非平凡平方根”，即不等于 1 或 n - 1的数，其平方等于 1 模 n

我认为它应该说：

其平方等于 1模n

Answer 3

这就是为什么措辞是针对 1 的非平凡平方根的原因。对于任何模数 n，1 是 1 的平凡平方根。

17 是 1 的非平凡平方根，取模 144。因此 17^2 = 289，等于 1 取模 144。如果 n 是素数，则 1 和 n-1 是 1 的两个平方根，它们是仅有的两个这样的根。然而，对于复合 n，通常有多个平方根。当 n = 144 时，平方根为 {1,17,55,71,73,89,127,143}。