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

　1│2│3│4│5│6　

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

楊重駿;楊照崑

首頁 | 搜尋

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

二、因子、質數、同餘式與費馬、尤拉定理

若 m,n 為兩整數，且 m>0，則以 m 除 n 可得二整數 α 與 r，使得

$\begin{displaymath}n=\alpha m+r\end{displaymath}$

其中 α 稱為商，r 稱為餘數，且 $0\leq r<m$ 。若 r=0，則我們說 n 可被 m 所整除，m 為 n 之因子，n 為 m 之倍數，若一數除 1 與本身之外無其他因子，則此數稱為質數，例如 2,3,5,7,11 都是質數，4,6,9,12 卻不是質數。我們定義 n 與 s 對 m 有同餘數：

$\begin{displaymath} n = s \pmod{m} \end{displaymath}$

如果 n 與 s 被 m 除時有相同的餘數。例如

$\begin{displaymath} \begin{eqalign} 12 & \equiv 2 \pmod{10} \; , \\ 8 & \equiv 5 \pmod{3} \end{eqalign}\end{displaymath}$

有一個關於同餘式的簡單定理，我們把它們列出來，讀者很容易證出來。

定理2.1: 若 $p \equiv q \pmod{m}$ ， $a \equiv b \pmod{m}$ ，則 $ap \equiv bq \pmod{m}$ 。

若兩正整數 p,q 的最大公因子(約數)是 1，則我們稱 p,q 互質，以

(p,q)=1

表示之。現在我們要證一個有關兩個互質數的一個基本定理。

定理2.2

若兩正整數 p,q 互質，則可以找到二整數(不一定正) a,b，使得

ap+bq=1

證明：

令 A 為含所有 x=ap+bq>0，a,b 為整數之集合，此集合顯然不是空集合，因可取a=b=1,p+g>0。令d為此集合中之最小者，若d=1，則本定理得證，若d>1，令ap+bq=d>1，則任取此集中之另一數。 a'p+b'q，則我們若以d除a'p+b'q，則得

$\begin{displaymath} a'p+b'q = \alpha d+r \, , \; 0\leq r<d \end{displaymath}$

代入

d=ap+bq

則得

$\begin{displaymath}(a'-\alpha a)p+(b'-\alpha b)q=r\end{displaymath}$

此r必為0，否則r為A集中一小於d之數，與假設d為最小數相矛盾，因r=0故d為A集中任何一數之因子。因

$\begin{displaymath} \begin{eqalign} p & \in A(a=1,b=0) \\ q & \in A(a=0,b=1) \end{eqalign}\end{displaymath}$

故d為p，q之公因子。但p，q之最大公因子為1，故d=1，定理證畢。

這是一個極有用的定理，讀者也許要問，我們如何找到a與b使ap+bq=1呢?一般可用輾轉相除法。

例：

找整數 a,b，使得 5a+9b=1。因

$\begin{displaymath}9=5+4,\,5=4+1,\end{displaymath}$

故

1=5-4=5-(9-5)=2 x 5-9 x 1

故

$\begin{displaymath}a=2,\, b=-1\end{displaymath}$

系2.2

若w與m為二互質的正整數且m>w，則可找到一正整數θ使得

$\begin{displaymath} w\theta \equiv 1 \pmod{m} \end{displaymath}$

證明：

由定理知，有 a、b 二整數使得aw+bm=1，因bm為m之倍數，故

$\begin{displaymath} aw\equiv =1 \pmod{m} \end{displaymath}$

令

$\begin{displaymath}a=\phi m+\theta\, , 0\leq \theta <m\end{displaymath}$

則得

$\begin{displaymath} \theta w \equiv 1 \pmod{m} \mbox{ {\fontfamily{cwM0}\fontseries{m}\selectfont \char 47} } \theta\geq 0 \end{displaymath}$

因θ不可能為0，故本系得證。

最後我們要用到一個不容易證明的「費馬、尤拉 (Fermat-Euler) 定理」。但因為我們只用到這個定理比較容易證明的特殊形式，我們就只證明簡單的部分。

定理2.3

若m為質數，w為任一與m互質之整數，則

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

證明：

先把w寫成w個1的和，則由多項式定理知

$\begin{displaymath}(1+1+1+\cdots +1)^m\end{displaymath}$

之展開式中除w個1之外，都含有m之因子，(m為質數m!中之m不可能消去)，故

$\begin{displaymath} w^m\equiv w \pmod{m} \end{displaymath}$

兩邊乘以系2.2中之a，即

$\begin{displaymath} aw\equiv 1 \pmod{m} \end{displaymath}$

得

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

本定理證畢。

系2.3

若 m 為二質數 p、q 之積，w 為任一與 m(即同時與 p 與 q 互質之整數，則

$\begin{displaymath} w^{(p-1)(q-1)}\equiv 1 \pmod{m} \end{displaymath}$

證明：先用定理之證明法得

$\begin{displaymath} \begin{eqalign} w^{p-1} &\equiv 1 \pmod{m} \\ w^{q-1} &\equiv 1 \pmod{m} \end{eqalign}\end{displaymath}$

由定理2.1可得

$\begin{displaymath} (w^{p-1})^q\equiv 1 \pmod{m} \end{displaymath}$

即

$\begin{displaymath} w^{pq-q}\equiv 1 \pmod{m} \end{displaymath}$

即

$\begin{displaymath} w^{pq-q} \equiv 1 \equiv w^{p-1} \pmod{m} \end{displaymath}$

因w^p-1與m互質，由系2.2之證明可知存在一 a 使 $aw^{p-1}\equiv 1 \pmod{m}$ ，上式乘以a得

$\begin{displaymath} aw^{pq-q} \equiv 1 \pmod{m} \end{displaymath}$

即

$\begin{displaymath} aw^{p-1}w^{pq-p-q+1}\equiv w^{(p-1)(q-1)} \equiv 1 \pmod{m} \end{displaymath}$

本系證畢。

我們還要利用到另一個簡單的定理，我們也在這節裏把它證完。

定理2.4

令 (a₁,a₂,…,a_n) 為一含n個正整數的數列，並滿足

$\begin{displaymath}\left\{ \begin{array}{rcl} a_1&\geq&1 \\ a_2&>&a_1 \\ a_3&>... ...dots& \\ a_n&>&a_1+a_2+\cdots +a_{n-1} \\ \end{array}\right. \end{displaymath}$