找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1321|回复: 1
收起左侧

[米群网大牛独家面经总结] 关于完美洗牌算法中圈和圈起点的一个证明

[复制链接]
发表于 11-29-2014 10:51 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

我们用mod表示对一个数取余数,例如3 mod 5 = 3,  5 mod 3 = 2……   a mod b = a - [a / b] * b。

在完美洗牌算法中,我们用到了一个映射关系  i' = (i * 2) mod (2n + 1)  其中i = 1,2,3,...2n 然后我们对2m = (3^k - 1) 开始找圈了,这个结论的证明还是需要一些数论的基础。现在简要介绍一下,其中一个定理(*)的证明还是稍显复杂,不过可以可以查到。

先把我们要证的结论用白话形容一下,

我们证明  M = 2m = 3^k - 1的情况下, i' = (i * 2) mod (M + 1) = (i * 2) mod (3^k) ,按照这个置换恰好形成k个圈,每个圈的头部(最小的数)是1,3,9,..3^(k - 1)。 (k >= 1)。证明的关键是这所有的圈合并必须包含全部从1到M之间的整数,一个都不能少。

要证这个结论,先要对原根有一个感性的认识。

一个数g,是另外一个数x的原根,是说集合S = {g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x…… },得到的集合包含了所有小于x并且与x互质的数。

这里S看起来像一个无限集合,实际上它是有限的。这是因为我们对x取余数,所以最多只有0到(x - 1)这x种结果。

举例,比如2是3的原根

因为2^0 mod 3 = 1, 2 ^ 1 mod 3 = 2, 2 ^ 2 mod 3 = 1, 2 ^ 3 mod 3 = 2....只有{1,2}两种结果,而且和3都互质。

而2不是7的原根,

这是因为2^0 mod 7 = 1, 2 ^ 1 mod 7 = 2, 2 ^ 2 mod 7 = 4, 2 ^ 3 mod 7 = 1 只有{1,2,4} 3种结果而没包含3,5,6。

为了方便还是先定义欧拉函数phi(x), 也有用希腊字母φ(x)表示的,表示不超过x的整数种和x互质的个数,特别地,当p是质数的时候因为所有小于p的数都与p互质,所以phi(p) = p - 1。

那么数g,是x的原根,表示为集合S = {g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x,……}  恰好包含phi(x)个整数。

首先,要判断原根g是x的原根,一个必要条件是g与x必须互质。否则g ^ 1 mod x 产生的数就不和x互质了。

我们之所以取g ^ 0 = 1 是为了方便。

如果我们在g ^ 0 mod x, g ^ 1 mod x, g ^ 2 mod x……这一串数中发现重复的余数,g ^ i mod x = g ^ j mod x 并且 i < j, 则有g ^ (j - i) mod x = 1  = g ^ 0 mod x (一般同余不能两遍随便做除法,但是互质的时候可以除)。这就说明在比j更早的时候,(j - i)时我们已经发现了重复的余数1了。也就是说当g与x互质的时候,按g ^ 0 mod x, g ^ 1 mod x,……的顺序,如果第一次发现重复,重复的数必定是1,这是我们从g^0开始计算的原因。出现余数循环一定是从开头循环的。这对我们要证明的结论至关重要,只看集合里元素的种类数是不够的。

比如不互质的时候 ,结论不一定正确,g = 9, x = 15, 9 ^ 0 mod 15 = 1, 9 ^ 1 mod 15 = 9, 9 ^ 2 mod 15 = 6, 9 ^ 3 mod 15 = 9, 我们发现9 ^ 3和9 ^ 1出现循环,并没有从开头的1开始循环。

有一个著名的定理叫做费马小定理,它告诉我们当g与x互质的时候,有g ^ phi(x) mod x = 1。

结合原根的定义还有前面的结论,我们要证集合S恰好包含phi(x)个数,只需要证明{g ^ 0 mod x, g ^ 1 mod x ,……g ^ (phi(x) - 1) mod x} 这些数都不相同就可以了。

我们不加证明的给出如下结论:

p是奇素数,如果g是p的原根且g ^ (p - 1)  mod p ^ 2 != 1,则g是任意p^k的原根。(k >= 1)

p是奇素数,如果g是p ^ 2的原根, 则g是任意p^k的原根。 (k >= 1)

这两个定理的描述和证明可参看

http://people.math.gatech.edu/~mbaker/pdf/primroots.pdf
0 H; \3 e3 B; B& K

http://en.wikipedia.org/wiki/Primitive_root_modulo_n
8 `* ^3 ~0 [( ]

取g = 2, p = 3。

我们知道2是3的原根,2是9的原根。

我们定义S(k)表示上述的集合S,并且x = 3 ^ k。

所以S(1) = {1, 2}

      S(2) = {1, 2, 4, 8, 7, 5}

我们没改变圈元素的顺序,由前面的结论S(k)恰好是一个圈里的元素,且认为从1开始循环的,也就是说从1开始的圈包含了所有与3 ^ k互质的数。

那与3 ^ k不互质的数怎么办?如果0 < i < 3 ^ k与 3 ^ k不互质,那么它与3 ^ k的最大公约数一定是3 ^ t的形式(只包含约数3),并且 t < k。即gcd(i , 3 ^ k) = 3 ^ t

我们把3 ^ t除下去,有gcd(i / (3 ^ t), 3 ^ (k - t))  = 1, i / (3 ^ t) 都与3 ^ (k - t) 互质了,并且i / (3 ^ t) < 3 ^(k - t), 根据定义,可见i / (3 ^ t) 在集合S(k - t)。 同理,任意S(k - t)中的数x,都满足gcd(x , 3 ^ k)  = 1,于是gcd(3 ^ k , x * 3 ^ t) = 3 ^ t, 并且x * 3 ^ t < 3 ^ k。可见S(k - t)中的数x * 3 ^ t 与 i形成了一一对应的关系。请仔细体会这种一一对应的关系。

      也就是说S(k - t)里每个数x * 3 ^ t形成的新集合包含了所有与3 ^ k的最大公约数为3 ^ t的数,它也是一个圈,原先圈的头部是1,这个圈的头部是3 ^ t。

于是,对所有的小于 3 ^ k的数,根据它和3 ^ k的最大公约数,我们都把它分配到了一个圈里去了。k个圈包含了所有的小于3^k的数。

举例:

比如k = 3。 我们有:

        S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且与27互质的所有数,圈的首部为1,这是原根定义决定的。

        那么与27最大公约数为3的数,我们用S(2)中的数乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的顺序没变化,圈的首部是3

               与27最大公约数为9的数,我们用S(1)种的数乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的顺序没变化,圈的首部是9。

因为每个小于27的数和27的最大公约数只有1, 3, 9这3种情况,又由于前面所证的一一对应的关系,所以S(2) * 3包含了所有小于27且与27的最大公约数为3的数,S(1) * 9 包含了所有小于27且和27的最大公约数为9的数。

. m' @- B1 l" }2 j' R, i, C

本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

12

主题

5

精华

480

积分

高级会员

Rank: 3Rank: 3

积分
480
发表于 11-29-2014 10:45 PM | 显示全部楼层
好高深~~~拜读~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表