記得在我上初一的時候做過這麼一道數學競賽題，就是求7的222次方的個位數字。當時教材上介紹的解題方法是将222分解成4*55+2，然後算出7的2次方個個位數字即為要算的數值。當時年幼無知的我根本不了解整個過程為什麼要這麼計算，隻知道根據規律也可以得出響應的結果，然後後來才知道這個裡面蘊含着一個非常重要的定理。
歐拉定理：若n,a為正整數，且n,a互質，如果算出不大于n且與n互質的正整數個數φ(n)，那麼a的φ(n)次方除于n的餘數為1.
用公式表明即為：
以3和5兩個數為例，假設a=3，n=5，那麼不大于5且與5互質的數有1，2，3，4四個數字，那麼φ(n)=4，根據公式就可以得出來3的4次方81除于5餘數是1.
再回到上題7的222次方的個位數字，其實這道題也就算要計算7的222次方除以10的餘數。因為7和10是互質數且φ(10)=4,那麼根據歐拉定理便有7的4次方（2401）除以10餘數是1。當然無論多少個個位數為1的數相乘其個位數字仍然是1，是以整個題目就轉變成算7的二次方了結果是9.
以上所講的隻是筆者曾經做過的一個無關痛癢的數學競賽題，但是如今這個思想卻成了目前地球上最重要的加密算法的基礎。目前常用的加密算法主要分為對稱加密和非對稱加密兩種。對稱加密就是加密和解密密鑰完全一樣，這樣以來加密解密過程簡單而效率高，不過由于傳輸當中需要把密鑰一并傳輸而是的安全性能下降；而非對稱加密則是加密密鑰和解密密鑰彼此獨立，這樣使得安全性大大增加，而典型的非對稱加密算法便是RSA算法。
RSA算法的基本步驟可以分為以下幾步：(以假設A和B通信為例子)
1，A首先選擇兩個質數，假設這裡選擇，61和53，實際選擇的質數都相當大
2，将兩個數相乘得到3233，然後計算出不大于3233且和3233互質的數，根據歐拉函數的定義可以算出是φ(3233)=（61-1）*（53-1）=3120
3，尋找一個不大于3120的質數e，這裡選擇e=17，然後計算摸反元素，也就是計算一個整數d，是的e和d相乘的數除以3120餘數為1。由于e=17，是以這一步可以寫出以下等式：17*d = 3120k+1.由于K的值我們不關心，是以也可以寫成17d+3120k=1.于是通過解這個二進制一次不定方程就可以算出d來。通過輾轉相除法計算出一組解為(2753,-15).此時加密公鑰為(3233,17),私鑰為(3233,2753).
4,真正個通信此時開始，假設A要把資訊65發給B，實際上首先計算下式中的C：6517 ≡ C(mod 3233)，這裡計算出的C=2790。然後A将2790發給B
5，當B收到2790後解密，解密實際上就是計算下面的C：27902753 ≡ C (mod 3233)，當然算出來就是65.此時加密解密的過程就結束了。
通過以上算法可以看出來，如果想破解RSA必須要根據公鑰計算出私鑰，要想通過3233和17計算出2753必須要首先得到φ(3233)，當然直接去暴力計算φ(3233)必須首先找出來61和53這兩個數字。不過可惜的是大數分解目前而言沒有相對良好的算法，将一個四位數分解很容易，但是對于一個四十位數恐怕就不是那麼容易了，真正強行計算首先還要實作大數相乘算法，兩個很大的數相乘所耗費的時間遠遠不是一條imul指令可以完成的。
當然超級計算機和量子計算機的問世将會對RSA算法的可靠性産生極大威脅，但是随着計算機計算速度的不斷提高RSA算法的密鑰長度也會不斷增長，其破解難度恐怕也會不斷增加，但誰能笑到最後還是得等時間的答複。今天就隻簡單寫了下RSA算法的基本原理和步驟，回頭再寫數學基礎以及證明。