數論在計算機科學中有哪些精彩的應用？

12-31

數學的許多分支都在計算機領域扮演著重要的角色，那麼產生了那麼多美妙的理論和猜想的數論，是不是也在計算機科學領域有著同樣美妙的應用呢？

那當然了，數論是支撐計算機科學的最重要的數學之一了，往大說有密碼學，往小說有hash演算法。

舉一個影響力非常大又通俗易懂的例子，RSA公鑰系統。

首先解釋一下相關概念，所謂公鑰系統是指一種不對稱的加密演算法。一般我們加密數據的時候，加密和解密需要使用相同的密鑰，這種叫做對稱密鑰系統，使用很廣泛，但是有一定局限性：必須有一個好的方法將對稱的密鑰安全交換到通信的雙方，否則如果這個密鑰丟了，加密的數據就會被人截走或者介入。

非對稱密鑰系統就厲害了，它有公鑰和私鑰兩把鑰匙，加密使用公鑰，解密使用私鑰，然而從公鑰幾乎不可能推算出私鑰，這樣我可以把公鑰隨便扔在們外邊，誰想給我發送加密信息都可以拿去用；加密完之後的數據，只有用我的私鑰才能解開，其他人即使知道公鑰也沒有辦法。這就非常有用了，最有用的用處之一就是交換前面的對稱密鑰，我先告訴你我的公鑰，你把對稱密鑰用我的公鑰加密發給我，我們就能安全交換對稱密鑰了。

RSA這個公鑰系統影響力非常大，目前看來也足夠安全，但是涉及到的知識完全在初等數論範圍內。我們通過選擇兩個非常大的質數p和q構造出這個公鑰系統，一般來說這兩個數需要在一千位二進位以上。記 $n = p q$ 是兩個質數的乘積，將兩個大數相乘相對簡單，而將n分解質因數變回p和q是極其困難的。同時我們計算出 $(p-1)(q-1)$ 。

現在我們任意選一個數 $e$ ，讓它與 $(p-1)(q-1)$ 互質。則根據初等數論的知識，一定存在一個同餘意義上唯一的 $d$ ，使得

$de equiv 1 pmod{(p-1)(q-1)}$

可以使用綜合歐幾里得輾轉相除法計算出 $d$ 。

接下來就是RSA演算法中最精華的一部分了。任取一個數C，C比p、q都小，因而與p、q互質。根據費馬小定理有：

$C^{p-1} equiv 1 pmod{p}$

$C^{q-1} equiv 1 pmod{q}$

因此有

$C^{(p-1)(q-1)} - 1 equiv 0 pmod{p}$

$C^{(p-1)(q-1)} - 1 equiv 0 pmod{q}$

由於p和q互質，因此 $C^{(p-1)(q-1)} - 1$ 是pq也就是n的倍數，即

$C^{(p-1)(q-1)} equiv 1 pmod{n}$

由於 $de - 1$ 是 $(p-1)(q-1)$ 的倍數，因此

$C^{de - 1} equiv 1 pmod{n}$

即

$C^{de} equiv C pmod{n}$

現在我們將 $(n, e)$ 這兩個數作為公鑰，將 $(n, d)$ 這兩個數作為私鑰。當我們要將一個數C用公鑰加密發送給私鑰持有者的時候，我們就計算

$C^{e} mod n$

僅僅根據這個值是很難重新計算回C的值的，即使知道n和e也不可以。但是當我們拿到這個結果，然後我們又知道n和d的時候，我們可以計算：

$(C^e mod n)^d mod n = C^{de} mod n = C$

哎呀不可思議，我們將原始的C解了出來。

注意到RSA系統中公鑰和私鑰是對稱的，除了前面的加密、解密作用以外，相同的RSA公鑰、密鑰系統還可以用來實現數字簽名，在數字簽名的時候，我們將需要簽名的內容通過SHA-1之類的Hash演算法計算出摘要，然後將摘要用私鑰進行加密，即計算 $C^d mod n$ 。加密的結果通過公鑰可以進行解密，解密後得到原始摘要；如果沒有私鑰，則不可能計算出可以解密得到原始Hash值的數值。如果有人在中途修改了被簽名的內容，則Hash值會改變，而修改的人得不到密鑰就無法重新簽名，就會導致簽名不匹配或者簽名無法驗證的情況出現。這樣可以有效防止經過簽名的內容被隨意篡改。

SSL當中廣泛使用的安全證書就使用了以上的加密演算法，它本身也使用簽名機制來確保安全證書本身不被篡改。操作系統和瀏覽器內置了一部分受信任的簽名機構的安全證書，稱作根證書；其他可信的證書必須由根證書籤名，或者由其他簽過名、且有相應授權的可信證書籤名，每一級簽名都可以確保這一級證書沒有被修改，一直追溯到根證書，這樣整個證書就能保證沒有被修改過。當證書被下載到客戶端並且通過了簽名認證之後，證書中的公鑰就可以用來進行加密，從而建立加密的連接。可以說今天幾乎所有的可信通信都建立在前面的簡單公式的基礎上，用到的知識不過是初等數論基礎知識和費馬小定理而已。

================================================================

補充一下，實際上如評論中所說，C&, 其中 $k < q$ 的情況即可（為q倍數時同理）

顯然有

$C^{(p-1)(q-1)} equiv 0 pmod p$

$C^{(p-1)(q-1)} equiv 1 pmod q$

於是有

$C^{de - 1} equiv 0 pmod p$

$C^{de - 1} equiv 1 pmod q$

即

$C^{de} equiv 0 equiv C pmod p$

$C^{de} equiv C pmod q$

由於p,q互質，因此

$C^{de} equiv C pmod n$

另外，雖然任意的C都可以用這種方法還原出來，但顯然並不適合加密C=0, C=1……

看到這個問題主要是想到了兩個（在計算機科學中經常用到）：

素性測試（即判斷素數），這是一個很有趣的問題，種類可以參見素性測試演算法，隨機演算法中最具有代表性的我覺得是Miller-Rabin素性測試法（數論部分第一節：素數與素性測試），一些實現的代碼可以看這裡（〖數學演算法〗素性測試）；確定性啟發演算法的代表是Baillie–PSW素性測試法(Baillie) 該演算法的反例是被證明存在的，但是在很大很大的數以內（大概是 $2^{64}$ ?）均成立所以請放心使用~

整數因子分解演算法：Pollard rho演算法詳解；
另外如果想了解 Floyd』s Cycle 演算法、Pollard rho演算法以及素數分解上面的一些（一點點）有趣的聯繫的話，可以參考鄙人的一篇博文從Happy num所想到的幾個問題

利益相關：CS業餘玩家

————————————

另外呢，數論相關的話不是一翻《演算法導論》就一大堆嗎？哈哈哈，如果是計算機科學和數學方面有趣的知識的話可以參考：計算機程序設計藝術（全套有點厚），裡面關於排序和隨機數的講解不能太棒

A few years ago, the following message was displayed to users who logged into my department"s thin client server:

Warning: Due to a known bug, the default Linux document viewer evince prints N*N copies of a PDF file when N copies requested. As a workaround, use Adobe Reader acroread for printing multiple copies of PDF documents, or use the fact that every natural number is a sum of at most four squares.

轉自quora

主要就是在密碼學計算機安全領域吧。md5，rsa，des等各種加密演算法都是以數論為依靠的。

比如說你的微信密碼。你的密碼在本地是經過密匙加密以後才發送到伺服器端的，在伺服器端再用密匙解密進行驗證。私有密匙公有密匙非對稱加密等等都是以數論為理論依據的。

看看計算機名著《計算機程序設計藝術》就知道數論是計算機的靈魂級的材料。