iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
2
自我挑戰組

到處挖坑,現在該來還(填)願(坑)ㄌ !!!系列 第 17

『 Day 17』密碼學卷宗 數論篇 - 上卷

https://ithelp.ithome.com.tw/upload/images/20191003/20115060ExKObZd3i9.jpg

在真正進入密碼學之前,首先,我們先拿起紙筆,開始算數學囉!!! ( * ̄▽ ̄)o ─═≡※:☆

想不到吧~ 意外吧~ 藍瘦香菇了嗎~

{整數算數}

- 整數集合

  • 標記為 Z

  • 是從負無窮大到正無窮大的所有整數形成的集合

  • Z = { ...,-2,-1,0,1,2,... }

- 二元運算

  • 二元運算可接受兩個輸出值,產生一個輸出值

- 整數除法

  • n 除 a,可以得到 q 和 r,可以表示成 a = q*n+r

  • 整數的除法演算法

- 整除性

  • 性質

    • 若 a/1 ,則 a = ±1
    • 若 a/b 且 b/a ,則 a = ±b
    • 若 a/b 且 b/c ,則 a/c
    • 若 a/b 且 a/c ,則 a/(m * b + n * c),其中 m 和 n 為任意整數
  • 歐幾里德演算法(Euclidean algorithm)

    • 又稱「輾轉相除法」
    • gcd(a,0) = a
    • gcd(a,b) = gcd(b,r),其中 r 是 a 除以 b 的餘數
  • 歐幾里德延伸演算法

    • 貝祖等式 (Bézout’s identity):給定兩個不全為零的整數 a 和 b,存在整數 s 和 t,稱為貝祖係數,使得 s * a + t * b = gcd(a,b)


    • 例如

      • 給定 a = 161 和 b = 28 ,求 gcd(a,b) 及 s 和 t 的值

      • 給定 a = 17 和 b = 0 ,求 gcd(a,b) 及 s 和 t 的值

      • 給定 a = 0 和 b = 45 ,求 gcd(a,b) 及 s 和 t 的值

  • 線性 Diophantine 方程式

    • 雙變數的線性 Diophantine 方程式是一種型態為 ax+by=c 的方程式
    • 特解:
      • x_0=(c/d)s
      • y_0=(c/d)t
    • 通解:
      • x=x_0+k(b/d)
      • y=y_0−k(a/d)
      • 其中 k 為整數

上一篇
『 Day 16』HITCON CMT | 心得文
下一篇
『 Day 18』密碼卷宗 數論篇 - 下卷
系列文
到處挖坑,現在該來還(填)願(坑)ㄌ !!!30

尚未有邦友留言

立即登入留言