困惑的米勒罗宾 [英] 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'< ñ
作为我们'重新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屋!