# 尤拉函數與尤拉定理

## 摘要
為了理解RSA加密法，我打算先從原理的數論下手。利用網站上的資料與老師的協助，完成了本次的探究。我初步理解了尤拉函數與定理的證明，也延伸學習證明過程中必要的數論，對未來再次接觸密碼學時，能夠有基礎來銜接知識。

## 研究動機

在現代密碼學，RSA作為較廣泛的加密方式，但到底是如何加密的著實令人好奇。為了理解RSA的運作，不可不談到的即是尤拉函數與尤拉定理。兩者皆是在RSA加密上的基礎，理解這定理的運用，將可以推廣到RSA加密上，所以本次報告將會試證尤拉函數與定理，以深刻了解RSA的基礎架構，也可順帶理解未曾見過的數論。因為本次報告使用的是LaTex的數學公式書寫方式，所以也能藉此學習LaTex的運作方式。

## 尤拉函數的證明

#### 尤拉函數 :小於n並且與n互質的正整數數目。
$$
\begin{eqnarray}
\phi \left ( n \right ) &=& \prod_{i=1}^{r} p_{i}^{k_{i} -1}(p_{i} -1) \\
&=&n(1-\frac{1}{p_1} )(1-\frac{1}{p_2} )...(1-\frac{1}{p_r} )
\end{eqnarray}
$$
___
### 證明

#### 1.尤拉函數是積性函數， 如果m,n互質，則有以下結果:
$$
\varphi (mn)=\varphi (m)\varphi (n)
$$

example:
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$
以72來說，因為72=9x8，所以將與9不互質的數刪掉，則剩下φ(9)=6行，剩下每一行有8個數，只有φ(8)=4個數與8互質(即框起來的數)，這些即為不大於72且與72互質的數，共有φ(9)xφ(8)=24。推論出φ(72)=24
$$
\varphi(72)=\varphi(8 \times 9)=\varphi(8)\varphi(9)
$$
而只要一個算術函數f，滿足滿足f(ab)＝f(a)f(b)，其中a和b互質，就稱函數f為積性函數。因此對於任意的自然數n，可將n分解成下式
$$
n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}
$$

#### 2.若m是質數p的k次方冪，則有以下結果:
$$
\varphi (m)=\varphi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^{k}(1-\frac{1}{p})
$$
因為除了p的倍數外，其他數都跟n互質。

example:
$$
以\varphi(8)為例: \varphi (2^3)=2^3-2^{3-1}=2^{3-1}(2-1)=4 \\
(與8互質的數為1,3,5,7)
$$

#### 3.綜合以上兩點，若有n有質因數分解式$n=p_1^{k_1}p_2^{k_2}...p_r^{k_r}$，則推論出以下式子:

\begin{eqnarray}
\varphi (n) &=&\varphi(\prod_{i=1}^{r}p_i^{k_i}) \\
&=&\prod_{i=1}^{r} \varphi (p_i^{k_i})\\
&=&\prod_{i=1}^{r} p_{i}^{k_{i} -1}(p_{i} -1)\;\;\;\;(由第二點推得)\\
&=&n\prod_{i=1}^{r} (1-\frac{1}{p_i} ) \\
&=&n(1-\frac{1}{p_1} )(1-\frac{1}{p_2} )...(1-\frac{1}{p_r} )\\
\\
&&其中p_1,p_2...p_r為n所有的質因數
\end{eqnarray}

example :
$$
\varphi(91)=91(1-\frac{1}{7} )(1-\frac{1}{13} )=72
$$

## 尤拉定理

若${\displaystyle n,a}$為正整數，且${\displaystyle n,a}$互質（即最大公因數為1），則:

$$
a^{\varphi(n)} \equiv 1(mod\; n)
$$
___
### 證明準備:

在證明之前，我們必須先了解些專有名詞。
同餘類:根據對m同餘的關係，可以將全體整數分成m個類，對模m同餘的數屬於同一類，稱為模m的一個同餘類。
簡化剩餘系:又稱為整數模 n 乘法群，說明在同餘理論中，模 n 的互質同餘類組成一個乘法群

我們將會在證明中會用到「所有與n互質的同餘類構成一個群」的性質，所以需要以上的概念。

### 證明

$$
{
設r_1，r_2\;...\; r_{\varphi(m)} 為模m的一個簡化剩餘系。
考慮 ar_1，ar_2\;...\; ar_{\varphi(m)}\\
\because \;if\;\;ar_i \equiv ar_j(mod\; m)\\
\because (a,m)=1 \Rightarrow \; r_i \equiv r_j (mod\;m) \Rightarrow i=j \\
\therefore ar_1，ar_2\;...\; ar_{\varphi(m)}兩兩不同餘(mod \;m)\\
\Rightarrow{ar_1，ar_2\;...\; ar_{\varphi(m)}}形成一個模m的簡化剩餘系\\
\Rightarrow ar_1，ar_2\;...\; ar_{\varphi(m)}\equiv r_1，r_2\;...\; r_{\varphi(m)}(mod\; m)\;\;\;\;\;(可將r_1，r_2\;...\; r_{\varphi(m)}消去) \\
\Rightarrow a^{\varphi(m)} \equiv 1 (mod\;m)
}
$$

#### example:
$$
{
以m=30為例，比30小和跟30互質的數為1，7，11，13，17，19，23，29 ，\varphi (30)=8。\\
當(a,30)=1，1a，7a\;...\;29a 對30的餘數會都不相同。\\
將兩個與30互質的數相乘後，依舊會保留與30互質的特性，所以
這八個數的餘數也只能在\\\left \{ 1，7，11，13，17，19，23，29 \right \}的乘法群裡 \\
\begin{eqnarray}
因&此&1\times 7\times 11\times 13\times 17\times 19\times 23\times 29\times a^8 \\
&\equiv& 1\times 7\times 11\times 13\times 17\times 19\times 23\times 29\; (mod\;m)\\
&\Rightarrow& a^8 \equiv 1 \;mod(30)
\end{eqnarray}
}
$$

### 從尤拉定理與費馬小定理的關聯

在尤拉函數中，當n是質數的時候，$\varphi (n)=n-1$ ，剛好與費馬小定理得出的公式雷同，所以我們可以帶入費馬小定理，最終推得出以下公式。

$$
a^{n-1} \equiv 1(mod\; n)
$$

## 結論與心得

RSA加密以同餘、尤拉定理、尤拉函數、模反元素作為基礎來加密，本次的報告中試證了其中的兩者，而因為本次的證明都需要用到同餘的技巧，所以順帶的理解了同餘的意義與性質，獲益是非常之多的，畢竟高中課程並未多講同餘這個技巧。
在閱讀公式的過程中，難免會有尚未學習到的部分，例如尤拉函數中的積函數、尤拉定理的簡化剩餘系等數論，所以多方的去尋找資料，去詢問老師這些數學符號和定義是什麼意思，我認為是這次報告中使我解決問題的能力提升的部分，也學習到了更多新奇的數論。
再加上書寫以上的公式時，採用的是LaTex的輸入方式，一開始是完全一竅不通，但隨著寫的次數變多，越來越能理解整體的概念，增進了更多的知識，也在未來如果也有需要運用到數學公式的報告中，排版能夠使閱讀者清晰的了解。

## 參考資料

[RSA加密演算法原理](https://www.gushiciku.cn/pl/2Jpg/zh-tw)

[尤拉定理+費馬小定理](https://www.itread01.com/content/1543925897.html)

[尤拉函數 Euler φ function(筆記)](http://peikailiao.blogspot.com/2013/08/euler-function.html)

[歐拉定理的論證](https://www.youtube.com/watch?v=P8VjTGAQQUo)

[(專題)尤拉定理與舉例(數論)](https://www.youtube.com/watch?v=Vqmhfhto6p8)

[整數模n乘法群-維基百科](https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4)

[尤拉定理（數論）-維基百科](https://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86_%E6%95%B0%E8%AE%BA)

[歐拉函數-維基百科](https://zh.wikipedia.org/zh-tw/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0)