取模計算機

計算模加法、減法、乘法、次方運算和反元素。學習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 進行質因數分解極為困難這項特性。