注册

当你穿越到道诡异仙的世界,如何利用密码学知识区分幻想和现实?

《道诡异仙》是一部流行的网络小说。


其中,剧情讲述了男主角李火旺穿越到诡异世界,但意识时不时会回到原来的现代社会中。两个世界时不时交错,男主角陷入到了混乱当中,一直在疑惑到底哪边世界是真实的,也因此发展出了精彩的故事。


那么,作为一个程序员,如果面临这样的处境,有没有办法利用专业知识区分世界是否是真实的呢?


其实不论什么样的异世界,数学始终不变,我们可以利用密码学背后的数学原理,来检查一个世界是否是真实世界。


在剧情中,男主角李火旺一直怀疑他所处的“现代世界”是幻觉,那么,我们很容易想到,幻觉没办法伪造算力,只要我们构造一个需要一定算力的数学问题,再交给“现代世界”的女主角杨娜去找计算机计算就可以了。


但是考虑到书中"诡异世界"并没有关于计算的神通,其数学发展水平也有限,所以我们构造出的问题应该是难以计算,但是又易于检验的。这样的问题与密码学所需的数学原理非常相似,我们可以利用一个简单的事实:



计算两个大质数的乘积非常简单,但是把两个大质数的乘积质因数分解却非常困难。



所以我们可以设计这样一个方案:



  1. 首先教会"诡异世界”一侧的女主角白灵淼学会基本算术(只要到整数乘法就可以了)。接下来,指挥白灵淼生成两个大质数,并且把它们的乘积告诉男主。
  2. 待男主穿越回“现代世界”,把这个乘积告诉"现代世界"女主角杨娜,请她去找计算机计算它的质因数分解,之后再告诉男主。
  3. 男主回到诡异世界,检查"现代世界"给出的质因数分解结果是否正确,如果正确,那么"现代世界"必定是真实的。

那么,如何在基础算术之内,生成较大的质数呢?我们可以利用费马小定理:



如果p是一个质数,而整数a不是p的倍数,则a^(p-1) 除以p余1 。



实际上,取a为偶数,ap−1×p+1a^{p-1} \times p+1ap1×p+1在多数情况下都是质数。在不那么严格的情况下,我们完全可以把这些伪质数当作质数来使用。


针对验证世界是否存在算力的场景,我们只需要选择两个大约几十万的整数就可以了,比如:


125−1∗5+1=10368167−1∗7+1=32659312^{5-1} * 5+1 = 103681\\
6^{7-1} * 7+1 = 326593
12515+1=1036816717+1=326593

如果怕踩到坑,可以拿一些小质数试验一下。


之后我们计算它们的乘积,得到了 338614888333386148883333861488833


这些计算量稍微有点大,但是应该还在小白的能力范围内,最多花上一个小时,足够完成计算了。


注意,为了防止幻觉作弊,小白只告诉李火旺最终的乘积,不需要告诉李火旺两个质因数。


接下来,让我们的主角回到"现代世界",把338614888333386148883333861488833交给"现代世界"女主角杨娜,要求她找计算机和程序员对33861488833做因式分解。


接下来杨娜大约要花一点钱,比如她找到了winter,因式分解的代码这样写:


let p = new Array(Math.ceil(Math.sqrt(33861488833))).fill(1)

p[0] = 0;
p[1] = 0;
for(let i = 2; i < p.length; i++) {
if(i === 0)
continue;
if(33861488833 % i === 0)
console.log(i);
for(let j = i * 2; j < p.length; j += i)
p[j] = 0;
}

//运行结果:103681

用计算机计算这个循环只需要几秒,但是如果是人肉计算,这个工作量几乎是不可完成的。


幻觉再怎么厉害,也不可能帮助李火旺超越数学,算出这个因式分解的结果。


如果在"现代世界"中,算出了正确的因式分解结果,因为李火旺本人并不知道质因数,所以可以确定不可能是李火旺的幻觉。


这样就可以验证"现代世界"的真实性了。


换句话说,即使"现代世界"是幻觉,那也是一个有巨大算力的幻觉系统,那么《道诡异仙》的故事可能就变成另一种风格了。


作者:winter
来源:juejin.cn/post/7250718023815528485

0 个评论

要回复文章请先登录注册