资源描述：
《高级密码学数论初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3部分数论初步3.1素数定义2.1（整除、倍数、因数）设a、b为整数，例如30=2×15=3×10=5×62，3，5都是30的因数，30是2，3，5的倍数。若存在整数c，使b=ac，则称a可整除b。记作a
2、b。b叫做a的倍数，a叫做b的因数。若不存在这样的整数c，则称a不能整除b。记作ałb。我们有2，3，5分别整除30。记作分别记为：2
3、30，3
4、30,5
5、30。或30被2，3，5分别整除。如果a
6、1，则a=1事实上，对于g=bⅹg1（g1为整数），有b
7、g。又例如7
8、84，-7
9、84，5
10、20，19
11、171，13
12、03ł8，5ł12。0是任何非零整数的倍数，1是任何整数的因
13、数，任何非零整数a是其自身的倍数。由此我们可以得出这样的结论如果a
14、b、b
15、a，则a=b如果b≠0，b则可整除0。如果b
16、g、b
17、h，对于任何整数m和n，则满足b
18、(mg+nh)。对于h=bⅹh1（h1为整数），满足b
19、h。所以有mg+nh=mbg1+nbh1=bⅹ(mg1+nh1)所以b能整除mg+nh。例b=7，g=14，h=63，m=3，n=27
20、14，7
21、63，必满足7
22、(3ⅹ14+2ⅹ63)。又由于（3ⅹ14+2ⅹ63）=7(3ⅹ2+2ⅹ9)所以有：7
23、(3ⅹ14+2ⅹ63)=7
24、(7(3ⅹ2+2ⅹ9)定义2.2（公约数、最大公约数、素数、互素、两两互素）设整数a,b,
25、….l若有整数d满足d
26、a，d
27、b，….，d
28、l，则称d为它们的公约数。公约数中最大者成为它们的最大公约数。记作：gcd(a,b,….,l)如果gcd(a,b,….,l)=1,则说a,b,…l互素。如果a,b,….,l中的每个数都与其它数互素，则称它们两两互素。性质2若关于公约数有以下性质：性质1若a是b的倍数，则gcd（a，b）=b。则gcd(a,b)=gcd(b,c)定义2.3(素数)只有1和自身为其因数的大于1的整数叫素数。显然除2外，所有素数都是奇数。寻找素数的方法：设n是一个正整数，如果对所有素数p<=根号n,都有płn，则n一定是素数。性质1若p为素数，则对任一整数a
29、，p
30、a或Pła性质2若p为素数，p
31、ab性质3素数有无穷多个。3.2同余或按模计算定义2.5（同余）设n为一自然数，若a-b为n的倍数，即(a-b)
32、n，则称a与b关于模n同余。则p
33、a或p
34、b。记为：若a与b关于模n不同余，则记作：7
35、（39-4）39mod7=4性质1模n具有以下性质：（1）自反性对任一整数a，有证：对任一正数a，我们有a=a+0•n，所以有：(2)对称性如果amodn=bmodn，则a≡b(modn)证：若则存在整数k使得：a=b+kn从而有：b=a+(-k)n因此有(3)传递性若,则证:若，则分别存在整数k1，k2使得：a=b+k1nb=c+k2n从而有
36、a=c+(k1+k2)n因为k1+k2是整数，所以有例3.3传递性例子39≡32（mod7)，32≡25(mod7),所以有39≡25（mod7)例3.4自反性39≡39mod725≡25mod7例3.5对称性32≡39（mod7)39≡32（mod7)性质2若则：根据以上性质，可得到以下两个重要的推论。推论1若则定义2.6(同余类)定义2.6（完全剩余系）推论2若则全体整数按照对模n的同余关系可分为n类，使得同类之数关于模n同余，不同类之数关于模n不同余。这样划分的类叫做模n同余类。整数a,b模同余的充要条件是a,b被n除的余数相同。全体整数对模n可划分为n个同余类。在模n的每
37、个同余类中取出一个数作为代表构成的集合叫做模n的完全剩余系。能被n所整除其余数为0的为一个剩余类。其余数为1的为一个剩余类，余数为2的为一个剩余类，….，余数为n-1为一个剩余类，被分成n个不同的剩余类，这就是模n的一个完全剩余系。0，1，2，3，4，5，6，7，8，9为模10的一个完全剩余系。例：设正数n=10，对任意a的集合C0={a+10k}是模n=10的剩余类。1，2，3，4，5，6，7，8，9，10为模10的一个完全剩余系。0，-1，-2，-3，-4，-5，-6，-7，-8，-9为模10的一个完全剩余系。集合定义3.7缩剩余系.若n为素数，则它的缩剩余系使n-1个元素的
38、集合。定义3.8（Euler函数）显然模n的素剩余系含有ø(n)。集合叫模n的最小非负完全剩余系。叫模n的绝对最小剩余系。从模n的n个同类中取出与n互素的同余类，从中各取一个代表构成的集合叫模n的缩剩余系。由于0能被任何数整除，所以它永远不会是素剩余系中的元素。设n唯一自然数，数列与n互素的个数叫n的Euler函数，记作ø(n)。由于两个数很大，在运算时可能遇到困难，更重要的是会产生溢出。有了这个定理，使得参与运算的两个数在参与算时，各自先求一次模运算，使得在对整个取模运算时整个
