对Miller-Rabin感到困惑

Question

作为我自己的练习，我正在实施Miller-Rabin测试。 （通过SICP工作）。我了解Fermat的小定理，并能够成功实施它。我在Miller-Rabin测试中被绊倒的部分是“ 1 Mod N”业务。 1 mod n（n是一个随机整数）不是总是1吗？因此，我对“ 1 modulo n的非平凡平方根”的态度感到困惑，因为在我的脑海中“ 1 mod n”在处理整数值时总是1个。我想念什么？

Answer 1

1与9 mod 8相一致，因此3是1 mod 8的非琐碎平方根。

您正在使用的不是单个数字，而是等价集。 [m]n 是个 放 所有数字 x 这样 x 是一致的 m mod n. 。该集合的任何元素的任何事物都是 m Modulo 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是Unity Modulo 9的根。的确，17^2 = 289和289％9 = 1。 [8]9 = [17]9 和 ([17]9)^2 = [1]9

Answer 2

这就是为什么措辞的非平凡平方根为1。1是1个琐碎的平方根，对于任何模量n。

17是1，mod 144的非平凡平方根。因此，17^2 = 289，它与1 mod 144相一致。如果n为prime，则1和n-1是1的两个平方根，它们是1的。是仅有的两个这样的根。但是，对于复合n，通常有多个平方根。在n = 144的情况下，方形为{1,17,55,71,73,89,127,143}。

Answer 3

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

“ 1个模量的非平凡平方根”，即，一个不等于1或n -1的数字 正方形等于1个模块

我相信应该说：

谁是正方形 全等 到1个模块