在單射成立的情況下,只要有一方是確定的,便能求出另一方,只是在不同的情況下,求解的難易程度差距很大。用N=p×q(p和q為質數)表示的質因數分解,可以作為一個代表性的例子供我們解讀。在講解質數的時候我曾提到過,質數中之所以不包括1,是為了讓數與數的分解質因數結果一一對應。即,確定N分解成p×q的結果只有一種,當然p和q相乘得到的N也只有一個結果。
我們對21這個數進行分解質因數。
21=3×7
很簡單吧?但是,如果讓大家對367153進行分解質因數呢?我想99%的人都會撓頭。然而,我只用了30秒的時間就解除了這道題(我用了計算器)。
367153分解質因數的結果如下:
367153=571×643
兩個質數相乘,就算得到的結果再大你也不會覺得困難。但是,如果讓你對一個較大的數進行分解質因數,求出原本的質數組合,就沒那麼容易了。「單射關係成立,得出結果很簡單,但變回原樣很難」,這是分解質因數的特性,許多密碼的設置正是運用了這個特性。
以N=p×q為基礎設定的密碼,稱為RSA公鑰加密法,這種加密法廣泛地應用於網絡和現金卡的密碼中。以前的密碼只要知道加密的方法,便能解讀出密碼,所以如何嚴守加密的方法成為一個大問題。RSA公鑰加密法在加密時使用了N,在解讀時使用了p×q,所以即使公開了加密的方法,也無法輕易解讀,可以說RSA公鑰加密法是一種劃時代的加密法。
順便說一下,如今加密法中的N用的是數百位的龐大數字,另外,2010年發布的研究報告指出,300臺電腦在3年間不停運轉,通過分解質因數得到的數是232位數。
因此,目前我們無需擔心自己現金卡的密碼會被快速解讀出來。