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

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

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

2、记作ab（modm）【注】∵∴a≡b（modm）a≡b（mod－m）66/66《数论算法》第二章同余运算假定：模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）存在k，使得a－b＝km，即a＝b＋km【性质2】同余是一种等价关系。即（i）自反性：a≡a（modm）（ii）对称性：a≡b（modm）b≡a（modm）（iii）传递性

3、：a≡b（modm）且b≡c（modm）a≡c（modm）（证）（i）m│0＝a－aa≡a（modm）（ii）a≡b（modm）m│a－bm│b－a＝－(a－b)b≡a（modm）（iii）a≡b（modm），b≡c（modm）m│a－b，m│b－cm│(a－b)＋(b－c)＝a－ca≡c（modm）【例3】【性质3】（等价定义）整数a、b模m同余66/66《数论算法》第二章同余运算a、b被m除的余数相同。（证）由欧几里得除法，存在q，r，，，使得＝qm＋r，b＝m＋即a－b＝(q－)m＋(r－)或（r－）＝(a－b)－(q－)m故m│(a－b)m│(r－)但0≤│r－│＜m且m│(r－)

4、r－＝0故m│(a－b)r－＝0，即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）a＝b＋hm且c＝d＋kma＋c＝(b＋hm)＋(d＋km)＝(b＋d)＋(h＋k)m，ac＝(b＋hm)(d＋km)＝bd＋(hd＋kb＋hkm)m由性质1即得结论。一般情形：（modm）（i＝1,2,…,k），则（i）（modm）（ii）（modm）【推论1】a≡b（modm）na≡nb（modm），其中n为正整数。【推论2】a≡b（modm）（m

5、od66/66《数论算法》第二章同余运算m），其中n为正整数。【推论3】x≡y（modm），（modm）（i＝1,2,…,k），则≡（modm）应用：求值a＋b（modm）＝（（a（modm））＋（b（modm）））（modm）ab（modm）＝（（a（modm））（b（modm）））（modm）na（modm）＝n(a（modm）)（modm）（modm）＝（modm）【例6】2003年5月9日是星期五，问此后的第22003天是星期几？（解）＋5（mod7）≡（（mod7）＋5（mod7））（mod7）≡（（mod7）＋5）（mod7）≡（（）（mod7）＋5）（mod7）≡（（）（mo

6、d7）＋5）（mod7）≡（（）（mod7）＋5）（mod7）≡（1·4（mod7）＋5）（mod7）≡9（mod7）≡2（mod7）所以，此后的第天是星期二。【例】设十进制整数n＝，则3│n3│9│n9│66/66《数论算法》第二章同余运算（证）因n＝≡（mod3）n＝≡（mod9）【例】设整数n的1000进制表示式为n＝则7（或11，或13）│n7（或11，或13）│－（证）因n＝≡（mod7）n≡（mod11）n≡（mod13）例如，判断n＝1234567能否被7整除：12345678＝12×10002＋345×1000＋678而(12＋678)－345＝345不能被7、11、13整

7、除故1234567不能被这3个数整除。【例】设十进制整数n＝，则11│n11│－2│n2│4│n4│4│8│n8│8││n│例如，判断n＝981234576能否被11、2、4、8、16整除。因为(6＋5＋3＋1＋9)－(7＋4＋2＋8)＝3，故n不能被11整除66/66《数论算法》第二章同余运算因2│6，故2│n4│76或4│2×7＋6＝20，故4│n8│4×5＋2×7＋6＝40，故8│n因8×4＋4×5＋10×7＋6≡