《數(shù)論算法》教案 2章(同余運(yùn)算)new

《《數(shù)論算法》教案 2章(同余運(yùn)算)new》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、《數(shù)論算法》第二章同余運(yùn)算第2章同余運(yùn)算1.同余概念2.性質(zhì)內(nèi)容3.剩余類→整數(shù)分類4.模冪運(yùn)算5.一次不定方程要點(diǎn)同余及其計算應(yīng)用：?密碼學(xué)?公鑰密碼學(xué)【例】RSA公鑰算法：準(zhǔn)備：選大素數(shù)p、q，記n＝pq，φ(n)＝(p－1)(q－1)，再選正整數(shù)e，滿足（e，φ(n)）≡1（modn）并求d，滿足ed＝1（modφ(n)）e加密：明文串P編碼為數(shù)字M，則密文C≡M（modn）d解密：M≡C（modn），再將數(shù)字M解碼得明文串P2.1同余的概念及基本性質(zhì)(一)同余概念【定義2.1.1】給定一個正整數(shù)m，兩個整數(shù)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《數(shù)論算法》第二章同余運(yùn)算∴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）；(二)性質(zhì)【性質(zhì)1】設(shè)m是一個正整數(shù)，a、b是兩個整數(shù)，則a≡b（modm）?存在整數(shù)k，使得a＝b＋km。（證）a≡b（modm）

6、?m

7、a?b?存在k，使得a－b＝km，即a＝b＋km【性質(zhì)2】同余是一種等價關(guān)系。即（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《數(shù)論算法》

8、第二章同余運(yùn)算【性質(zhì)3】（等價定義）整數(shù)a、b模m同余?a、b被m除的余數(shù)相同。（證）由歐幾里得除法，存在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?【性質(zhì)4】設(shè)m為正整數(shù)，a、b、c、d為整數(shù)，若a≡b（modm），c≡d（modm）則（i）a＋c≡b＋d（modm）；（ii）ac≡bd（modm）。（證）已知

9、a≡b（modm）且c≡d（modm）?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?由性質(zhì)1即得結(jié)論。一般情形：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為正整數(shù)。3/57《數(shù)論算法》第二章同余運(yùn)算nn【推論2】a≡b（modm）?a?b（modm），其中n為

10、正整數(shù)?！就普?】x≡y（modm），a?b（modm）（i＝1,2,…,iik），則2k2ka?ax?ax???ax≡b?by?by???by012k012k（modm）應(yīng)用：求值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

11、≡（2（mod7）＋5（mod7））（mod7）36672≡（?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天是星期二。【例】設(shè)十進(jìn)制整數(shù)n＝?aa?aa?，則kk?110103│n?3│a?a???a?akk?1104/57《數(shù)論

12、算法》第二章同余運(yùn)算9│n?9│a?a???a?akk?110（證）因kn＝a10???a10?a≡a?a???a?a（mod3）k10kk?110kn＝a10???a10?a≡a?a???a?a（mod9）k10kk?110【例】設(shè)整數(shù)n的1000進(jìn)制表示式為