本文作者[遇見數學創作小組]：蘑菇長頸鹿

在 我們主要介紹了同餘運算的來源，以及模的加減法。在實數運算中，乘法與除法運算也扮演者十分重要的角色。在這篇文章中，我們將介紹模的乘除法運算，乘方運算，以及模的逆。

模的乘法運算

模的乘法(modular multiplication)運算為

同樣的，我們通過一個實際的例子來理解。

我們假設 A=4, B=5, C=3。若上式成立，等式左邊等於 (4*5)mod 3 = 20 mod 3 =2，等式右邊為
((4 mod 3)*(5 mod 3))=(1*2) mod 3=2 mod 3。

因此，從實際計算中我們可以看出等式成立，下面我們不妨從實際圖例中觀察一下，這個運算是怎樣運作的呢？

若我們將 (4×5) mod 3 看作圍繞圓順時針轉 5 次，步長為 4 的轉動，那麼我們可以得到上圖中的圖（1）。與加減法時相同，模運算中圍繞圓的完整環不影響終點的位置。因此，從上圖中（2），（3）可以看出，加粗部分為對終點有實際影響的移動。圖（3）中幫助我們省去了步長多餘的移動；由於此題中若次數為 3 的整數倍，無論步長為幾，最終模 的結果均為 ，因此，圖（2）幫我們省去了多餘的移動次數。

模的冪運算

因為模的冪運算(modular exponentiation)實際上是重複的乘法運算，因此我們有

在平時我們計算的過程中，A^B 常常會得到非常大的數，例如下面兩個例子：

• 2^{90}=1237940039285380274899124224
• 7^{256}=221359540004604815545018861547494593...

這就會在我們的計算過程，以及計算機的工作過程造成很大的工作量。即便我們算出了答案，也很難直接計算它的模。

那麼怎樣減少計算量呢？接下來就要靠模的冪運算髮揮作用了。

假設我們現在要計算 2^90 mod 13 , 如果我們先將 2^90 算出來，想要計算其餘數則必須要完整精確的數字，但是我們的計算器只能最大顯示到 2^50 的完整數字。這個時候我們需要做一個小拆分，即 2^90=2^50 × 2^40 進而再利用模的乘法運算問題就可以解決啦。

在第二個問題中，對於 7 次冪的數字，普通計算器上只能完整顯示 7^10，那我們怎樣用計算器計算出 7^256 mod 13 呢？顯然，將 7^256 拆分成 25 個 7^10 和 1 個 7^6，並不是很高效。

其實，對於模的冪運算還有另外一種表達方法。即為，

而這種表達方式，則可以幫助我們更快速的解決問題。

我們先通過舉例的方法觀察一下對 7 進行冪運算時前幾項餘數的規律，

在表格的最後兩行我們發現，所得結果為 1 和 −1 ，當我們把其放入原式當中，就會得到我們想要的結果，以 −1 為例（帶入 1 同理），即為

因此，我們可以利用 1 和 −1 這樣特殊的數字，來幫助我們簡化模的冪運算計算，但是在我們計算的過程中會發現，並不是所有的運算最終都會得到 1 或 −1 ，比如這道題目：計算 2^40(mod10)。和上一道題目一樣觀察一下對 7 進行冪運算時前幾項餘數的規律，

從上面的計算我們可以看出，雖然沒有得到 1 或 −1，但結果是四組一

因此，在實際運算中，我們往往根據不同的題目選擇以上三種方法進行計算。

模的除法運算

我們考慮 4≡8(mod4) ，因為 2 ≢ 4(mod4) ，所以我們不能直接簡單的在等式兩邊都除 2 。這就說明，一般情況下模的除法運算是不成立的。但是，如果我們增加一個條件，存在 k 與 C 互質，那麼模的除法運算(modular division)就成立,如下式：

模的逆運算

說到逆運算，我們不妨回憶一下，什麼樣的數字才稱為逆(inverse).

一個數字乘它的逆等於 1。從一些基礎的運算我們知道：

• 數字 A 的逆為 1/A ，因為 A∗(1/A)=1。（例如， 5 的逆為 1/5 ）
• 除 0 以外的所有實數都有逆。
• 一個數字乘 A 的逆就相當於除以 A 。（例如， 10/5 與 10∗1/5 相同）

雖然在模的運算中不存在除法運算，但我們仍然有逆運算，類比數的逆運算，我們可以得到:

在瞭解了模的逆後，怎樣找到逆成為我們現在的主要問題。一種比較天真的辦法來找到 A(modC) 為：

1. 把 A∗B mod C 中的 B ，從 0 到 C−1 依次帶入來計算。
2. 當 A∗B mod C=1 時，所得 B 即為所求。

在這裡要注意，B mod C 只存在於整 0 到 C 中，因此測試時給予 B 更大的值是沒有必要的。來看下面的一個示例：

閱讀更多 遇見數學 的文章

關鍵字: 蘑菇 運算 數學