米勒·拉宾的困惑

1与9模8相等,因此3是1模8的非平凡平方根。

你使用的不是单个的数字,而是等价集。 [m]n 是 设置 x 以至于 十 与…一致 m 国防部 n . 这个集合中任何元素的平方根是 米 模 .

不 ,我们有一组模n的整数,可以写成 Zn . 这是一套 [1]n , [2]n , ... , [n]n [a]n + [b]n = [a + b]n 乘法也是如此。所以一个平方根 [1] 不 [b]n 以至于 [b*b]n = [1]n

米 具有 通常选择独特的元素, m' 属于 [m] 不 以至于 0 <= m' < n m mod n . 但重要的是要记住,正如数学家所说,我们正在“滥用符号”。

以下是一些(非惯用的)python代码,因为我没有scheme解释器:

>>> 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

我相信误解来自于书中对非平凡根的定义:

模n为1的非平凡平方根,即不等于1或n-1的数 其平方等于1模n

全等的

这就是为什么用这个词来表示1的非平凡平方根。对于任意模n,1是1的平凡平方根。

17是1的非平凡平方根,mod 144。因此17^2=289,等于1 mod 144。如果n是素数,那么1和n-1是1的两个平方根,它们是唯一的两个平方根。但是,对于复合n,通常有多个平方根。n=144时,平方根为{1,17,55,71,73,89127143}。