費馬小定理、尤拉定理、RSA演算法證明

今天會比較晚發文有一部分原因和這個有關@@，我絕對不會說另一部分原因是因為我整個下午都在睡覺和滑手機><。

其實，費馬小定理很好證，網路上也一堆教學，而 RSA 演算法只要知道尤拉定理也是小菜一疊，真正讓我頭疼的是尤拉定理的證明。

會這樣說是因為我有點自虐症，放著簡單的證明手法不用偏偏要選一個自認漂亮的證明手法，結果想了一整個早上也沒想出來，後來就放棄了QQ。

以下是我的學習成過，大家請過目。

費馬小定理

尤拉定理

要了解尤拉定理必須先了解尤拉函數。尤拉函數 𝜑(n) 為小於 n 以及與 n 互質的整數個數，因此它有個特性。若 n 為質數，則 𝜑(n) 為 (n-1)，這是因為 n 只有 1、n 這兩個質因數而已。

而尤拉定理的證明只要將費馬小定理中所有的 (n-1) 皆改為 𝜑(n) 就可以得證。

尤拉函數其實還有一個蠻特別的等式，如下：

不瞞大家說，我就是想利用這兩行來倒出尤拉定理，可惜以失敗告終。不過，我還是把我證到一半的證明 po 出來讓大家看看，說不定高手在民間，還真會有人幫我倒出來也說不定。

RSA演算法

我最主要就是要證 RSA 演算法，又我為甚麼要證它，因為我有自虐症😂本來在寫 picoCTF 寫到和 RSA 相關的題目，好奇心起就想說來證明一下。以下是我的成果。

結尾

看了看時間也來到了 12:37，因為剛做完運動加上夜晚瞌睡蟲的侵擾，總感覺自己有點胡言亂語了。如果以上有那裡寫錯的地方歡迎糾正。

最後祝大家有個好夢。