首页 > 试题广场 >

Alice有一份很长的n位文件复印件A=n-1su...

[问答题]
Alice有一份很长的n位文件复印件A=<an-1, an-2,...,a0>,Bob也有--份类似的文件B=<bn-1, bn-2，...，b0〉。Alice 和Bob都希望知道他们的文件是否一样。为了避免传送整个文件A或B,他们运用下列快速的概率检查方法。他们共同选择-一个素数q>1000n,并从{0, 1，....q一1}中随机选取一个整数x。然后，Alice 求出
                                                      
的值，Bob 也用类似方法计算出B(x)。证明:如果A≠B，则A(x)= B(x)的概率至多为1/1000;如果两个文件相同，则A(x)的值必定等于B(x)的值。
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 285浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号