环( Rings) 环R,由{R,+,x}表示,是具有加法和乘法两个二元 运算的元素的集合,对于环中的所有a,b,C,都服 从以下公理: (A1-A5),单位元是0,a的逆是-a (M1),乘法封闭性,如果a和b属于R,则ab也属于R (M2),乘法结合律,对于R中任意a,b,C有a(bC)=(ab)C o(M3),乘法分配律,a(b+C)=ab+acor(a+b)C=ac+bC (M4),乘法交换律,ab=ba,交换环 (M5),乘法单位元,R中存在元素1使得所有a有a1=1a (M6),无零因子,如果R中有a,b且ab=0,则a=0or b=0. 满足M4的是交换环;满足M5和M6的交换环是整环 claat ay Camerer sclence /echvocage mfy@ustc.edu.cn 现代密码学理论与实践 7/55
mfy@ustc.edu.cn 现代密码学理论与实践 7/55 环R, 由{R, +, x}表示, 是具有加法和乘法两个二元 运算的元素的集合，对于环中的所有a, b, c, 都服 从以下公理： ◦ (A1-A5), 单位元是0，a的逆是 -a. ◦ (M1), 乘法封闭性, 如果a和b属于R, 则ab也属于R ◦ (M2), 乘法结合律,对于R中任意a, b, c有a(bc)=(ab)c. ◦ (M3), 乘法分配律, a(b+c)=ab+ac or (a+b)c=ac+bc ◦ (M4), 乘法交换律, ab=ba，交换环 ◦ (M5), 乘法单位元, R中存在元素1使得所有a有 a1=1a. ◦ (M6), 无零因子, 如果R中有a, b且ab=0, 则 a=0 or b=0. 满足M4的是交换环；满足M5和M6的交换环是整环
域( Fields) 域F,可以记为{,+,X},是有加法和乘法的两个二 元运算的元素的集合,对于F中的任意元素a,b,C, 满足以下公理: (A1-M6),F是一个整环 (M7),乘法逆元,对于F中的任意元素a(除0以外),F中都存 在一个元素a,使得a1=( a-1)a=1. 。域就是一个集合,在其上进行加减乘除而不脱离该集合, 除法按以下规则定义:a/b=a(b-1 有理数集合,实数集合和复数集合都是域;整数集合 不是域,因为除了1和-1有乘法逆元,其他元素都无 乘法逆元 都 mfy@ustc.edu.cn 现代密码学理论与实践 8/55
mfy@ustc.edu.cn 现代密码学理论与实践 8/55 域F, 可以记为{F, +, x}, 是有加法和乘法的两个二 元运算的元素的集合，对于F中的任意元素a, b, c, 满足以下公理： ◦ (A1-M6), F是一个整环 ◦ (M7), 乘法逆元, 对于F中的任意元素a(除0以外), F中都存 在一个元素a -1 , 使得aa-1=(a-1)a=1. ◦ 域就是一个集合，在其上进行加减乘除而不脱离该集合, 除法按以下规则定义: a/b=a(b-1). 有理数集合, 实数集合和复数集合都是域；整数集合 不是域，因为除了1和-1有乘法逆元，其他元素都无 乘法逆元
群、环和域的关系 (Al)Closure under addition If a and b belong to s, then a+ b is also in (A2) Associativity of ad a+(6+c)=(a+b)+cfor all a, b, c in S (A3)Additive identity There is an element o in r such that a+0=0+a=a for all a in s (A4)Additive inverse For each a in s there is an element-a in s such that a+(a)=(a)+a=0 AcE a+b=b+a for all a b in s (MI)Closure under multiplication: If a and b belong to S, then ab is also in S (M2) Associativity of multiplication: a(bc)=(ab)c for all a, b, c in S (M3)Distributive laws a(b+c)=ab +ac for all a, b, cin s (a +b)c= ac bc for all a, b, c in s (M4) Commutativity of multiplication: ab= ba for all a, b in S (MS) Multiplicative identity There is an element 1 in S such that a1=la= a for all a in s (M6) No zero divisors If a. b in s and ab=0 then either a=or b=0 (MT) Multiplicative inverse If a belongs to s and a 0, there is an element al in S such that acl=ala=1 Figure 4.1 Group, Ring, and Field mfy@ustc.edu.cn 现代密码学理论与实践 9/55
mfy@ustc.edu.cn 现代密码学理论与实践 9/55
4.2 MODULAR ARITHMETIC 给定任意正整数n和a,如果用a除以n,得到的商q 和余数r满足如下关系 a=qn+r0≤r<n;q=□a/n」□」表示小于等于x 的最大整数。给定a和η时,q和r即唯一确定。(证明) g l=1X7+4,r=4 11=(-2)x7+3 r=3 3 a(q+I)n 012 Figure 4.2 The Relationship a= qn+r; Osr<n mfy@ustc.edu.cn 现代密码学理论与实践 10/55
mfy@ustc.edu.cn 现代密码学理论与实践 10/55 给定任意正整数n和a，如果用a除以n，得到的商q 和余数r满足如下关系: a=qn + r 0≤r <n; q=⌊a/n」⌊x」表示小于等于x 的最大整数。 给定a和n时，q和r即唯一确定。 （证明） Eg: 11=1x7 + 4, r=4; -11=(-2)x7 + 3, r=3
因子( Divisors) 如果a=mb,其中a,b,m为整数,则当b≠0时,即b 能整除a,或a除以b余数为0,b|a.b是a的一个因子 24的正因子有1,2,3,4,6,8,12和24。 以下关系成立 如果a|1,则a=± 如果a|b,且b|a,则a=±b 任何b≠0能整除0 0如果b|g,且bh,则对任何整数m和n有bmg+nh) 例:b=7,g=14,h=63,m=3,n=2,714and 7|63 求证:7(3×14+2×63) 证明:(3×14+2X63)=7(3X2+2X9) 显然 如果a 0n7(7(3X2+2x9) modn,则na皿 都 mfy@ustc.edu.cn 现代密码学理论与实践 11/55
mfy@ustc.edu.cn 现代密码学理论与实践 11/55 如果a=mb, 其中a, b, m为整数，则当b≠0时，即b 能整除a, 或a除以b余数为0, b|a. b是a的一个因子。 24的正因子有1, 2, 3, 4, 6, 8, 12和24。 以下关系成立 ◦ 如果a|1, 则a=±1 ◦ 如果a|b，且b|a, 则a=±b ◦ 任何b≠0能整除0 ◦ 如果b|g，且b|h, 则对任何整数m和n有b|(mg+nh) 例: b=7, g=14, h=63, m=3, n=2, 7|14 and 7|63 求证：7|(3x14 + 2x63) 证明：(3x14 + 2x63)=7(3x2 + 2x9) 显然, 7|(7(3x2 + 2x9)) 如果a ≡ 0 mod n，则n|a