{模數算數}

- 模運算子(modulo operator)

• 符號為 mod

• 除法關係與模運算子
  

  • 模數(modulus)：第二個輸入值(n)
  • 餘數(residue)：輸出值 r

- 餘數集合

• 符號為 Z_n

• 模運算產生的集合，被稱為「模 n 之最小餘數集合(Set of least residues modulo n)」

• Z_n = {0,1,2,3,...,(n-1)}

• 比較 Z 和 Z_n
  

- 同餘

• 符號為 ≡

• 用來表示兩個整數是同餘

剩餘類

• 符號為 [a] 或 [a]_n

• 在模 n 之下所有餘數為 a 的整數集合

• 例如

  • 

- Z_n 下的運算

• Z_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
  • 

- 反元素

加法反元素(Additive Inverse)

• 在模數算術中，整數一定有乘法反元素

• 整數和其加法反元素之和，在模 n 下與 0 同餘

  • a + b ≡ 0 (mod n)

• 例如：

  • 列出所有 Z_10 中互為反元素的數對
  • (0,0)、(1,9)、(2,8)、(3,7)、(4,6)、(5,5)

- 乘法反元素(Multiplicative Inverse)

• 在模數算術中，整數不一定有乘法反元素

• 整數和其乘法反元素的乘積必定在模 n 下與 1 同餘

  • a * b ≡ 1 (mod n)

  • 例如：

    • 列出所有 Z_11 中互為反元素的數對
    • (1,1)、(2,6)、(3,4)、(5,9)、(7,8)、(10,10)

• 求法：歐幾里德延伸演算法
  

  • 給定整數 n 和 b，且 gcd(n,b) = 1，可求出 b 在 Z_n 中的乘法反元素

  • 例如：

    • 11 在 Z_26 中的乘法反元素
      

      • gcd (26,11) = 1
      • 11 的乘法反元素為 -7 或 19

    • 23 在 Z_100 中的乘法反元素
      

      • gcd (100,23) = 1
      • 23 的乘法反元素為 -13 或 87

    • 12 在 Z_23 中的乘法反元素
      

      • gcd (26,12) = 2
      • 乘法反元素不存在

  • Z_10 的加法表和乘法表
    

- 加法和乘法的不同集合

• 加法反元素: Z_n
• 乘法反元素: Z_n*

- 另外兩種集合

• 密碼學中常使用：Z_p、Z_p*

• 使用之模數皆為「質數(Prime)」

• 例如：