預(yù)備知識(shí)：
歐拉函數(shù)
在數(shù)論廷雅，對(duì)正整數(shù)n耗美，歐拉函數(shù)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目（其中φ(1)=1）
通式為：
其中p1,p2...pn為x所有質(zhì)因數(shù)，x是不為0的整數(shù)航缀。
特殊：若n為質(zhì)數(shù)p的k次冪幽歼，
因?yàn)槌藀的倍數(shù)外，其他數(shù)都與n互質(zhì)谬盐。
歐拉函數(shù)是積性函數(shù)——若m,n互質(zhì)甸私，φ(mn)=φ(m)φ(n)
當(dāng)n為奇數(shù)時(shí)，φ(2n)=φ(n)
當(dāng)n為質(zhì)數(shù)時(shí)飞傀，φ(n)=n-1
P.S.積性函數(shù)：對(duì)于任意互質(zhì)的整數(shù)a和b有性質(zhì)f(ab)=f(a)f(b)的數(shù)論函數(shù)皇型。
完全積性函數(shù)：對(duì)于任意整數(shù)a和b有性質(zhì)f(ab)=f(a)f(b)的數(shù)論函數(shù)。
性質(zhì)：
一 與算數(shù)基本定理有關(guān)砸烦。若將n表示為質(zhì)因子分解式 n = p1a1p2a2 ...pnan 弃鸦，則有f(n)=f(p1a1)f(p2a2 )...f(pnan)
二 若r為積性函數(shù)且有f(pn)=fn(p)，則f為完全積性函數(shù)幢痘。
歐拉定理（數(shù)論）
在數(shù)論中唬格，歐拉定理，（也稱(chēng)費(fèi)馬-歐拉定理）是一個(gè)關(guān)于同余的性質(zhì)颜说。歐拉定理表明购岗，若n，a為正整數(shù)门粪，且n喊积，a互質(zhì)，則：
應(yīng)用：用來(lái)簡(jiǎn)化冪的模運(yùn)算玄妈。
例如乾吻，計(jì)算7222的個(gè)位數(shù)髓梅。
分析：本質(zhì)上就是求7222≡x(mod 10)，而容易知道φ(10)=4绎签。
7222=(74)55 72≡x(mod 10)
72≡x(mod 10)
9
所以答案就是9.
P.S. 費(fèi)馬小定理
a是不能被質(zhì)數(shù)p整除的正整數(shù)枯饿，則有a(p-1) ≡ 1(mod p)，他還有另外一個(gè)描述诡必，ap ≡ a(mod p)
證明鸭你，p是質(zhì)數(shù)，所以 φ(p) = p-1擒权，帶入歐拉即可袱巨。
應(yīng)用：
密碼學(xué)、信息論
對(duì)稱(chēng)加密碳抄，即對(duì)稱(chēng)算法：又是又叫傳統(tǒng)密碼算法愉老，就是加密密鑰能夠從解密密鑰中推算出來(lái)，反過(guò)來(lái)也成立剖效。在大多數(shù)對(duì)稱(chēng)算法中嫉入，加密解密密鑰是相同的。這些算法也叫密碼密鑰算法或單密鑰算法璧尸。
非對(duì)稱(chēng)算法：也叫公開(kāi)密鑰加密咒林，它是用兩個(gè)數(shù)學(xué)相關(guān)的密鑰對(duì)信息進(jìn)行編碼。其中一個(gè)密鑰為公開(kāi)密鑰（公鑰）爷光，另一個(gè)叫私有密鑰（私鑰）垫竞。
非對(duì)稱(chēng)算法運(yùn)用過(guò)程：
1）乙方生成兩把密鑰，公鑰是公開(kāi)的蛀序，任何人都可以獲得欢瞪，私鑰是保密的。
2）甲方獲取乙方的公鑰徐裸，然后它對(duì)信息加密遣鼓。
3）乙方得到加密信息后，用私鑰解密重贺。
RSA算法
1）選擇兩個(gè)很大的素?cái)?shù)P和Q 骑祟。
然后計(jì)算N=PQ和φ(N)=(P-1)(Q-1)
2）找到一個(gè)與φ(N)互質(zhì)的整數(shù)E（也叫“模范元素”）
3）找一個(gè)整數(shù)D，使得ED ≡ 1 (mod φ(N))
其中公鑰是（E,N）气笙，密鑰是（D,N）
設(shè)密文為X次企，則
加密：XE ≡ Y (mod N)
獲得Y
解密：YD ≡ X (mod N)
正確性討論：
第一，不能直接通過(guò)公鑰（E,N）推出X是不科學(xué)的健民，會(huì)有無(wú)數(shù)個(gè)X（比如23 ≡ 1 (mod 3)抒巢，你可能推出X=2,4...）
第二，必須嘗試推出D
1）ED ≡ 1 (mod φ(N))秉犹，只有知道E和φ(N)蛉谜，才能推D
2）φ(N)=(P-1)(Q-1),只有知道P和Q，才能推φ(N)
3）N=PQ崇堵，只有對(duì)N做因數(shù)分解型诚，才能推出P和Q
對(duì)大整數(shù)的因數(shù)分解是一件非常困難的事情。
RSA算法的證明
要證明私鑰解密出來(lái)的答案一定是正確的X鸳劳，即證明
