兩個素數打贏的戰爭
來源:科學松鼠會 文章作者:安婆婆 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的兩個素因數語焉不詳,你有興趣算算是哪倆數么?
相關文章
- 小學1-6年級作文素材大全
- 全國小學升初中語數英三科試題匯總
- 小學1-6年級數學天天練
- 小學1-6年級奧數類型例題講解整理匯總
- 小學1-6年級奧數練習題整理匯總
- 小學1-6年級奧數知識點匯總
- 小學1-6年級語數英教案匯總
- 小學語數英試題資料大全
- 小學1-6年級語數英期末試題整理匯總
- 小學1-6年級語數英期中試題整理匯總
- 小學1-6年語數英單元試題整理匯總