費馬小定理和素數在密碼學的應用

陳政培

【摘要】素數一直以來都是數學界研究的重要課題，而素數的正確利用可以為密碼學提供有效的工具。本文將要介紹獲取并檢驗素數的方法，以及著名的RSA密碼的原理。

【關鍵詞】求模運算 ?RSA算法 ?米勒拉賓算法 ?密碼學

【中圖分類號】G642 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標識碼】A ? ? ?【文章編號】2095-3089（2016）11-0199-02

公元前在古希臘就產生了早期的算術，直到20世紀初才開始使用數論這個詞匯。而從早期到中期的這段時間數論卻幾乎沒有什么發展，直到19世紀才由費馬、梅森、歐拉、高斯、黎曼、希爾伯特等人發展起來。而且主要內容是尋找素數通項公式，由初等數論向解析數論和代數數論轉變，但也產生很多無法解決的猜想。20世紀有些猜想得以解決，但現在仍然有很多結論是以黎曼猜想一類未能被完全證明的猜想為理論基礎的，也就是說假使這些猜想是正確的很多理論也會隨之正確并有可能上升為定理，一旦猜想是錯誤的很多理論也會隨之覆滅。目前解決大多數猜想的瓶頸就是素數通項公式，有這樣一個說法“如果找到一個素數通項公式，一些困難問題就可以由解析數論轉回到初等數論范圍”，可見，素數在當今還有很大的研究空間，盡管我們無法確定素數通項公式是否存在。而我想就當前日益發展的科技領域談談數論中素數的關鍵地位。

在這個科技化時代，計算機的地位不斷上升，人們對計算機的訴求也不斷增大，可能作為一個普通的程序員對于計算機內部的數據處理和優化沒有太大的需求。而想要使計算機變得更加強大性能更加優異，除了在硬件方面的進步，在優化算法方面，數論方面的知識有著廣泛的應用。例如在計算機算術、計算機設計、計算機理論、計算機復雜度等。而這之后，就會有大量的信息在網絡世界中流通，而這之中不乏一些機密信息，信息安全就顯得日益重要，密碼學也就應運而生。20世紀中后期就產生了一種RSA碼，這種神奇的密碼正是利用了素數成為至今仍有實用價值的密碼。

隨著人們慢慢注意到素數的特殊性，人們對這種特殊數字的研究也更加深入，素數在密碼學的作用也變得越來越大。

一、素數測試

如果用最普通的方法獲得素數，無非就是隨機獲得一個數，然后對其進行素性測試。素數的定義就是除了1和它本身以外沒有其它的因子。假定該數字為p。

用簡單的計算機語言描述就是：

for （int i=1;i<p;++i）

if（p%i==0） continue; ?//p≡0（mod i）即p能被i整除

則p不是素數。

但是這樣的方法復雜度高達O（n）。如果加以優化，只需要試除到：

for （int i=1;i<sqrt（p）;++i）

if（p%i==0） continue; ?//p≡0（mod i）即p能被i整除

這樣復雜度就降到了O（sqrt（n））。

但是如果采用了米勒拉賓素性檢測法，計算將更加簡單。

數學原理如下：

若p為素數，a為整數，且a、p互質。

則有ap-1≡1（mod p）

其等價形式為： ? ? ?ap≡a（mod p）

證明如下： ? ? ? ? ?令ap-1=k×p+1

則ap=（k×p+1）*a

也即 ap≡a（mod p）

引理：若p為素數（p>2），

如果 x2 ≡1 （mod p） 且x既不是1也不是p-1，則稱x為“1模p的非平凡平方根”

欲證明素數沒有滿足模p余1的非平凡平方根存在。

證明：假設x是一個模p余1的非平凡平方根，則有：

x2≡1（mod p）

（x+1）（x-1）≡0（mod p）

因為x是非平凡的，就有（x+1）與（x-1）和x互質，就是說（x+1）和（x-1）都不能被p整除，因此（x+1）（x-1）不能被p整除，矛盾。證畢

素數沒有滿足模p余1的非平凡平方根。

即如果一個數模p余1下有非平凡平方根，則n必為合數。

由該引理可知，若存在x2≡1（mod p），則p必為合數。

利用以上這些性質，產生了著名的米勒-拉賓素性檢測算法：

定義

x02≡1（mod n）

x12≡1（mod n）

…

xtt-12≡1（mod n）

xi是滿足1<xi<n-1的隨機數，在這一計算過程中，如果有任意一個xi≡1（mod n），根據引理，則n必為合數。

二、RSA碼

RSA碼的發明就是對素數實際運用的例子。由歐幾里得證明的算數基本定理可知任何一個自然數都可以分解為素數的乘積。但是將一個大整數分解只能用較小的素數依次嘗試，這種方法無疑是很耗時的。大可在一段固定的時間就更換一次，這樣的密碼策略堪稱無懈可擊。

接下來有N、a、X、p、q，其獲得過程如下：

1.任意選取素數p、q，N=p×q。

2.中間量r=（p-1）×（q-1）。

3.選取a和X兩個互質的數，使之滿足aX≡1（mod r）。

4.徹底銷毀p、q，公開N和a，將X作為解密關鍵。

小明想把數字A（A要小于N）傳送給小芳，他并不是直接把A發出去因為這樣有可能會被其他人截獲，于是我將A連續乘a次，再除以N，將余數發給小芳。小芳手里有一個小明都不知道的數字X，她將余數連乘X次，然后除以N，得到的余數就是A。

即小明需要執行的程序是：

temp=pow（A，a）; temp=temp%N; //temp是一個中間量

然后將temp發給小芳，小芳需要執行的程序是：

temp=pow（temp，X）; B=temp%N;

答案B就是當時小明實際想表達的A。

只要素數p、q足夠大，N也就很大，a和X的推導過程都是由p和q決定的，只要我銷毀p、q，破密的人則需要對N進行整數分解，那將是一個非常龐大的計算量。而且只要N足夠大，可以表達的A也就非常大。

這種加密方式其實是公開了打亂一個特定信息的方式，任何人都可以用我公開的方法加密信息，但是由于計算量太大，最終能夠整理混亂的信息解出最終答案的人只有我自己。可是有人會說利用現有的費馬小定理加上概率測試素數法，在一個較短的可以接受的時間內是可以算出幾十位數的分解結果的。即便是一百多位的數，利用現在的網絡技術無數臺電腦通過交流信息將這個龐大的計算任務細分化，也就是云計算的方式，也是可以解決的。但是試想現在已經計算出的素數位數早已上千位，兩個千位級別的素數相乘之后得到的數字恐怕計算機技術有再大的突破也是難以匹敵的。

綜上所述RSA碼成功的秘訣就是能夠獲得很大的素數，米勒算法就是一個獲得素數的不錯算法。將兩者結合起來就形成了著名的RSA密碼。

參考文獻：

[1]張爾光.正整數的方冪的方陣與費馬定理——費馬定理不成立的必要條件[J].數學學習與研究，2012.12.

[2]袁樹雄，韓鳳英.密碼學基礎研究[J].科技資訊，2008.5.

[3]張麗媛.RSA密碼算法的研究與實現[D].山東科技大學，2005.5.