22教论基本术语 网络安金 NETWORK SECURIY 数论是研究整数性质的一个数学分支, 同时也是加密技术的基础学科之一。首 先介绍一些数论的基本知识
2.1.2 数论基本术语 • 数论是研究整数性质的一个数学分支， 同时也是加密技术的基础学科之一。首 先介绍一些数论的基本知识
且。数 网络安金 NETWORK SECURITY 定义:设b∈Z,a≠0。如果存在q∈Z使得b=aq,那么就说b可 以被a整除,记为ab,且称b是a的倍数是b的因数或称约 数、除数、因子)。b不能被n整除可以记作dFa。由定义及乘 法运算的性质,可推出整除关系具有以下性质(注:符号b 本身包含了条他≠0): (1)aa; (2)如果ab且bc,则alc; (3)设m≠0,那么ab与ambm等价; (4)如果b且ac,则对所有的x,y∈Z有abx+cy; (5)设b≠0如果ab那么园l≤b1
1. 整 数 定义：设 。如果存在 使得 ，那么就说b可 以被a整除，记为 ，且称b是a的倍数,a是b的因数(或称约 数、除数、因子) 。 b不能被a整除可以记作dFa。由定义及乘 法运算的性质，可推出整除关系具有以下性质（注：符号 本身包含了条件 ）： （1） ； （2）如果 且 ，则 ； （3）设 ,那么 与 等价; （4）如果 且 ,则对所有的 ,有 ; （5）设 ,如果 ,那么 ; a,b Z,a 0 q Z b = aq a b a b a 0 a a a b b c a c m 0 a b ambm a b a c x, y Z abx + cy b 0 a b a b
2,录数 网络安金 定义:设整数p≠0。如果它除了显然因数士1p外没有其他的 因数,则就称为是素数,也叫不可约数。若a≠0,±1且不 是素数,则a称为合数。 关于素数,有以下性质: (1)如果是素数,且pb,则pa或pb,即至少整除与中 的一个 (3)若不计因数的顺序,这个分解式是唯一的。其中k≥1,P (2)任何一个整数n≥2,均可以分解成素数幂之积:n=pp2 是两两互不相同的素数,e,(1≤i≤k)是正整数。 (4)素数有无穷多个。 (5)设z(x)表示不大于的素数的数目,则imz(x)hx/x=1°
2. 素 数 定义:设整数 。如果它除了显然因数 外没有其他的 因数，则p就称为是素数，也叫不可约数。若 ， 且a不 是素数，则a称为合数。 关于素数，有以下性质： （1）如果p是素数，且 ，则 或 ，即p至少整除a与b中 的一个。 （2）任何一个整数 ，均可以分解成素数幂之积： （3）若不计因数的顺序，这个分解式是唯一的。其中 , 是两两互不相同的素数， 是正整数。 （4）素数有无穷多个。 （5）设 表示不大于的素数的数目，则 。 p 0 1, p a 0 1 p ab p a p b n 2 k e k e e n p p p 1 2 = 1 2 k 1 i p (1 i k) e (1 i k) i (x) lim (x)ln x / x = 1
3。同 网络安金 NETWORK SECURIY 设ab∈Z,n≠0,如果ma-b),则称a和b模n同 余,记为 a≡b(modn ,整数n称为模数。由 于na-b等价于m-b,所以=mdm与a=bmd-m) 等价。因此,一般我们总假定n≥1。如 果0≤b<n,我们称b是对模n的最小非负剩 余,有时也称b为a对模n的余数
3. 同 余 设 ，如果 ，则称a和b模n同 余，记为 ，整数n称为模数。由 于 等价于 ，所以 与 等价。因此，一般我们总假定 。如 果 ，我们称b是a对模n的最小非负剩 余，有时也称b为a对模n的余数。 a,b Z,n 0 n(a −b) a b(mod n) n a − b − n a − b a b(mod n) a b(mod(−n)) n 1 0 b n
同余式的一些基本性质 网络安金 NETWORK SECURIY (1)反身性a≡a(modn); (2)对称性如果=b(mdm),那么b≡a(mdm); (3)传递性如果≡bmdm),b=cmdm),那么a=≡c(modm); (4)如果≡a1(mdn),b=b(mdn)那么a+b≡a1+b(mdm) a-b=a-b,(modn);ab= a, b, (mod n)o (5)如果c≡bd(modn),a=b(modn),gcda,n)=1,(两个 不同时为0的整数a与b的最大公约数表示成gcd(a,b)那 么≡d(mdm),存在ae= 1(mod n)当且仅当gcda,n)=1
同余式的一些基本性质 （1）反身性: ； （2）对称性:如果 ，那么 ； （3）传递性:如果 ， ,那么 ； （4）如果 ， 那么 ； 。 （5）如果 ， ，gcd ，(两个 不同时为0的整数a与b的最大公约数表示成gcd(a,b))那 么 ，存在 ,当且仅当gcd 。 a a(mod n) a b(mod n) b a(mod n) a b(mod n) b c(mod n) a c(mod n) (mod ) a a1 n (mod ) b b1 n (mod ) a +b a1 +b1 n (mod ) a −b a1 −b1 n (mod ) ab a1 b1 n ac bd(mod n) a b(mod n) (a, n) = 1 c d(mod n) ac 1(mod n) (a, n) = 1