看守打算和 A 、 B 两名囚犯做一个游戏。首先，看守从一副牌中取出大小王，将剩余的 52 张牌洗好，并在桌子上从左至右地把它们摆成一排，每张牌都是正面朝上。然后，看守让囚犯 A 来到桌前，允许囚犯 A 观察牌面，并交换其中两张牌的位置。接着，看守将囚犯 A 关回牢房，把所有牌全都翻到背面朝上（但位置不变），让囚犯 B 来到桌前。看守随便报出一张牌的花色和点数（比如“梅花 3”），要求囚犯 B 找出这张牌。囚犯 B 每次可以翻开任意一张尚未翻开的牌，但一共只有 26 次机会。如果囚犯 B 在这 26 次机会之内找到了看守想要的牌，则两名囚犯赢得游戏，无罪释放；如果囚犯 B 翻开了 26 张牌之后，还没找到看守想要的牌，则两名囚犯输掉游戏，立即死刑。在整个游戏开始之前，两名囚犯可以商量一个策略；游戏开始后，两人就不能有任何其他形式的交流。果不其然，这又是一个关满了数学天才的监狱。两名囚犯碰头后，很快就商量出了一种必胜的策略。这种必胜的策略是什么？
协议
趣题：怎样向别人证明两个图不同构？
若干个顶点（vertex）以及某些顶点对之间的边（edge）就构成了一个图（graph）。如果图 G 和图 H 的顶点数相同，并且它们的顶点之间存在着某种对应关系，使得图 G 中的两个顶点之间有边，当且仅当图 H 中的两个对应顶点之间有边，我们就说图 G 和图 H 是同构的（isomorphism）。直观地说，两个图是同构的，意思就是它们本质上是同一个图，虽然具体的画法可能不一样。下面的两个图就是同构的。其中一种顶点对应关系是： 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。
目前，人们还没有找到任何高效的算法，能迅速判断出两个图是否同构。在普通计算机上，判断两个图是否同构，这需要花费大量的时间。因此，人们经常以图的同构为例，来解释复杂度理论和现代密码学中的诸多概念。
假设你家里的计算机十分强大，能很快判断出两个图是否同构，还能在两个图确实同构的情况下，给出一种顶点对应关系。但你的同桌家里的计算机却非常弱，没法做什么大型运算。课堂上，老师向全班展示了两个很复杂的图，不妨把它们叫作图 G 和图 H 。老师布置了一个特别的选做题：判断出这两个图是否同构。每个同学都可以提交答案，答案里只需要写“是”或者“不是”即可。按时提交答案并答对者，期末考试会获得 5 分加分；按时提交答案但答错了的，期末考试成绩将会倒扣 30 分；不参与此活动的同学，期末考试既不加分也不扣分。显然，每个同学都不敢随意提交答案，除非百分之百地能保证自己获得的答案是正确的。回到家后，借助家里的超级计算机，你很快判断出了这两个图是同构的。你给你的同桌发送了信息：“我已经算出来了，这两个图是同构的。”但是，你的同桌却回复说：“你不会是骗我的吧？”你打算怎样说服他，这两个图确实是同构的呢？
趣题：如何在数据库中秘密地查询隐私数据
日常生活中经常会出现这样的场景：你想在数据库上查询某个东西，但却不希望留下线索，让别人知道你查询了什么。比方说，投资人可能会在数据库上查询某支股票的信息，但却不希望任何人知道他感兴趣的股票究竟是哪一支。看上去，似乎唯一的办法就是把整个数据库全部拷回家。然而，这些数据往往都拥有非常庞大的体积，全部拷走通常都是很不现实的；另外，考虑到数据内容的隐私性和数据本身的宝贵价值，数据的持有者通常也不允许其他人把整个数据全盘拷走。不过，随着分布式数据库的广泛应用，上面的难题有了一个两全其美的好办法：假设有两个内容完全相同的数据库，投资人可以先在第一个数据库上执行一个不会透露目的的查询，再在另一个数据库上执行另一个不会透露目的的查询，两次查询结合起来便能推出想要的结果。只要没有人刻意去收集并且对比两个数据库的查询记录，那么谁也不会知道投资人真正想要查询的是什么。在这个背景下，我们有了下面这个有趣的问题。
服务器随机产生了一个 {1, 2, …, 100} 的子集 S ，并且同时发送给了 A 和 B 两名前台工作人员。 A 、 B 两名前台都接受其他人的提问，但为了保护数据，两个人都只能用“是”或者“否”来回答问题，并且都不允许同一个人重复提问。你非常关心某个数 n 是否在这个子集里。其实，你本来可以直接问 A 和 B 中的任何一个人“数字 n 是否在集合 S 里”，但是这样一来，对方就知道了你想要查询的是什么。为此，你可以向 A 和 B 各问一个问题（结合两人的回答便能推出集合 S 里是否包含数字 n ），但却不能让 A 和 B 当中的任何一个人知道你查询的是哪个数（我们假设 A 、 B 两人不会串通起来，把他们各自收到的问题联系在一起）。事实上，你需要保证 A 和 B 两人都不能从你的问题中获取到任何信息，也就是说，对于 A 和 B 当中的任何一个人来说，各种问题出现的概率不会随着 n 值的改变而改变。再换句话说，如果 n 的值变了，那么 A 和 B 各自将会听到的问题应该拥有和原来相同的概率分布。
跨越千年的RSA算法
数论，数学中的皇冠，最纯粹的数学。早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》，但受篇幅限制，只有一万字左右的内容。其实，从数论到 RSA 算法，里面的数学之美哪里是一万字能扯完的？在写作的过程中，我查了很多资料，找到了很多漂亮的例子，也积累了很多个人的思考，但最终都因为篇幅原因没有加进《程序员》的文章中。今天，我想重新梳理一下线索，把所有值得分享的内容一次性地呈现在这篇长文中，希望大家会有所收获。需要注意的是，本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释，一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述，可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后，希望大家能够积极指出文章中的缺陷，我会不断地做出修改。
======= 更新记录 =======
2012 年 12 月 15 日：发布全文。
2012 年 12 月 18 日：修改了几处表达。
2021 年 9 月 13 日：根据 Chang 的指正做了修改。
======== 目录 ========
（一）可公度线段
（二）中国剩余定理
（三）扩展的辗转相除
（四）Fermat 小定理
（五）公钥加密的可能性
（六）RSA 算法
趣题：八根并排放置的水管
下面这个有趣的问题来自于 2012 年 4 月的 IBM Ponder This 谜题。
有 8 根很长的并且颜色不同的水管并排放在一起， A 、 B 两人分别位于这些水管的两端。两个人手中各有若干根很短的橡皮管，他们可以用这些橡皮管任意连接自己这一侧的水管口。 A 的旁边还有一个水龙头， A 可以用橡皮管把水龙头与自己这一侧的其中一个水管口相连。
A 、 B 两人各将获得一个五位 01 串，然后两人可以根据自己手中的 01 串来连接水管口。当 A 打开水龙头后，容易看出，水必然会从其中一侧流出。两人需要保证，如果两人手中的 01 串相等，则水从 A 的一侧流出，否则水从 B 的一侧流出。他们事先可以商量一个策略，但游戏一旦开始，两人一旦拿到各自的 01 串之后，就不允许再交流了（因此两人都不知道对方手中的 01 串是什么）。请你想出一个能保证两人获胜的策略。