奥数网
全国站
您现在的位置:奥数 > 小学数学网 > 数学故事 > 正文

两个素数打赢的战争

来源:科学松鼠会 文章作者:安婆婆 2009-07-03 10:28:05

  宁小宝上课又迟到了。历史老师正在回顾地球人和天煞星人因为抢夺小行星资源引发的那场战争。这个本想溜进来的倒霉蛋刚好被逮到:“宁小宝,你能不能告诉大家,这场战争的导火索是什么?”小宝当场就凝固在那里了,额头上一滴汗。老师的眼睛扫向全班,所有的头都埋得更低了。老师叹了口气,恢复了机械的语调:“银历339年,天煞星人违反公约,抢先向蝎虎座ADS 16402 B的小行星带进行挖掘,地球人为了维护星际公平正义,决定对其进行武装打击……”这单调的语声就是小宝耳中可以自动过滤的背景音乐,他只顾着启动座位上的电脑屏幕,悄悄地迅速翻过防火墙,查看他订阅的游戏新闻。

  “快讯:‘小行星哀歌’的制作公司乐得迷于今日在全球范围发行历史手册,给玩家提供更有策略的通关技巧。点击查看详情。”点进去,有样书章节预览。“银历339年,天煞星人和地球人之间爆发了一场激烈的战争。”小宝心头一跳,原来‘哀歌’的游戏背景是这个啊。老师正在调试他的星空投影仪,寻找战略地图。小宝继续拉下滚动条:“星际公约中规定,蝎虎座ADS 16402 B区域的小行星属于公共资源,于银历338年由天煞星和地球共同出资买下。然而双方在后续的分配中未能达成协议,地球在小行星带的巡航机器人捣毁了天煞星的挖掘机,引发了双方机器人的激烈对抗。”

  “宁小宝!”老师的吼声吓了他一跳。“又是你动了我的星空仪,对不对!上来给我弄好!”下面有人在窃笑,历史老师束手无策的样子让小宝很得意,边往讲台走边回头做着鬼脸。系统的密码被破解然后改掉了,老师没法登陆进去。

  很快,蓝色的激光亮了起来,一幅星空图笼罩了整个教室。几个桔黄色箭头指的地方,就是无数机器人当年的葬身之地。“战斗异常惨烈,每天都有无数的零件飞入虚空成为星际的尘埃。双方的远星系巡航机器人都在锐减,双方的高层们也意识到这对本星球的防御体系是很不利的损失,因为需要很多地球年才能将新的机器人补充到那么遥远的地方去。于是战争在两个地球天之后停止了。”“啊?”全班异口同声。小宝很不解:“不打了,争端怎么解决呢?”老师拍了拍他的脑袋:“谈判啊。好了你回座位去吧。”

  “两个星球争论的焦点集中在其中一颗比较大的小行星,勒格-B上,因为它含有丰富的硅。大家知道,在后信息时代,硅是银河系中需求量最大的元素之一。地球和天煞星都同意,如果一方得到勒格-B,另一方就得出让十颗含硒的小行星。可是,双方都不肯轻易放弃这颗‘硅星’,谈判陷入了僵局。”

  “那就抽签吧!”有同学恶作剧地喊道。

  悬案

  “阿毛,这其实是个好主意。”没想到历史老师马上首肯了这个建议。“后来两个星球都同意抛硬币来解决。”

  全班同学的脸上都写满了惊讶的表情。抛硬币?这怎么可能呢?地球人都知道,这是一项需要面对面进行的活动。一个人挑正反面,一个人抛,两个人都看到结果是什么才行。可是迄今为止,银河系内的高级生命还没有互相见过面呢。没有哪一族可以把活体发送到300光年以外的地方去,所有的远程探索都是通过机器人和量子通讯来实现的。银河系里充斥着各种流言,说这些高级智慧之间互相发送的量子名片上,种族的头像都是PS过的。既然连这个都没法求证,更没法抽签了啊。小宝的脑中浮现出一幅景象—— 天煞来信:地球人,你们选什么?地球回信:选正面。天煞回复:错了,反面朝上,你们输啦!——“哈哈哈哈哈!”小宝忍不住大笑起来:“老师,这太荒谬啦!”

  历史老师的定力可不是一天炼成的,他关上星空仪,打开幻灯片:“当然这不是很容易的事情。两星球首脑首先决定让小行星带的机器人会面,用四处漂浮的残片打造了一个硬币来抛。结果地球新闻发布了你们历史书里的这张图片,我们赢了。可是,天煞星一口咬定他们看见的是‘天煞胜’,谴责地球在耍赖。双方仍旧争执不下,至于那个遥远的硬币到底哪一面朝上,已经成了历史的谜团。”

  “那么,我们需要一个第三方的见证人。”小宝认真地说道。

  “对的,所以星际联盟调用了附近的维和机器人赶去观看,并把信号发回星际总部。”

  “谁赢了?”全班再次激动了。

  “不知道。”历史老师耸耸肩。“信号在发送的途中遭受有预谋的干扰,无法识别。到底干扰波来自地球还是天煞星,这又是一个历史谜团。总之,联盟也无法判断硬币是哪一面朝上。”

  “啊……”一片惋惜之声。

  “真相就这么难以看见吗?!”小宝愤愤地一捶桌子。

  “同学们,今天的课程就到这里。天煞星和地球是如何解决争端的,是这次的家庭作业。请你们回去好好查资料,把你得到的史实写成一个小报告,说说你对这一事件的看法。记得按时交。下周见。”

  启示

  小宝回到家就把这事忘得一干二净。周六游泳回来,他打开“小行星哀歌”,决定把很久都没通的那关再试一遍。转眼间,星尘激扬,碎片横飞,他的地球战队损失惨重。系统弹出了熟悉的对话框:“天煞请求谈判,是否接受?请注意地球防线也已告急!”若是往日,小宝肯定毫不犹豫地选择“否”。他的原则一向是永不妥协死光为止的。可是这次,他想起了历史课,一下子恍然大悟:哦,原来谈判才是通关的关键啊。

  突然他记起了老师布置的作业——不管,先通关要紧。游戏的界面中出现了一个远程会议室,房间前面赫然挂着一个大屏幕,显示着天煞星首脑发来的谈判讯息。“地球人,你们准备好了吗?现在发送数字:n=2836921和c=2539740。我们在1到n之间选择了一个数m,m的立方除以n的余数是c。请猜测m是奇数还是偶数。”天,数学!小宝最讨厌的就是数学,他从来就没算清过买游戏时找的零钱够不够。奇数吧奇数吧,他咬牙选中奇数的按钮。“现在发送数字:m = 1692704,请核对m的立方除以n的余数是否正确。”小宝用电脑的计算器算了一下,果然。只好点正确。那么m是偶数,他猜错了。“n是下面这两个素数的乘积,请核对是否正确。”小宝把屏幕上显示的两个数字输入计算器,乘积确实是n,只好又点正确。“恭喜你们,地球人!勒格-B现在是我们的啦!祝你们和十颗含硒小行星玩得愉快!再见~!”小宝眼前一黑,屏幕上出现了大大的“Game Over”。

  什么嘛!欺负我数学不好!乐得迷真是个破公司!找个数学家来算一下就完了嘛,历史上怎么会拿这个来谈判?话说这个神秘的抛硬币事件到底是怎么回事?小宝从来没有对历史课的作业如此火烧眉毛。他气急败坏地骑上自行车,往学校的资料馆飞驰而去。

  真相

  历史部在“银历339年”的条目下面有8847963条数据。继续缩小范围,关于“谈判”有700条数据。他肾上腺素的分泌加快了,一目十行地扫视,忽然一个条目映入眼帘:“利用密码学抛硬币促成了最终协议的签署”。密码学?

  “密码的原理就是把真实信息通过几个转换步骤,变成另外一副相貌,让其它人无法通过外表来猜到隐藏的真相。由地球人在地球历20世纪首创的密码学,更是为银河系的安全作出了杰出贡献。他们甚至连转换的步骤都一并告诉你,你也无法猜到原始信息是什么。就像在天地二星谈判桌上发生的一样:地球人知道编码的结果n和c,并且知道用于编码的公式:m的立方除以n余数为c。但他们无法推出m是奇数还是偶数,除非能把n分解素因数。可是,n被设计成两个素数的乘积,要知道当两个素数都很大的时候,分解n是十分困难的。比如,当两个素数都超过77位数时,银河系里最先进的计算机,使用目前最先进的算法,也得花上宇宙年龄的几百分之一吧。何况此次谈判中使用的素数有154位,到那时,小行星带说不定都消失了……”小宝倒吸一口凉气,看来乐得迷公司还是很尊重史实的,只不过替换成了几个小数字而已。原来不是我数学不好的问题呀,这玩意儿只能靠猜……那么猜对猜错都是一半的几率咯?哦!!他高兴地叫起来,我明白了!怪不得叫做抛硬币,两者是一样的原理。只不过天煞星人抛的是一个数字m,正反面变成了奇偶数而已!那……地球人到底猜对了没啊?他迫不及待地往下阅读。

  “地球人在这场硬币战争中脆败,他们猜错了。天煞星人发回的m值和两个素数经过验证准确无误,地球人接受了谈判结果,带走了10颗硒星。这未尝不是一个皆大欢喜的结局。地球人的失败说明他们无法解码自己发明的编码方式,意味着他们的密码学是何等强大!这场小规模战争给星际空间增添了一些垃圾,然而整个银河系都从中受益。各星球纷纷起而效仿地球人的网络安全办法,学习他们给信息加密的方式。我们今天的和平有相当的功劳要归于他们祖先的智慧。而天煞星的IT产业也在勒格-B的基础上蓬勃发展起来,成为了今日银河系的领头羊。”

  回到家,小宝兴奋地在历史作业中写道:“老师,您该换一个密码了……”

  延伸阅读

  这篇小说的灵感来自于一个真实的事件:1998年,网络安全专家Marc Joye和Sung-Ming Yen共同完成了一篇学术文章,准备在国际会议上作报告。但是该由谁来演讲呢?当然是抛硬币决定最公平。可他们分别住在世界的两个角落,没办法碰面。于是这俩密码学专家想出用电子邮件来抛硬币的办法,结果Sung-Ming Yen输了,只好去做报告。

  Yen把这件事写在自己的网页上,十年后被我无意中看到了。这么精彩的东东怎么能忍得住让它继续埋没在数字大海中呢?于是我决定四处八卦。这里是他的原文:

  http://www.csie.ncu.edu.tw/~yensm/funny/coinflip.html

  实际上,这个简单的例子可以做出让人眼花缭乱的延伸,其后的思想也可以回溯到费马的定理。Yen在文末提出的几个“小”问题,有同学想挑战一下吗?小说里对‘小行星哀歌’中给出的n的两个素因数语焉不详,你有兴趣算算是哪俩数么?