第110章 百万富翁问题 (3-2)

后者倒是还好，表示自己听说过这个，“我记得提出这个问题的人是一位图灵奖得主来着。”

“哈哈，是的。”克莱因洛克点点头，说道：“说起来，这位图灵奖获得者和萧易一样，也都是华国人，他的英文名叫做安德鲁·姚，中文名好像是叫做姚启智吧。”

“简单来说，百万富翁问题就是，假设有两位分别叫做爱丽丝和鲍勃的百万富翁，现在想要比较他们谁更加有钱，但是他们又不想向对方暴露自己到底有多少钱，那么在这种情况下，他们该如何进行财富上的比较呢？”

说着，克莱因洛克也在黑板上写下了描述。

【假设爱丽丝和鲍勃两个人的财产分别为i、j，并且i、j的大小都位于1百万到10百万之间，那么要如何让对方不知道i或j的具体数字，而实现对i、j大小的比较？】

看着这个问题，陶哲轩倒是知道该怎么解决，不过梅纳德和萧易就开始思考了起来。

这个问题看上去也挺有意思的。

稍稍过了一会儿，给这两位留下了一点思考时间，不过克莱因洛克也并没有想过让他们现场解答，随后就开口道：“好了，这个问题咱们可以之后再……”

“等等。”

然而就在这个时候，萧易开口了，“我想，这个问题也许可以这样解决。\b”

随后他便走到了黑板前，拿起笔开始写了起来。

【设M是一个所有元素为N-bit非负整数的集合，QN是M到M的置换群。】

“如果我的设计没有出错，只要按照接下来的这个协议进行比较，他们就可以在对自身资产保密的情况下完成财富对比。”

“首先，爱丽丝从QN中随机选择一个元素Ea作为公钥，并将其告诉给鲍勃，同时保留Ea的逆Da作为私钥自己保留。”

“然后，鲍勃随机选择一个N-bit的整数x，并利用爱丽丝给的公钥计算k=Ea(x)……”

随着萧易的讲述开始，旁边的三个人就略显沉默了起来。

他们相互对视一眼，对眼前这一幕有些猝不及防\b。

特别是詹姆斯·梅纳德。

虽然吧，这个问题如果真的要仔细研究一下的话，也不至于难住他，作为一道类似数学建模题而言，它的难度也就那样。

毕竟，这个问题都已经完全具体化了，从抽象程度来说，它和梅纳德研究的那些解析数论上面的问题比较，实在是太小儿科了。

但是，要让他这么快就能够反应过来，并且直接就开始给出方案，那就有些做不到了。

看着萧易已经写了半个黑板的东西，梅纳德第一次体会到了什么叫做【降维打击】。

大概他以前在自己的学生面前展示什么叫做【顶级数学逻辑思维】的时候，他的学生们也是这样的感觉吧？

简直是开了挂了！

克莱因洛克的反应和梅纳德也差不多，本来吧，他提出这个问题也没想过让他们当场解决出来，刚才留了那么几分钟的时间，也只是让他们对这个问题稍微熟悉一些。

结果，谁成想，这才几分钟过去，这个年轻人就已经开始动笔写了起来。

原谅他作为一名计算机科学家，数学上面真的不是特别好，至少相比起这些数学家们来说，毕竟有一句话说得好，只有真正数学好的人才能够一直扎根于纯数学，数学不好的人早早地就转行了。

但是吧，萧易的这个“数学很好”，未免好得有些超出他想象了。

“第4步，爱丽丝随机生成一个N/2-bit的素数p，并计算Zu=yu mod p，其中u=1，2，…，10。”

“然后我们保证，所有zu中至少有两个不相等，否则重新x选择p计算……”

“爱丽丝将素数p以及【z1，z2，…，zi，zi+1】……重新标记为……”

“鲍勃检查第zj`，若zj`=x mod p，则说明i大于或等于j，否则i小于j。”

学霸就是要肝提示您：看后求收藏（百发小说网http://www.baifabohui.com），接着再看更方便。