上頁 123456 次頁

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

楊重駿;楊照崑

 


首頁 | 搜尋

.原載於數學傳播第七卷第二期、第七卷第三期
.作者當時任教於美國海軍研究實驗所;美國佛羅里達大學統計系
對外搜尋關鍵字
 
二、因子、質數、同餘式與費馬、尤拉定理

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

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

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

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

如果 nsm 除時有相同的餘數。例如

\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>0a,b 為整數之集合,此集合顯然不是空集合,因可取a=b=1,p+g>0。令d為此集合中之最小者,若d=1,則本定理得證,若d>1,令ap+bq=d>1,則任取此集中之另一數。 a'p+b'q,則我們若以da'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,否則rA集中一小於d之數,與假設d為最小數相矛盾,因r=0dA集中任何一數之因子。因

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

dpq之公因子。但pq之最大公因子為1,故d=1,定理證畢。

這是一個極有用的定理,讀者也許要問,我們如何找到ab使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
wm為二互質的正整數且m>w,則可找到一正整數θ使得

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

證明:
由定理知,有 ab 二整數使得aw+bm=1,因bmm之倍數,故

\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 為二質數 pq 之積,w 為任一與 m(即同時與 pq 互質之整數,則

\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}

wp-1m互質,由系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}

本系證畢。

我們還要利用到另一個簡單的定理,我們也在這節塈漭污狶飽C

定理2.4
令 (a1,a2,…,an) 為一含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}

又令 (x1,x2,…,xn) 為一由0與1組成的數列,即所有的xi不是0就是1,現設a1a2,…,an為已知,x1x2,…,xn為未知,c為一正整數,則方程式

\begin{displaymath}
c=\sum_{i=1}^n a_ix_i \eqno{(2.2)}
\end{displaymath}

只有一解或無解。

證明:
設此方程式有二解 (x1,x2,…,xn) 及 (x1',x2',…,xn') 則消去 c 之後可得

\begin{displaymath}\sum_{i=1}^n (x_i-x_i')a_i=0\end{displaymath}


\begin{displaymath}\vert x_i-x_i'\vert\leq 1 \end{displaymath}


\begin{displaymath}\sum_{i=1}^{n-1} a_i<a_n\end{displaymath}

an之係數必為0,即xn=xn',因此

\begin{displaymath}\sum_{i=1}^{n_1} (x_i-x_i')a_i=0\end{displaymath}

同理可得

\begin{displaymath}x_{n-1}=x_{n-1}',\cdots ,x_1=x_1'\end{displaymath}

此兩解原為一。本定理得證。

而要解(2.2)是非常容易的事,因為若

\begin{displaymath}c>a_1+a_2+\cdots +a_{n-1}\end{displaymath}

xn必為1,否則必為0,同理若

\begin{displaymath}c-x_na_n>a_1+a_2+\cdots +a_{n-2}\end{displaymath}

xn-1必為1,否則必為0,以此類推,一下子就解出來了。

這幾個定理就足夠瞭解新的密碼法了。

   

上頁 123456 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

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


編輯:陳文是 / 繪圖:簡立欣 最後修改日期:6/17/2002