在真正進入密碼學之前，首先，我們先拿起紙筆，開始算數學囉！！！ ( *￣▽￣)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 為整數