数的素性测试

概念：整数p(p>1)是素数,当且仅当其公因数只有1与其本身。
github源码

相关定理

1.任意整数a>1都可以唯一的因式分解为：
$a = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times … \times p_{n}^{a_{n}}$
其中$p_{1},p_{2},…,p_{n}$都是素数($p_{1} \lt p_{2} \lt … \lt p_{n}$)，
所有的$a_{i}$都是正整数。
例如$12 = 2^{2} \times 3^{1}$

另一种表示方法：
设P是所有素数的集合，则任意正整数a可唯一的表示为
$a = \prod p^{a_{p}}, {p \in P} ,a_{p} \ge 0$
对于任意的a，其大多数指数$a_{p}$为0，那么可根据上面的公式，以所有非零指数来唯一的表示一个正整数。
例如，整数12可用{$a_{2}=2,a_{3}=1$}来表示。

我们知道，$a^{b} \times a^{c} = a^{b+c}$,
设$k=ab$，
$a= \prod p^{a_{p}},b= \prod p^{b_{p}},k= \prod p^{k_{p}}$
则对于所有的$p \in P$,有$k_{p} = a_{p} + b_{p}$成立。

从素因子的角度看，a整除b意味着，对于任意的$p \in P$，有$a_{p} \le b_{p}$。

若将整数以上述公式表示，则很容易确定两个正整数的最大公约数。
例如：
$300 = 2^{2} \times 3^{1} \times 5^{2}$
$18 = 2^{1} \times 3^{2}$
则$gcd(18,300) = 2^{1} \times 3^{1} = 6$

即如果$d=gcd(a, b)$,则有$d_{p}=min(a_{p},b_{p})$

2.费马定理
第一种表述：
若p是素数，a是正整数且不能被p整除，则：
$$a^{p-1} \ mod \ p = 1 \ mod \ p$$
例：
a=7,p=19
$a^{p-1}=7^{18}$
$7^{18} \ mod \ 19 = 1 \ mod \ 19$

第二种表述：
若p是素数，a是任意正整数，则：
$$a^{p} \ mod \ p = a \ mod \ p$$
例：
a=3,p=5
$a^{p}=3^{5}$
$3^{5} \ mod \ 5 = 3 \ mod \ 5$

3.欧拉定理

3.a 欧拉函数$\phi (n)$
$\phi (n)$为小于n且与n互素的正整数的个数。
$\phi (1) = 1$

欧拉函数$\phi (n)$前30项的值：

n $\phi (n)$ n $\phi (n)$ n $\phi (n)$
1 1 11 10 21 12
2 1 12 4 22 10
3 2 13 12 23 22
4 2 14 6 24 8
5 4 15 8 25 20
6 2 16 8 26 12
7 6 17 16 27 18
8 4 18 6 28 12
9 6 19 18 29 28
10 4 20 8 30 8

显然，对于素数p有
$\phi (p) = p-1$

3.b 欧拉定理
第一种表述：
对任意互素的正整数a和n，有：
$$ a^{\phi (n)} \ mod \ n = 1 \ mod \ n $$
例：
a=3,n=10
$\phi (10) = 4$
$a^{\phi (n)}=3^{\phi (10)}=3^{4}$
$3^{4} \ mod \ 10 = 1 \ mod \ 10$

第二种表述：
对任意的正整数a，n，有：
$$ a^{\phi (n)+1} \ mod \ n = a \ mod \ n $$
例：
a=3,n=6
$\phi (n)+1 = \phi (6) + 1 = 3$
$a^{\phi (n)+1} = 3^{3}$
$3^{3} \ mod \ 6 = 3 \ mod \ 6$

素性测试

许多密码算法需要随机选择一个或多个非常大的素数，因此需要确定一个给定的大数是否为素数。

Miller-Rabin算法
Miller和Rabin提出的这一算法是典型的大数素性测试算法