取模計算機

模加法、減法、乘法、次方運算、逆元計算。學習 RSA 加密中使用的模運算。

基本取模 — 模加法 — 模減法 — 模乘法 — 模次方運算 — 模逆元 —

指南

瞭解更多

取模運算(a mod m)是 a 除以 m 後所得的餘數。例如：17 mod 5 = 2。它在日常生活中經常用到，如時鐘計算(24小時制)、星期計算等。在程式設計中，它對於陣列索引循環、雜湊函式等都不可或缺。

模加法：(a + b) mod m。模乘法：(a × b) mod m。在計算大數時，為防止溢位，應在每一步都取模。例如：(12 + 8) mod 5 = 20 mod 5 = 0。

計算 a^b mod m 時，若直接求次方，數值會變得過大。採用分治法的快速冪演算法，可以在 O(log b) 時間內完成計算。這是 RSA 加密的核心運算。

模逆元是指使 (a × x) mod m = 1 成立的 x。僅當 a 與 m 互質時才存在。使用擴充歐幾里得演算法可在 O(log m) 時間內求出。它常用於密碼解密和分數計算。

RSA 是一種以模次方運算和模逆元為核心的公開金鑰密碼系統。加密：c = m^e mod n，解密：m = c^d mod n。它利用了對兩個大質數之積 n 進行因式分解十分困難這一特性。

負數取模會得到什麼結果？

不同語言對負數取模的處理方式不同，但本計算機按照數學定義計算，結果始終介於0到m-1之間。例如：-7 mod 5 = 3。

如果模數(m)輸入為0會怎樣？

除以0是未定義的運算，因此模數不能為0。m 必須是大於等於1的整數。

什麼情況下模逆元不存在？

只有當 a 與 m 的最大公因數不為1（即兩者不互質）時，模逆元才不存在。例如當 m 為偶數且 a 也為偶數時，就無法求出逆元。

這個計算機在實際中有哪些用途？

模運算廣泛應用於雜湊表的桶索引計算、循環排程（星期、時間）、RSA 等公開金鑰加密系統的加解密運算，以及 ISBN 等驗證碼的檢核。