互联网的数学

1、丘成桐教授丘成桐教授美美 國國 哈哈 佛佛 大大 學學 數數 學學 系系 教教 授授 香香 港港 中中 文文 大大 學學 數數 學學 講講 座座 教教 授授香香 港港 中中 文文 大大 學學 數數 學學 科科 學學 研研 究究 所所 所所 長長菲菲 爾爾 茲茲 獎獎 得得 獎獎 人人 今日很高興的在這裏和公開大學的同學談今日很高興的在這裏和公開大學的同學談談我自己對數學服務社會的看法。談我自己對數學服務社會的看法。公開大學這麼多年來訓練了許多有上進心公開大學這麼多年來訓練了許多有上進心的青年，使我欽佩，在五十年代，除了香的青年，使我欽佩，在五十年代，除了香港大學外，沒有一家政府承認的大學，中港

2、大學外，沒有一家政府承認的大學，中文大學前身的崇基、新亞、聯合和當時的文大學前身的崇基、新亞、聯合和當時的浸會學院吸收了香港很多人材，當時無論浸會學院吸收了香港很多人材，當時無論老師和學生都很窮苦，但是以後卻成為社老師和學生都很窮苦，但是以後卻成為社會的中堅份子。我想公開大學的學生也會會的中堅份子。我想公開大學的學生也會成為香港的人材，為二十一世紀的新中國成為香港的人材，為二十一世紀的新中國服務。服務。這十多年來，香港、中國和整個亞洲社會都這十多年來，香港、中國和整個亞洲社會都逐漸轉型，尤其是中國改革開放以後，香港逐漸轉型，尤其是中國改革開放以後，香港社會所需要的人材更多姿多采。亞洲各國要社會

3、所需要的人材更多姿多采。亞洲各國要與全世界的經濟、文化、科學接軌，而中國與全世界的經濟、文化、科學接軌，而中國大陸和日本會領導亞洲的發展，所以香港的大陸和日本會領導亞洲的發展，所以香港的青年也應當訓練自己來適應這個趨勢。沒有青年也應當訓練自己來適應這個趨勢。沒有辦法迎接這個新時代來臨的青年恐怕要吃虧。辦法迎接這個新時代來臨的青年恐怕要吃虧。縱觀全世界大學訓練人材的最基本要求乃是縱觀全世界大學訓練人材的最基本要求乃是語文和數學，所有美國大學都看語文和數學，所有美國大學都看SAT的成績，的成績，而而SAT中最基本的乃是這兩門學問的考試。中最基本的乃是這兩門學問的考試。這為的是甚麼呢？這為的是甚麼呢

4、？語文訓練使我們能夠表達自己的意思，數語文訓練使我們能夠表達自己的意思，數學訓練讓我們具有推理的能力，沒有這兩學訓練讓我們具有推理的能力，沒有這兩種能力，我們實在很難說我們是具有文化種能力，我們實在很難說我們是具有文化氣息的現代人。氣息的現代人。很多人對於數學不切實際的看法，以為數很多人對於數學不切實際的看法，以為數學家都躲在象牙塔裏，不食人間煙火，這學家都躲在象牙塔裏，不食人間煙火，這是極為錯誤的看法。事實上，整個智識型是極為錯誤的看法。事實上，整個智識型的現代社會極度需要經濟、工程、管理等的現代社會極度需要經濟、工程、管理等等方面的人材，而在現代化的前提下，這等方面的人材，而在現代化的前提

5、下，這些人材都需要相當程度的數學訓練。些人材都需要相當程度的數學訓練。一般來說，數學訓練分兩個層次，一個層次一般來說，數學訓練分兩個層次，一個層次是在象牙塔裏的為了追求純真純美的研究，是在象牙塔裏的為了追求純真純美的研究，表面上這些研究與實用毫無關係，從前我們表面上這些研究與實用毫無關係，從前我們知道這些研究十多年或數十年後總會有大的知道這些研究十多年或數十年後總會有大的用場，但是近二十多年來，我們發覺純數學用場，但是近二十多年來，我們發覺純數學和應用的距離愈來愈縮小距離了。和應用的距離愈來愈縮小距離了。數學的第二個層次就是在各行業上的應用，數學的第二個層次就是在各行業上的應用，這是今天演講的

6、主題。這是今天演講的主題。二十一世紀的重要科學二十一世紀的重要科學w訊息科學訊息科學w生命科學生命科學w能源科學能源科學w材料科學材料科學w環境科學環境科學w經濟金融科學經濟金融科學它們之間的它們之間的橋樑、溝通橋樑、溝通就是數學就是數學近年的科技發展近年的科技發展 都需要很多數學的支援都需要很多數學的支援 醫學素描，生物色素分佈醫學素描，生物色素分佈( (豹紋、虎紋豹紋、虎紋) )，DNADNA結構，量結構，量子物理，材料科學，子物理，材料科學，半導體半導體，財經科學，大型晶體結，財經科學，大型晶體結構，構，互聯網互聯網 Radon Transform, Diffusion Equation

7、, Knot Theory, Gauge Theory, Mathematics Computation on Quantum Mechanics, Many Body Model, Inverse Problems數學研究對科學的貢獻數學研究對科學的貢獻美國政府美國政府Labor Dept. 關於關於大學畢業生報告的一段話大學畢業生報告的一段話Other (non-mathematics) occupations that require extensive knowledge of mathematics include actuary, statistician, computer pr

8、ogrammer, system analyst, system engineer, operation research analyst. A strong background in mathematics also facilitates employment in engineering, economics, finance, and physics.其他需要其他需要深入數學知識深入數學知識的行業包括精算的行業包括精算、統計師、程式編寫、系統分析、系統、統計師、程式編寫、系統分析、系統工程、運籌分析等。而工程、運籌分析等。而數學基礎良好數學基礎良好往往往有助於發展工程、經濟、財務及物

9、理往有助於發展工程、經濟、財務及物理等事業。等事業。美國政府美國政府Labor Dept. 關於關於大學畢業生報告的一段話大學畢業生報告的一段話數學為基礎的多元發展數學為基礎的多元發展從事其他學科研究從事其他學科研究的的，包括包括：電子計算、經濟、統計、財務、風險管理、電子計算、經濟、統計、財務、風險管理、社科、哲學社科、哲學 還有從事非學術研究的各行業的還有從事非學術研究的各行業的 圖像壓縮圖像壓縮數據保安數據保安數學與社會數學與社會物流物流風險管理風險管理數據壓縮數據壓縮 (JPEG 2000)小波小波 (Wavelet) 壓縮壓縮如果如果 A 是平滑的，那麼是平滑的，那麼 Di 就很小就

10、很小Si = A 的的平滑平滑部份部份Di = A 的的高頻高頻部份部份A一個信號和它的小波變換一個信號和它的小波變換原始信號原始信號變換後信號變換後信號Di 0 圖像是平滑的圖像是平滑的 壓縮壓縮 = 刪除小的刪除小的 Di2D1D小波小波壓縮：壓縮：考慮以下考慮以下 16 個數字：個數字：A = 1, 2, 3, 4, 5, 6, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1S1 = 3, 7, 11, 15, 15, 11, 7, 3D1 = 1, 1, 1, 1, 1, 1, 1, 1兩兩相加：兩兩相加：A = S1 D1兩兩相減：兩兩相減：對對S1重複剛才的程序：重複剛才

11、的程序：S2 = 10, 26, 26, 10 D2 = 4, 4, 4, 4對對S2重複剛才的程序：重複剛才的程序：S3 = 36, 36D3 = 16, 16S1 = S2 D2S2 = S3 D3最後，我們有最後，我們有S4 = 72，D4 = 0S3 = S4 D4以魚骨來表示：以魚骨來表示：1S2S3S4S1D2D3D4DA因此因此A = S4 D1 D2 D3 D4 JPEG (Fourier) 對對 JPEG 2000 (小波小波)未經壓縮處理的原有圖像的大小為 15 MBytes再壓縮幾何訊息的壓縮幾何訊息的壓縮w 將三維圖形影射到球上將三維圖形影射到球上w 在球上找一組互相垂

12、直的多項式在球上找一組互相垂直的多項式 ( ( 球球面調和多項式面調和多項式 ) )w 將三維訊息由這組多項式展開將三維訊息由這組多項式展開w 壓縮訊息只要保持其中足夠多的多項壓縮訊息只要保持其中足夠多的多項式式圖像影射到圓球體上圖像影射到圓球體上壓縮壓縮 256 256 倍後的圖像倍後的圖像原來的圖像原來的圖像數據保安數據保安數學與社會數學與社會RSA 公鑰密碼公鑰密碼w傳統密碼需要大量密鑰以至密鑰的分傳統密碼需要大量密鑰以至密鑰的分配及管理極為困難配及管理極為困難w現代保密的常用做法是由現代保密的常用做法是由 RivestRivest, , ShamirShamir, , AdlemanA

13、dleman 於於19781978年提出年提出w安全性是基於大整數分解安全性是基於大整數分解 ( ( 已知是一已知是一個計算來說極為困難的個計算來說極為困難的問題問題 ) )w加加密鑰可以公開因此稱為公鑰密碼密鑰可以公開因此稱為公鑰密碼 解密算法依賴數論中的解密算法依賴數論中的 Fermat 定理定理 破解破解 RSA 密碼的主要方法大數分解是密碼的主要方法大數分解是數論中一個重要課題數論中一個重要課題 現今最快的全面性大數分解算法依次現今最快的全面性大數分解算法依次為：二次域篩法，數域篩法，橢圓曲為：二次域篩法，數域篩法，橢圓曲線法均建基於深刻的數學上線法均建基於深刻的數學上RSA 公鑰密碼

14、的數學公鑰密碼的數學n = 63,978,486,879,527,143,858,831,415,041一個例子一個例子我們取我們取公鑰公鑰 e = 1193 = 1193及及國防部要傳遞以下重要訊息：國防部要傳遞以下重要訊息：WE_ARE_UNDER_ATTACK_LAUNCH_THE_MISSILE_NOW29個數位轉化為一個轉化為一個84位的位的數字：數字：230500011805002114040518000120200103110012012114030800200805001309191909120500141523將它分為將它分為3個個28位的數字：位的數字：M1 = 23050

15、00118050021140405180001M2 = 2020010311001201211403080020M3 = 0805001309191909120500141523加密後變成：加密後變成：C1 = 1060546943595003247867569919C2 = 2485275951856773770355929250C3 = 13101173280250715817550140912 前述的前述的 n 是兩個大素數是兩個大素數 p 和和 q 的乘積的乘積 要破解密碼必須找到要破解密碼必須找到 p 和和 q，大數分大數分解就派上用場解就派上用場n = 63,978,486,879

16、,527,143,858,831,415,041 = p q = 440,334,654,777,631 145,295,143,558,111取取 r = (p-1) (q-1) = 63,978,486,879,526,558,229,033,679,300用公鑰用公鑰 e 算出一個算出一個密密鑰鑰 d 滿足滿足e d 1 (mod r) , 1 d rd = 30,568,095,156,186,201,333,234,581,057解密算法解密算法：Cd (Me)d M (mod n)原文原文這個大數經過十七年才給人用這個大數經過十七年才給人用二二次域篩法分解出來次域篩法分解出來349

17、052951084765094914784961990389813341776463849338784399082057732769132993266709549961988190834461413177642967992942539798288533 RSA 於於 1977 年提出用年提出用n = RSA-129 =114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541在在2002年，三位印

18、度數學家，年，三位印度數學家，Agrawal, Kayak 和和 Saxena 發現如何用快速方法來發現如何用快速方法來決定一個大整數是素數的方法。這個方法決定一個大整數是素數的方法。這個方法有助於上述有助於上述 RSA 中中因子分解的問題。主因子分解的問題。主要的觀念如下：要的觀念如下： 設設 p 為奇正整數，而為奇正整數，而 a 為任一與為任一與 p 無公約無公約數的整數，則數的整數，則 p 為素數的充份必要條件為為素數的充份必要條件為(x-a)p = xp - a (mod p)三位印度數學家發現去驗證上述的條件的三位印度數學家發現去驗證上述的條件的最佳手法為找到另一正整數最佳手法為找到

19、另一正整數 r，使得，使得(x-a)p = xp - a (mod xr-1, p)這個計算極為快速，只須大約這個計算極為快速，只須大約 r2 log p 步的步的計算即可。計算即可。數學與社會數學與社會物流貨物及訊息傳輸的數量和容量，都正貨物及訊息傳輸的數量和容量，都正在急劇上升，令目前的網絡架構設施不在急劇上升，令目前的網絡架構設施不勝負荷，引致用戶不勝其煩勝負荷，引致用戶不勝其煩互聯網之應用日益廣泛互聯網之應用日益廣泛如：電子商貿、網上電台等如：電子商貿、網上電台等物流與物流與互聯網絡互聯網絡 國際及中港商貿國際及中港商貿 (CEPA, 9+2) ) JIT 以減少存倉成本以減少存倉成本

20、 到達時間到達時間離開時間離開時間尺寸尺寸貨運大樓貨運大樓普通貨物普通貨物超大貨物超大貨物香港空運貨站中的貨物香港空運貨站中的貨物傳輸傳輸航機班次和容量航機班次和容量重量重量裝載裝載/拆拆卸貨物卸貨物服務時間服務時間自自動化貨物處理及貯存動化貨物處理及貯存系統系統超前時間超前時間服務時間服務時間服務時間服務時間路徑的取捨路徑的取捨1. 1. 以最短路徑傳遞貨物及訊息以最短路徑傳遞貨物及訊息 假如網絡暢通無阻，我們會以最短路徑假如網絡暢通無阻，我們會以最短路徑傳遞貨物及訊息，節省傳遞時間傳遞貨物及訊息，節省傳遞時間2. 2. 減低擠塞減低擠塞 若網絡十分擠塞，我們需要尋找別的若網絡十分擠塞，我們

21、需要尋找別的路徑，避免擠進閉塞的路徑路徑，避免擠進閉塞的路徑排隊論排隊論 ( (Queuing Theory)Queuing Theory) 如何建立一個有效的數學模型？如何建立一個有效的數學模型？ 預算不同地域、不同時間網絡的使用預算不同地域、不同時間網絡的使用量量 預算貨物及訊息的到達時間和大小預算貨物及訊息的到達時間和大小 避免眾多貨物及訊息在同一時間擠進單一避免眾多貨物及訊息在同一時間擠進單一伺伺 服器或同一地域內服器或同一地域內圖論圖論 ( (Graph Theory)Graph Theory)在網絡上尋找最短路徑在網絡上尋找最短路徑尋找所有發送人與接受者之間的可行路徑尋找所有發送人

22、與接受者之間的可行路徑國際互聯網絡11312公開大學公開大學中文大學中文大學44253758246782111141由中文大學往公開大學的由中文大學往公開大學的最短路徑最短路徑一個數學家創富的故事一個數學家創富的故事F. Thomson Leighton麻省理工學院應用數學麻省理工學院應用數學系教授系教授 Akamai Technologies Incorporate (網路數據快網路數據快遞服務商遞服務商) 的創辦人的創辦人 市場總值逾廿多億美元市場總值逾廿多億美元 Akamai 的成功之道的成功之道傳統的網絡架傳統的網絡架構構 單一訊息來源單一訊息來源 網絡呈樹狀形態網絡呈樹狀形態若某一伺

23、服器發生故若某一伺服器發生故障，其分枝將會癱瘓，障，其分枝將會癱瘓，訊息將無法傳遞至使訊息將無法傳遞至使用者用者系統在首次發出訊息時，系統在首次發出訊息時，會將訊息複製及傳播至網會將訊息複製及傳播至網絡邊緣絡邊緣無間斷地傳遞訊息至全世無間斷地傳遞訊息至全世界每一個角落界每一個角落若部份伺服器、甚至網絡中樞若部份伺服器、甚至網絡中樞發生故障，發生故障，AkamaiAkamai 仍能在鄰近仍能在鄰近的伺服器內提取使用者所需的的伺服器內提取使用者所需的訊息訊息AkamaiAkamai 分配系統分配系統利用圖論、運籌學計算伺服器的利用圖論、運籌學計算伺服器的最佳擺放位置最佳擺放位置Akamai 的網絡

24、覆蓋全球的網絡覆蓋全球 54 個國家個國家數學與社會數學與社會風險管理風險管理風險管理風險管理甚麼叫風險甚麼叫風險 (Risk)？一般來說，風險是關乎災難發生的一般來說，風險是關乎災難發生的可能性。可能性。災難的例子：災難的例子： 911 事件事件 (紐約紐約) SARS 地震地震風險可以定義作由災難而導致損失的或風險可以定義作由災難而導致損失的或然率，這個觀念可以用統計學上的然率，這個觀念可以用統計學上的標準標準偏差偏差 (Standard Deviation) 來描述。現在來描述。現在我們來解釋客觀風險我們來解釋客觀風險 (Objective Risk) 這這個觀點。個觀點。年份年份123

25、45區域區域 171110913區域區域 216410128例如，某保險公司一年接受例如，某保險公司一年接受 1000 次火次火險的投保，由過去險的投保，由過去 5 年的數據得知在年的數據得知在兩個不同區域有如下數據：兩個不同區域有如下數據：在這兩區域上，平均值為在這兩區域上，平均值為 10，所以損失，所以損失的概率為的概率為 10/1000 = 0.01，可是在這兩個，可是在這兩個不同區域有不同的標準偏差，在第一個不同區域有不同的標準偏差，在第一個區域為區域為 2，在第二個區域為，在第二個區域為 4。0123456789481216202428323640444852566064687276

26、8084889296正態分佈正態分佈 (Normal Distribution)例子：學生某次測驗成績的分佈例子：學生某次測驗成績的分佈00. 050. 10. 150. 20. 25-4-2024681012141618202224區域 1區域 2平均值+3個標準偏差-3個標準偏差正態分佈主要取決於兩個參數：正態分佈主要取決於兩個參數：平均值和標準偏差平均值和標準偏差現在假定出事事件的發生分佈為正態分佈。現在假定出事事件的發生分佈為正態分佈。在區域一，它會有平均值在區域一，它會有平均值 10 和標準偏差和標準偏差 2。在區域二，它會有平均值在區域二，它會有平均值 10 和標準偏差和標準偏差

27、4。於是，在區域一，我們應當預期明年的數量於是，在區域一，我們應當預期明年的數量會在會在 10 2 x 2 = 6, 14 中間。中間。在區域二，則為在區域二，則為 10 2 x 4 = 2, 18 中間。中間。所以在第一區域，可能發生的事件為所以在第一區域，可能發生的事件為 8 件。件。 在第二區域，可能發生的事件為在第二區域，可能發生的事件為16件。件。客觀風險客觀風險雖然可能發生的或然率在區域一和區域二是一雖然可能發生的或然率在區域一和區域二是一樣的，但是區域一的風險為樣的，但是區域一的風險為 8/2 x 1/10 = 0.4，而區域二為而區域二為 16/2 x 1/10 = 0.8，所

28、以我們知道第，所以我們知道第二區域比第一區域風險為大。二區域比第一區域風險為大。現在假設保險人數增加一百倍，由一千現在假設保險人數增加一百倍，由一千人增加到一萬人，則預期事件會增加為人增加到一萬人，則預期事件會增加為100 x 10 = 1000。但第一區域的標準偏差則為但第一區域的標準偏差則為 而第二區域的標準偏差則改為而第二區域的標準偏差則改為 , 202100. 404100因此，對區域一，發生的事件會在因此，對區域一，發生的事件會在 1,000 2 x 20 = 960, 1040 中間，而客觀風險等於中間，而客觀風險等於 0.04。對區域二，則會在對區域二，則會在 1,000 2 x

29、 40 = 920, 1080 中間，而客觀風險為中間，而客觀風險為 0.08。可見當數目增加後，客觀風險大量減少，這是可見當數目增加後，客觀風險大量減少，這是 Law of Large Number 的一部份。的一部份。保險業保險業保險業的做法乃是將個人的風險分散到眾保險業的做法乃是將個人的風險分散到眾人身上。人身上。當人數夠多時，我們對損失的或然率會估當人數夠多時，我們對損失的或然率會估計得較為準確計得較為準確，而使得公司風險減少。而使得公司風險減少。但這些都由所謂但這些都由所謂 Law of Large Number 得得出的結果，我們必須由假設每次損失的事出的結果，我們必須由假設每次損失的事件互不相關，不能預測並且並非人為的。件互不相關，不能預測並且並非人為的。金融科學裏面的數學：金融科學裏面的數學：在對沖基金中有不同的手法來減少投在對沖基金中有不同的手法來減少投資風險，因此華爾街有大量的數學家資風險，因此華爾街有大量的數學家來幫忙他們處理數學的問題，最有名來幫忙他們處理數學的問題，最有名的是的是 Black-Scholes 方程的創作。方程的創作。歐式期權歐式期權在對沖基金裏有一種方法，