取模計算機

模加法、減法、乘法、次方運算、逆元計算。學習 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 進行因式分解十分困難這一特性。