Math in CS:置换的轮换分解

目录 数学, 算法

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

Math in CS: 数论和公钥密码学

目录 安全, 数学, 社会, 算法

1940年,英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说:“如果有用的知识是这样的知识(我们暂时同意这样说):它大概会在现在或相对不远的未来,为人类在物质上的享受方面作出贡献,因而,它是否在单纯的智力上满足人们乃是无关紧要的,那么,大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验,也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。”但是我们会看到,哈代这个断定在当时“不远的未来”几乎被一一证明是错误的,数论就是其中一个。

在 1970 年代以前,人们所知道的密码学都是对称密码学,就是在加密和解密过程中需要使用同一个密钥。在那个时代,一些密码算法已经能保证足够的安全性,比如数据加密标准 DES。但是人类的需求是很难完全得到满足的,他们为每次密钥交换的复杂度而苦恼,比如在战时如果密码本被敌方获得,就必须重新向无线电收发员分发密码本,这个工作量和代价是相当大的;还有一个需求就是数字签名,能不能用加密实现对数字文件的签名,像手写的签名一样,确保该文件出自谁人之手?

上述问题,就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的,他们也给出了其中一个问题的解决办法,那就是 Deffie-Hellman 密钥交换算法(后来被改为 Deffie-Hellman-Merkle 密钥交换算法,里面还有一段小故事。)。但是 DH 没做完的功课,仅仅在一年后就被 RSA 解决了,那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥,即公钥和私钥,你可以将你的公钥扔到世界上任何一个位置,我用你的公钥加密一段信息,除了你用自己的私钥解密,没有别的人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是,但箱子一旦锁上,就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法,但是 RSA 算法还带来一个另外的意义,那就是:数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows,因为每台 Windows 上都装配着 RSA 算法程序,但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端,你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换,混淆和扩散,DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性,RSA 和 DH 算法描述要比 DES, AES 简练许多,我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理:费马小定理、欧拉定理和中国剩余定理(几乎处处都在),和一个古典难题:大整数分解问题。如果你是数学系的学生,对这些概念一定不会陌生。

费马小定理:若 p 是素数,a 是正整数且不能被 p 整除,则: ap-1 = 1(mod p)。或者另一种形式:ap=a(mod p),这种形式不要求 a 与 p 互素。

欧拉定理:对任意互素的 a 和 n,有 aΦ(n) = 1(mod n)。其中,Φ(n)是欧拉函数,即小于 n 且与 n 互素的正整数的个数。

大整数分解问题:将两个整数乘起来是简单的,但是将一个整数分解为几个整数的乘积是困难的,尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题,甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢?

密钥的产生:
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) (这是欧拉函数的性质)
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候,私钥就是{d, n},公钥就是{e, n}。
加密算法:
假设 M 是明文(M<n),那么密文就是 C = Memod n。(为什么明文是数字?在计算机科学里任何数据最终表示都是数字。)
解密算法:
假设 C 是密文,那么明文就是 M = Cd mod n。

我们来证明一下算法是否正确,由于 Cd = Me*d = Mk*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的,显然直接由欧拉定理我们就能得到:
Cd = Mk*Φ(n)*M1 = M (mod n) = M
说明算法是正确的;
如果 M 和 n 不互素,由于 n 是两个素数 p 和 q 的乘积且 M<n,那么 M 要么是 p 的倍数,要么是 q 的倍数,由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得:
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成: e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理,我们有:Me*d = Mk*(p-1)+1 = M(mod p) 和 Me*d = Mh*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数,且 p, q 均整除 Me*d-M,所以我们有:
Cd = Me*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥,而且证明了这个算法的正确性。但 RSA 算法要想实用,光有正确性还不够,最重要的一点是安全性,即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到,关键要知道 Φ(n),知道了 Φ(n),使用欧几里德算法就能求出 e 的逆元,就得到了用户的私钥{d, n}。要求出 Φ(n),就必须知道 p,q,但 p,q 是不公开的,仅仅知道 p,q 的乘积 n 去求 p,q,根据大整数分解古典难题,当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的,所以它就有能力同时实现加密和签名的功能。由于公钥是公开的,每个人都可以用你的公钥加密一段信息发给我,而私钥是保密的,所以只有你能看到别人用你的公钥加密的消息;而也因为可逆性,如果你用私钥解密一段明文(实际是加密),所有人都可以用你的公钥加密它来得到明文(实际是解密),因为私钥只有你一个人知道,这个消息只有可能是你发出的,就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单,它也是基于数论中的一个古典难题:离散对数问题。

离散对数问题:若 p 是素数,p 已知,考虑方程 y = gx mod p,给定 g,x 求 y 是简单的,但给定 y,g 求 x,即求 x = logg,py mod p,在计算上是不可行的。

DH 密钥交换算法的描述如下:
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p,计算 Ya = αXa mod p,将其发送给 B。
2. 用户 B 选择秘密的 Xb<p,计算 Yb = αXb mod p,将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)Xa mod p 和 Kb = (Ya)Xb mod p,就同时得到了共享的密钥 K=Ka=Kb,然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于:双方在通信前不需要知道任何共享的密钥,而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性,Ka = Kb 是否成立:
Ka = (Yb)Xa = (αXb)Xa = αXa*Xb (mod p)
Kb = (Ya)Xb = (αXa)Xb = αXa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性,就是能否从公开的信息推导出 K 来:
由于密钥是 K = αXa*Xb,那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K,而公开的信息只有 Ya 和 Yb,由离散对数问题,从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的,就保证了算法的安全性。

从上面两个算法我们可以看出,数论在公钥密码学中的重要地位,恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧!