從無窮求和到RSA加密

新用戶05287284 2021-12-09

展開全文

由于一個理論模型過于頭疼,，所以打算寫點東西放松一下,。

正好也已經(jīng)很久不寫東西了，最近數(shù)學(xué)界又有兩件大事,，所以打算寫點東西,。

對于黎曼Zeta函數(shù)，最早接觸是在調(diào)和函數(shù)中：

$\sum_{i=1}^\infty \frac{1}{i}$

這個級數(shù)當(dāng)然是發(fā)散的,，不過它很有趣,，因為有一個常數(shù)就和這個調(diào)和級數(shù)相關(guān)：

$\gamma = \lim_{n \rightarrow \infty} \sum_{i=1}^n \frac{1}{i^s} - \ln(n)$

調(diào)和級數(shù)當(dāng)然可以進一步拓展，比如p-級數(shù)：

$Z_p = \sum_{i=1}^\infty \frac{1}{i^p}$

顯然,，這個無窮級數(shù)求和的收斂半徑是 $\Re(p) > 1$ ,，這個級數(shù)就是收斂的,，而如果 $\Re(p) \le 1$ ,，那么級數(shù)就是發(fā)散的。

比如如果p=1,，那么就是調(diào)和級數(shù),，它是發(fā)散的；如果p=0,，那么就是無窮個1相加,，也是發(fā)散的；如果p=2,，那么結(jié)果是有限的,，為 $\frac{\pi^2}{6}$ 。p在小于0的時候是一些有趣的無窮級數(shù)求和,，比如p=-1時是所有自然數(shù)之和,，p=-2時是所有自然數(shù)的平方和，等等,。顯然所有這些無窮級數(shù)的和都是發(fā)散的，這點毫無疑問,。

但,，數(shù)學(xué)上有個東西叫做“解析延拓”，它的作用就是,，如果某個函數(shù)的定義域是 A,，那么我們可以通過解析延拓，將其推廣到包含A的更大的范圍B中,，如果能延拓的話,。

比如說,，大家都熟悉下面這個幾何級數(shù)：

$1 + x + x^2 + x^3 + ... = \sum_{i=0}^\infty x^i = \frac{1}{1-x}\ \ \ \ \ \ \ \ \ \ \ \ (|x| < 1)$

最左側(cè)的幾何級數(shù)，其收斂半徑是1,。而且當(dāng) $x=1$ 時,，級數(shù)發(fā)散；當(dāng) $x=-1$ 時,，級數(shù)在0和1上振蕩,，沒有普通定義下的求和值，但有Abel求和定義下的求和值： $\frac{1}{2}$ ,。而如果 x>1 或 x<-1 ,，那么這個級數(shù)求和顯然是發(fā)散的（但存在拉馬努金和）。

可最右側(cè)的函數(shù),，只要 $x \neq 1$ 就有定義,，從而定義域比級數(shù)求和的定義域要大得多，是級數(shù)求和的解析延拓的結(jié)果,。很顯然,，后者在 |x| > 1 的區(qū)域所得到的值，并不是前者的求和值,，前者的求和值依然是無窮,，所以上面第二個等號雖然寫是這么寫，但實際上并不是真的相等,。

顯然并不是所有函數(shù)都可以被延拓,，但上面的p-級數(shù)求和，恰恰就是可以延拓的那種,。

p-級數(shù)可以寫成積分的形式：

$Z(s) = \sum_{i=1}^\infty \frac{1}{i^s} = \frac{1}{\Gamma(s)} \int_0^\infty \frac{x^{s-1}}{e^x - 1} dx = \zeta(s)$

這里用到了 $\Gamma$ 函數(shù)的性質(zhì),，很容易就能推得。這個函數(shù)的定義域也是 $\Re(s) > 1$ ,，但和無窮級數(shù)求和不同,，現(xiàn)在它已經(jīng)變成了定義域內(nèi)的解析函數(shù)。

利用 $\Gamma$ 函數(shù)的性質(zhì)： $\Gamma(z) \Gamma(1-z) = \frac{\pi}{\sin (\pi z)}$ ,，以及負實軸上的圍道積分,，我們還可以將黎曼 $\zeta$ 函數(shù)進一步解析延拓：

$\zeta (s) = \frac{\Gamma(1-s)}{2 \pi i} \oint \frac{z^{s-1} e^z}{1 - e^z} dz$

這里圍道積分沿著從實軸負無窮到0再回到負無窮的高度趨向0的逆時針閉合回路,。這樣,，就可以將函數(shù)解析延拓到 $\Re(s) \le 1$ 的部分了，只留下 s=1 這一個極點,。

由此可得一個很有用的等式：

$\zeta(1-s) = 2 (2\pi)^{-s} \Gamma(s) \cos \left( \frac{s \pi}{2} \right) \zeta (s)$

這使得我們在求一些 $\zeta$ 函數(shù)值的時候可以方便很多,，比如很顯然s為負偶數(shù)的時候函數(shù)值為0,。

至此，我們就完成了從最開始的p-調(diào)和級數(shù)的求和到黎曼 $\zeta$ 函數(shù)的解析延拓,。

在原級數(shù)求和的定義域中,，我們有 $\zeta(s) = \sum_{i=1}^\infty i^{-s}$ ,，但在原定義域之外則沒有這個關(guān)系，這就和之前舉的幾何級數(shù)求和的例子相同,。

所以,，雖然我們有 $\zeta(-1) = - \frac{1}{12}$ ，但并不表示下面這個無窮級數(shù)求和等式成立：

$1 + 2 + 3 + 4 + ... = - \frac{1}{12}$

因為左邊的求和并不直接等于p-級數(shù)求和的解析延拓,，而后者是p-級數(shù)求和的解析延拓的結(jié)果,。

這就是很多看似奇葩的求和結(jié)果的來源，一個看著明顯發(fā)散或者振蕩總之不收斂的級數(shù),，都和一些意想不到的常數(shù)通過等號聯(lián)系了起來,，使得很多人覺得莫名其妙，但本質(zhì)上這里的等號都不是真的表示其左右的級數(shù)和常數(shù)是相等的,，而是表示級數(shù)的解析延拓在給定參數(shù)下等于另一側(cè)的常數(shù),。

事實上，對于無窮級數(shù)的求和,，除了通常的“加法”和“收斂極限”,，還有很多不同的方法，比如對于振蕩級數(shù)的平均收斂極限,，對應(yīng)的就是Abel和,；或者拉馬努金由歐拉-麥克勞林公式得到的拉馬努金和。這些“求和”都與我們平常所理解的求和不同,，如果不明確其定義,，直接看著等式望文生義的話，往往會認為等式結(jié)果非?？尚Α?/p>

從另一個角度來說,，這些解析延拓與求和往往都是通過在原函數(shù)定義域之外丟掉一些無窮大來實現(xiàn)的,，比如最簡單的就是之前的幾何級數(shù)求和的例子，其有限部分和為：

$J_n(x) = \sum_{i=0}^n x^i = \frac{x^{n+1} - 1}{x - 1}$

當(dāng) $n \rightarrow \infty$ 時,，如果 |x| < 1 ,，那么 $x^{n+1} \rightarrow 0$ ，所以結(jié)果自然得到我們之前所熟悉的分式,。而當(dāng) |x| > 1 時,， $x^{n+1} \rightarrow \infty$ ，是一個發(fā)散項,，但在 $\frac{1}{1-x}$ 中卻將這個發(fā)散項給移除了，只保留有限項部分,。當(dāng) |x| = 1 時,，我們得到的是一個模為1的不定項,，在一般級數(shù)極限的意義下將導(dǎo)致級數(shù)沒有收斂極限。

這點在物理上其實很常見,，我們在做量子場論時經(jīng)常會遇到各種無窮,，然后在這些無窮中扣除一部分與物理無關(guān)的無窮，保留下和物理相關(guān)的有限部分,，這個過程就是“正規(guī)化”（找到物理相關(guān)部分的過程是“重整化”,，扣除的部分是“正規(guī)化”）（所以弦論中上述所有自然數(shù)之“和”等于-1/12的情況是有的，但那是在重整化意義上的“相等”）,。在解析延拓的過程中,，我們也可以認為是做了一次正規(guī)化，當(dāng)然具體情況要具體分析,。

回過頭來繼續(xù)說黎曼 $\zeta$ 函數(shù),。

前面已經(jīng)提到， $\zeta(-2n)=0$ ,，這些負偶數(shù)的零點（即函數(shù)值為0的點）被稱為平凡零點,。但 $\zeta$ 函數(shù)本身除了這些平凡零點，還包含無數(shù)個非凡零點,，著名的“黎曼猜想”就是針對這些非凡零點的分布的,，簡單說來就是：

黎曼猜想：黎曼 $\zeta$ 函數(shù)的所有非凡零點的實部分都為 $\frac{1}{2}$ 。

這個猜想寫起來非常簡單,，但實際上要證明卻是非常困難的,。

人們已經(jīng)對大量（數(shù)十億個）非凡零點做了研究，發(fā)現(xiàn)都滿足黎曼猜想,，但這樣只能增加人們的信心,，卻并不是證明了黎曼猜想，畢竟發(fā)現(xiàn)再多非凡零點也不過是有限個,，對無限個非凡零點,，證明力依然很小。

比如說,，素數(shù)定理告訴我們 $\lim_{n \rightarrow \infty} \frac{\pi(x)}{\mathrm{Li}(x)} = 1$ （其中 $\pi(x)$ 是素數(shù)計數(shù)函數(shù),，即小于x的素數(shù)的個數(shù)），且在人們驗證了的范圍內(nèi)都有 $\mathrm{Li}(x) > \pi (x)$ ,，但數(shù)學(xué)家們證明了在大約 $e^{727.95133}$ 左右（大約是一個316位數(shù)）,，這個不等式會不成立。

可見,，有限個數(shù)的驗證對無窮來說,，真的沒什么說服力。

那么,，黎曼 $\zeta$ 函數(shù)到底為什么這么重要呢,？

一個最直接的作用,，就是它能提供精確的素數(shù)計數(shù)函數(shù)（也就是上面提到的 $\pi(x)$ ）。

我們還是從p-級數(shù)開始看起（下面對于求和如果不另外寫明,，則對n的求和表示對所有自然數(shù),，對p的求和表示對所有素數(shù)）：

$\sum_n \frac{1}{n^s} = \prod_p \frac{1}{1 - p^{-s}}$

這個等式被稱為歐拉乘積公式，其證明過程很容易,，將所有自然數(shù)項根據(jù)素數(shù)從小到大進行篩選,，在利用 $\Re(s) > 1$ 時的幾何級數(shù)求和公式，就能得到,。

從而,，考慮解析延拓則有： $\zeta(s) = \prod_{p} \frac{1}{1 - p^{-s}}$ 。兩邊取對數(shù),，再考慮泰勒展開,，就有：

$\ln \zeta(s) = \sum_p \sum_n \frac{1}{n} p^{-ns}$

我們可以引入一個輔助函數(shù)，稱為黎曼素數(shù)計數(shù)函數(shù)J(x),，它是一個很奇特的階躍函數(shù)：

$J(x) = \sum_n \frac{1}{n} \pi(x^{\frac{1}{n}})$

也就是說,，每經(jīng)過一個素數(shù)的n次方，該函數(shù)增加 $\frac{1}{n}$ ,，且 J(0)=0 ,。因此我們就有 J(2_+)=1 、 J(3_+)=2 ,、 J(4_+)=2.5 ,、 J(5_+)=3.5 、 J(6_+)=3.5 ,、 J(7_+)=4.5 ,、 $J(8_+)=\frac{29}{6}$ 、 $J(9_+)=\frac{16}{3}$ ,，其中下標+表示比該值略大（右極限）,，而在該點處的值為左右極限的平均值。

然后,，我們可以使用黎曼-斯蒂爾杰斯積分（一種分區(qū)取樣求和然后取極限的積分法,，是初學(xué)積分時的矩形分割法的升級版）：

$\lim_{n \rightarrow \infty} \sum_{i=0}^{n-1} f(t_i) [g(x_{i+1}) - g{x_i}] = \int_a^b f(x) dg(x)$

其中 x_0 = a 、 x_n = b ,， t_i 是分片區(qū)間 $(x_i, x_{i+1})$ 中的取樣值,。

由于黎曼素數(shù)計數(shù)函數(shù) J 是一個階躍函數(shù)，所以如果取它為上述積分公式中的g,，那么積分就變成了求和,。而又由于階躍點在素數(shù)的n次方，所以我們就有：

$\int_0^\infty f(x) dJ(x) = \sum_p \sum_n \frac{1}{n} f(p^n)$

于是，我們就可以把歐拉乘積公式改寫為積分形式：

$\ln \zeta(s) = \int_0^\infty x^{-s} dJ(x) = s \int_0^\infty J(x) x^{-s-1} dx$

這樣,，黎曼 $\zeta$ 函數(shù)就和黎曼素數(shù)計數(shù)函數(shù)聯(lián)系在了一起,。

我們進一步用Mellin變換，就可以將黎曼素數(shù)計數(shù)函數(shù)用黎曼 $\zeta$ 函數(shù)表達出來了：

$J(x) = \frac{1}{2 \pi i} \int_{a - i \infty}^{a + i \infty} \frac{\ln \zeta(z)}{z} x^z dz$

其中a是大于1的實數(shù),。

而黎曼素數(shù)計數(shù)函數(shù)與素數(shù)計數(shù)函數(shù)之間可以用逆莫比烏斯變換來聯(lián)系：

$\pi (x) = \sum_n \frac{\mu (n)}{n} J(x^{\frac{1}{n}})$

其中 $\mu (x)$ 是莫比烏斯函數(shù)，它有如下特點：

如果x能寫成偶數(shù)個不同素數(shù)的乘積,，則值為1,；
如果x能寫成奇數(shù)個不同素數(shù)的乘積，則值為-1,；
否則為0,；
規(guī)定 $\mu(1) = 1$ 。

因此,，很顯然,，只要我們能得到黎曼 $\zeta$ 函數(shù)的完整信息，就能得到黎曼素數(shù)計數(shù)函數(shù)J(x),，進而就能得到素數(shù)計數(shù)函數(shù) $\pi(x)$ ,。也就是說，只要掌握了黎曼 $\zeta$ 函數(shù),，就能知道素數(shù)到底是怎么分布的——也就是說,，我們能找到每一個素數(shù)了。

而,，要計算黎曼 $\zeta$ 函數(shù),，我們還需要從輔助用的黎曼 $\xi$ 函數(shù)入手：

$\xi (s) = (s-1) \pi^{-\frac{s}{2}} \Gamma \left( \frac{s}{2} + 1 \right) \zeta(s)$

黎曼 $\xi$ 函數(shù)利用 $\Gamma$ 函數(shù)以及開頭的 s(s-1) ，將原來 $\zeta$ 函數(shù)中的所有平凡零點和極點都消除了,，從而是一個在整個復(fù)平面都解析的整函數(shù),，并且它的零點就是 $\zeta$ 函數(shù)的非凡零點。

這個函數(shù)有兩個很獨特的性質(zhì)：

$\xi (s) = \xi (1-s)$

以及更重要的：

$\xi(s) = \frac{1}{2} \prod_\rho \left( 1 - \frac{s}{\rho} \right)$

這里無窮乘積是對所有黎曼 $\xi$ 函數(shù)的零點求積,。

這么一來,， $\zeta$ 函數(shù)的對數(shù)就可以寫為：

$\ln \zeta(z) = - \ln(s - 1) + \sum_\rho \ln \left( 1 - \frac{s}{\rho} \right) - \ln \Gamma \left( \frac{s}{2} + 1 \right) - \ln 2 + \frac{s}{2} \ln \pi$

代入黎曼素數(shù)計數(shù)函數(shù)，用一定技巧化簡后就得到了這么一個東西：

$J(x) = \mathrm{Li}(x) - \sum_\rho \mathrm{Li}(x^\rho) - \ln 2 + \int_x^\infty \frac{dt}{t(t^2-1) \ln t}$

其中,， $\mathrm{Li}(x) = \int_2^\infty \frac{dx}{\ln x}$ 就是前面提到的對數(shù)積分,。

至此， $\zeta$ 函數(shù)的非凡零點對素數(shù)計數(shù)函數(shù)的作用終于變得顯然了（所以上述公式被稱為黎曼顯式公式）,，也因此,，我們掌握的非凡零點的精確值越多，我們就能得到越精確的素數(shù)計數(shù)函數(shù),，從而也就能得到越精確的素數(shù)分布,。

當(dāng)然，這里不得不說的是，計算非凡零點,，尤其是其精確值的難度,，比判斷一個數(shù)是不是素數(shù)要難得多得多得多得多得多。在沒有計算機之前,，手算也只能得到幾百個零點,，但找素數(shù)那可以找?guī)兹f個，只要有耐心——算非凡零點可不是光有耐心就足夠的,。

那么,，黎曼猜想如果被證實了，對我們尋找素數(shù)能帶來多大的影響呢,？

事實上,，影響并不是非常大。

我們可以看到,，在黎曼素數(shù)計數(shù)函數(shù)中出現(xiàn)了素數(shù)定理中所提到的對數(shù)積分,，以及由非凡零點調(diào)制的高階項（第三項是常數(shù)，第四項隨著x的增大而縮小,，可以認為是高階誤差項）,，而從聯(lián)系 J(x) 與 $\pi(x)$ 的那個逆莫比烏斯變換的公式可以看到，其中最主要的共享就來自于 J(x) ,，因此可以說非凡零點決定了 $\pi(x)$ 與 $\mathrm{Li}(x)$ 之間的偏離程度,。

如果黎曼猜想成立，那么這兩個函數(shù)之間的偏離基本就是 $\mathrm{Li}(\sqrt x)$ 的量級,。但如果黎曼猜想不成立,，考慮到 $\xi$ 函數(shù)的對稱性我們可以知道，兩者的偏離就會達到 $\mathrm{Li}(x^{\frac{1}{2} + \delta})$ 的量級,，其中 $\delta > 0$ ,。

另一方面，如果黎曼猜想成立,，我們只需要集中精力在臨界線 $\Re(s) = \frac{1}{2}$ 上尋找非凡零點就可以了,，這對我們計算來說會帶來一定的便捷——但實際上，現(xiàn)在計算零點很多都是在約定黎曼猜想成立的前提下進行的,，數(shù)以千計的命題也都是建立在這個假設(shè)成立的基礎(chǔ)上,，所以如果真的被證明成立，對已有內(nèi)容其實不會帶來太大的影響,，最多就是讓本來就已經(jīng)很放下的心,，放得更下一點罷了。

當(dāng)然,，也還有一些很讓人出乎意料的領(lǐng)域可能會有影響,，比如物理。

有一個“Hilbert-Pólya猜想”，是這么說的：

黎曼 $\zeta$ 函數(shù)的非凡零點與某個厄米算符的本征值對應(yīng),。

或者簡單一點說,，就是存在一個量子系統(tǒng)，其本征能態(tài) E_n 對應(yīng)了黎曼 $\zeta$ 函數(shù)的非凡零點 $\frac{1}{2} + i E_n$ ,。

事實上,，我們有Montgomery-Odlyzko 定律：

黎曼 $\zeta$ 函數(shù)的非凡零點分布可以用任何一個典型隨機厄米矩陣的本征值分布來描述。

這次數(shù)學(xué)家Atiyah用來證明黎曼猜想的尚未公開的方法（本文寫于22號,，Atiyah將于24號公布其成果,，所以寫本文的時候方法尚未公開），就有人相信是采用了這種“量子證明法”,，構(gòu)造了可能如下形式的哈密頓量：

$\hat H = \frac{1}{1 - e^{-i \hat p}} (\hat x \hat p + \hat p \hat x) (1 - e^{-i \hat p})$

然后使用算子理論對其進行譜分析所得到的結(jié)論。

總之,，就個人來看,，由于現(xiàn)在其實很多人都在默認黎曼猜想成立的情況下進行數(shù)學(xué)工作，得到了很多有意思的結(jié)論,，那么進一步證明這個猜想真的成立,，也不會突然帶來巨大的進展或改變——假如說證明它不成立，那帶來的沖擊才叫大呢,。

那么,，它和RSA加密又有什么關(guān)系呢？

RSA加密的本質(zhì),，其實是大素數(shù)分解,，即我們要在知道兩個很大的素數(shù)p和q，然后使用它們的一些數(shù)論結(jié)果來進行數(shù)據(jù)的加密（基本都是模運算）,。

要破解RSA加密,，那本質(zhì)就是在知道p和q的乘積N的情況下，逆向找出p和q,。

由于這里涉及的都是素數(shù),，所以自然會有人認為如果黎曼猜想被證明成立，那么RSA就岌岌可危了,。

這純粹是危言聳聽胡說八道,。

首先，就算黎曼猜想被證明成立,，我們計算非凡零點的進程也依然不會有什么加速——因為,，人們早就在默認黎曼猜想成立的情況下來尋找非凡零點了（當(dāng)然，數(shù)值驗證猜想的人并不局限在這點上,，然后數(shù)十億,、百億的結(jié)果都支持黎曼猜想）。

其次，就算黎曼猜想的證明讓我們突然能很快地找到所有非凡零點,，從而找出素數(shù)分布的精確模式,，也就是俗話所說的找到了素數(shù)地圖，那么也不表示破解RSA所要的從N=pq找出p和q就會變得很快,，畢竟,，知道有哪些素數(shù)，和找出符合條件的素數(shù),，是兩碼事,，后者的所要求的計算量依然是 $O(\pi(\sqrt N))$ 級的。

這就好比說,，我告訴你房間里五個開關(guān),，控制五盞燈，讓你找出哪一個開關(guān)控制哪一盞燈,，然后告訴你這五個開關(guān)具體的位置,，能降低你開關(guān)燈的次數(shù)么？并不能,。

充其量,，是我們生成素數(shù)的算法可以有改進——這還是在能從黎曼猜想帶來非凡零點計算的加速這個假設(shè)上來的，而這個假設(shè)本身并不成立,。

要攻破RSA,，還是期待量子計算機吧——量子Shor算法理論上可以將大數(shù)素數(shù)分解的計算復(fù)雜度降低到 $O(\ln N)$ 的量級，這才叫提速,。

本文遵守創(chuàng)作共享CC BY-NC-SA 4.0協(xié)議