技术 | 边际效应 - 杨文博的个人博客 - 页码 4

用两个非门和任意的与、或门构造三个非门

计算机科学中有很多有趣的 puzzle，他们可能出现在那些自命清高的企业的笔试题中，也可能来源于在网路上不经意的一瞥。后者比如我在无意中访问到的 Jamie Zawinski 的个人主页：http://www.jwz.org/，他即是在著名的 Teach Yourself Programming in Ten Years 一文中，Peter Norvig 提到的那位：

One of the best programmers I ever hired had only a High School degree; he's produced a lot of great software, has his own news group, and made enough in stock options to buy his own nightclub.

Jamie Zawinski 的个人主页看起来就像是 hexdump 的结果，而且以某种规律变化着，比较奇怪的是其中埋藏的一些超级链接并不发生变化。Jamie Zawinski 在网页的源代码中这样写道：

<!-- mail me if you find the secret -->
<!--   (no, you can't have a hint)  -->

我徒劳无功地搜索了一下，没有找到任何明确的解答。如果您通过我这篇文章了解到这个 puzzle，并且解答了它的话，非常希望您也 mail 给我一份解答。

说了那么多，其实本文的主题 puzzle 却是来源于前者。这个问题更详细的阐述是：

假设有一个逻辑黑盒，三个布尔型变量 x, y, z 作为输入，输出三个布尔变量 X, Y, Z，其中：
X = ~x; Y = ~y; Z = ~z;
注意，~ 符号代表一个非门。请用两个非门和任意多个与、或门实现这个黑盒。

这个问题大概是在计算机硬件设计中提出来的，所以看起来貌似很“电子”，但是其基础却是计算机科学中的布尔代数运算。下面代码的注释中已经包含详细的算法和分析，这里我就不再解释了。（当然，这个问题的答案不是我想出来的，我只是实现并分析了一下，作为我算法学习的笔记记录在此。）

/* ===========================================================================

* Problem:
*   Construct 3 NOT gates from only 2 NOT gates(and *no* XOR gates).
*
*   Assume that a logical blackbox has three Boolean inputs x, y, z and
*   three Boolean outputs X, Y, Z where the outputs are defined as:
*     X = ~x
*     Y = ~y
*     Z = ~z
*   Note that ~ stands for a NOT gate. Please realize this blackbox using
*   only two NOT gates, and as many as possible AND and OR gates.
*
* Algorithm I:
*   Internal Nodes:
*   r = (x & y) | (x & z) | (y & z);
*   R = ~r;
*   s = (R & (x | y | z)) | (x & y & z);
*   S = ~s;
*
*   Equations for Outputs:
*   X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
*   Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
*   Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));
*
* Analysis I:
*   We create 4 internal signals first: r, R, s and S. What equations above
*   say is that signal `r' will be 1 if two or three of the inputs are 1.
*   Meanwhile, signal `s' will be 1 if only one input is 1 or if all three
*   inputs are 1. The end result is that the two-bit word formed from `r'
*   and `s' tells us how many 1's we have[1]:
*   | r s | Means |    | x y z | r s |    | x y z | r s |
*   |++++++++++++++|    |+++++++++++++|    |+++++++++++++|
*   | 0 0 | 0 Ones |    | 0 0 0 | 0 0 |    | 1 0 0 | 0 1 |
*   | 0 1 | 1 One |    | 0 0 1 | 0 1 |    | 1 0 1 | 1 0 |
*   | 1 0 | 2 Ones |    | 0 1 0 | 0 1 |    | 1 1 0 | 1 0 |
*   | 1 1 | 3 Ones |    | 0 1 1 | 1 0 |    | 1 1 1 | 1 1 |
*
*   Thus now that we have the signals r and s (and their inverse
*   counterparts R and S), it's easy to construct any Boolean function of
*   x, y, and z, using only AND and OR gates:
*     X = (R & S) | (R & s & (y | z)) | (r & S & (y & z))
*   Proof:
*    1> x, y, z are all 0s, (R & S) = ~(r | s) = 1, obviously X=Y=Z=1, X = ~x;
*    2> (x, y, z) has at least one 1, R & S = 0, will be ignored, hence we
*       have:
*         X = (R & s & (y | z)) | (r & S & (y & z))
*    2.1> (x, y, z) has two or three 1s, R = ~r = 0, (R & s & (y | z)) = 0,
*         will be ignored, then we get:
*           X = S & (y & z)
*    2.1.1> (x, y, z) has three 1s, S = ~s = 0, obviously X=Y=Z=0, X = ~x;
*    2.1.2> (x, y, z) has two 1s, S = ~s = 1, will be ignored, hence we have:
*             X = y & z
*    2.1.2.1> (y, z) has one 1, x = 1, X = y & z = 1 & 0 = 0, X = ~x;
*    2.1.2.2> (y, z) has two 1s, x = 0, X = y & z = 1 & 1 = 1, X = ~x;
*    2.2> (x, y, z) has one 1, r = 0, (r & S & (y & z)) = 0, will be ignored,
*         we have:
*           X = y | z
*    2.2.1> (y, z) has one 1, x = 0, X = y | z = 1 | 0 = 1, X = ~x;
*    2.2.2> (y, z) has no 1s, x = 1, X = y | z = 0 | 0 = 0, X = ~x.
*    In conclusion, X = ~x for all cases.
*   QED.
*
* Algorithm II:
*   Internal Nodes:
*   _2or3_1s = ((x & y) | (x & z) | (y & z));
*   _0or1_1s = !(_2or3_1s);
*   _1_1     = _0or1_1s & (x | y | z);
*   _1or3_1s = _1_1 | (x & y & z);
*   _0or2_1s = !(_1or3_1s);
*   _0_1s    = _0or2_1s & _0or1_1s;
*   _2_1s    = _0or2_1s & _2or3_1s;
*
*   Equations for Outputs:
*   X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
*   Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
*   Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));
*
* Analysis II:
*   Almost the same as Analysis I.
*
* [1] http://www.edadesignline.com/howto/191600992
* ===========================================================================
*/

#include <stdio.h>

typedef unsigned int BOOL;

int main()
{
int i, fail;
BOOL x, y, z, X, Y, Z;
BOOL r, R, s, S;
BOOL _2or3_1s, _0or1_1s, _1_1, _1or3_1s, _0or2_1s, _0_1s, _2_1s;

/* ==================== Algorithm I ==================== */
printf("Algorithm I:n");
fail = 0;
for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    r = (x & y) | (x & z) | (y & z);
    //R = !r;                               /* #1 NOT gate. */
    R = ~r & 1;                             /* #1 NOT gate. */
    s = (R & (x | y | z)) | (x & y & z);
    //S = !s;                               /* #2 NOT gate. */
    S = ~s & 1;                             /* #2 NOT gate. */
    /* Output. */
    X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
    Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
    Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
}
if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
} else if (!fail) {
    printf("ALL TEST PASSED!n");
}

/* ==================== Algorithm II ==================== */
printf("Algorithm II:n");
fail = 0;
for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    _2or3_1s = ((x & y) | (x & z) | (y & z));
    //_0or1_1s = !(_2or3_1s);               /* #1 NOT gate. */
    _0or1_1s = ~(_2or3_1s) & 1;             /* #1 NOT gate. */
    _1_1     = _0or1_1s & (x | y | z);
    _1or3_1s = _1_1 | (x & y & z);
    //_0or2_1s = !(_1or3_1s);               /* #2 NOT gate. */
    _0or2_1s = ~(_1or3_1s) & 1;             /* #2 NOT gate. */
    _0_1s    = _0or2_1s & _0or1_1s;
    _2_1s    = _0or2_1s & _2or3_1s;
    /* Output. */
    X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
    Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
    Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
}
if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
} else if (!fail) {
    printf("ALL TEST PASSED!n");
}
return 0;
}

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 整除，则： a^p-1 = 1(mod p)。或者另一种形式：a^p=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 = M^emod n。（为什么明文是数字？在计算机科学里任何数据最终表示都是数字。）
解密算法：
假设 C 是密文，那么明文就是 M = C^d mod n。

我们来证明一下算法是否正确，由于 C^d = M^e*d = M^k*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的，显然直接由欧拉定理我们就能得到：
C^d = M^k*Φ(n)*M¹ = 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
由费马小定理，我们有：M^e*d = M^k*(p-1)+1 = M(mod p) 和 M^e*d = M^h*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数，且 p, q 均整除 M^e*d-M，所以我们有：
C^d = M^e*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 = g^x mod p，给定 g,x 求 y 是简单的，但给定 y,g 求 x，即求 x = log_g,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 在计算上是不可行的，就保证了算法的安全性。

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

薄弱的算法基础

这几日复习累时，翻出来 MIT 的《算法导论》课程录像来看，发现一个非常沮丧的事实：我对算法知道的真少。

仅仅看了 3 节课，就听到了几个我不懂的东西。比如计算递归算法复杂度的 master method，计算 Fibonacci 数列的复杂度为 θ(lg(n)) 的算法，计算矩阵相乘的复杂度为 θ(n^log₂(7)) 的 Strassen 算法。这些东西我以前都没听说过，真是孤陋寡闻啊！

那本《算法导论》大概在我的书架上已经摆了两年了，两年我仅仅看了六七十页。我太懒是最主要的原因，但还有一个原因是从头开始看激发不了兴趣，前面讲的一些算法都是数据结构书上看过的东西，不是很有吸引力，看着看着就觉得索然无味，扔一边了。

不过我也从来没自诩过算法好，逛 BBS 时我主要在电脑技术版转，在其它的版都敢指手画脚一番，唯有在算法版老老实实潜水。计算机科学就是这样，知识层次不如别人，那就根本插不上话。这也是我极少在 pongba 兄的 TopLanguage 讨论组发言的一个原因，因为里面我感兴趣的话题主要是算法相关，而算法问题我又插不上嘴，只好默默潜水。

我的算法知识，大概仅限于我现在都不知道扔哪儿的一本《数据结构》书了。不是科班出身，也没正儿八经听过算法课，所以现在就有系统地学习算法知识的打算了，把存在电脑里好久的算法导论视频翻了出来。Charles Leiserson 讲的很不错，单就趣味性来说，《算法导论》的课程录像可比书要有意思多了。我想在最近的这段时间里，我应该至少能把录像看完。

另外，我在博客分类里添加了 Algorithm 一项，我将看看，在过一段日子后，我对算法的使用和理解能力能否有一些提高。