數論在密碼上的應用 (第 5 頁)

　1│2│3│4│5│6　

數論在密碼上的應用（第 5 頁）

楊重駿;楊照崑

首頁 | 搜尋

．原載於數學傳播第七卷第二期、第七卷第三期
．作者當時任教於美國海軍研究實驗所;美國佛羅里達大學統計系
‧對外搜尋關鍵字

五、如何尋找大質數

現在也許你有興趣學一點難一些的數論定理了。

定理5.1

設 a,m 互質，且

$\begin{displaymath}ab\equiv ac(\mbox{mod}\, m)\end{displaymath}$

則

$\begin{displaymath}b\equiv c(\mbox{mod}\, m)\end{displaymath}$

證明：

因 $a(b-c)\equiv 0$ (mod m)而a不含m之因子，故b-c必為m之倍數即 $b-c\equiv 0$ (mod m)本定理得證。

定義

設 m 為任何一正整數，定義 $\phi (m)$ 為所有小於 m 且與 m 互質的自然數的數目，例如取 m=5，則小於 m 又與m互質的數為 1,2,3,4，故 $\phi (5)=4$ ，又如取 m=12，則小於 m 而又與 m 互質的數為 1,5,7,1l，故 $\phi (12)=4$ 。 $\phi (m)$ 一般稱為尤拉函數，是數論中一個重要的函數。

定理5.2

設m為一自然數 $\phi (m)$ 表示所有小於m且與m互質的自然數，又以 r₁，r₂，…， $r_{\phi (m)}$ 表示這些自然數。。如果a與m互質，則 ar₁，ar₂，… $ar_{\phi (m)}$ 對 $\pmod{m}$ 而言是 r₁,r₂,…, $r_{\phi (m)}$ 的一個排列。

證明：

令 $x_i=ar_i \pmod{m}$ 且 $0\leq x_i <m$ ，則

ar_i=qm+x_i

因 ar_i 與 m 互質，故 x_i 必與 m 互質，因此 x_i 是 r₁,r₂,…, $r_{\phi (m)}$ 中的一員，但由定理5.2知 $x_i \equiv x_j \pmod{m}$ 之充要條件為 $r_i\equiv r_j$ ，故所有的 x_i 皆不相同，本定理得證。

定理5.3（費馬、尤拉定理）

設 w 與 m 為兩互質之自然數， $\phi$ 為尤拉函數，則

$\begin{displaymath} w^{\phi (m)}\equiv 1 \pmod{m} \end{displaymath}$

證明：

由定理5.2知

$\begin{displaymath} r_1r_2\cdots r_{\phi (m)} \equiv (wr_1)(w_r2)\cdots (wr_{\phi (m)}) \pmod{m} \end{displaymath}$

即

$\begin{displaymath} r_1r_2\cdots r_{\phi(m)} \equiv w^{\phi (m)}r_1r_2\cdots r_{\phi (m)} \pmod{m} \end{displaymath}$

因 $r_1r_2\cdots r_{\phi (m)}$ 與m互質，故

$\begin{displaymath} w^{\phi (m)}\equiv 1 \pmod{m} \end{displaymath}$

本定理得證。(此定理為定理2.3之推廣，因m為質數時， $\phi (m)= m-1$ )

我們又可以推廣定理2.2，若以 (a,b) 表示 a,b 之最大公約數(公因子)，若d=(a,b)，則存在兩整數 x,y 可使

ax+by=d

這個證法與定理2.2極相似，求法也是用輾轉相除法。

定理5.4

設 a,m 為兩個互質之正整數且 1<a<m，若 $a^k\equiv 1 \pmod{m}$ ，則 k 與 $\phi (m)$ 不互質。

證明：

設A為所有 $k\geq 1$ 且

$\begin{displaymath} a^k\equiv 1 \pmod{m} \end{displaymath}$

之集合，因 $\phi (m)\in A$ ，故A非空集合。令d為A中之最小一員，因 $a^1\equiv a \pmod{m}$ ，故 $1 \not\in A$ ，即d>1。設 $a^k\equiv 1 \pmod{m}$ ，令 k=qd+r， $0\leq r<d$ ，顯然由 $a^d\equiv 1 \pmod{m}$ 可得

$\begin{displaymath} 1\equiv a^k\equiv a^{qd+r} \equiv (a^d)^qa^r\equiv a^r \pmod{m} \end{displaymath}$

但因d為此集合中之最小者，故r=0，即k必為d之倍數，且因 $\phi (m)\in A$ ，可知(k， $\phi (m)$ ) $\geq d >1$ ，故k與 $\phi (m)$ 不互質。

現在我們終於走到了最後一個求證某數是質數的定理。

定理5.5 (魯克斯(Lucas)定理)

若 m 為大於 1 之整數，a 為任一與 m 互質之數，若 $a^{m-1} \equiv 1 \pmod{m}$ ，且對所有的 (m-1) 因子而言， $a^k \not\equiv 1 \pmod{m}$ 則 m 必為一質數。

證明：

設 m 不是質數，則由 $\phi (m)$ 之定義可知 $\phi (m) < m-1$ ，但由於 a,m 互質，由定理5.3知 $a^{\phi (m)} \equiv 1 \pmod{m}$ ，由已知條件及前定理知

$\begin{displaymath}(m-1,\phi (m))=d>1\end{displaymath}$

故d為m-1之一因子，由(5.1)知存在二整數 x,y 使得

$\begin{displaymath}(m-1)x+\phi (m)y=d\end{displaymath}$

即

$\begin{displaymath} \begin{array}{rcl} a^d&\equiv &a^{(m-1)x+\phi (m)y} \\ &\eq... ...m-1})^x(a^{\phi (m)})^y \\ &\equiv &1 \pmod{m} \\ \end{array}\end{displaymath}$

故(m-1)有一因子使得 $a^d\equiv 1 \pmod{m}$ ，與假設相矛盾，故m必為質數，本定理證畢。

這個定理若用來檢定一已知數m是否是質數並不容易，因為m-1的因子往往不易找到，前面已談過要分解一個大數的因子是件極費時的事，但這個定理來找一些大質數卻很容易，例如我們令

m=2ⁿ+1

則m的因子只有2，2²…，2ⁿ個，若我們能試一試一個可能與m互質的數a，像3，5，7之類的而且證得

$\begin{displaymath} a^{m-1}\equiv 1 \pmod{m} \end{displaymath}$

但

$\begin{displaymath} a^{2^{n-1}}\equiv 1 \pmod{m} \end{displaymath}$

則m必為質數。原因是若

$\begin{displaymath} a^{2^{n-1}}\equiv 1 \pmod{m} \end{displaymath}$

則對所有的 k<n-1，a^{2^k} 都不等於 $1 \pmod{m}$ 。（假如 $a^{2^k}\equiv 1 \pmod{m}$ 則 $a^{2^{n-1}} \equiv (a^{2k})^{2^{n-1-k}}$ $\equiv 1 \pmod{m}$ 。）

對一個固定的a而言，這個整個檢驗過程不過一次驗定a與m互質，二次 $\pmod{m}$ 而已，比硬除不知快了多少倍。

例：

若令 m=2ⁿ-1，則我們若能試出一與m 互質的數 a 像 3,5,7,… 而也證得

$\begin{displaymath} a^{m-1}\equiv 1 \pmod{m} \end{displaymath}$

且

$\begin{displaymath} a^2 \not\equiv 1 \pmod{m} \end{displaymath}$

及

$\begin{displaymath} a^{2^{n-1}-1} \not\equiv 1 \pmod{m} \end{displaymath}$

則m必為一質數(因m-1=2ⁿ-2=2(2^n-1-1))目前最大的質數多半都是這樣求得的，在1979年納爾遜與斯羅溫斯基 (H. Nelson & Slowinski) 用電子計算機證明 2⁴⁴⁴⁹⁷-1 是一個 13,395 位的質數。若以 100 元一千字作稿費，把這個數寫出來就是一千三百元，《數播》一頁大約二千字，所以把這個字寫出來要佔去六頁半的篇幅。

例：

若p為一質數，s，t為兩正整數，m=2^sp^t+1則我們若能試出一個與m互質的數a並證得

$\begin{displaymath} a^{m-1}\equiv 1 \pmod{m} \end{displaymath}$

且

$\begin{displaymath}a^{2^{s-1}p^t} \not\equiv 1 \pmod{m}\end{displaymath}$

$\begin{displaymath}a^{2^sp^{t-1}} \not\equiv 1 \pmod{m}\end{displaymath}$

則m為一質數。

例：

若 p,q 為兩質數，m=2pq+1，則我們若能試出一個與m互質的數d並證得

$\begin{displaymath}a^{m-l}\equiv 1 \pmod{m}\end{displaymath}$

$\begin{displaymath}a^{2p} \not\equiv 1 \pmod{m}\end{displaymath}$

$\begin{displaymath}a^{pq} \not\equiv 1 \pmod{m}\end{displaymath}$

及

$\begin{displaymath} a^{2q} \not\equiv 1 \pmod{m} \end{displaymath}$

則m為一質數。

如此這般，我們可以由小而大滾雪球式的很容易的找到許多大質數，由於走的路徑千變萬化，所可能找到的大質數也是一個天文數字。當然電子計算機是不可少的工具。在定理5.5中我們只要求任何一個與m互質的a，因此什麼與m互質的a都可以，根據一般的經驗，若m是質數，很快就可以找到一個小的a像3，5，7之類的滿足定理5.5，若不成功，就可以放棄另找了，反正侯選的m多得不得了，最近有一個極巧妙的結果由Lehmer, Soloorary與Shassen同時發現。即若m不是質數，則至少有一半以上的數從2，3，…，到m-1不能滿足 $a^{m-1}\equiv 1$ (mod m)，可惜我們沒有辦法在本文中證明此一結果。這個結果在另一個角度看來，即一個不是質數的m只有很小的機會能通過許多小的a。我們最後舉一個數字的例子。

例：

257=2⁸+1是不是質數?

因m-1=2⁸，故我們若能找到一個與m互質的a且

$\begin{displaymath} a^{2^8}\equiv 1 \pmod{m} \end{displaymath}$

$\begin{displaymath} a^{2^7} \not\equiv 1 \pmod{m} \end{displaymath}$

m即為質數。m=275不是3的倍數，我們先取a=3，我們一步一步的求 $3^{2^7} \pmod{m}$ 與 $3^{2^8} \pmod{m}$ 。

k 2^k $3^{2^k}\equiv ?$ $\pmod{357}$

0 2⁰=1 $3\equiv 3$

1 2¹=2 $3^2\equiv 9$

2 2²=4 $3^4\equiv 9^2\equiv 8$

3 2³=8 $3^8\equiv 81^2\equiv 136$

4 16 $136^2\equiv 249$

5 32 $249^2\equiv 64$

6 64 $64^2\equiv 241$

7 128 $241^2\equiv 256$

8 256 $256^2\equiv 1$

故257是一個質數。

　1│2│3│4│5│6　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：陳文是 ∕ 繪圖：簡立欣

最後修改日期：6/17/2002