对米勒-拉宾感到困惑

发布于 2024-09-19 08:15:44 字数 189 浏览 7 评论 0原文

作为对自己的练习，我正在实施米勒-拉宾测试。（通过 SICP 进行工作）。我理解费马小定理并且能够成功地实现它。我在米勒-拉宾测试中遇到的问题是“1 mod n”业务。 1 mod n（n 是某个随机整数）不是总是 1 吗？所以我对“1 modulo n 的非平凡平方根”可能是什么感到困惑，因为在我看来，在处理整数值时“1 mod n”始终为 1。我缺少什么？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

沩ん囻菔务 2024-09-26 08:15:44

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

您使用的不是单个数字，而是等价集。 [m]n 是所有数字 x 的集合，使得 x 与 m< /代码> mod <代码>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

1 is congruent to 9 mod 8 so 3 is a non trivial square root of 1 mod 8.

what you are working with is not individual numbers, but equivalence sets. [m]n is the set of all numbers x such that x is congruent to m mod n. Any thing that sqaures to any element of this set is a square root of m modulo n.

given any n, we have the set of integers modulo n which we can write as Zn. this is the set (of sets) [1]n, [2]n, ... ,[n]n. Every integer lies in one and only one of those sets. we can define addition and multiplication on this set by [a]n + [b]n = [a + b]n and likewise for multiplication. So a square root of [1]n is a(n element of) [b]n such that [b*b]n = [1]n.

In practice though, we can conflate m with [m]n and normally choose the unique element, m' of [m]n such that 0 <= m' < n as our 'representative' element: this is what we usually think of as the m mod n. but it's important to keep in mind that we are 'abusing notation' as the mathematicians say.

here's some (non-idiomatic) python code as I don't have a scheme interpreter 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]

So, in particular (looking at the last example), 17 is a root of unity modulo 9. indeed, 17^2 = 289 and 289 % 9 = 1. returning to our previous notation [8]9 = [17]9 and ([17]9)^2 = [1]9

回复收藏 0 原文

南笙 2024-09-26 08:15:44

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

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

我认为应该这样说：

其平方与 1 模 n全等

回复收藏 0 原文

天气好吗我好吗 2024-09-26 08:15:44

这就是为什么该措辞是针对 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,89,127,143}。

回复收藏 0 原文

~没有更多了~