密碼學(xué) 模運(yùn)算

取模運(yùn)算（“Modulus Operation”）

它和取余運(yùn)算（“Remainder Operation ”）兩個概念有重疊的部分但又不完全一致。主要的區(qū)別在于對負(fù)整數(shù)進(jìn)行除法運(yùn)算時操作不同。取模主要是用于計(jì)算機(jī)術(shù)語中。取余則更多是數(shù)學(xué)概念。 模運(yùn)算在數(shù)論和程序設(shè)計(jì)中都有著廣泛的應(yīng)用，奇偶數(shù)的判別到素?cái)?shù)的判別，從模冪運(yùn)算到最大公約數(shù)的求法，從孫子問題到凱撒密碼問題，無不充斥著模運(yùn)算的身影。雖然很多數(shù)論教材上對模運(yùn)算都有一定的介紹，但多數(shù)都是以純理論為主，對于模運(yùn)算在程序設(shè)計(jì)中的應(yīng)用涉及不多。

“?！笔侵敢粋€計(jì)量系統(tǒng)的計(jì)數(shù)范圍；如時鐘，12個整點(diǎn)為計(jì)算范圍，則模為12；計(jì)算機(jī)也是一個計(jì)量機(jī)器，模為32位或者64位；

32位計(jì)算機(jī)正常理解 在模 范圍內(nèi)能表達(dá)的 有 [0, 232-1]；那么負(fù)數(shù)該怎么表達(dá)呢，所以出現(xiàn)了補(bǔ)碼；也就是 正數(shù) + 負(fù)數(shù) 正好達(dá)到模的溢出閥值232；所以在計(jì)算機(jī)中負(fù)數(shù)是用補(bǔ)碼方式表達(dá)的原因；

關(guān)于補(bǔ)碼的例子：在12模的時鐘中；假設(shè)當(dāng)前時針指向10點(diǎn),而準(zhǔn)確時間是6點(diǎn),調(diào)整時間可有以下兩種撥法

• 倒撥4小時,即：10-4=6 (10-4) mod 12 = 6
• 順撥8小時：10+8=12+6=6 （10+8）mod 12 = 6

在以12模的系統(tǒng)中，加8和減4效果是一樣的；因此凡是減4運(yùn)算，都可以用加8來代替。對“?！倍?，8和4互為補(bǔ)數(shù)。實(shí)際上以12模的系統(tǒng)中11和1、10和2、9和3、7和5、6和6都有這個特性；共同的特點(diǎn)是兩者相加等于模

“取?！睂?shí)質(zhì)上是計(jì)量器產(chǎn)生“溢出”的量，它的值在計(jì)量器上表示不出來，計(jì)量器上只能表示出模的余數(shù)(取模)；任何有模的計(jì)量器，均可化為加減法運(yùn)算

5 mod 3 = 2 例子中；模 為 3；2 為取模的值

取模和取余的區(qū)別

1.相同

假設(shè)有整數(shù)a和b，那么取模/取余運(yùn)算可以分為兩步運(yùn)算：

求整數(shù)商：c = a/b; 計(jì)算模/余數(shù)：2.計(jì)算?；蛘哂鄶?shù)： r = a - c*b.

2.不同

取余運(yùn)算 在計(jì)算商值時 商值向0方向舍入；靠近0原則 取模運(yùn)算 在計(jì)算商值時 商值向負(fù)無窮方向舍入；盡可能讓商值小的原則(不超多商值的最大值)

求模運(yùn)算和求余運(yùn)算在第一步不同: 取余運(yùn)算在取c的值時，向0 方向舍入(fix()函數(shù))；而取模運(yùn)算在計(jì)算c的值時，向負(fù)無窮方向舍入(floor()函數(shù))。

例子

取模

取余

java 中 % 是取余運(yùn)算；Python中 % 是取模運(yùn)算

Python代碼

## 取模，Python中可直接用%，計(jì)算模，r = a % b
def mod(a, b):
    c = a // b
    r = a - c * b
    return r


## 取余
def rem(a, b):
    c = int(a / b)
    r = a - c * b
    return r
x=mod(-5,3)
y=rem(-5,3)
print(x,y)

輸出結(jié)果 1 -2