互联网的数学

丘成桐教授美國哈佛大學數學系教授香港中文大學數學講座教授香港中文大學數學科學研究所所長菲爾茲獎得獎人今日很高興的在這裏和公開大學的同學談談我自己對數學服務社會的看法。公開大學這麼多年來訓練了許多有上進心的青年，使我欽佩，在五十年代，除了香港大學外，沒有一家政府承認的大學，中文大學前身的崇基、新亞、聯合和當時的浸會學院吸收了香港很多人材，當時無論老師和學生都很窮苦，但是以後卻成為社會的中堅份子。我想公開大學的學生也會成為香港的人材，為二十一世紀的新中國服務。這十多年來，香港、中國和整個亞洲社會都逐漸轉型，尤其是中國改革開放以後，香港社會所需要的人材更多姿多采。亞洲各國要與全世界的經濟、文化、科學接軌，而中國大陸和日本會領導亞洲的發展，所以香港的青年也應當訓練自己來適應這個趨勢。沒有辦法迎接這個新時代來臨的青年恐怕要吃虧。縱觀全世界大學訓練人材的最基本要求乃是語文和數學，所有美國大學都看SAT的成績，而SAT中最基本的乃是這兩門學問的考試。這為的是甚麼呢？語文訓練使我們能夠表達自己的意思，數學訓練讓我們具有推理的能力，沒有這兩種能力，我們實在很難說我們是具有文化氣息的現代人。很多人對於數學不切實際的看法，以為數學家都躲在象牙塔裏，不食人間煙火，這是極為錯誤的看法。事實上，整個智識型的現代社會極度需要經濟、工程、管理等等方面的人材，而在現代化的前提下，這些人材都需要相當程度的數學訓練。一般來說，數學訓練分兩個層次，一個層次是在象牙塔裏的為了追求純真純美的研究，表面上這些研究與實用毫無關係，從前我們知道這些研究十多年或數十年後總會有大的用場，但是近二十多年來，我們發覺純數學和應用的距離愈來愈縮小距離了。數學的第二個層次就是在各行業上的應用，這是今天演講的主題。二十一世紀的重要科學訊息科學生命科學能源科學材料科學環境科學經濟金融科學它們之間的橋樑、溝通就是數學近年的科技發展都需要很多數學的支援醫學素描，生物色素分佈(豹紋、虎紋)，DNA結構，量子物理，材料科學，半導體，財經科學，大型晶體結構，互聯網RadonTransform,DiffusionEquation,KnotTheory,GaugeTheory,MathematicsComputationonQuantumMechanics,ManyBodyModel,InverseProblems數學研究對科學的貢獻美國政府LaborDept.關於大學畢業生報告的一段話Other(non-mathematics)occupationsthatrequireextensiveknowledgeofmathematicsincludeactuary,statistician,computerprogrammer,systemanalyst,systemengineer,operationresearchanalyst.Astrongbackgroundinmathematicsalsofacilitatesemploymentinengineering,economics,finance,andphysics.其他需要深入數學知識的行業包括精算、統計師、程式編寫、系統分析、系統工程、運籌分析等。而數學基礎良好往往有助於發展工程、經濟、財務及物理等事業。美國政府LaborDept.關於大學畢業生報告的一段話數學為基礎的多元發展•從事其他學科研究的，包括：電子計算、經濟、統計、財務、風險管理、社科、哲學•還有從事非學術研究的各行業的圖像壓縮數據保安數學與社會物流風險管理數據壓縮(JPEG2000)小波(Wavelet)壓縮如果A是平滑的，那麼Di就很小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,1}S1={3,7,11,15,15,11,7,3}D1={1,1,1,1,1,1,1,1}兩兩相加：A=S1D1兩兩相減：對S1重複剛才的程序：S2={10,26,26,10}D2={4,4,4,4}對S2重複剛才的程序：S3={36,36}D3={16,16}S1=S2D2S2=S3D3最後，我們有S4={72}，D4={0}S3=S4D4以魚骨來表示：1S2S3S4S1D2D3D4DA因此A=S4D1D2D3D4JPEG(Fourier)對JPEG2000(小波)未經壓縮處理的原有圖像的大小為15MBytes再壓縮幾何訊息的壓縮將三維圖形影射到球上在球上找一組互相垂直的多項式(球面調和多項式)將三維訊息由這組多項式展開壓縮訊息只要保持其中足夠多的多項式圖像影射到圓球體上壓縮256倍後的圖像原來的圖像數據保安數學與社會RSA公鑰密碼傳統密碼需要大量密鑰以至密鑰的分配及管理極為困難現代保密的常用做法是由Rivest,Shamir,Adleman於1978年提出安全性是基於大整數分解(已知是一個計算來說極為困難的問題)加密鑰可以公開因此稱為公鑰密碼•解密算法依賴數論中的Fermat定理•破解RSA密碼的主要方法大數分解是數論中一個重要課題•現今最快的全面性大數分解算法依次為：二次域篩法，數域篩法，橢圓曲線法均建基於深刻的數學上RSA公鑰密碼的數學n=63,978,486,879,527,143,858,831,415,041一個例子我們取公鑰e=1193及國防部要傳遞以下重要訊息：WE_ARE_UNDER_ATTACK_LAUNCH_THE_MISSILE_NOW29個數位轉化為一個84位的數字：230500011805002114040518000120200103110012012114030800200805001309191909120500141523將它分為3個28位的數字：M1=2305000118050021140405180001M2=2020010311001201211403080020M3=0805001309191909120500141523加密後變成：C1=1060546943595003247867569919C2=2485275951856773770355929250C3=13101173280250715817550140912•前述的n是兩個大素數p和q的乘積•要破解密碼必須找到p和q，大數分解就派上用場n=63,978,486,879,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(modr),1drd=30,568,095,156,186,201,333,234,581,057解密算法：Cd≡(Me)d≡M(modn)原文這個大數經過十七年才給人用二次域篩法分解出來349052951084765094914784961990389813341776463849338784399082057732769132993266709549961988190834461413177642967992942539798288533RSA於1977年提出用n=RSA-129=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541在2002年，三位印度數學家，Agrawal,Kayak和Saxena發現如何用快速方法來決定一個大整數是素數的方法。這個方法有助於上述RSA中因子分解的問題。主要的觀念如下：設p為奇正整數，而a為任一與p無公約數的整數，則p為素數的充份必要條件為(x-a)p=xp-a(modp)三位印度數學家發現去驗證上述的條件的最佳手法為找到另一正整數r，使得(x-a)p=xp-a(modxr-1,p)這個計算極為快速，只須大約r2logp步的計算即可。數學與社會物流•貨物及訊息傳輸的數量和容量，都正在急劇上升，令目前的網絡架構設施不勝負荷，引致用戶不勝其煩•互聯網之應用日益廣泛如：電子商貿、網上電台等物流與互聯網絡•國際及中港商貿(CEPA,9+2)—JIT以減少存倉成本到達時間離開時間尺寸貨運大樓普通貨物超大貨物香港空運貨站中的貨物傳輸航機班次和容量重量BCDS&BSSOversizeStack裝載/拆卸貨物服務時間自動化貨物處理及貯存系統超前時間服務時間服務時間路徑的取捨1.以最短路徑傳遞貨物及訊息–假如網絡暢通無阻，我們會以最短路徑傳遞貨物及訊息，節省傳遞時間2.減低擠塞–若網絡十分擠塞，我們需要尋找別的路徑，避免擠進閉塞的路徑排隊論(QueuingTheory)如何建立一個有效的數學模型？•預算不同地域、不同時間網絡的使用量•預算貨物及訊息的到達時間和大小–避免眾多貨物及訊息在同一時間擠進單一伺服器或同一地域內圖論(GraphTheory)•在網絡上尋找最短路徑•尋找所有發送人與接受者之間的可行路徑國際互聯網絡11312公開大學中文大學44253758246782111141由中文大學往公開大學的最短路徑一個數學家創富的故事F.ThomsonLeighton•麻省理工學院應用數學系教授•AkamaiTechnologiesIncorporate(網路數據快遞服務商)的創辦人•市場總值逾廿多億美元Akamai的成功之道•傳統的網絡架構–單一訊息來源–網絡呈樹狀形態•若某一伺服器發生故障，其分枝將會癱瘓，訊息將無法傳遞至使用者–系統在首次發出訊息時，會將訊息複製及傳播至網絡邊緣–無間斷地傳遞訊息至全世界每一個角落•若部份伺服器、甚至網絡中樞發生故障，Akamai仍能在鄰近的伺服器內提取使用者所需的訊息•Akamai分配系統利用圖論、運籌學計算伺服器的最佳擺放位置Akamai的網絡覆蓋全球54個國家數學與社會風險管理風險管理甚麼叫風險(Risk)？一般來說，風險是關乎災難發生的可能性。災難的例子：•911事件(紐約)•SARS•地震風險可以定義作由災難而導致損失的或然率，這個觀念可以用統計學上的標準偏差(StandardDeviation)來描述。現在我們來解釋客觀風險(ObjectiveRisk)這個觀點。年份12345區域171110913區域216410128例如，某保險公司一年接受1000次火險的投保，由過去5年的數據得知在兩個不同區域有如下數據：在這兩區域上，平均值為10，所以損失的概率為10/1000=0.01，可是在這兩個不同區域有不同的標準偏差，在第一個區域為2，在第二個區域為4。01234567894812162024283236404448525660646872768084889296正態分佈(NormalDistribution)例子：學生某次測驗成績的分佈00.050.10.150.20.25-4-2024681012141618202224區域1區域2平均值+3個標準偏差-3個標準偏差正態分佈主要取決於兩個參數：平均值和標準偏差現在假定出事事件的發生分佈為正態分佈。在區域一，它會有平均值10和標準偏差2。在區域二，它會有平均值10和標準偏差4。於是，在區域一，我們應當預期明年的數量會在10±2x2=[6,14]中間。在區域二，則為10±2x4=[2,18]中間。所以在第一區域，可能發生的事件為8件。在第二區域，可能發生的事件為16件。客觀風險雖然可能發生的或然率在區域一和區域二是一樣的，但是區域一的風險為8/2x1/10=0.4，而區域二為16/2x1/10=0.8，所以我們知道第二區域比第一區域風險為大。現在假設保險人數增加一百倍，由一千人增加到一