数论-质数

作者: dachengquan | 来源:发表于2020-07-28 18:57 被阅读0次

定义：若一个正整数无法被1和他自身除外的任意自然数整除，则称该数为质数，否则为合数。

质数的数量：在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约 $N\div \ln N$ ，每 $\ln N$ 个数中大约有一个质数。

1判断质数的方法

1.1试除法

定理：若一个正整数N为合数则存在一个能整除N的数T，其中 $2 \leq T \leq \sqrt{N}$ 。

证明：

因为N是合数，所以一定存在一个T能整除N，并且 $2\leq T \leq N-1$ 。

反证法：假设命题不成立，T能整除N，T一定满足 $\sqrt{N} +1 \leq T \leq N-1$ 。因为T能整除N，所以 $N/T$ 的商也能整除N。N/T满足 $2 \leq N/T \leq \sqrt{N}$ ，令让T=N/T，与假设矛盾。假设不成立，原命题成立。

算法：扫描 $2$ ~ $\sqrt N$ 之间的所有整数，如果能整除N，说明N是合数。如果都不能整除N，那么N是质数

1.2Miller-Robbin

需要先掌握，费马小定理，为了证明费马小定理的欧拉定理，

1.2.1费马小定理

费马小定理：若p为素数，a是任意整数并且 $gcd(a,p) =1$ 则有 $a^{p-1} \equiv 1 \pmod{p}$ 。

分析：考虑 $gcd(a,p)$ 不等于1的情况

1） $a=p^k$ 其中 $k\geq1$ , $gcd(a,p)=p$

2） $a=0$ ， $gcd(a,p)=p$

总结两种情况就是a取余p不为0。

思考：为什么这个公式会成立，看一种特殊情况。

$3^6\equiv 1 \pmod{7}$

可以看出当x按顺序从1到6排列时， $3x\pmod{7}$ 出现的数是1~6，但是顺序打乱了。可以得到公式

$\prod_{i=1}^6x \equiv \prod_{i=1}^6 3x \pmod{7}$

$\prod_{i=1}^6x \equiv 3^6\prod_{i=1}^6 x \pmod{7}$

$1 \equiv 3^6 \pmod{7}$

定理：若p为素数，a是任意整数并且 $gcd(a,p)=1$ 。那么数列1,2,3,4....p-1与序列a,2a,3a,4a....(p-1)a (mod p)数相同，但是次序不同。

反证法：假设任意两个数j和k并且 $p-1\geq j>k\geq 1$ ，使得 $ja\equiv ka \pmod{p}$ 成立。因为ja与ka同余所以必定有 $p|(j-k)a$ ,但是序列a,2a,3a,4a....(p-1)a都不能被p整除。这个公式永远无法成立 $ja\equiv ka \pmod{p}$ ，假设不成立。

费马小定理通过 $3^6$ 的特殊情况，将3变为a，6变为p-1，7变p。就可以证明成功。

证明：费马小定理是欧拉定理的一种特殊情况。通常是证明欧拉定理，欧拉定理正确就说明费马小定理正确。下面我们看看欧拉定理

1.2.2欧拉定理

欧拉定理：若正整数a,m满足 $gcd(a,m)=1$ ,则 $a^{\phi (m)}\equiv 1\pmod{m}$

其中 $\phi(m)$ 是欧拉函数，1到m中与m互质的数的个数。

定理：若 $gcd(a,m)=1$ 并且 $gcd(b_i,m)=1$ 其中 $1\leq b_i<m$ 那么整数数列 $b_1,b_2,b_3...b_{\phi (m)}$ 与序列 $ab_1,ab_2,ab_3...ab_{\phi (m)} \pmod{m}$ 数相同，但是次序不同。其中b是按从小到大的顺序排序。

证明这个很简单，使用反证法假设任意两个数j和k属于数列b、并且j>k，使得 $ja\equiv ka \pmod{p}$ 成立，那么必定有 $p|(j-k)a$ ，但是这个p是不可能整除(j-k)a的，所以对于 $ab_i\pmod{m}$ 来说任意两个数都不相同。

因为 $gcd(b_i,m)=1$ 这样的b一共有 $\phi(m)$ 个,并且 $gcd(a,m)=1$ 。对于任意的 $gcd(ab_i,m)$ 都等于1,并且互不相同。所以对于任意的 $ab_i$ 一定能找到一个相等的 $b_j$ 。

其中当m是质数时， $\phi(m)=m-1$ 费马小定理显然成立。

1.2.3Fermat 素性测试

Miller-Robbin算法希望用费马小定理 $a^{p-1} \equiv 1 \pmod{p}$ 判断x是否为质数。

使用公式 $a^{x-1} \equiv 1 \pmod{x}$ 如果这个公式成立，那么x为质数。但是这个想法是错误的，因为x是质数这个公式一定成立，但是x不是质数这个公式不一定会失败。例如： $2^{340}\equiv 1\pmod{341}$

如果随机选取a，多判断几次呢只要判断判断的次数够多，那么是否可以避免这种情况呢。不过 $\forall a<561,a^{560}\equiv 1\pmod{561}$ 对于任意的a都不满足。

只使用费马小定理是有很小的概率将合数错误判断为质数的。

1.2.4二次探测定理

如果p是素数， $p>x,p>1$ 那么 $x^2\equiv1\pmod p$ 的唯一解就是x=1或x=p-1。

证明： $x^2\equiv1\pmod p$

$p\vert x^2-1$

$p|(x-1)(x+1)$ 因为p是大于x的质数， $p=x+1\pmod p$ 或者 $p=x-1\pmod p$ 。

1.2.5具体实现

对于随机的a，使用二次探测和费马小定理同时测试。只要测试的次数够多一定能得到答案。但是这样太慢了。

Miller-Robbin算法流程判断n是否是素数。

1将x-1分解成 $n-1=u*2^t$ 的形式，其中u的最后一位必须是1。例如 $110_2$ 变为 $11_2$ , $1010_2$ 变为 $101_2$ 。

2生成一个随机数a,求出x = $a^u\pmod n$

3令y = $x^2 \pmod n$ ，如果y是1，并且 $x\neq 1$ 并且 $x\neq n-1$ 说明n不是质数。否则让x=y执行下一步

4重复步骤3，t次如果每次都没证明n不是质数，并且最后y为1。那么说明p是质数。

5重复执行2，直到验证k次都成功。

二次探测和费马小定理同时测试成功率非常高，但是还是有可能误判，需要多次判断，最好判断8次。比较好的a有2,3,5,7,11,13,17,61。

时间复杂度大概是logn级别的吧。

2质数的筛选

给出从1到n之间的所有质数

2.1埃筛

埃筛的思想是，任何整数的倍数都不是质数。从1到n扫描，对于每个数标记他的倍数为合数。

1扫描到x，如果x是合数，那么x的倍数一定被比x小的数筛过一遍。每次从小到大只对质数的倍数进行筛选就可以了。

2如果x是质数 $x*k$ 如果 $k<=x$ 那么xk一定被k或者k的质因数筛过了。

避免掉这两种情况埃筛的时间复杂度就已经接近线性了。

2.2线筛

线筛的思想就是每个数只被最小质因子筛一次。埃筛2会筛一遍12,3会筛一遍12。

线筛首先生成一个数列p，p是从1到N的所有素数并且从小到大排序， $p_1 = 2,p_2=3,p_3 = 5,p_4=7.....$ 。从1到n扫描x，对于任意一个数x，对于i从1到p.length()扫描标记 $xp_i$ 是合数，如果 $p_i是x最小的质因子$ 。那么停止扫描因为如果让i接着+1，那么对于 $xp_{i+1}$ 来说，x的最小质因子是 $p_{i}$ 但是他被 $p_{i+1}$ 标记为合数。如果 $p_i$ 不是x最小的合数那么对于 $xp_i$ 的最小质数一定是 $p_i$ 。每个合数只会被他最小的质因数标记一次。所以时间复杂度是O（N)

3质因数分解

3.1算数基本定理

任何一个大于1的正整数都能被唯一分解为有限个质数的乘积，可写作：

$N=p_1^{c_1}p_2^{c_2}...p_n^{c_n}$ 其中 $c_i$ 是正整数， $p_i$ 是质数，且满足 $p1<p2<...<pm$

3.2试除法

试除法扫描 $2$ ~ $\sqrt{x}$ 直接的每个数d，如果d能整除N，则从N中除掉d的所有因子，同时累计d的个数。最后剩余的N如果是1，那么说明我们已经扫描完了d的所有质因子。否则N就是剩下的那个质因子。

3.3Pollard's Rho

3.3.1生日悖论

反面思考，对于一个人来说与其他人生日都不同的概率。对于第一个人是365/365选择任何一天都可以。对于第二个人来说是364/365不能和第一个人选择同一天。所以一个班n个人生日都不同的概率是 $\prod_{i=1}^{n}(1-\frac{i-1}{365} )$

当n为23时，一个班中有生日相同的概率就到50%以上了，当n为50时一个班有相同生日的概率达到了97%

3.3.1Pollard算法流程

1使用Miller-Robbin判断n是否是质数，如果n是质数，那么直接返回n

2找到一个p，p能整除n，分别使用pollard计算p与n/p

Pollard's Rho算法本身看着不优秀，关键是寻找这个p的难度大。首先进行一个优化寻找p, $p = gcd(x,n)$ 这样不止判断了x，还判断了x的质因子。这种做法正是根据生日悖论，加入比较的数越多，比较成功的概率会以指数上升。x的选择通常采用两个数p1,p2相减的绝对值得到， $p1 = p1^{2}+c$ 。其中c是一个常数。这样x的值每次重复的概率比较小，但是我也不知道为什么。另外p1和p2计算的过程中可能遇到环，因此要让两个走的步伐不一致，如果p1==p2说明出现环。

这就是算法的一个完整过程，看着并不快，但是期望时间复杂度是 $O( n^{\frac{1}{4}})$ 。