何謂模倒數 modulus inverse

何謂模倒數,參考文章:  https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses

要先明瞭何謂模序列.一個模的序列產生是用除法取其餘數, 故須先要有除數 n, 及被除數 x, 兩者做除法運算得出商數q及餘數r,而除數n就稱為模(modulus),模運算所產生的數必定在序列0 .. n-1之間的一個整數, 在c語言中用%當作模運算符號,因此  r = x % n , 0=<r<n-1, 我們可以定義模函數:

                                                    r = f(x) mod n = mod(x,n)

為了找尋它的反函數 f', 必須滿足 f'(r) = f('f(x)) mod n = x mod n, 但這不是模倒數的定義方式

再談談何謂倒數(inverse),一個數A的倒數就是1/A,記號改成 A-1(指數負一, 意思等同倒數, 並不是減一的意思),在模運算中不能用除法運算只能用乘法,而A的倒數滿足條件是

                                                  Ａ＊Ａ-1 =1

因此對於模倒數,用上述相同的邏輯,一個模n的倒數R(mod n)就是R-1因為

                                                  (R*R-1)(mod n) =1 (mod n)


這個才是模倒數真正的定義,如同乘法運算所陳述的倒數語意,當乘上某一個數之後經運算等於1,該數就是此運算倒數,因模運算產生序列必定在模序列 0 .. n-1 之間,因此只要在該範圍內找尋d判斷  (R*d)%n==1 如果成立那d就是R的模倒數(modulus inverse), 但是當 n 數字太大時, 上述找尋將花太久的時間. 有個演算法叫作Extended Eculidean Algorithm可以改善這個問題:

p.s. 在模運算中的倒數, 須注意它並不是中文語意中的某個數的倒數,它只是一個名詞用語 modulus inverse. 在中文語意中一個整數N的倒數是 1/N, 它必定小於1, 但模運算中的倒數並非這個意思, 實際上模n倒數是一個介於序列0 .. n-1之間的一個整數, 如果模運算結果等於 0 那它必定是模n的倍數