歐拉函數(shù)的性質(zhì)：
若$n=qp，p和q是兩個質(zhì)數(shù),則\phi (n)=(q?1)(p?1)$

歐拉定理：若a與n互質(zhì)，即$gcd(a,n)=1,則a^{\phi (n)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$
進一步，若n是質(zhì)數(shù)，$a^{n?1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$，$a^n\equiv a\mathrm{m}\mathrm{o}\mathrm{d}n$

費馬小定理：若n是質(zhì)數(shù)，a與n互質(zhì)，，則$a^{n?1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$，

逆元：如果$ab\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n,則a和b互為逆元$

RSA加密的條件：
· $n=p\times q$
· $L=\phi (n)=(p?1)(q?1)$
· 隨機選取 $1<e<L，使得gcd(e,L)=1$
·計算 $ed\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}L$
·公鑰對 =（n, d），私鑰對 =（n, e）

繼續(xù)設明文 = M，密文 = C，現(xiàn)在來證明可以用上述方法加解密的條件。
$$M^{E}modN=C,C^D\mathrm{m}\mathrm{o}\mathrm{d}N=M$$
根據(jù)模法，$C^D?kN=M$，代回第一個式子，
$$(C^D?kN{)}^E\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}N$$ $$C^{DE}\equiv C\mathrm{m}\mathrm{o}\mathrm{d}N$$由于 $E\times D\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\phi (N)$，也即 $ED?k\phi (N)=1$
若gcd(C, N) = 1，根據(jù)歐拉定理，$$C^{\phi (N)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}N$$$$C^{k\phi (N)+1}\equiv C\mathrm{m}\mathrm{o}\mathrm{d}N$$$$C^{ED}\equiv C\mathrm{m}\mathrm{o}\mathrm{d}N$$若C與N不互質(zhì)，由于N是兩個質(zhì)數(shù)的積，所以gcd(C,N)=q or gcd(C,N)=p。設 $C=k_{1}qorC=k_{2}p$，假設C = kp，而且gcd(m,q)=1，由歐拉定理和歐拉函數(shù)的性質(zhì)，$$(kp{)}^{q?1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}q$$$$((kp{)}^{q?1}{)}^{k_2(p?1)}\equiv (kp{)}^{q?1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}q$$$$(kp{)}^{k_2\phi (n)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}q$$$$C^{k_2\phi (n)}?aq=1$$兩邊同時乘上C,$$C^{k_2\phi (n)+1}=aCq+C=akpq+C=akN+C=k_{3}N+C$$也即 $C^{ED}\equiv C\mathrm{m}\mathrm{o}\mathrm{d}N$，原式得證。

素數(shù)檢驗（Miller-Rabbin算法）
涉及到兩個定理：
5.1 費馬小定理：參見3，但是費馬小定理的逆定理不一定成立
5.2 二次探測定理：如果 p是一個素數(shù)，$0<x<p$，則方程 $x^2\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p$ 的解為 $x=1$ 或 $x=p?1$
算法內(nèi)容：
· 設一個數(shù)為x，分解為$2^{s}t=x?1$，t為x不斷除以2得到的最大奇數(shù)
· 隨機取a，$a=a^t$，對a進行s次平方（也即計算$b=a^2\mathrm{m}\mathrm{o}\mathrm{d}x,a=b$），如果其中有次平方的結果為b=1而且此時a不為1或x-1，則不滿足二次探測定理
· 如果 $a^{x?1}\mathrm{m}\mathrm{o}\mathrm{d}x=1$，則不滿足費馬小定理
如果可以，a取小于x的足夠多的質(zhì)數(shù)或者隨機選取a進行多次檢測。Miller-Rabbin算法只能保證x大概率是一個素數(shù)，不過這個概率已經(jīng)足夠大了。

快速冪
計算$a^x\mathrm{m}\mathrm{o}\mathrm{d}n=?$，當a和x很大的時候，中間結果超出存儲容量又或者數(shù)字太大計算復雜，此時需要快速計算這個指數(shù)模余值，可以如下進行：
對x分解為二進制形式，則有$$a^{x}modn=a^{2^{b_k}+2^{b_{k?1}}+??????+2^{b_0}}modn=((a^{2^{b_k}}modn)??????(a^{2^{b_0}}modn))modn$$