《数论算法》教案 2章(同余运算)

《《数论算法》教案 2章(同余运算)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数论算法》第二章同余运算第2章同余运算1.同余概念2.性质内容3.剩余类→整数分类4.模幂运算5.一次不定方程要点同余及其计算应用：密码学公钥密码学【例】RSA公钥算法：准备：选大素数p、q，记n＝pq，φ(n)＝(p－1)(q－1)，再选正整数e，满足（e，φ(n)）≡1（modn）并求d，满足ed＝1（modφ(n)）e加密：明文串P编码为数字M，则密文C≡M（modn）d解密：M≡C（modn），再将数字M解码得明文串P2.1同余的概念及基本性质(一)同余概念【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果

2、a－b被m整除，即m

3、ab，记作a≡b（modm）；否则叫做模m不同余，记作ab（modm）【注】∵m

4、abm

5、ab1/57《数论算法》第二章同余运算∴a≡b（modm）a≡b（mod－m）假定：模m≥1。判断同余的方法一：利用定义【例1】7│28＝29－1，故29≡1（mod7）；7│21＝27－6，故27≡6（mod7）；7│28＝23－（－5），故23≡－5（mod7）；(二)性质【性质1】设m是一个正整数，a、b是两个整数，则a≡b（modm）存在整数k，使得a＝b＋km。（证）a≡b（modm）m

6、ab存在k

7、，使得a－b＝km，即a＝b＋km【性质2】同余是一种等价关系。即（i）自反性：a≡a（modm）（ii）对称性：a≡b（modm）b≡a（modm）（iii）传递性：a≡b（modm）且b≡c（modm）a≡c（modm）（证）（i）m│0＝a－aa≡a（modm）（ii）a≡b（modm）m│a－bm│b－a＝－(a－b)b≡a（modm）（iii）a≡b（modm），b≡c（modm）m│a－b，m│b－cm│(a－b)＋(b－c)＝a－ca≡c（modm）【例3】2/57《数论算法》第二章同余运算【性质3】（等价

8、定义）整数a、b模m同余a、b被m除的余数相同。（证）由欧几里得除法，存在q，r，q，r，使得a＝qm＋r，b＝qm＋r即a－b＝(q－q)m＋(r－r)或（r－r）＝(a－b)－(q－q)m故m│(a－b)m│(r－r)但0≤│r－r│＜m且m│(r－r)r－r＝0故m│(a－b)r－r＝0，即r＝r【性质4】设m为正整数，a、b、c、d为整数，若a≡b（modm），c≡d（modm）则（i）a＋c≡b＋d（modm）；（ii）ac≡bd（modm）。（证）已知a≡b（modm）且c≡d（modm）

9、a＝b＋hm且c＝d＋kma＋c＝(b＋hm)＋(d＋km)＝(b＋d)＋(h＋k)m，ac＝(b＋hm)(d＋km)＝bd＋(hd＋kb＋hkm)m由性质1即得结论。一般情形：ab（modm）（i＝1,2,…,k），则iikk（i）aibi（modm）i1i1kk（ii）aibi（modm）i1i1【推论1】a≡b（modm）na≡nb（modm），其中n为正整数。3/57《数论算法》第二章同余运算nn【推论2】a≡b（modm）ab（modm），其中n为正整数。【推论3】x≡y（modm），ab（mo

10、dm）（i＝1,2,…,iik），则2k2kaaxaxax≡bbybyby012k012k（modm）应用：求值a＋b（modm）＝（（a（modm））＋（b（modm）））（modm）ab（modm）＝（（a（modm））（b（modm）））（modm）na（modm）＝n(a（modm）)（modm）nna（modm）＝amodm（modm）2003【例6】2003年5月9日是星期五，问此后的第2天是星期几？2003（解）2＋5（mod7）2003≡（2（mod7）＋5（mod7））（mod7）36672≡

11、（22（mod7）＋5）（mod7）667≡（（8mod74mod7）（mod7）＋5）（mod7）667≡（（8mod7mod74）（mod7）＋5）（mod7）667≡（（1mod74）（mod7）＋5）（mod7）≡（1·4（mod7）＋5）（mod7）≡9（mod7）≡2（mod7）2003所以，此后的第2天是星期二。【例】设十进制整数n＝aaaa，则kk110103│n3│aaaakk1104/57《数论算法》第二章同余运算9│n9│aaaakk110（证）因

12、kn＝a10a10a≡aaaa（mod3）k10kk110kn＝a10a10a≡aaaa（mod9）k10kk110【例】设整数n的1000进制表示式为