1、環在密碼學中的應用,設(Z26,+26)為模26的整數加法群，+26為模26的加法運算，該群可用來對移位密碼體制(Caesar cipher)的原理進行簡單刻畫。設移位密碼體制中有： 明文； IREADABOOK 密文：LUFDGDERRN 密鑰：K=3 其中密文L由明文I在英文字母表內循環后移3位得到，其他類同。注意，這里循環后移3位指明文X 變為密文A,R變為密文U等等，這一加密法則可概括為群(Z26,+26)中的表達式 y=x+263,x,yZ26 (1),這里 x為明文，y為密文，字母ABCDXYZ分別對應0，1，2，3,23，24，25。加密明文時，先將明文字母串變換為Z26上的數字

2、串，再按上述表達式每次一個字符地將明文數字串變換為密文數字串，最后將密文數字串變換為密文字母串。式（1）可更簡潔地寫為 Y=x+3mod26, x,yZ26 (2),環在密碼學中的應用,環在密碼學中的應用(仿射密碼),由前面的知識我們知道(Z26,+26,26)為環。仿射密碼(Affine cipher)可由該環刻畫。仿射密碼體制的加密變換為 y=(a26x)+26b, x,yZ26 （3） 其中,a與b為參數且a與26互質，而x為明文，y為密文，與上例一樣，字母ABCDXYZ分別對應0，1，2，3,23，24，25。加密明文時，先將明文字母串變換為Z26上的數字串，再按上述表達式每次一個字符

3、地將明文數字串變換為密文數字串，最后將密文數字串變換為密文字母串。式（3）可更簡潔地寫為 Y=ax+bmod26,x,yZ26 (7),6.7 環 同 態,6.7.1 理想 6.7.2 環 中 合 同 關 系 6.7.3 環 同 態 與 同 構 6.7.4 單純環與極大理想,6.7.1 理想,定義. 設R是一個環，R的一個子集N說是R的一個理想子環，簡稱理想，如果 （1）N非空； （2）若aN,bN,則a-bN; （3） 若aN,R,則 aN,aN。 平凡理想：0，R,理想的例,設R為實數域上的二階正方矩陣環， 形如 的所有元素組成的子集為 N，則N為R的子環，但不是R的理想。 比如，取x=

4、R，a= N，則 xa = N。,理想的例,設R=（Z,+,*)是整數環，則nZ是R的理想，其中n為自然數，容易看出(nZ,+)是Abel群。任取kZ，有knz nZ和nzk nZ。即knZnZ和nZk nZ，所以nZ是R的理想。,結論1. 理想一定是子環,但子環未必是理想。 結論2. 任意體R只有平凡理想。 證明： 任取R的理想N，若N=0，則得證。否則，往證N=R。 因N 0，故存在aN，且a 0。 于是有a的逆元素a-1R。由N為理想知，有 a-1 aN，即R中的1N。 從而對R中任意元素x，都有x = 1xN。 因此，R N。故N=R。,例子,設R是含1的交換環，且10，則R是域當且僅

5、當R只含平凡理想。 證明：必要性證明如結論2。 充分性，任取xR,x0 ,則易證D=Rx=rxrR是R的理想，從而有Rx=R,這就證明了存在yR，使得yx=1,y是x的逆元。即R是交換體（域）。,結論3. 設R是有壹的交換環，aR，則 aR=ar | rR是R的理想，而且包含a。 證明： (1)aR非空，因為0=a0aR，a=a1aR。 (2)若xaR，yaR，則存在r1，r2R， 使得x=ar1，y=ar2，故 x-y = a（r1-r2） aR (3) 若zaR，rR，則存在r3R，使得 z = ar3， 故 zr = ar3r = a(r3r)aR，rz = rar3 =a(r r3)a

6、R。 因此，aR是含a的理想。,定義. 設R是有壹的交換環，aR，則aR稱為由a生成的主理想，記為（a）。 (a)=aR=R在什么條件下成立?什么條件下不成立為什么? 結論4. 環R的主理想（a）是R中包含a的理想中最小（在集合包含關系下）的理想。 證明：設N是R中包含a的任一理想，往證（a） N。 任取x(a)，即xaR，則存在rR，使得x=ar。由aN， rR，N是理想知，arN，即xN。所以，（a） N。,主理想結論,6.7.2 環 中 合 同 關 系,定義. 設R是一個環，N是一理想。對于a，bR，如果 a-b=nN，或a=b+n，nN， 則稱a和b模N合同，記為 ab (mod N)

7、。 N的一個剩余類:N的一個陪集。 含a的剩余類:a+N. 例 設環R=(Z,+, )是整數環，4Z=4kkZ是R的理想，0+N=,-4,0,4,8,1+N=,-3, 1,5,9,都是N的剩余類。 例. 設R為整數環I，N=（m）=mI，則 ab（mod N），即a-bmI或ma-b，即 ab（mod m）。,定理6.7.1 在環R中，對于模N，有 (1)反身性：aa; (2)對稱性：若ab，則ba; (3)傳遞性：若ab，bc，則ac; (4)加法同態性：若ab,cd,則acbd。 (5)乘法同態性：若ab，cd，則acbd。,環中合同關系的性質,(1)至(3)在群中已證，不過是加法群R模加

8、法子群N的合同性。 （4）因為ab,cd,故a+N = b+N,c+N = d+N,于是 ac+N = a+N（c+N）= b+N（d+N）= bd+N, 即acbd。 （5）因為a b，cd，故a = b+n1，c = d+n2，n1N，n2N。于是 ac =bd+ bn2 + n1d + n1n2。 但N是一個理想，故bn2N，n1dN，n1n2N， 因而bn2 + n1d + n1n2N，故acbd.,證明,定義. 設R是一個環,S是有加、乘兩種運算的系統，稱R到S中的映射是環R到S中的同態映射，如果 (a+b)=(a)+(b)，(ab)=(a)(b)。 若R到R上有一個同態映射,則稱R

9、與R同態,記為 RR。 定義. 若是環R到系統R上的一對一的同態映射，則稱是R到R上的同構映射或同構對應。 若R到R上有一個同構映射，則稱R與R同構，記為R R。,6.7.3 環同態與同構,定理6.7.2 設R是一個環,S是一個有加法和乘法 的運算系統.若是R到S中的一個同態映射,則 R的映象R=（R）也是一個環， (0)就是R的零0， (-a)=-(a)。 若R有壹而R不只有一個元素，則 R有壹而且（1）就是R的壹1； 若aR有逆，則（a）在R中有逆而且 （a-1）就是（a）-1。,設是環R到R上的同態映射，R的 零0的逆映象-1(0)叫的核。 -1(0)=x x R ,(x)=0,環的同態

10、核,定理6.7.3 同態映射的核N是R的一個理想。設 a是R的任意元素，則a的逆映象 -1(a)=aR(a)=a是N的一個剩余類.。 證明：因為是R的加法群到R的加法群上面 的同態映射,所以的核N=-1(0)是R的子群， 且a的逆映象-1(a)是模N的一個剩余類。 再證N做成理想，若aN，R，則 (a)=(a)()=0()=0， 故aN，同樣可證aN。,環的第一同態定理,設R是環，N是R的理想，對R的關于N的 剩余類引進運算，規定： （a+N）+（b+N）（a+b）N （a+N）（b+N ） = ab+N,剩余類的加、乘,定理6.7.4 按照剩余類的加法和乘法，R對 于理想N的所有剩余類的集合

11、RN是一個環，RN叫做R對于N的剩余環 （商環） 規定（a）= a+N，則是R到RN上的一個同態映射，其核為N。 證明：分析，由群中已證的結果，模N的所有剩余類的加法作成一個加法群，就是R對于N的商群R/N，如果規定(a)= a+N，則是加法群R到到商群RN上的一個同態映射，其核為N。那么要想證明是環R到R/N上的同態映射，必須有(ab)=(a)(b)成立，而根據剩余類乘法的定義(ab)=ab+N=(a+N)(b+N)=(a)(b)。,環的第二同態定理,例子 設環R=(Z,+, )是整數環，4Z=4kkZ是R的理想，商環(Z/4Z,)稱為模4的剩余類環，其中Z/4Z=0+4Z,1+4Z,2+4

12、Z,3+4Z= , , , 且 = , = 。并且模4的剩余類環和模4的整數環是同構的。 定理6.7.5 若是環R到R上的一個同態映 射，其核為N，則R與RN同構： R RN。 證明：設a是R的任意元素，則-1(a)是N 的一個剩余類。規定R到RN上的映射 ：a -1(a) 。 則是R到RN上的對應的加群同 態映射。,環的第三同態定理,只需證明乘同態，即若a，bR，往證（ab）=（a）（b） 由a,bR,有a,b R,使得(a)=a, (b)=b, 于是，(ab)= -1(ab） = -1(a) (b) = -1(ab)=ab+N (a)(b)= -1(a) -1(b) = -1(a) ) -

13、1( (b) =(a+N)(b+N)= ab+N 故是R到RN上的一個同構對應。,證明,設環R同態于R:RR,同態核為N,于是 R與N之間的子環與R的子環一一對應， 大環對應大環，小環對應小環， 理想對應理想。 R與（0）間無理想 iff R與N間無理想。 例 設環R1=(Z,+,)是整數環， 到R2=(Z8, , ) 是模8的整數環。令:ZZ8, (x)=x(mod8), xZ,則是R1到R2的同態映射，N=8Z是同態核，我們可以看到R1包含著N的理想是：,定理6.7.6,例子,N1=R1=Z, N2=2Z=2k kZ, N3=4Z= 4k kZ, N4=8Z= 8k kZ。 R2的理想是：

14、 Z8,0,2,4,6,0,4,0。 令A1=Z,2Z,4Z,8Z, A2=Z8,0,2,4,6,0,4,0并定義f:A1A2,f(Z)=Z8,f(2Z)= 0,2,4,6,f(4Z)= 0,4,f(8Z)= 0。則f是A1和A2之間存在一一對應關系。,定義.如果環R除自己和（0）外沒有別的理想,則稱R為單純環。 例. 設R是模5的整數環:0，1，2，3，4。任取R的理想N,則從加法角度看,N是R的子群，故由Lagrange定理,|N|R|。而|R|=5,所以|N|只能為1或5,亦即,N 或為(0),或為R,因此，R是單純環。,6.7.4 單純環與極大理想,定義. 環R的一個理想N說是一個極大

15、理想，如果N R，而R與N之間沒有別的理想。 例. 設R是模12的整數環：0,1,2,11。 設N1=6R=0，6,則N1是主理想,但非極大理想:有R的理想N2=2R=0,2,4,6,8,10,且N N2 R。 N2是R的極大理想。 若取N3=3R=0,3,6,9,則N3也是R的極大理想。 可見，極大理想不唯一。,極大理想,定理6.7.7 若N R，則N是R的極大理想必要而且只要RN是單純環。 證明：因RRN，所以， N是R的極大理想iff R與N之間沒有別的理想 iff RN與（0）間無理想 iff RN是單純環。 例. 由上例,N2是R的極大理想,故 R/N2= N2 ,1+N2為單純環.N1不是極大理想,則 R/N1=N1,1+N1,2+N1,3+N1,4+N1,5+N1不是單 純環。,極大理想與單純環的關系,定理6.7.8 任意有壹的交換的單純環R是一個域。 證明： 只需證明R中任意非零元素有逆。 任取aR，a0?？碼R=（a），因為a0， 又aaR。故aR（0）。但R為單純環，故 aR=R。今R有壹，故必有R中之元素b適合ab=1， 即a在R中有逆b。,單純環與域的關系,定理6.7.9 任意域F是有壹的交換的單純環。 證明： 取F的任意理想N(0)，往證N=F。 由N(0)知，有aN，a0，于是有a-1F。 因為N是F的理想，故aa-1N，即1N，因