Flipping Coins By Telephone（电话硬币问题）

故事的背景是这样的：

Alice和Bob本是一对（程序员/数学家）夫妻，因为不知道哪个筋搭错了决定离婚，对于财产的归属，他们决定采用抛硬币的方式决定。然而两个人都在气头上，见面不免要打起来，于是两个人决定通过打电话的方式来进行猜硬币这一过程。然而，如果其中一个人说“我刚扔了硬币，我猜对了你猜错了”，另一个人肯定不信对吧（腹诽：我**又不是傻*），于是他们想出了如下的方法：

0. 前提：无法在多项式时间内完成质数乘积的分解。

例：对于143这个数，Bob无法快速给出143=11*13这个答案。

1. Alice出题：Alice任选两个质数p、q，计算n = p * q并将n告诉Bob。

Alice在电话里把n的值（143）告诉Bob，却不告诉Bob这个数是哪两个质数（11、13）的乘积。

2. Bob接招：Bob随机选择一个小于n的整数x，计算z = x^2 mod n并将z告诉Alice。

Bob这时候正在看NBA比赛，想到自己最喜欢的球员是科比，于是选择x=24， 算出z = 24^2 mod 143 = 4，将4这个数告诉Alice，却不告诉她x的值（24）。

3. Alice抉择：解出x的两个可能的正整数值，猜测哪个是Bob所选择的并告诉Bob。

Alice收到z=4，通过中国剩余定理（刚看到这个名字的时候我也是很震惊……）得出x的两个可能的值（请参考中国剩余定理，此处不占篇幅）：x1 = 2, x2 = 24。

4. Bob公布答案：Alice是否猜对了自己选择的x值。如果Bob声称Alice猜错了而Alice不服，Bob须给出n的质因数分解；如果Bob无法给出n的质因数分解，则必须承认Alice猜对了。

Bob能给出n的质因数分解的充要条件：Alice猜错了x的值并告诉了Bob。

一方面，若Alice猜对了x的值，则Bob在仅知道自己给出的x值的情况下无法给出n的质因数分解（前提条件）；

另一方面，若Alice发送给Bob的是猜错的x值，那么Bob可通过x1、x2两个值算出p、q两个质因数。

若Bob收到的x值为2，可做出如下计算：

24^2 mod 143 = 4

2^2 mod 143 = 4

So: 

24^2 = 2^2 (mod 143)

(24^2 - 2^2) mod 143 = 0

143 | (24+2)*(24-2) // a | b 表示 a整除b，即b mod a = 0

由于143为两质数之积，两个括号必然能各被其中一个质数整除，求出最大公约数即可：

p = gcd(143,26) = 13

q = gcd(143,22) = 11

一种可能（Alice猜错了，Bob给出n的质因数分解而获胜）：

Bob：“抱歉，我现在知道143=11*13了，是不是你猜错了？”

Alice：“打得好，我认输……”

另一种可能（Alice猜对了，Bob无法给出n的质因数分解，Alice获胜）：

Alice：“你快说啊，143是哪两个质数的乘积？说不出来算你输哦~ ”

Bob：“我选择死亡……”

参考文献：

1. Flipping Coins By Telephone, Department of Electrical and Computer Engineering, University of Toronto

2. 两个人如何通过电话「扔硬币」？ - AC-130H的回答 - 知乎 https://www.zhihu.com/question/30824110/answer/119343068

最后

以上就是羞涩电脑为你收集整理的Flipping Coins By Telephone（电话硬币问题）的全部内容，希望文章能够帮你解决Flipping Coins By Telephone（电话硬币问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。