閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 本篇性質：

  • 適合的人：對密碼學、大數處理有興趣的人
  • 背景知識：Mod、費馬小定理、中國剩餘定理
  • 建議讀過Day 14:[離散數學]同餘（Mod）是什麼？、Day 15:[離散數學]中國餘式定理、Day 16:[離散數學]費馬小定理

▌前情提要

在Day 19:[離散數學] 處理某超難題(2)---用歐拉定理當中，我用歐拉定理解決了「23^4800017 除以35餘數是多少？」這個問題，並表示了自己對費馬小定理的鄙視（因為他竟然花了我一個週末的早上）

但是我沒想到....峰迴路轉....現在又出現了一個比歐拉定理更短的解法，就是——中國餘式定理＋費馬小定理
這實在是讓我太震驚了，我真的沒想過，我竟然會把這個討厭的問題連續解三次wow

▌複習：中國餘式定理＋費馬小定理

我發現我在Day 15:[離散數學] 中國餘式定理該篇中，沒有解釋什麼是中國餘式定理，只有解釋怎麼解中國餘式問題ＸＤ，所以這邊來做補充：

x  ≡  a1  (mod m1)
x  ≡  a2  (mod m2)
.
.
.
x  ≡  an (mod mn) 
如果m1、m2....mn`兩兩互質`，則x 有唯一解在(0,1,....m-1中）
>m = m1Xm2X.....mn

下面這條性質等下會用到：

如果m1、m2....mn`兩兩互質`，則x 有唯一解在(0,1,....m-1中）
m = m1Xm2X.....mn

至於費馬小定理如下

a^(p-1)≡1  mod P  // 如果 gcd(a,p)=1 `互質` 且 `p 為質數`

▌處理某超難題(3)---用費馬小定理＆中國剩餘定理

題目是「23^4800017 除以35餘數是多少？」

23^4800017 ≡ 2^4800017  (mod 7) //因為 23 ≡ 2 (mod 7)
23^4800017 ≡ 3^4800017  (mod 5) //因為 23 ≡ 3 (mod 5)
2^6 ≡ 1(mod 7) //根據費馬小定理
3^4 ≡ 1(mod 5) //根據費馬小定理
因此
23^4800017 ≡ 2^4800017 ≡ 2^6(800002) x 2^5 ≡  2^5 ≡ 4 (mod 7)  
23^4800017 ≡ 3^4800017 ≡ 3^4(1200004) x 3 ≡  3 (mod 5)  
現在知道
23^4800017 ≡ 2^4800017 ≡ 4 (mod 7)  
23^4800017 ≡ 3^4800017 ≡  3 (mod 5)  
要如何變出mod 35呢！？
精妙的地方來了，這時候可以使用中國剩餘定理
23^4800017 ≡ x ≡  4 (mod 7)  
23^4800017 ≡ x ≡  3 (mod 5)  
23^4800017 ≡ x (mod 5)  
因為5,7兩兩互質，因此x有唯一解在0,1,....34當中
7|x-4
5|x-3
x=18 //在0,1,....34當中慢慢找

答案就是18

沒想到這個費馬小定理＋中國剩餘定理的組合又比單純用費馬小定理、歐拉定理來得快很多

▌心得

• 雖然歐拉定理完勝費馬小定理，但費馬小定理＋中國剩餘定理組合，完勝歐拉定理
• 知識就是力量：
  • 使用好的工具，效率是不用的好幾倍
  • 使用複數的好工具，效率可能是單一工具的好幾倍