困惑的米勒罗宾 [英] Confused on Miller-Rabin

问题描述

作为练习我自己，我采取了米勒罗宾测试。 （通过SICP工作）。我理解费马小定理，并能成功地实现这一点。那我越来越绊倒在米勒罗宾测试的部分是1模N的经营。是不是1模N（N是一些随机的整数）始终为1？所以我很困惑什么是1模平凡的平方根N可能是因为在我心中1模N时，与整数值处理始终为1。我在想什么？

As an exercise for myself, I'm implementing the Miller-Rabin test. (Working through SICP). I understand Fermat's little theorem and was able to successfully implement that. The part that I'm getting tripped up on in the Miller-Rabin test is this "1 mod n" business. Isn't 1 mod n (n being some random integer) always 1? So I'm confused at what a "nontrivial square root of 1 modulo n" could be since in my mind "1 mod n" is always 1 when dealing with integer values. What am I missing?

推荐答案

1是全等9mod8所以3是1模8的非平凡平方根。

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

您正在使用的不是个人的数字，但同值。 [M] n的是设置所有数字 X ，使得 X 是一致的，以 M MOD N 。这sqaures这一套元素的任何事情是一个平方根 M 模 N 。

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.

给出任何 N ，我们有整数集模N，我们可以写成锌。这是（套）的集 [1] n的， [2] n的，...， [N] n的。每个整数在于一个且只有一个的那些套。我们可以定义加法和乘法这套由 [一] N + [B] N = [A + B] n的，同样也倍增。因此，的平方根[1] n的是（n个元素） [B] n的，使得 [B * B] N = [1] 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.

但在实践中，我们可以混为一谈 M 与 [M] n的，通常选择的唯一元素， M [M] n的，使得 0℃= M'＆LT; ñ作为我们'重新presentative'元素：这就是我们通常所认为的在 M模ñ。但重要的是要记住，我们是'滥用符号作为数学家说。

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.

这里的一些（非惯用语）蟒蛇code，因为我没有计划除preTER ATM：

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]

所以，特别是（看最后一个例子），17是统一模9.的确，17 ^ 2 = 289和289％9 = 1的根回到我们previous形式 [8] 9 = [17] 9 和（[17] 9）^ 2 = [1] 9

这篇关于困惑的米勒罗宾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！