模運算(密碼學/算法)

模運算的概念
- 模運算是一種算術運算，常寫作a mod n，表示整數a除以正整數n后的余數。
  模數是模運算中的除數n，它決定了結果的范圍。
公式表達：
- 對于任意整數a和正整數n，可以將a表示為：a = qn + r，其中0 ≤ r < n，q是整數商，即q = ?a/n?。
  a除以n的余數是a mod n。
示例：
- 11 mod 7 = 4（11除以7的余數是4）
- -11 mod 7 = 3（-11除以7的余數是3)

同余關系：
- 當兩個整數a和b除以同一個正整數n得到相同的余數時，稱a和b模n同余。
  表達式為a ≡ b (mod n)。
- 同余具有傳遞性 a ≡ b (mod n) and b ≡ c (mod n) 則 a ≡ c (mod n)
模運算（加，減，乘）
- (a + b) mod n = [(a mod n) + (b mod n)] mod n
- (a + b) mod n = [(a mod n) + (b mod n)] mod n
- (a * b) mod n = [(a mod n) * (b mod n)] mod n
模除運算（逆運算）
模除運算跟實際意義上的除法并不相同，比如
- 逆元，如果有如下公式成立
  $a^{'} * a) mod (n) = 1$
  則稱 $a^{'}$ 為 a 在模n下的一個逆元。
- 逆元的作用
  逆元在模除的場景下需要使用到，比如在如下取模運算中
  $\frac{a}{v} mod(n)) * v) mod(n)$
  如下面例子所示：
  $(\frac{103}{3} mod(5)) * 3 ) mod(5) = 1$
  我們希望通過計算機運算的結果為整數3，由于計算機計算精度有限，就會導致實際運算的結果可能為2.999… ，特別是存在多次模除的時候，就會導致實際進行嚴重下降，計算機處理過程如下：
  $\begin{aligned} &(\frac{103}{3}mod(5)) * 3 ) mod(3) \\ & = ( (34.333......... )mod(5)) * 3 ) mod(5) \\ &= (4.333...... * 3) mod(5) \\ &=12.999.... mod(5) \\ &= 2.999... \end{aligned}$
  故通過逆元的存在將模除過程中的除法運算改為乘法運算，證明如下：

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/94542.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/94542.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/94542.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！