網(wǎng)絡(luò)安全理論與應(yīng)用第三章(編輯修改稿)
2025-02-26 11:13 本頁面
【文章內(nèi)容簡介】 而敵人則始終無法弄清他的部隊究竟有多少名士兵。 4 中國剩余定理 例子： （ 孫子算經(jīng) ） 今有物不知其數(shù) 。 三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二 。 問物幾何 ？ 答曰：二十三 。 23≡ 2*70+3*21+2*15(mod 105) （ 口訣：三人同行七十稀 ， 五樹梅花廿一枝 ， 七子團圓月正半 ， 除百零五便得知 。 ） 問 ， 70， 21， 15如何得到的 ？ 原問題為： 求解同余方程組 2( m od 3 )3 ( m od 5 )2( m od 7 )xxx?????? ?? 注意 ：若 x0為上述同余方程組的解，則 x0?=x0+105*k(k∈ z) 也為上述同余方程組的解。有意義的是，解題口訣提示我們先解下面三個特殊的同余方程組 (1) (2) (3) 的特殊解 =? =? =? 以方程（ 1）為對象，相當于解一個這樣的同余方程 35y≡1(mod 3)，為什么呢？ 原因是，從（ 1）的模數(shù)及條件知， x應(yīng)是 35的倍數(shù)，于 是可以假設(shè) x＝ 35y有 1( m od 3 )0( m od 5 )0( m od 7 )xxx??? ??? ??0( m od 3 )1 ( m od 5 )0( m od 7 )xxx??? ??? ??0( m od 3 )0( m od 5 )1 ( od 7 )xxx??? ??? ??100??????????010??????????001?????????? 35y≡1(mod 3)相當于 //35y=33y+2y 2y≡1 (mod 3) //同乘 2的乘法逆元 21 解出 y=2（ mod 3） //y=3k+2 于是 x?35*2 ?70(mod 105) //x=35y=105k+70 類似地得到 （ 2） 、 （ 3） 方程的模 105的解 2 15。 于是有 得 70001???????????21010???????????15100???????????)105(mod2315*221*370*2100201030012232??????????????????????????????????????????????? 《 孫子算經(jīng) 》 的“物不知數(shù)”題雖然開創(chuàng)了一次同余式研究的先河，但由于題目比較簡單，甚至用試猜的方法也能求得，所以尚沒有上升到一套完整的計算程序和理論的高度。真正從完整的計算程序和理論上解決這個問題的，是南宋時期的數(shù)學家秦九韶。 秦九韶在他的 《 數(shù)書九章 》 中提出了一個數(shù)學方法“大衍求一術(shù)”，系統(tǒng)地論述了一次同余式組解法的基本原理和一般程序。 中國剩余定理 ：設(shè)自然數(shù) m1,m2,… mr兩兩互素 ， 并記 N=m1m2… mr， 則同余方程組 在模 N同余的意義下有唯一解 。 1122( m od )( m od )...............( m od )rrx b mx b mx b m???????????? 證明：考慮方程組 ， (1=i=r) 由于諸 mi(1=i=r)兩兩互素，這個方程組作變量替換，令 x=(N/mi)*y，方程組等價于解同余方程： (N/mi)y≡1(mod mi) 1110( m od )........0( m od )1 ( m od )0( m od )...............0( m od )iiirxmxmxmxmxm??????? ????????????? 若要得到特解 yi,只要令 xi=(N/mi)yi 則方程組的解為 x0=b1x1+ b2x2+ … + brxr (mod N) 模 N意義下唯一 。 例一：由以下方程組求 x x ?1mod 2 x ?2mod 3 x ?3mod 5 x ?5mod 7
教學課件相關(guān)推薦
鄂ICP備17016276號-1