質因數和密電碼,複雜的問題有了新發展

2020-12-05 中學數學精準輔導

數學來源於生活。我們所學的數學知識,都是直接或間接地為實際服務的。大家都知道,小學學分解質因數是為了學習分數的需要。因為分數的加減法要用到通分,乘除法要用到約分,而通分、約分需要用到分解質因數。除此而外,分解質因數還有什麼用,大家可能就不知道了。前幾年,美國數學家把分解質因數問題應用於密電碼,為國家安全保密工作找到了一條新的途徑。

我們需要先講一點密碼學。把明文變換成密文,需要兩個元素:變換的規則和變換的參數。前者是編碼的算法,例如「在英文字母表上前進x步」。後者是密鑰,例如上述算法中的x這個數。如果取x = 1,明文的「fly at once」(立即起飛)就會變成密文的「gmz bu podf」。

最容易想到的保密框架,是通信雙方都知道同一組密鑰,A用它將明文轉換成密文,B用它將密文變換回原文。《紅燈記》、《潛伏》等諜戰片中情報人員捨死忘生、殫精竭慮保護和爭奪的密碼本,就是密鑰。由於通信雙方都知道同一組密鑰,所以這種方法叫做「對稱密碼體制」。對稱密碼體制究竟安全不安全呢?回答是:密碼本身可以是安全的,但密鑰的分發不安全。

在易守難攻的數學問題中,「因數分解」就是一個典型例子。目前世界最常用的密碼系統之一,就是基於因數分解的RSA(這是三位發明者的首字母縮寫)公鑰密碼體制。

把兩個質數相乘,這是很容易的事。可是,反過來,要想把一個相當大的數分解為質因數的乘積,就不那麼簡單了。例如,計算29與31的乘積,這是不難的,答案是899。但反過來,若要把899分解為質因數,就不那麼容易了。至於要分解更大的數,就更困難了。下面是分解幾個大數的質因數所需用的時間:

由表中可以看出,用筆算試除法來分解一個50位的大數,竟需要約100億年的時間,這實際上是不可能做到的事。而用電子計算機,只要15秒鐘就可以完成。可是,也應該看到,對於更大的數,即使用電子計算機,目前也是很費事費時的。例如一個1000位大的大數進行分解,就需用連續一星期的時間。至於更大的數,那困難就更大了。大數難分解,國家安全機關就把這種「難」的原理應用到密電碼上,為國家的安全保衛工作立了大功,且被銀行和工礦企業廣泛應用。

原來,在具體編碼時,是用01、02、03、04、……09、10、11、……26分別表示英文的26個字母,將電文中的單詞按字母的順序「翻譯」成數,然後按照一定的方法進行編碼。由於人們只知道大數(即質因數的乘積),而不知道這些質因數,因此並不知道電碼的秘密。唯一能破譯這種密電碼的是掌握質因數這個「謎底」的人。

目前世界最常用的密碼系統之一,就是基於因數分解的RSA(這是三位發明者的首字母縮寫)公鑰密碼體制。

解釋一下,因數分解指的是把一個合數分解成兩個質因數的乘積,例如21 = 3 × 7。分解21當然輕而易舉,你不管三七二十一就能分解它。不過,來分解2^67 – 1 = 147,573,952,589,676,412,927看看?這是個18位數。1644年(李自成進北京那一年),人們以為它是一個質數。直到1903年(清朝都快亡了),人們才發現它是一個合數,等於193,707,721 × 761,838,257,287。分解這個數,幾乎花了一個朝代的時間!

為什麼會這麼困難呢?用計算機科學的語言說,隨著位數的增加,因數分解的計算量是「指數增長」的,而指數增長是一種非常快的增長,比「多項式增長」要快得多。

具體一點說,如果計算機一秒做1012次運算,那麼分解一個300位的數字需要15萬年,分解一個5000位的數字需要50億年,——地球的年齡也不過是46億年而已!

公鑰密碼體制的安全性,依賴於數學問題的困難性。但是,計算量是與算法有關的。比如說你要計算17乘以28,愚笨的做法是把17個28一個個加起來,聰明的做法是按照多位數的乘法列出算式,後者顯然比前者快得多。

對於像因數分解這樣的難題,人們在不斷尋找更好的算法。我們肯定的只是,在目前公開的最好的算法下,因數分解的計算量是指數增長的。將來有沒有可能找到更好的算法,把計算量減到可破解的程度?當然有可能。這還只是就公開資料而言。更令人夜不安寢的是,能解密的算法也許已經被某些國家、某些組織掌握了,只是沒有公布!

當然,隨著電子計算機的不斷發展,人們對質因數的分解也會逐漸取得新的突破,今天分解不了的大數,明天就可能分解。到那時,分解質因數的奧秘將逐一被揭穿,而這種密電碼的安全性就成問題了。因此,密碼學處於一種無止境的軍備競賽對抗之中,一方提出更強的攻擊算法,另一方提出更強的保密算法,無限地循環下去。而量子密碼術,改變了密碼攻防的基本格局,量子密碼術是目前唯一能從原理上證明安全性的密碼體制。

量子通信具有很多特點,與傳統的通信方式相比較,量子通信最大的優勢就是不可比擬的高安全性和高效率性。首先,傳統通信方式採用加密方式保證信息的安全,比較容易被破解。量子通信利用光量子的不可複製性,其密鑰不是固定的,充滿隨機性,即使密鑰被截獲也無法被破譯。因此,理論上量子通信可以做到絕對安全。其次,量子編碼的效率非常高,是兩個量子自旋態的組合態。因此,用少量光子可以傳輸大量的信息。此外,量子通信還有較強的抗幹擾能力、很好的隱蔽性能及較低的噪音比等特點。

量子通信根據應用途徑,可分為量子密碼通信、量子遠程傳態和量子密集編碼等。按所傳輸光的特性,可分為經典通信和量子通信,前者主要傳輸量子密鑰,後者則可用於量子隱形傳態和量子糾纏密鑰的分發。當前,量子通信為滿足通信過程中較高的保密需求,主要採用量子糾纏態,隨著技術不斷進步,量子通信的內涵也將不斷延展。

2017年8月,世界首顆量子科學實驗衛星「墨子號」在國際上首次實現千公裡星地雙向量子糾纏分發、星地高速量子密鑰分發、地星量子隱形傳態;「天宮二號」成功實現了基於小型化終端的星地量子密鑰分發。2017年9月,世界首條連接多個城市的量子通信「京滬幹線」正式開通;同時,結合「京滬幹線」和「墨子號」的天地鏈路,實現了世界首次洲際量子視頻通信,標誌著我國已構建天地一體化廣域量子通信網絡雛形。

相關焦點

  • 量子計算機分解的最大質因數有新紀錄了!
    我們知道破解加密涉及到相當複雜的技術,破解與反破解總是在不斷升級之中。現在由於量子技術的發展,量子計算機有一天可能會通過破解加密而威脅到網際網路的安全。最近量子計算初創公司Zapata與IBM合作開發了一種分解大數字的新方法,成功將其應用到迄今為止量子計算機所能分解的最大質因數上,該進展可能讓量子技術距離加密破解又近了一步。
  • 分解質因數
    前面我們已經學習過了質數與合數,這一期我們要學習的是進一步的內容:分解質因數。
  • 分解質因數注意點
    剛學分解質因數的時候,很多同學做題的過程當中出現的問題比較多。我們今天主要看一下分解質因數部分需要注意的問題。首先:分解質因數是什麼意思?把一個合數,分解成若干個質數相乘的形式,就叫做分解質因數。正確的寫法應該是:18=2x3x3這樣才叫做把18分解質因數。另外關於質因數的概念,有些同學也搞不清楚,比如說下面這個題:「3是質因數」這句話對嗎?當然不對,為什麼呢?
  • 從質因數入手,理解公因數和公倍數的本質關係
    從質因數入手,理解公因數和公倍數的本質關係   已知a與b、a與c、b與c的最小公倍數分別是60、90和36,問:
  • 日本開發出分解質因數專用計算機
    新華網東京9月2日電 (記者 錢錚) 日本研究人員最近利用安裝有專用晶片的並行計算機,對一個128位的數字完成了分解質因數的實驗,這在世界上尚屬首次。   除了1和本身以外,不能被其他正整數所整除的整數叫做質數。所謂分解質因數,是指將一個數分解成質數相乘的形式。
  • 專題講解——短除法分解質因數
    把一個合數,分解成若干個質因數的乘積的形式,即求質因數的過程叫做分解質因數。分解質因數隻針對合數。
  • 巧妙使用分解質因數解答題目
    通過下面一道題目,考考你對質數和合數定義的理解。猜一猜下面的8位數是多少?通過上面的內容回憶,正式展開本篇內容「分解質因數及其解題應用」的論述。定義說:把一個合數分解成若干個質因數的乘積的形式,即求質因數的過程叫做分解質因數。
  • 有趣的數學-分解質因數
    把一個自然數分解成若干個質因數的乘積的形式,即求質因數的過程叫作分解質因數。在這裡,我大致介紹一下這個概念的定義。因數:整數相乘,整數就是積的因數質因數:顧名思義,既是質數又是因數分解質因數的順序1)依此除以能整除的質數2)把用於分解的質數和最後剩下的質數寫成乘積形式分解質因數時使用的短除號就是倒過來的除號
  • 2020省考行測技巧:巧用質因數分解解決乘積問題
    通過分析這類題目多為幾個數相乘的形式,下面中公教育專家為各位考生介紹如何巧用質因數分解解決幾個數乘積的問題。一、質因數分解的定義定義: 將一個合數分解為幾個質數相乘的形式。比如:136=2×2×2×17二、質因數分解的應用例1 :某種產品每箱48個。小李製作這種產品,第1天製作了1個,以後每天都比前一天多製作1個。X天后總共製作了整數箱產品。問X的最小值在以下哪個範圍內?
  • 五十八、如何對一個數進行分解質因數
    「---- Runsen」❞先問你們一個小學問題:「什麼是質因數?小學是對一個數進行分解質因數」上次,我介紹了短除法,短除法其實是一種分解質因數的方法。分解質因數隻針對合數。(分解質因數也稱分解素因數)求一個數分解質因數,要從最小的質數除起,一直除到結果為質數為止。分解質因數的算式叫短除法,和除法的性質相似,還可以用來求多個數的公因式。將需要分解的數字從2開始遍歷,則分解的結果都會是質數。需要分解的數字是每一次上次分解之後的結果。
  • 運算1個月 完成一個128位數字的質因數分解
    日本研究人員最近利用安裝有專用晶片的並行計算機,對一個128位的數字完成了分解質因數的實驗,這在世界上尚屬首次。  除了1和本身以外,不能被其他正整數所整除的整數叫做質數。所謂分解質因數,是指將一個數分解成質數相乘的形式。
  • 淺談將一個正整數分解質因數的邏輯思維和Python開發設計
    今天討論的是如何將一個正整數分解質因數。例如:輸入36,列印出36=2*2*3*3。1.首先要清晰兩個概念,要知道什麼是質數,如何進行分解質因數?質數是指在大於1的自然數中,除了1和它本身以外不再有其他因數的自然數。分解質因數是把一個正整數用質因數相乘的形式表示出來。2.
  • 淺析有源功率因數校正技術及發展趨勢
    近幾年來,為了符合國際電工委員會61000-3-2的諧波準則,功率因數校正電路正越來越引起人們的注意。功率因數校正技術從早期的無源電路發展到現在的有源電路;從傳統的線性控制方法發展到非線性控制方法,新的拓撲和技術不斷湧現。本文歸納和總結了現在有源功率因數校正的主要技術和發展趨勢。
  • ghpython_分解質因數
    今天咱們繼續來看老潘微博裡的一個python小案例,將一個合數分解質因數,我記得以前中學課本裡,咱們用的是短除法來做,就是用合數依次去除以每一個質數,將能被整除的質數記錄下來,最後將合數轉化為多個質數相乘的形式,就為分解質因數。今天咱們來看看用python怎麼做。
  • 寧波小升初數論知識點:質數合數、分解質因數(三)
    寧波奧數網小編將數論問題中幾個重要的知識點的習題講解整理出來希望對大家有所幫助。   質數、質因數和互質數這三個術語的概念極易混淆,因為它們都有「質」和「數」兩個字。正確地區分這幾個概念,對掌握數的整除性這部分基礎知識,有著極其重要的意義。   (1)質數:一個自然數,如果只有1和它本身兩個約數,這個數叫做質數(也稱素數)。
  • 2021年甘肅省考行測數量關係:分解質因數
    2021年甘肅省考行測數量關係:分解質因數 甘肅省公務員考試筆試內容包括:行政職業能力測試以及申論,其中《行政職業能力測驗》主要包括言語理解與表達、數量關係、資料分析、資料分析和綜合知識等部分。
  • 科學網—中科大在室溫固態體系中實現絕熱量子質因數分解
    本報訊(記者楊保國)中國科大杜江峰課題組利用金剛石中的自旋作為量子處理器,首次在室溫大氣條件下實現了基於固態單自旋體系的質因數分解量子算法
  • 五年級數學教學內容補充:分解質因數(學習必備收藏,轉發)
    在新的北師大版本當中分解質因數這節課已經被刪除,據專家講述由於涉及的數在100以內,數字相對比較小,分解質因數比較簡單。但在實際教學當中書本上的內容涉及的數字較小,對於學習水平在中間一下孩子們來說反而有些困難。所以後來專門又設計了這樣一節課,讓學生來了解一下分解質因數。
  • 中科大在室溫固態體系中實現絕熱量子質因數分解—新聞—科學網
    本報訊(記者楊保國)中國科大杜江峰課題組利用金剛石中的自旋作為量子處理器,首次在室溫大氣條件下實現了基於固態單自旋體系的質因數分解量子算法
  • 中國科大首次在室溫固態體系中實現絕熱量子質因數分解
    RSA密鑰體系是當今金融、網絡等領域普遍使用的加密方式,其之所以安全,是因為對經典計算而言,尚無有效的方法在合理的時間內完成大數的質因數分解。1994 年,美國科學家Peter Shor提出了基於量子計算機的質因數分解算法,即著名的Shor算法,從理論上證明量子計算機可以指數加速大數的質因數分解,使原本用當前最好的計算機也需要上萬年才能完成的計算任務,量子計算機瞬間即能完成。該算法的提出極大地推動了量子計算的研究進程。