檢視模除的原始碼

'''模除'''（閣稱'''模數'''、'''取模操作'''、'''取模運算'''等，英語：modulo 有時嘛叫做 modulus）得著的是一个數除了另外一个數的數量。

予定兩个正整數：被除數 $ a $ 佮除數 $ n $，_ a _ modulo _ n _ ( 縮寫為 $ a { \ bmod { n } } $ ) 得著的是使用歐幾里德除法的時陣 $ { \ frac { a } { n } } $ 的餘數。
比一个例：計算表達式 " $ 五 { \ bmod { 二 } } $ " 得著一，因為乎 $ 五 \ div 二=二 \ ldots 一 $（五除以二商二餘一）； 而且 " $ 九 { \ bmod { 三 } } $ " 得著無，因為乎 $ 九 \ div 三=三 \ ldots 零 $；注意：若使用計算器做除法，袂當整除的時陣，你袂得著商，是會得著一个小數，如：$ 五 \ div 二=二嬸五 $。

雖然通常情況下 $ a $ 和 $ n $ 攏是整數，但許多計算系統允准其他類型的數字操作，如：著浮點數取模。一个整數嘿 $ n $ 彼个取模仔的結果範圍為著：無到 $ n 影一 $（$ a { \ bmod { 一 } } $ 恆等於零；$ a { \ bmod { 零 } } $ 是未定義的，佇咧程式語言里會當通會致使除零錯誤）。
有關概念佇數論中的應用請參閱模算數。

當 $ a $ 和 $ n $ 攏為著負數的時陣，通常的定義就無適用矣，無仝的程式語言對結果有無仝的處理。

==定義佮餘數的計算==

佇咧數學中，取模運算的結果就是歐幾里德除法的餘數。當然嘛是真濟其他的定義方式。計算機佮計算機器有真濟種表示佮儲存數字的方法，因此佇咧無仝的硬體環境之下、無仝款的程式語言內底，取模運算有著無仝的定義。

會當看著所有的計算系統內底，$ n $ 除 $ a $ 得著商 $ q $ 佮餘數 $ r $ 攏滿足以下式的：


: :

毋過按呢做，做餘數無零時，餘數的符號猶原是有歧義的：餘數無零時，這伊的符號有兩種選擇，一个正、一个負。通常情況下，佇數論中總是使用正餘數。但是程式語言內底，餘數的符號決於程式語言的類型佮被除數 _ a _ 抑是除數 $ n $ 的符號。
標準 Pascal 和 ALGOL 六十八總是用零抑是正餘數；另外一寡程式語言，如 C 九十，當除數 $ a $ 佮除數 $ n $ 攏是負數的時陣，C 九十標準並無做具體的規定，是留予編譯器去定義並實現。
佇大多數系統頂懸 $ a { \ bmod { 零 } } $ 時未定義的，雖然有一寡系統定義等於 $ a $。閣較濟詳細參見表格。

* 足濟號模的實現攏使用矣 _ 截斷除法 _，這陣商對斷函數定義定義 $ q=\ mathrm { trunc } \ left ( { \ frac { a } { n } } \ right ) $，因此由等式'''一'''有，餘數 _ 佮被除數符號一致 _。商向零取整：結果等於普通除法所得的小數靠近零方向的第一个整數。


: $ r=a-n \ operatorname { trunc } \ left ( { \ frac { a } { n } } \ right ) $

* 高德納定義的 _ 取底除法 _ 的商對取底函數定義：$ q=[{ \ frac { a } { n } }] $。因此由等式'''一'''有，餘數 _ 佮除數符號一致 _。因為使用了取底函數，商總是向下跤取整，就算商已經是負數。


: $ r=a-n \ left [{ \ frac { a } { n } } \ right] $

* Raymond T . Boute 使用的歐幾里著定義，餘數總是非負的 $ 零 \ leq r $，這佮歐幾里著算法是一致的。

佇這个情形下：


: $ n > 零 \ Rightarrow q=\ left [{ \ frac { a } { n } } \ right] $


:$ n < 零 \ Rightarrow q=-\ left [-{ \ frac { a } { n } } \ right ] $

抑是等價數的：


: $ q=\ operatorname { sgn } ( n ) \ left [{ \ frac { a } { \ left | n \ right | } } \ right] $

遮的 $ \ mathrm { sgn } $ 是符號函數，所以


: $ r=a-| n | \ left [{ \ frac { a } { \ left | n \ right | } } \ right] $

* Common Lisp 嘛定義家己的捨入除法佮進位除法，商分別定義為 $ q=\ mathrm { round } \ left ( { \ frac { a } { n } } \ right ) $ 和 $ q=-\ left [{ \ frac {-a } { n } } \ right] $。
* IEEE 七百五十四定義矣一个取余函數，商人定義做 $ { \ frac { a } { n } } $，根據若入去約定取整。所致餘數的符號選定做 _ 最接近零 _。



==定定看毋著==

當取模的結果佮被除數符號相仝時陣，可能會致使想袂到的錯誤。

比一个例：若需要判斷一个整數敢是奇數，有人可能會試講這个數除二的餘數敢是一：

毋過佇一个號模結果佮被除數符號相仝的程式語言里，按呢做是毋著。因為當被除數 _ n _ 是奇數而且為負數的時陣，$ n { \ bmod { 二 } } $ 得著 − 一，這當時函數倒轉來「假」。

一種正確的實現是咧試模仔結果敢是替零，因為餘數做零時無符號的問題：

抑是考慮餘數的符號，有兩款狀況：餘數可能為一抑是影一。

==記號==

一寡計算器有號模 mod ( ) 揤鈕，足濟程式語言里嘛有類似的函數，通常像講 mod ( _ a _ , _ n _ ) 按呢乎。
有的語言嘛支持咧表達式內使用 " % "、" mod " 抑是 " Mod " 作為取模抑是取余操作符。


: ` a  % n `

抑是


: ` a mod n `

抑是佇一寡無 mod ( ) 函數的環境中使用等價的：
（ 注意'int'事實上等價於截斷函數 $ { \ frac { a } { n } } $，進行矣共零取整）


: ` a-( n * int ( a / n ) ) `

==等價性==

一寡取模操作，經過分解佮展開會當等仝款其他數學運算。這佇密碼學的證明中十分有用，比如講：迪菲-赫爾曼密鎖交換。

* 恆等式：
* $ ( a { \ bmod { n } } ) { \ bmod { n } }=a { \ bmod { n } } $
* 著所有的正數 $ x $ 有：$ n ^ { x } { \ bmod { n } }=零 $
* 若是 $ p $ 是一个質數，而且無為 $ b $ 的因數，現此時由費馬小定理有：$ ab ^ { p 影一 } { \ bmod { p } }=a { \ bmod { p } } $
* 逆運算：
* $ [(-a { \ bmod { n } } ) + ( a { \ bmod { n } } )]={ \ bmod { n } }=零 $ .
* $ b ^ { 影一 } { \ bmod { n } } $ 表示模反元素。若是唯一 $ b $ 佮 $ n $ 互質的時陣，等式倒爿有定義：$ [( b ^ { 影一 } { \ bmod { n } } ) ( b { \ bmod { n } } )] { \ bmod { n } }=一 $。
* 分配律：
* $ ( a + b ) { \ bmod { n } }=[( a { \ bmod { n } } ) + ( b { \ bmod { n } } )] { \ bmod { n } } $
* $ ab { \ bmod { n } }=[( a { \ bmod { n } } ) ( b { \ bmod { n } } )] { \ bmod { n } } $
* $ d { \ bmod { ( } } abc )=( d { \ bmod { a } } ) + a [( d \ backslash a{ \ bmod { b } } )] + ab [( d \ backslash a \ backslash b ) { \ bmod { c } }] $，符號 \ 是歐幾里德除法內面的除法操作符，運算結果做商
* $ c { \ bmod { ( } } a + b )=( c { \ bmod { a } } ) + [bc \ backslash ( a + b )] { \ bmod { b } }-[bc \ backslash ( a + b )] { \ bmod { a } } $ .
* 除法定義：干焦做式正爿有定義的時陣，即 $ b $、$ n $ 時間有：$ { \ frac { a } { b } } { \ bmod { n } }=[( a { \ bmod { n } } ) ( b ^ { 影一 } { \ bmod { n } } )] { \ bmod { n } } $，其他情形為未定義的。
* 乘法逆元：$ [( ab { \ bmod { n } } ) ( b ^ { 影一 } { \ bmod { n } } )] { \ bmod { n } }=a { \ bmod { n } } $ .

==性能問題==

會當通過依照數算紮餘數的除法實現取模操作。特殊情況下，若某一寡硬體，存在閣較緊的實現。
比如講：二的 n 次冪的模，會當通過逐家佮運算實現：


: ` x  % 二 n==x & ( 二 n-一 ) `

例， 假定 _ x _ 為正數：


: ` x  % 二==x & 一 `


: ` x  % 四==x & 三 `


: ` x  % 八==x & 七 `

佇咧進行位操作比取模操作效率較懸的設備抑是軟體環境內底，以上的形式的取模運算速度閣較緊。

編譯器會當自動識別出對二的 n 次冪取模的表達式，自動共優化做為著 ` expression & ( constant 影一 ) `。按呢會當佇咧兼顧效率的情況下寫出閣較清氣的代碼。這个優化咧號模結果佮被除數符號一致的語言內底（包括講 C 語言）袂當用啦，除非被除數是無符號整數。這是因為若被除數是負數，則結果嘛是負數，猶毋過 ` expression & ( constant 影一 ) ` 總是正數，進行按呢的優化就會致使錯誤，無符號整數是無這个問題。

==用途==

* 取模運算可用佇判斷一个數敢會當予另外一个數整除。著二取模即可判斷整數的奇偶性；對兩到 $ n 影一 $ 取模無會當判斷一个數敢是質數。
* 進制之間的轉換。
* 用佇咧求取上大公約數的研究相除法使用取模運算。
* 密碼學中的應用：對古老的凱撒密碼到現代定定用的 RSA、雞卵行曲線密碼，𪜶的實現過程攏使用矣取模運算。

==參見==

* 模 ( 消歧義 ) 和模 ( 術語 )——「模數（Modulo）」 這个詞的真濟用法，攏是一八空一年卡爾 ・ 被里德里希望 ・ 高斯引入模算數時產生的。
* 模冪運算
* 仝餘

==跤註==

==參考文獻==

[[分類: 待校正]]