今天还是数论的内容。密码学的基础是数论，数论又绕不开素数。
素数
算数基本定理：任意整数n=p1^a1+p2^a2+…+pn^an. 其中pi为小于等于n的素数。
定义P为素数集，如果aℓb，那么对于任意p∈P，都有ap≤bp.
素数基本定理还可以写成n=∏pi^ai. 将整数表示成素数积，很容易可以确定两个整数的最大公因数：如果k=gcd(a,b),则kp=min{ap,bp}.
费马小定理(Fermat's Little Theorem）
若p是素数，a是正整数且不能被p整除，则a^（p-1）≡1（mod p）.证明过程如下：
也可以表示成a^p≡a（mod p）.这里a可以被p整除。
欧拉函数（Euler's totient function）
定义φ（n）为小于n且与n互素的正整数的个数，规定φ（1）=1.
易知n为素数时φ（n）=n-1
若p，q都为素数，n=p*q，则φ（n）=（p-1）（q-1）.证明过程如下：
欧拉函数通用表达式为φ(n) = n ∏(1 - 1/p)= n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ).
欧拉定理（Euler's totient theorem）
对于a^φ（n）≡1（mod p）.对于任意正整数n都成立。可理解为费马小定理的推广。
