線性代數(shù)模型

關(guān)于線性代數(shù)模型10.1Durer魔方

德國著名的藝術(shù)家AlbrechtDurer(1471--1521)于1514年曾鑄造了一枚名為“MelencotiaI”的銅幣。令人奇怪的是在這枚銅幣的畫面上充滿了數(shù)學(xué)符號、數(shù)學(xué)數(shù)字和幾何圖形。這里我們僅研究銅幣右上角的數(shù)字問題。第2頁,共79頁，2024年2月25日，星期天1Durer魔方16321351011896712415141特點每行之和、每列之和、對角線之和、四個小方塊之和、中心方塊之和都相等，為確定的數(shù)34。所出現(xiàn)的數(shù)是1至16的自然數(shù)。四角之和、中間對邊之和均為34。最下邊一行中心數(shù)為1514，正是制幣的時間。問題是否還存在具有這些（或部分）性質(zhì)的魔方？第3頁,共79頁，2024年2月25日，星期天06118910601509119960711891070160911997108010015014011050407020160901201303060定義如果4×4數(shù)字方，它的每一行、每一列、每一對角線及每個小方塊上的數(shù)字之和都為一確定的數(shù)，則稱這個數(shù)字方為Durer魔方。R=C=D=S第4頁,共79頁，2024年2月25日，星期天你想構(gòu)造Durer魔方嗎？如何構(gòu)成所有的Durer魔方？Durer魔方有多少？2Durer魔方的生成集所有的Durer魔方的集合為D0000000000000000O=1111111111111111E=R=C=D=S=0R=C=D=S=4第5頁,共79頁，2024年2月25日，星期天a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44A=b11b12b13b14b21b22b23b24b31b32b33b34b41b42b43b44B=類似于矩陣的加法和數(shù)乘，定義魔方的加法和數(shù)乘。易驗證，D加法和數(shù)乘封閉，且構(gòu)成一線性空間。記M={所有的4×4數(shù)字方}

，則其維數(shù)為16。而D是M的子集，則D是有限維的線性空間。根據(jù)線性空間的性質(zhì)，如果能得到D的一組基，則任一個Durer方均可由這組基線性表示。第6頁,共79頁，2024年2月25日，星期天由0,1數(shù)字組合，構(gòu)造所有的R=C=D=S=1的魔方。共有8個，記為Qi,i=1,2,…,8。Q1=1000001000010100Q2=1000000101000010Q3=Q4=00011000001001000001010010000010第7頁,共79頁，2024年2月25日，星期天Q5=0010100001000001Q6=0100001010000001Q7=0010010000011000Q8=0100000100101000第8頁,共79頁，2024年2月25日，星期天易知則線性相關(guān)。而由0000000000000000=線性無關(guān)。任一Durer方可由它們線性表示。第9頁,共79頁，2024年2月25日，星期天結(jié)論：1Durer方有無窮多個。2Durer方可由線性組合得到。AlbrechtDurer的數(shù)字方的構(gòu)成：=16321351011896712415141第10頁,共79頁，2024年2月25日，星期天3Durer方的應(yīng)用推廣（1）要求數(shù)字方的所有數(shù)字都相等?；鶠?維空間（2）要求行和、列和、每條主對角線及付對角線數(shù)字和都相等?；鶠?維空間1010101001010101第11頁,共79頁，2024年2月25日，星期天0110100101101001100101101001011001011010101001011100001111000011第12頁,共79頁，2024年2月25日，星期天例1721116161122-3127621126712R=C=H=N=46H主對角線，N付對角線數(shù)字和。（3）要求行和、列和及兩條對角線數(shù)字和相等。8維空間Q。基為D是Q的7維子空間。01-10000000000-110第13頁,共79頁，2024年2月25日，星期天例679812657510967779R=C=D=30（4）要求行和、列和數(shù)字相等。10維空間W?；鶠?10-110-10-10010-1100000100-1-100100000100100000010010第14頁,共79頁，2024年2月25日，星期天（5）對數(shù)字沒有任何要求的數(shù)字方16維空間M空間維數(shù)015781016思考能否構(gòu)造出其他維數(shù)的數(shù)字方？第15頁,共79頁，2024年2月25日，星期天練習(xí)完成下面的Durer方61494887116798597R=C=D=S=30R=C=D=S=100第16頁,共79頁，2024年2月25日，星期天作業(yè)構(gòu)造你自己認為有意義的Durer方。6798125586119467710第17頁,共79頁，2024年2月25日，星期天10.2植物基因的分布設(shè)一農(nóng)業(yè)研究所植物園中某植物的的基因型為AA、Aa和aa。研究所計劃采用AA型的植物與每一種基因型植物相結(jié)合的方案培育植物后代。問經(jīng)過若干年后，這種植物的任意一代的三種基因型分布如何？第18頁,共79頁，2024年2月25日，星期天1建模準備植物遺傳規(guī)律？動植物都會將本身的特征遺傳給后代，這主要是因為后代繼承了雙親的基因，形成了自己的基因?qū)Γ驅(qū)痛_定了后代所表現(xiàn)的特征。常染色體遺傳的規(guī)律：后代是從每個親體的基因?qū)χ袀€繼承一個基因，形成自己的基因?qū)?，即基因型。?9頁,共79頁，2024年2月25日，星期天如果考慮的遺傳特征是由兩個基因A、a控制的，那末就有三種基因?qū)?，記為AA、Aa和aa。金魚草花的顏色是由兩個遺傳因子決定的，基因型為AA的金魚草開紅花，Aa型的開粉紅花，而aa型的開白花。人類眼睛的顏色也是通過常染色體來控制的?；蛐蜑锳A，或Aa型的人眼睛顏色為棕色，而aa型的人眼睛顏色為藍色。這里AA，Aa表示同一外部特征，我們認為基因A支配基因a，即基因a對A來說是隱性的。如第20頁,共79頁，2024年2月25日，星期天父體-母體的基因?qū)A-AAAA-AaAA-aaAa-AaAa-aaaa-aa后代基因?qū)A11/201/400Aa01/211/21/20aa0001/41/21雙親體結(jié)合形成后代的基因型概率矩陣第21頁,共79頁，2024年2月25日，星期天2假設(shè)分別表示第n代植物中基因型為AA,Aa,aa的植物占植物總數(shù)的百分率。第n代植物的基因型分布為表示植物基因型初始分布。假設(shè)1第22頁,共79頁，2024年2月25日，星期天假設(shè)2植物中第n-1代基因型分布與第n代分布的關(guān)系由上表確定。父體-母體的基因?qū)A-AAAA-AaAA-aa后代基因?qū)A11/20Aa01/21aa0003建模第23頁,共79頁，2024年2月25日，星期天第24頁,共79頁，2024年2月25日，星期天4求解模型關(guān)鍵計算特征值為1，1/2，0，M可對角化，即可求出可逆對角矩陣P，使PMP-1為對角型矩陣。特征值為1，1/2，0的特征向量分別為第25頁,共79頁，2024年2月25日，星期天則第26頁,共79頁，2024年2月25日，星期天第27頁,共79頁，2024年2月25日，星期天當(dāng)時，經(jīng)過足夠長的時間后，培育出來的植物基本上呈現(xiàn)AA型。5結(jié)論第28頁,共79頁，2024年2月25日，星期天10.3數(shù)學(xué)與密碼

第29頁,共79頁，2024年2月25日，星期天一個數(shù)學(xué)家兒子

的兩部作品第30頁,共79頁，2024年2月25日，星期天丹·布朗(DanBrown)是《數(shù)字城堡》、《達·芬奇密碼》

的作者。他堪稱今日美國最著名暢銷書作家。他的小說《達·芬奇密碼》自問世以來，一直高居《紐約時報》暢銷書排行榜榜首。丹·布朗的父親是一位知名數(shù)學(xué)教授，母親則是一位宗教音樂家，成長于這樣的特殊環(huán)境中，科學(xué)與宗教這兩種在人類歷史上看似如此截然不同卻又存在著千絲萬縷關(guān)聯(lián)的信仰成為他的創(chuàng)作主題。第31頁,共79頁，2024年2月25日，星期天第32頁,共79頁，2024年2月25日，星期天《數(shù)字城堡》

在信息時代，各國間諜、恐怖分子開始通過互聯(lián)網(wǎng)傳遞情報，但是為了使電子郵件不被他人截獲，他們紛紛給自己的郵件加上了密碼。為了從網(wǎng)絡(luò)上獲得重要情報，世界上最為隱秘的情報部門——美國國家安全局(NSA)斥巨資建造了一臺可以破解密碼的機器——萬能解密機……第33頁,共79頁，2024年2月25日，星期天《數(shù)字城堡》探討的主題是一個在美國社會被廣泛關(guān)注的問題——國家安全與個人隱私的矛盾問題。整部小說跌宕起伏、玄機重重，秘密直到最后才被解開。該書的創(chuàng)作靈感來源于一起真實的事件。第34頁,共79頁，2024年2月25日，星期天其成功要訣就是通過破譯一個可以產(chǎn)生國際影響力的密碼來結(jié)構(gòu)小說。讀者的樂趣之一就是跟隨作者進入密碼世界，并很快對密碼術(shù)也略知一二，同時我們還可以一睹運用高科技而進行的政治斗爭中的爾虞我詐。《數(shù)字城堡》是近年來最精彩同時也是最真實的高科技驚悚小說。丹·布朗以生動的筆觸描寫了個人自由與國家安全之間的灰色區(qū)域，其手法之高超著實令人敬畏，會使讀者感到極度震撼，戰(zhàn)栗不止。這是一部扣人心弦的最前沿...第35頁,共79頁，2024年2月25日，星期天《達芬奇密碼》

凌晨時分，哈佛大學(xué)的符號學(xué)家羅伯特-蘭登突然接到緊急求助電話———巴黎盧浮宮的老館長在博物館內(nèi)慘遭殺害。在尸體旁邊，警方發(fā)現(xiàn)了一封秘信。后來，蘭登和其他解密專家絞盡腦汁，終于弄明白了秘信中的內(nèi)容。種種跡象顯示，破案的線索就藏在達芬奇的諸多名畫之中！如果蘭登不能破解達芬奇的密碼，一個遠古時代的重大秘密也將永遠不為人知曉。……第36頁,共79頁，2024年2月25日，星期天丹·布朗說，達芬奇是加密術(shù)的開路先鋒，其藝術(shù)作品和手稿中包含著大量令人費解的符號和詭異的代碼。他說，《達芬奇密碼》中最精彩的內(nèi)容就是對加密術(shù)的探討，尤其是由達芬奇親自研究出來的種種加密設(shè)計令人忍不住拍案叫絕。第37頁,共79頁，2024年2月25日，星期天在加密術(shù)誕生之前，如何把私人信件委托給郵差傳遞而又不使隱私外泄一直都是個讓人頭痛的問題。達芬奇發(fā)明了第一代“公匙加密術(shù)”的雛形———一個可以保證信件安全的便攜式“密碼箱”。而且一旦有人試圖用暴力手段將“密碼箱”砸開，里面的信息將立即自行銷毀。第38頁,共79頁，2024年2月25日，星期天密碼的由來第39頁,共79頁，2024年2月25日，星期天密碼，并不是什么奇怪的東西。它只是按照“你知，我知”的原則組成的信號。密碼的歷史源遠流長。據(jù)史料記載，在中國，密碼的使用可以追溯到三國時期。第40頁,共79頁，2024年2月25日，星期天公元前2000年古埃及墓碑上刻的一些銘文就是用一些奇怪的符號代替當(dāng)時使用的文字。公元前130年左右，美索不達尼亞的一些碑文上將一些人名改用數(shù)字密寫。第41頁,共79頁，2024年2月25日，星期天公元4世紀，希臘出現(xiàn)了隱蔽書信內(nèi)容的初級密碼。1200年，羅馬教皇政府和意大利世俗政府開始系統(tǒng)地使用密碼術(shù)。在文藝復(fù)興時期的歐洲，密碼被廣泛用于政治、軍事和外交上。到16世紀末期，多數(shù)國家設(shè)置了專職的密碼秘書，重要文件都采用密碼書寫。第42頁,共79頁，2024年2月25日，星期天莫爾斯電碼與密碼通訊第43頁,共79頁，2024年2月25日，星期天1832年10月，美國畫家塞繆爾·莫爾斯在乘船從法國返回美國途中，看到一個青年醫(yī)生在擺弄一塊環(huán)繞著一圈圈絕緣銅絲的馬蹄形鐵塊，銅絲的通電可以產(chǎn)生對鐵丁的吸引力，而一旦斷電則吸引力消失。這就是電磁感應(yīng)現(xiàn)象。第44頁,共79頁，2024年2月25日，星期天受此啟發(fā)，莫爾斯在1844年5月24日發(fā)明了一種被后人稱為“莫爾斯電碼”的電報碼和電報機，開始了無線電通訊。這種編碼后來逐步應(yīng)用到軍事、政治、經(jīng)濟等各領(lǐng)域，形成了早期的密碼通訊。第45頁,共79頁，2024年2月25日，星期天到第一次世界大戰(zhàn)時，密碼通訊已十分普遍，許多國家成立專門機構(gòu)，進一步研制和完備密碼，并建立了偵察破譯對方密碼的機關(guān)。目前，信息時代的到來，密碼的使用更多、更廣，也更加先進了。

第46頁,共79頁，2024年2月25日，星期天在各種各樣的通訊傳輸過程中，人們會通過各種手段截取傳輸資料，造成傳輸安全問題。尤其是在科技高度發(fā)達的今天，傳送過程幾乎無法保證安全。于是人們就要在如何對內(nèi)容加密上進行研究，以保證即使對方截獲傳送資料，也會由于不了解密碼而不知所云。第47頁,共79頁，2024年2月25日，星期天密碼聯(lián)絡(luò)原理第48頁,共79頁，2024年2月25日，星期天“置換”思想“置換”思想加密或者用密碼聯(lián)絡(luò)是自古就有的事情，民間使用較多的所謂“暗號”就是最簡單的表現(xiàn)形式?！鞍堤枴敝皇鞘瞻l(fā)雙方對某些具體內(nèi)容進行的事先約定，其方法只適用于特定時間內(nèi)的特定內(nèi)容，不具有一般性。但是“暗號”的基本思想?yún)s是一般加密所共有的，這就是“置換”或“代換”的思想——用一種形式取代另外一種形式。

第49頁,共79頁，2024年2月25日，星期天語言→數(shù)字，比如英文的莫爾斯電碼，中文漢字的電報碼等。重要性1.

把各種復(fù)雜的文字用10個數(shù)字符號來代替，符號的簡化便于通訊傳遞；2.

各種文字轉(zhuǎn)化為數(shù)字以后，要進行加密研究，只需要對數(shù)字加密進行研究，大大地降低了加密難度。第50頁,共79頁，2024年2月25日，星期天加密傳送基本模式加密傳送基本模式

無論何種加密傳送，其基本模式都是一樣的：把要傳遞的內(nèi)容——“明文”，按照“密鑰”加密變成“密文”；將密文按照正常方式發(fā)送出去；對方接收到密文后，按照密鑰解密再還原成原來的明文。

第51頁,共79頁，2024年2月25日，星期天加密方法之一

——代換法第52頁,共79頁，2024年2月25日，星期天加密的方法是人為地產(chǎn)生的，因此也就各種各樣?！按鷵Q”或“置換”，是自古以來普遍采用的加密思想。所謂“代換”，就是用一種形式取代另外一種形式。這種方法早在羅馬帝國時代就已經(jīng)使用，當(dāng)時他們把26個字母分別用其后面的第三個字母來代替，用“群”的記號就是如下的“矩陣”：第53頁,共79頁，2024年2月25日，星期天hello

khoor

第54頁,共79頁，2024年2月25日，星期天一種變形：把字母或數(shù)字用其它字母或數(shù)字代換時沒有明顯的代換規(guī)律。比如把0，1，2，…，9等10個數(shù)字分別換成3，5，6，2等等，即有下表：第55頁,共79頁，2024年2月25日，星期天缺欠：在日常書面語言中，每個字母所使用的頻率是不相同的，人們可以通過截取大量信息進行統(tǒng)計分析，推測出大體的代換法則，然后再經(jīng)過檢驗調(diào)整，即可確定正確的代換法則，從而破解出所有信息。第56頁,共79頁，2024年2月25日，星期天密鑰可以公開了第57頁,共79頁，2024年2月25日，星期天早期的各種加密方法有一個共同的弱點：他們都是封閉式的制解法，即收發(fā)雙方都必須同時知道這種密碼的構(gòu)造。這些方法有許多不便之處，而且如果在通訊系統(tǒng)中有一個聯(lián)絡(luò)站被間諜滲入，則密碼的機密就全盤暴露。20世紀70年代后期，美國幾個電機工程師用數(shù)論知識創(chuàng)造了一種編碼方法，用這種方法制造了密碼，可以公開密鑰，但他人卻無法破解。第58頁,共79頁，2024年2月25日，星期天密碼通訊中的加密與解密方法實際上是兩個互逆的運算。數(shù)學(xué)中許多運算是本身容易而逆向困難。比如，乘法容易，除法困難；乘方容易，開方困難等。第59頁,共79頁，2024年2月25日，星期天用兩個百位數(shù)字相乘得到一個200位數(shù)字，利用計算機是輕而易舉的。但要把一個200位數(shù)分解為兩個數(shù)的乘積，卻極其困難。按照通行的做法：用一個一個較小的數(shù)去試除，其工作量是極其巨大的。人們做過估算，要分解一個200位數(shù)字，用每秒10億次的電子計算機，大約需要40億年，即使分解一個100位數(shù)字，所花時間也要以萬年計。第60頁,共79頁，2024年2月25日，星期天這就給數(shù)學(xué)家一種啟示：能否利用這種矛盾編制密碼，使我方編碼、譯碼輕而易舉，而敵方破譯卻難上加難?第61頁,共79頁，2024年2月25日，星期天1978年，美國三位電機工程師Rivest、Schamir與Adleman利用這個思想創(chuàng)造了一種編碼方法，稱為RSA方法。其本質(zhì)是制造密碼與破解密碼的方法都是公開的，同時又可以公開編制密碼所依賴的一個很大的數(shù)N，這個N是由我方通過兩個大的素數(shù)p、q乘積而得到的，而破解密碼則必須依靠這兩個素數(shù)p、q。因此要破解密碼則必須首先分解大數(shù)N，但這是極端困難的。第62頁,共79頁，2024年2月25日，星期天RSA編碼方法與原理第63頁,共79頁，2024年2月25日，星期天RSA編碼方法

RSA方法可以公開用以制造密碼與破解密碼的方法，它依賴于兩個大素數(shù)p、q，當(dāng)然，不同的機構(gòu)應(yīng)當(dāng)使用不同的p、q。下面是其基本方法：第64頁,共79頁，2024年2月25日，星期天制造密碼與密鑰：1.我方掌握兩個大素數(shù)p、q，由此可以造出一個大數(shù)N=pq；2.選取一個較小的數(shù)n，使得n與p-1,q-1均互素；3.再選取m，使得mn-1是(p-1)(q-1)的倍數(shù),即mn=k(p-1)(q-1)+1；4.對外公開密鑰：N和n。第65頁,共79頁，2024年2月25日，星期天m是我們破解密碼的唯一秘訣，絕不可以外傳。敵方在不了解p，q的情況下，是難以分解出p，q的，因而也就不可能了解我們的唯一秘訣m.第66頁,共79頁，2024年2月25日，星期天假如我們的朋友要向我們發(fā)送信息1.他可以通過查到的我們的密鑰N和n，將要發(fā)送的信息（數(shù)）由明文x轉(zhuǎn)化為密文y:

算出xn，設(shè)xn被N除所得的余數(shù)y，用數(shù)論的記號就是，xn≡y(modN)，y就是要發(fā)出的密文。密碼通訊第67頁,共79頁，2024年2月25日，星期天2.我方收到密文y后，計算出ym，按照數(shù)論的知識，一定有ym≡x(modN),

即ym被N除所得的余數(shù)就是對方想發(fā)出的明文x。密碼通訊第68頁,共79頁，2024年2月25日，星期天收發(fā)過程總結(jié)：我們把上述過程總結(jié)如下：(1)對方要發(fā)的明文x轉(zhuǎn)化為密文y:xn≡y(modN)；(2)對方發(fā)送密文y；(3)我方收到密文y后轉(zhuǎn)化為明文x:ym≡x(modN)。

第69頁,共79頁，2024年2月25日，星期天RSA編碼原理

問題的關(guān)鍵在于為什么能有ym≡x(modN)？這依賴于數(shù)論中的一個基本公式：歐拉定理設(shè)a,N

為正整數(shù),如果

(a,N)=1,則有

其中為歐拉函數(shù)，它代表在1，2，3，……，N中與N互素的正整數(shù)的個數(shù)。

第70頁,共79頁，2024年2月25日，星期天其中k是正整數(shù)。我們只需證明，對于任意正整數(shù)x,有ym≡xnm(modN)（因為xn≡y(modN)

）≡xk

(N)+1(modN)≡x(modN)

根據(jù)歐拉定理，注意到當(dāng)N=pq時，而上述選取的m,n滿足mn-1是(p-1)(q-1)的倍數(shù)，即第71頁,共79頁，2024年2月25日，星期天事實上，由于N=pq,只有四種可能：(x,N)=1、(x,N)=p

、(x,N)=q或(x,N)=N情況1

如果(x,N)=1，由歐拉定理，必有xk

(N)≡1(modN)，從而

xnm≡xk

(N)+1(modN)≡x(modN)。第72頁,共79頁，2024年2月25日，星期天情況2

如果(x,N)=