密碼學(xué)與信息安全第8章數(shù)論入門(mén)2

1、最小公倍數(shù)最小公倍數(shù)最小公倍數(shù)最小公倍數(shù)最小公倍數(shù)最小公倍數(shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù) 每一個(gè)比每一個(gè)比1 1大的整數(shù)，要么本身是一個(gè)素?cái)?shù)，要大的整數(shù)，要么本身是一個(gè)素?cái)?shù)，要么可以寫(xiě)成么可以寫(xiě)成一系列不同素?cái)?shù)一系列不同素?cái)?shù)的乘積的乘積： 所有所有ai均為正整數(shù)，不均為正整數(shù)，不考慮乘積順序時(shí)，表示法是惟一的考慮乘積順序時(shí)，表示法是惟一的 paataaptppppaa.2121或或例如例如，999999 = 3337111337999999 = 3337111337素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)素?cái)?shù)8.2 Fermat8.2 Fermat8.2 Fermat8.2 Fermat8.2 Fermat8.2 F

2、ermat定理和定理和定理和定理和定理和定理和EulerEulerEulerEulerEulerEuler定理定理定理定理定理定理8.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler定理和定理和定理和定理和定理和定理和FermatFermatFermatFermatFermatFermat定理定理定理定理定理定理8.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler定理和定理和定理和定理和定理和定理和FermatFermatFermatFermatFermatFermat定理定理定理定

3、理定理定理 例如：20=22*51， 這樣， (20) =20(1-1/2)(1-1/5)=88.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler8.2 Euler定理和定理和定理和定理和定理和定理和FermatFermatFermatFermatFermatFermat定理定理定理定理定理定理8.3 Euler8.3 Euler8.3 Euler8.3 Euler8.3 Euler8.3 Euler定理和定理和定理和定理和定理和定理和FermatFermatFermatFermatFermatFermat定理定理定理定理定理定理解：解： 問(wèn)題歸結(jié)為解問(wèn)題

4、歸結(jié)為解 南北朝時(shí)期南北朝時(shí)期孫子算經(jīng)孫子算經(jīng)中有中有“物不知數(shù)物不知數(shù)”問(wèn)題：?jiǎn)栴}：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？七數(shù)之剩二，問(wèn)物幾何？8.4 8.4 8.4 8.4 8.4 8.4 中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理270321215=233，2331052=23Xb1 (mod m1)Xb2 (mod m2)Xbk (mod mk)8.4 8.4 8.4 8.4 8.4 8.4 中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理8.4 8.4 8

5、.4 8.4 8.4 8.4 中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理8.4 8.4 8.4 8.4 8.4 8.4 中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理中國(guó)剩余定理u課堂練習(xí)：三位運(yùn)動(dòng)員跨臺(tái)階，臺(tái)階總數(shù)在100-150級(jí)之間，第一位運(yùn)動(dòng)員每次跨3級(jí)臺(tái)階，最后一步還剩2級(jí)臺(tái)階。第二位運(yùn)動(dòng)員每次跨4級(jí)臺(tái)階，最后一步還剩3級(jí)臺(tái)階。第三位運(yùn)動(dòng)員每次跨5級(jí)臺(tái)階，最后一步還剩4級(jí)臺(tái)階。問(wèn)：這些臺(tái)階總共有多少級(jí)?uA. 119 B. 121 C. 129 D. 1318.5 8.5 8.5 8.5 8.5 8.5 離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù)離散對(duì)數(shù) 21 2(mod 7) 22 4(mod 7) 23 1(mod 7) 24 2(mod 7)