剩余類環(huán)上線性方程組的carmar法則推廣_第1頁
剩余類環(huán)上線性方程組的carmar法則推廣_第2頁
剩余類環(huán)上線性方程組的carmar法則推廣_第3頁
剩余類環(huán)上線性方程組的carmar法則推廣_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

剩余類環(huán)上線性方程組的carmar法則推廣

如果方程的數(shù)量與未知數(shù)量相同,且系數(shù)的列方程為零,則卡姆法顯示了系數(shù)的明顯關(guān)系。在許多問題的討論中,它非常重要。有時(shí)線性方程不是包含在數(shù)學(xué)域中的,而其他環(huán)中的線性方程組也不一定。因此,在這項(xiàng)工作中,將通用數(shù)字方程組的原理推廣到剩余環(huán)的線性方程中。1矩陣同余的定義引理1一次同余式ax≡b(modm),(modm)有解的充分必要條件是(a,m)|b.引理2整數(shù)方陣的行列式的值是整數(shù).證明行列式的計(jì)算是通過數(shù)的加、減、乘得到的,所以整數(shù)方陣的行列式的值還是整數(shù).由引理2和矩陣的乘法運(yùn)算容易得到引理3:引理3設(shè)A,B是同階整數(shù)方陣,則AB也是整數(shù)方陣,且|AB|=|A||B|.定義1如果整數(shù)矩陣A,B的行數(shù)與列數(shù)相同,且對應(yīng)的元素aij,bij滿足aij≡bij(modm),i=1,…,s,j=1,…,n,則稱矩陣A與矩陣B關(guān)于模m同余,記A≡B(modm).若給定模m,則任意整數(shù)矩陣A,必與由模m的最小非負(fù)完全剩余系的元素構(gòu)成的某一矩陣同余.定義2設(shè)α∈Zm={0,1,…,m-1}。若存在β∈Zm使αβ≡1(modm),則稱α是可逆元,β為α的關(guān)于模m的逆元,記β≡α-1(modm),在m給定的前題下,也記為β=α-1定理1Zm中的元素α是可逆元的充要條件是元素α與m是互素的.證明?α∈Zm,由引理1知,同余式ax≡1(modm)有解當(dāng)且僅當(dāng)(a,m)│1,所以Zm中的元素α是可逆元的充要條件是元素α與m是互素的.定義3設(shè)A是Zm上的n階方陣,若存在Zm的元素構(gòu)成的n階方陣B使則稱B是A的關(guān)于模m的逆矩陣,記B≡A-1(modm)(可記B=A-1,其中I是n階單位矩陣)所以定理2設(shè)A是Zm上的方陣,則A有逆矩陣A-1(modm)當(dāng)且僅當(dāng)行列│A│是Zm上的可逆元.若A可逆,則A-1(modm)≡│A│-1A*(modm)(其中│A│-1為│A│的逆元).證明必要性:若A有逆矩陣A-1(modm)=B,則有AB≡BA≡I(modm),由引理3有│AB│≡│A││B│≡1(modm).于是可得│A│為Zm上的可逆元,且逆元為│B│.充分性:設(shè)A的伴隨矩陣為A*,由引理2知A*是整數(shù)方陣,若│A│為Zm上的可逆元,設(shè)│A│的逆元為│A│-1,則由AA*=│A│I,有A(│A│-1A*)≡I(modm),所以A為Zm上的可逆矩陣且其逆矩陣為│A│-1A*.由定理1與定理2可得推論1A為Zm上的可逆矩陣當(dāng)且僅當(dāng)(│A│,m)=1.2微分方程ax定理3設(shè)AX=b是剩余類環(huán)Zm上的線性方程組,其系數(shù)矩陣A的行列式│A│在Zm上可逆則方程組AX=b有唯一解:證明將xi≡│A│-1│Ai│(modm),i=1,2,…,n代入方程組AX=b的第i個(gè)方程,得即xi≡│A│-1│Ai│(modm),i=1,2,…,n是方程組AX=b的一個(gè)解.若X0是方程組AX=b的任一解,即AX0=b用A-1(modm)左乘AX0=b得X0≡A-1b(modm),再用A-1(modm)=|A|-1A*代入X0≡A-1b(modm)得于是這樣所以xi≡|A-1|Ai|(modm),i=1,2,…,n是方程組AX=b的唯一解.3behnopk加密希爾提出以矩陣變換的方法建立文字字母間的對應(yīng)關(guān)系,給定分組長度為n,并選擇一個(gè)n×n可逆矩陣K,其元素屬于Z26,用此可逆矩陣K對信息進(jìn)行加密和解密.將一個(gè)具有n個(gè)字符的分組y=(y1,y2,…,yn)重新寫為n×1矩陣y=(y1,y2,…,yn)T.對矩陣加密可用矩陣乘法對此矩陣進(jìn)行:Ky≡x(mod26),而解密階段是已知x求y,也就是要在剩余類環(huán)Z26上求方程組Ky≡x(mod26)的解.要將文字轉(zhuǎn)化為數(shù)字,一般要建立一個(gè)字母與非負(fù)整數(shù)的一一對應(yīng),一種自然的對應(yīng)方式是令這一整數(shù)為任一字母在字母表中的位置,并且將每個(gè)數(shù)叫做相應(yīng)字母的代碼.以26個(gè)英文字母為例:這種對應(yīng)關(guān)系不一定要按順序給出,也可以是26個(gè)字母的任一個(gè)排序作為代碼.還可以給標(biāo)點(diǎn)符號也給出與數(shù)字的對應(yīng)關(guān)系.例4已知矩陣對明文Iamastudent進(jìn)行加密;對密文:Eswjibednexk解密.解因矩陣是3階的,所以對給定的文字按長度為3分組,最后一組只有兩個(gè)文字,因此加上一個(gè)不影響文字的任一個(gè)字母a,然后將文字化為數(shù)字向量y1=(9,1,13)T,y2=(1,19,20)T,y3=(21,4,5)T,y4=(14,20,1)T利用Ek(y)=Ky≡x(mod26)解出由|K|=5,(5,26)=1,由5x≡1(mod26)可解得|K|-1=21,將密文分組:Eswjibednexk對應(yīng)的數(shù)值向量分別為x1=(5,19,23)T,x2=(10,9,2)T,x3=(5,4,14)T,x4=(5,24,11)T,然后根據(jù)定理3由x1可解得:所以y11≡21×(-7)≡9(mod26),即y1=(9113)T,同理由x2,x3,x4可解得y2=(11920)T,y3=(2145)T,y4=(14201)T.將數(shù)值對應(yīng)字母得:Iamastudenta,即明文為Iamastudent(最后一個(gè)a是為了滿足每組為3個(gè)字母而加上的,應(yīng)刪除).若將密文分成若干個(gè)n個(gè)字符的組,以各組為列構(gòu)成矩陣P,以KP≡Q(modm)求出矩陣Q那么以Q的列向量為字符所對應(yīng)的就密文,而以K-1Q≡P(modm)求出的P就是原文.定理4m≥2為整數(shù),為m的既約因子分解,ri≥1,P1,…,Pk是互異的素?cái)?shù),則表示Zm上n階可逆矩陣的個(gè)數(shù))采用矩陣同余的方法來加密,方法簡單,但解密卻很困難.針對安全性考慮,一種好的密碼系統(tǒng)要求有足夠的密鑰以抵抗對密鑰的窮搜索破譯法采用矩陣同余加密,因?yàn)槠谱g的人不知道矩陣K因而也不知道它的階數(shù),即便知道它的階數(shù),如對例題中n=3,由定理3可知有N3(26)=1.634×1012個(gè)3階可逆矩陣,當(dāng)n=4時(shí),N4(26)=1.230×1022個(gè)4階可逆矩陣.它足以抵抗對密鑰的搜索破譯法.(mod7)對于任意的n階方陣A,是否存在A-1(modm)?這是Cramer法則能否實(shí)現(xiàn)的關(guān)鍵.推論2若A為Zm上的可逆矩陣當(dāng)且僅當(dāng)(│A│,pi)=1,i=1,…,n.例3在Z7上,求的逆矩陣A-1(mod7)解,(3,7)=1,則3可逆,其逆為3-1(mod7)=5,因此存在A-1(mod7).求A的伴隨矩陣,由定理2,有記Ai=(α1,…,αi-1,b,αi+1,…,αn),α1,α2,…αn是A的列向量,則│Ai

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論