[數論] 二次剩餘 (Quadratic Residues)

參考資料
Chapter 4: Quadratic residues http://www.math.uiuc.edu/~hildebr/453.spring11/nt-notes4.pdf
中文數學百科Wiki http://zh.math.wikia.com/wiki/二次剩餘?variant=zh-tw
Number of Quadratic Residues of a Prime
http://www.proofwiki.org/wiki/Number_of_Quadratic_Residues_of_a_Prime
Euler's Criterion http://www.proofwiki.org/wiki/Euler's_Criterion
第五講 二次剩餘 http://wenku.baidu.com/view/0c908d0dba1aa8114431d942

如果對同餘的的概念不熟悉，可以先看這一段影片：

「二次剩餘」定義
任意非零平方整數除以某個數後可能的餘數，我們稱之為「二次剩餘」。用數學式表達如下：

For $x,m\neq 0$, $a$ is a quadratic residue mod $m$ if $x^{2}=a$ (mod $m$). Otherwise, $a$ is a quadratic nonresidue(二次非剩餘).

例如對模$10$而言，可能的餘數集合為$\left \{ 0,1,4,5,6,9 \right \}$：

$\left\{\begin{matrix}0^{2}\equiv 0 & \\1^{2}\equiv 1 & \\2^{2}\equiv 4 & \\3^{2}\equiv 9 & \\4^{2}\equiv 6 & \\5^{2}\equiv 5 & \mathbf{(mod\; 10)}\\6^{2}\equiv 6 & \\7^{2}\equiv 9 & \\8^{2}\equiv 4 & \\9^{2}\equiv 1 &\end{matrix}\right.$

一般來說，因為 $x^{2}=0$ (mod $m$)總是有解，所以通常不會把 $0$ 考慮進去。這也是一開始定義 $x$ 時會強調是「非零整數」的原因。在此例中，模 $10$ 的二次剩餘是 $\left \{1,4,5,6,9 \right \}$。

若 $p$ 是一個奇質數(odd prime，除了 $2$ 以外的質數)，則在 $\{1, 2, \ldots, p - 1\}$ 中，模 $p$ 的二次剩餘與二次非剩餘的數量會是相等的。 換句話說，對一奇質數 $p$ 而言，模 $p$ 的二次剩餘數量 = 二次非剩餘數量 = $\frac{p-1}{2}$。

欲看證明可看參考資料第三個連結：Proof Wiki。簡單來說，就是要證明 $(p-i)^{2}\equiv i^{2}\; (\mathbf{mod}\; p)$。把 $(p-i)^{2}$ 展開，得到 $(p-i)^{2}=p^2-2pi+i^2\equiv i^2\; (\mathbf{mod}\; p)$，證明完畢。

例如以模 $11$ 為例，在 $1,2,...,10$ 中有一半為平方剩餘，他們分別與 $1^{2},2^{2},3^{2},4^{2},5^{2}$ 同餘。由於

$\left\{\begin{matrix}1^{2}\equiv 1 &\mathbf{mod}\: 11 \\2^{2}\equiv 4 &\mathbf{mod}\: 11 \\3^{2}\equiv 9 &\mathbf{mod}\: 11 \\4^{2}\equiv 5 &\mathbf{mod}\: 11 \\5^{2}\equiv 3 &\mathbf{mod}\: 11\end{matrix}\right.$

所以 $1,4,9,5,3$ 是模 $11$ 的平方剩餘。

現在我們知道對於某奇質數 $p$，求出模 $p$ 之二次剩餘的方法。反過來看，現在我給你一個數 $a$，有沒有辦法判別 $a$ 是不是模 $p$ 的二次剩餘呢？當然，我們可以照著上面的步驟，先將模 $p$ 的二次剩餘全部找出來，再看 $a$ 是不是在剩餘集合裡面。但對於數字較大的 $p$，這樣顯得很沒效率。因此我們要介紹一種判別法，可以幫助我們快速判別一個數是否為模 $p$ 之二次剩餘。

Euler's Criterion(歐拉準則)：判定給定的整數是否是一個質數的二次剩餘
定義：若 $(a,p)=1$，$p$ 是奇質數，則
(1) $a$ 是模 $p$ 的平方剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$
(1) $a$ 是模 $p$ 的平方非剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv -1\; (\mathbf{mod}\; p)$

注意上式給的是"充分必要"條件，因此有必要去證明。證明可參考 Euler's Criterion 網頁，過程中會用到 Euler's Totient Theorem。

充分性：若 $a$ 是模 $p$ 的平方剩餘，則  $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$。
<pf> Assume $a$ is a quadratic residue modulo $p$. $\exists \; k\in \mathbb{Z}$ s.t. $k^{2}\equiv a\; (\mathbf{mod\; }p)$. $(k^{2})^{\frac{p-1}{2}}\equiv k^{p-1}\equiv a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod\; }p)$ by Congruence of Powers and Fermat's Little Theorem.

必要性：若 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$，則 $a$ 是模 $p$ 的平方剩餘。
<pf> $(a^{\frac{p-1}{2}})^{2}\equiv a^{p-1}\equiv 1^{2}\equiv 1\; (\mathbf{mod}\; p)$. Let $b$ is a *primitive root for $p$. $\exists k\in \mathbb{Z}$ s.t. $a=b^{k}$.

$a^{\frac{p-1}{2}}=(b^{k})^{\frac{p-1}{2}}=b^{\frac{k(p-1)}{2}}\equiv 1\; (\mathbf{mod}\; p)$. $\frac{k(p-1)}{2}$must be a multiple of $(p-1)$, so $\frac{k}{2}$ is an integer, which means $k$ is even. $a=b^{k}$ is the square of $b^{\frac{k}{2}}.$

*何謂原根？Let $p$ be a prime. Then $b$ is a primitive root for $p$ if the powers of $b$, $1$, $b$, $b^2$, $b^3$, ...
include all of the residue classes mod $p$ (except $0$).

歐拉準則給了我們另一種判別 $a$ 是否為 $p$ 的二次剩餘的方法，這顯然比列出剩餘系、然後一個一個慢慢檢驗來的方便。但是，一旦 $p$ 很大的時候，計算 $a^{\frac{p-1}{2}}$ 絕非易事！因此數學家又想到另一種方式去檢驗二次剩餘。這種方式其實和歐拉準則有點像，但表達的方式略有差異。

Legendre Symbol(勒讓得符號，二次特徵)
定義：令 $p$ 是奇質數，$a$ 是整數，$(a,p)=1$。 Legendre Symbol $\left ( \frac{a}{p} \right )\overset{def}{=} a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$

在歐拉準則中我們已經看過 $a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$ 了。Legendre Symbol 則是改用另一種符號來表示：$\left ( \frac{a}{p} \right )$。我們可以進一步改寫上面的定義，使其看起來更簡潔。

Legendre Symbol 其實是 Jacobi Symbol 的特例(當分母是質數 $p$ 的特例)。使用 Legendre Symbol 時別忘了分子與分母的限制(分母是質數，分子與分母互質)。有些書會寫 $\left ( \frac{a}{p} \right )=0$ if $p\mid a$，也就是說當 $a$ 是 $p$ 的倍數，$(a,p)=p$，則 $\left ( \frac{a}{p} \right )=0$。因為我們一般只討論當 $a$ 與 $p$ 互質的情形，所以沒有把 $0$ 寫在定義裡。

Legendre Symbol 有下列性質。想看證明的可以參考這個網頁，或是看 YouTube 這段影片。
1. $\left ( \frac{a^2}{p} \right )=1$。
2. 若 $a_{1}\equiv a_{2}\; (\mathbf{mod}\; p)$，有 $\left ( \frac{a_{1}}{p} \right )=\left ( \frac{a_{2}}{p} \right )$。
3. $\left ( \frac{a}{p} \right )$ 是完全積性函數，即 $a=a_{1}a_{2}...a_{n}$ 時，有 $\left ( \frac{a}{p} \right )=\left ( \frac{a_{1}}{p} \right )\left ( \frac{a_{2}}{p} \right )...\left ( \frac{a_{n}}{p} \right )$。

透過第三個性質，把 $a$ 拆解成較小的數字相乘，再去計算其 Legendre Symbol 的值，會比直接用 $a$ 去計算來的方便多了。最後總結一下這篇文章介紹的三種判別二次剩餘的方法。
1. 逐項代入法，亦即逐項檢驗 $p$ 的剩餘系。
2. 歐拉準則
3. 利用 Legendre Symbol

RSA加密演算法

參考資料
Proof of the RSA Algorithm https://sites.google.com/site/danzcosmos/proof-of-the-rsa-algorithm
RSA算法原理 http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

資料加密(Data encryption)，如同替家門或金庫上鎖一樣，都是為了防止外人輕易窺知裡頭的東西。加密可分為「對稱式」與「非對稱式」。「對稱式」是指用同一把鑰匙進行加密和解密動作，「非對稱式」則是指加解密時採用不同的鑰匙。

對稱式的加解密方法比較直觀，也比較方便，但這也是它的致命傷。因為對稱式加密系統，加解密都是用同一把鑰匙，萬一鑰匙在某個環節被破解，等於宣告整個系統瓦解，因此有必要改進這種加密系統模式。

非對稱式加密系統是利用公開鑰匙(Public Key)和私密鑰匙(Private Key)進行加密解密動作。公開鑰匙是公開資訊，用於加密資料時使用；私密鑰匙是隱藏資訊，只有解密者擁有，用於解密時使用。

關鍵：加密用公鑰，解密用私鑰。

RSA加密演算法於1973年，由Ron Rivest、Adi Shamir 和 Leonard Adleman 三人提出，1977年正式對外發表。

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。

RSA演算法會用的數論工具主要有二：Euler's theorem(歐拉定理)及Modular inverse(模反元素)。

Euler's theorem 會在製作公鑰時用到，modular inverse 用於製作私鑰。公私鑰製作流程如下圖。

有了公鑰和私鑰元素，接著我們來看如何進行加解密的操作，並針對RSA的安全性做討論。

加解密的流程如下圖，我們限制$m<n$：

我們必須證明 $c^{d}\equiv m$ (mod $\varphi (n)$) 這條同餘式的正確性。

<pf> $c^{d}\equiv (m^{e})^d \equiv m^{ed}\equiv m^{k \cdot \varphi (n)+1}$ (mod $\varphi (n)$), where $k$ is an integer.

CASE 1. If $(m,n)=1$, according to Euler's theorem, we have $m^{\varphi (n)}\equiv 1$ (mod $n$), so $m^{k\cdot \varphi (n)}\equiv 1$ (mod $n$). Therefore, $m^{k\cdot \varphi (n)+1}\equiv m$ (mod $\varphi (n)$)

CASE 2. If $m$ and $n$ are not coprime, you can try to prove it yourself. The answer is written in the 2nd reference.

透過上式證明，我們可以確定加解密的算法是正確的，但它的安全性呢？我能否光憑 $n$, $e$ 兩數，就可以算到 $d$ 呢？

$d$ 從何而來？$d$ 是在上述的步驟5出現，由 $e$ 而來；而 $e$ 是步驟4中由 $\varphi (n)$，也可以說由 $n$ 而來；而 $n$ 是兩個質數的乘積。因此$d$ 的破解與否，$n$ 的質因數分解扮演莫大的角色。如同我們在一開始提到到這段話：

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。