设p为一素数，对于任意整数a，有a^(p-1)≡ 1 (mod p)。

由费马小定理可得，若n为素数，则对任意整数b，且b和n互素，都有b^n-1(mod n) ≡1。因此，若存在整数b，使得b^n-1(mod n)≡1不成立，则n是一个合数。

3.欧拉函数

对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）

4.剩余类（同余类）

设模为n，则根据余数可将所有的整数分为n类，把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类，记作[a]。并把a叫作剩余类[a]的一个代表元。

5、既约剩余系

6.Carmichael’s function

详见https://brilliant.org/wiki/carmichaels-lambda-function/?subtopic=modular-arithmetic&chapter=eulers-theorem

7、二项式定理

二、paillier同态加密算法

1.密钥产生

2、加密过程

3、解密过程

4、正确性证明

其中