iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 18
1

https://ithelp.ithome.com.tw/upload/images/20191004/20115060n3pKvVQk4B.jpg

{模數算數}

- 模運算子(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)」

  • 例如:


上一篇
『 Day 17』密碼學卷宗 數論篇 - 上卷
下一篇
『 Day 19』密碼卷宗 古典篇 - Caesar & Vigenere
系列文
到處挖坑,現在該來還(填)願(坑)ㄌ !!!30

尚未有邦友留言

立即登入留言