1、第八章 数论初步8.1 素数 8.2 费马定理和欧拉定理8.3 素数测试 8.4 剩余定理 8.5 离散对数 * 大连理工大学8.1 素数 定义 8.1：（ 整除、倍数、因数）设 a， b为整数，若存在整数 c，使 b=ac，则称 a可整除 b，记作 a|b。 b叫做 a的倍数， a叫做 b的因数。若不存在这样的整数 c，则称 a不能整除 b，记作 a | b。* 如果 b|g， b|h,对于任何整数 m和 n，则满足b|(mg+nh).* 大连理工大学8.1 素数 定义 8.2：（ 公约数、最大公约数、素数、互素、两两互素）设 a， b， ， l是整数，若有整数 d满足 d|a， d|b，
2、， d|l的公约数。 a， b， ， l的公约数中最大者成为它们的最大公约数，记作（ a， b， ， l ）。如果（ a， b， ， l ） =1，则说 a，b， ， l 为互素。如果 a， b， ， l 中的每个数都与其它数互素，则称它们两两互素。* 大连理工大学8.1 素数 关于公约数有以下性质：性质 1 若 a是 b的倍数，则（ a， b） =b性质 2 若 a=bq+c，则（ a， b） = （ b， c） 定义 8.3（素数）：只有 1和自身为其因数的，大于 1的整数叫素数。 * 大连理工大学 to factor a number n1 is to write it as a pro
3、duct of other numbers: n=a x b x c note that factoring a number is relatively hard compared to multiplying the factors together to generate the number the prime factorisation of a number n is when its written as a product of primes l eg. 91=7x13 ; 3600=24x32x52 Relatively Prime Numbers & GCD two num
4、bers a, b are relatively prime if have no common divisors apart from 1 eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only common factor conversely can determine the greatest common divisor by comparing their prime factorizations and using least po
5、wers eg. 300=21x31x52 18=21x32 hence GCD(18,300)=21x31x50=68.2 费马 定理 Fermats Theorem 费马小定理 ：若 p 是素数， a 是正整数且不能被 p 整除， gcd(a,p)=1， 则： ap-1 = 1(mod p)。或者另一种形式：ap=a(mod p)，这种形式不要求 a 与 p 互素。 useful in public key and primality testing定理： (消去律 )对于 abac（ mod m）来说，若 gcd(a,m) 1则 bc(mod m) 例如 1：附加条件不满足的情况 63=
6、182 mod 8 a=6 n=8 67=422 mod 8 但 3 7 mod 8 例如 2：附加条件满足的情况53 157 mod 8 a=5 n=8 511=557 mod 8 311 mod 8 证明：构造模 p的完全剩余系 P = 0， 1, 2, ,p-1 ，step1： gcd(a, p) = 1，所以 A= 0*a, 1*a, 2*a, ,(p-1)*a也是模 p的一个完全剩余系。假设 ja=ka(modp) ,因为 gcd(a, p) = 1， j=k(modp),显然 j、 k 不能相等 A= 0*a, 1*a, 2*a, ,(p-1)*a也是模 p的一个完全剩余系。 就是说 P和 A在模 p意义下是相等的。因为 0 0a (mod p)，所以 P-0 与 A-0*a在模 p意义下是相等的。记 P=P-0,A=A-0*a* 大连理工大学
