algorithm - 对 Miller-Rabin 感到困惑

Question

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

Answer 1

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

您使用的不是单个数字，而是等价集。 [m]n是所有数字的集合 x这样 x与 m 一致国防部 n .对这个集合的任何元素求平方的任何东西都是 m 的平方根模 n .

给定任何n ，我们有整数模 n 的集合，我们可以写成 Zn .这是一组(一组)[1]n , [2]n , ... , [n]n .每个整数都位于其中一个集合中。我们可以通过 [a]n + [b]n = [a + b]n 定义这个集合的加法和乘法乘法也是如此。所以 [1]n 的平方根是 [b]n 的(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