第2周 密码学中的数学基础知识.ppt

文档介绍：密码学中的数学知识因子若b|a,则称b为a的因数若a=kb,而b既非a又非1,:1,2,3,4,6,1212的真因子:2,3,4,6整除实例Q:下面哪个是对的?77|77|7724|240|2424|0实例Q:,a是整数,如果用n去除a,得商为q,余数为r,则可以表示为:a=qn+r,0≤r<n,用amodn表示余数r,则r≡:令a=17,n=5,则17=3×5+2,r=2≡17mod5模运算典型实例时钟模12的运算同余设n是正整数,a,b是整数,如果amodn≡bmodn,则称整数a和b模n同余,记为a≡bmodn。显然,a≡bmodn,则n|(a-b).例如:a=17,b=-8,n=5,因为17=3×5+2,-8=-2×5+2,则17mod5≡-8mod5,通常记为:17≡-:下面哪个是真的?33(mod17)3-3(mod17)172177(mod5)-1313(mod26)同余式实例A:33(mod17)True.(3-3=0,divisiblebyall)3-3(mod17)False.(3-(-3))=177(mod5)-177=-5能整除5-1313(mod26)True:-13-13=-①[(amodn)+(bmodn)]modn=(a+b)modn②[(amodn)-(bmodn)]modn=(a-b)modn③[(amodn)×(bmodn)]modn=(a×b)modn