对Miller-Rabin感到困惑

Question

作为我自己的练习,我正在实施Miller-Rabin测试.(通过SICP工作).我理解费马的小定理并且能够成功地实现它.我在米勒 - 拉宾测试中被绊倒的部分是这个"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是集所有的数字x,使得x是一致的,以m国防部n.任何与该集合的任何元素相关的东西都是m模数的平方根n.

给定任何一个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的NONTRIVIAL平方根的原因.对于任何模数n,1是1的平凡平方根.

17是1,mod 144的非平凡平方根.因此17 ^ 2 = 289,这与1 mod 144一致.如果n是素数,则1和n-1是1的两个平方根,并且它们是1是这样的根源.然而,对于复合物n,通常存在多个平方根.当n = 144时,平方根为{1,17,55,71,73,89,127,143}.