数论第一节：质数与质因数-526互联

参考博客：

素数的分布：

10的1次方        4
10的2次方        25
10的3次方        168
10的4次方        1229
10的5次方        9592
10的6次方        78498
10的7次方        664579
10的8次方        5761455
10的9次方        50847534

大致为 $n/log$ 的数量级，但似乎有2倍常数，欧拉筛可以在1s时间内筛出1e7的质数，存放质数的数组开1e6即可。

因子规模：

最大的因子数量
10的6次方        240个
10的9次方        1344个
int             1600个
10的15次方       26880个
long long       200000个左右。

因子规模与质因数关系不大，但是出于方便在此记录一下。

由此可见int范围内的因子个数在1e3级别，可以进行n^2复杂度的处理，而long long范围就到了1e5级别了。

素数的性质：

存在任意长的区间，所有数都是合数

eg: $n!+1,n!+2,n!+3...n!+n$ , n可取无限大

所有奇素数都可以唯一地表示成两个平方数之差

设 $p=a^2-b^2$，则 $(a+b)(a-b)=p, \Rightarrow a+b=p,a-b=1$ 。若 $p$ 为合数，$p$ 能拆成多少对奇偶相同的因子就能有多少种平方差表示。若p是偶数但不能被4整除，则 $p$ 不能被表示成两个平方数之差。

$2^n$-1和$2^n$+1至少有一个是合数

$2^n-1, 2^n,2^n+1$ 三个数连在一起，$2^n$ 不能被 $3$ 整除，因此剩下两个数必有一个是 $3$ 的倍数。

费马小定理：

$a^{p-1}\equiv 1\ (mod\ p)$

首先证明：$p$ 为质数，$a<p$ 时，$ka\ (k\in Z[1,p-1])$ 可以取遍 $1$ 至 $p-1$ 的排列且互不相等，$a^k$ 不是这样，不要混淆，满足这个性质的 $a^k$ 的 $a$ 是原根。（原根很小可以暴力求解）

证明：若存在 $na=ma$ ，由于 $a<p$ ，因此 $n-m\equiv 0\ (mod\ p)$ ，$0<n,m<p$ ，因此矛盾。

将所有 $ka$ 相乘：$a*2a*3a*...*(p-1)a\equiv (p-1)!\ \ \Rightarrow\ \ (p-1)!*a^{p-1}\equiv (p-1)!\ \ \Rightarrow \ \ a^{p-1}\equiv 1$ 。

费小得证。

费马小定理和欧拉定理等比较基础的数论定理有相当多的证法，会一个比较简单的即可。

推广：欧拉定理

$p$ 可以不是质数了，$a$ 与 $p$ 互质时：$a^{\varphi(p)}\equiv 1\ (mod\ p)$，

证明与费小大致相同，只需要取 $k$ 为所有 $p$ 以内与 $p$ 互质的数 $k_1,k_2,...,k_{\varphi(p)}$，其值可以取所有 $p$ 以内与 $p$ 互质的数。

证明：$a$ 与 $k_i$ 均与 $p$ 互质，因此 $k_ia$ 与 $p$ 互质，若存在 $i,j$ 使 $k_ia=k_ja$ 则 $k_i-k_j\equiv 0\ (mod\ p)$，显然不存在，因此 $k_ia$ 与 $k_i$ 集合相同。

$k_1a*k_2a*...*k_{\varphi(p)}a\equiv k_1*k_2*...*k_{\varphi(p)}\ \ \Rightarrow \ \ a^{\varphi(p)}\equiv 1$

重要推论，用于消减指数：$a^b\equiv a^{b\mod\varphi(p)}\ (\mod p)$

再推广：扩展欧拉定理

$\begin{align} a^b= \left \{ \begin{array}{ll} a^{b\mod \varphi(p)} &gcd(a,p)=1 \\a^b &gcd(a,p)\neq1 ,b\leq \varphi(p) \\a^b\equiv a^{b\mod\varphi(p) + \varphi(p)}\ (\mod p), &gcd(a,p)\neq1,b\ge \varphi(p)\end{array}\right.\end{align}$

扩展的部分主要是第三个case：

证明：将 $a$ 质因数分解：$a=q_1^{r_1}*q_2^{r_2}*...$，我们证明任意的i：$q_i^b=q_i^{b\mod\varphi(p)+\varphi(p)}$

以下将 $q_i$ 简写成 $q$ ，$q$ 与 $p$ 互质时为case1，$q$ 与 $p$ 不互质时：

设 $p=s*q^r$ ，显然 $\varphi(p)\geq q^{r-1}\geq r$（注意这里的 $r$ 不一定是 $a$ 分解的那个 $r_i$），$gcd(s,q^r)=1$ ，$\varphi(p)=\varphi(s)*\varphi(q^r)$ ，$q^{\varphi(p)}=(q^{\varphi(s)})^{\varphi(q^r)}=1^{\varphi(q^r)}=1$，$q^{r+\varphi(p)}=q^{r}$。

$b\geq \varphi(p)$ 时 $b\geq r$，$q^{b}=q^{b-r+r}=q^{b-r}*q^{r+\varphi(p)}=q^{b+\varphi(p)}$，

$b\geq 2*\varphi(p)$ 时，$q^b=q^{b-\varphi(b)}$，

因此若 $c=b\ (\mod\varphi(p))$ 且 $c\geq \varphi(p)$，$q^b=q^c$，

简单计算得 $c=b\mod \varphi(p)+\varphi(p)$，即 $q^b=q^{b\mod\varphi(p)+\varphi(p)}$，质因数相乘可得 $a^b=a^{b\mod\varphi(p)+\varphi(p)}$。

数学DNA——素数的普遍公式：

人们都知道素数是无限多的，有一个简单的反证，假设世界上只有 $n$ 个素数，从小到大排序后得 $d = p_1*p_2*p_3*....*p_n+1$ ，由于 $d$ 不可被这 $n$ 个素数整除，要么被一个小于 $d$ 大于 $p_n$ 的数整除，要么 $d$ 本身是一个质数，假设矛盾。

那么既然分前者和后者两种情况，$d$ 就不是生成新的大质数的方式。事实上，在 $n=6$ 时，$2*3*5*7*11*13+1=30031=59*509$就已经不是一个质数了。

由于此生成方式产生的数无任何特殊性质，且越大的数质数分布越稀疏，因而当 $n$ 趋近无穷时，$d$ 为质数的概率趋近与 $0$，事实上，人类目前只发现了22个满足 $d$ 为质数的 $n$，详情见oeis.org中A005234。

几千年来人们一直在寻找素数的普遍生成公式，但是目前还莫得人找到。

费马数

人们错误认识到的第一个素数生成公式是费马数，形如 $2^{2^n}+1$ 的数称为费马数，费马写到 $n=4$ 的情况发现成立，因此猜想对于所有的 $n$ ，费马数都是质数。

然而费马死后的第64年，哥德巴赫给欧拉写一封信想让他证明，三年后欧拉却发现 $n=5$ 的费马数不是质数，$4294967297=641×6700417$。这使得费马数无法为质数生成公式。甚至有人提出相反的命题：$n$ 大于 $4$ 时的费马数都是合数。

梅森数

17世纪另一位数学家梅森做过一个猜想：当p是质数时，$2^p-1$也是质数。

欧拉证明了int的上限，$2^{31}-1=2147483647$ 是个质数。

但是 $2^{11}-1=2047=23×89 $，可见梅森数中合数其实有很多。

已知的最大质数

由于人类并没有找到质数的普遍生成算法，因此人类还未找到一个趋近于无穷的质数。

人类已知的最大质数是 $2^{82589933}-1$ ，是第51个梅森素数。

素数的判定：

既然无法找到质数的生成公式，但是人们对于大质数的需求依然不少，如何找出一个大质数是一个重要的问题，由于质数出现的概率大致 $log$ 的倒数，那么期望扫描 $log$ 个数即可得到一个质数，判定一个大数是否为质数成为寻找质数的主要问题。

费马小定理逆命题

若 $a^{n-1}\equiv 1\ (\mod n)$，则n为质数（a与n互质）。

很长一段时间以来人们认为逆命题成立，直到1819年发现的第一个反例：$2^{340}\mod341=1$，但是 $341$ 不是质数。类似的有 $561, 645, 1105$ 等，虽然满足这个条件的合数并不多，但是不可忽略，这些数n满足 $n|2^{n-1}-1$，人们把这些数称为伪素数(pseudoprime)。

那么有一个比根号算法快的多的想法，既然伪素数不多，我们把所有伪素数记录下来，剩下的满足 $n|2^{n-1}-1$ 的n就是质数了。

伪素数和素数的比例是多大，1e9以内有50847534个素数，只有5597个伪素数，我们只有0.01%的概率会出错，但是不可忽略。

目前判定方式只是用2作为底数，我们再使用3或5之类的数当做 $a$ 再进行测试，伪素数会少很多。设满足 $a^{n-1}\equiv 1\ (\mod n)$ 的合数 $n$ 为以 $a$ 为底的伪素数(pseudoprime to base a)，1e9中同时以2和3为底的伪素数变成了1272个，出错概率降到了0.0025%。

我们可以随机挑选几个 $a$（和 $n$ 互质的）作为底数来判断一个数的合素，这个方法被称为费马素性检验。

Carmichael数

如果我们用费马素性检验考虑了所有小于 $n$ 且和 $n$ 互质的数，仍然会出现一些数满足所有的底数 $a$ ，比如 $561$，我们称这样的数为Carmichael数（卡迈克尔数），1e9以内有600个Carmichael数，甚至只是伪素数的一半，Carmichael数的存在使得费马素性检验变得很不正确。

Miller_Rabin素性检验

Miller和Rabin是两个人，算法是两人共同创造的，类似于费马素性检验的推广升级版。

算法基于这样一个简单性质：如果 $p$ 是质数，$x$ 是小于 $p$ 的正整数，有 $x^2\mod p= 1$ ，则 $x$ 为 $1$ 或 $p-1$，因为 $(x-1)(x+1)$ 是 $p$ 的倍数，而 $x$ 又小于 $p$。

这个性质正好可以和费马小定理一起套用，例如我们已经知道 $2^{340}\mod341=1$ ，如果341真的是质数，应该也满足 $2^{170}\mod341=1$ ，算出来确实是，然后因为余数是1，我们可以继续套用这个性质，检验 $2^{85}\mod341=32$，发现余数既不是 $1$ 也不是 $340$，那 $341$ 就是个伪素数实锤了。

总结一下这个算法就是，想检验 $n$ 是否为质数，随机找几个底数（不一定是2），指数 $n-1$ 一定有质因子 $2$，每次检测当前指数下余数的结果是否为 $1$ 或 $n-1$，如果是 $1$ 且仍然有质因子 $2$，再检验除 $2$ 的余数。如果答案是 $n-1$ 或指数不能再除以 $2$ 则停止，视为检验成功，如果余数出现了不是 $1$ 和 $n-1$ 的其他数，检验失败。

Miller_Rabin是费马素性检验的升级版，但同样是不确定算法，我们将这个算法检验不出来的合数称为强伪素数(strong pseudoprime)。虽然有一半的指数都只能多检查一次（质因子2只有一个），但是这个检验方式的正确率却是指数级的上升。仅以2为底，第一个强伪素数到达了2047，同时以2和3为底的强伪素数到达了1373653。

虽然是不确定算法，但是在算法竞赛中对一个 $int$ 以内或 $long long$ 以内的数进行素性检验已经是非常给力的算法，通常认为选取 $k$ 个底数进行检测，失误率大概是 $4^{-k}$ ，而不是像费马素性检验那样无论取任何值都会被Carmichael数给卡掉。Riesel在1994年给出了一张表，计算了取前 $k$ 个质数作为底的最小强伪素数，可以看出取到23就可以使$long\ long$ 范围内无强伪素数。

下面的数据来自于Matrix67的原博客：

比如，如果被测数小于4 759 123 141，那么只需要测试三个底数2, 7和61就足够了。当然，你测试的越多，正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试，所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数，那么10^16内唯一的强伪素数为46856248255981。

复杂度有所保证，但正确率需要通过随机化的次数来确定。类似的随机化素性检验算法也有许多，Miller_Rabin是比较出名的一个了(1976年提出的)。

AKS素数测试

具体原理还没学qwq，留个坑下辈子补。

2002年印度计算机科学家发表论文《PRIMES is in P》，他们找到了一个多项式时间下的确定性素数检验算法，称为AKS素数测试。

不太清楚密码学常用库目前使用的生成质数的检验算法是哪一个，即使现在是随机性的算法但早晚也会改为AKS类的确定性算法吧。

大整数分解

给我们一个大整数，我们可以用各种算法在多项式复杂度内算出是否是质数，但如果是合数，我们该如何分解。

Pollard Rho

Pollard-Rho算法是John Pollard发明的一种能在期望1/4次方时间内找到大整数的一个除自身与一以外的因子的算法。

想要使用Pollard Rho进行质因数分解时经常搭配Miller_Rabin算法，每次使用Pollard Rho找到大数的一个因子，Miller_Rabin判断是否为质数，如果是加入质因数，不是的话就将大数打散成两个小数继续递归使用Pollard Rho。递归完成后即可得到所有的质因数。虽然是递归，但是由于递归次数和质因子的大小成反比，每次Pollard Rho随机次数和质因子的大小成正比，两者相乘还是1/4次方的复杂度。

Pollard Rho算法的时间复杂度的证明比较复杂，可以理解为 $n$ 的1/4次方。大致感性理解一下：

对于一个合数，一定有一个小于根号的因子(非1)，那么随机两个数字之差可被这个因子整除的期望随机次数就是这个因子的大小。那么这样随机的复杂度大概是根号，Pollard想了一个优化方式，用平方加 $c$ 的伪随机数生成方式产生数列，这个数列满足：如果下标距离为 $d$ 的两个数之差为因子的倍数，所有距离为d的两个数之差都是因子的倍数，这个性质优化了我们对两两之数差的枚举，我们发现如果距离为 $d$ 的一对数不满足，那么所有距离为 $d$ 的数对都不满足，大大减少了我们枚举的数量，我们只需要枚举每一个距离的数对一次即可，复杂度降为1/4次方。

大整数分解是困难问题

我们可以看出，虽然是大整数分解，但是Pollard Rho算法也是一个基于随机化的幂函数复杂度算法，只能解决 $long\ long$ 以内的大整数分解，并没有降到log级别。

在密码学中，我们用到的质数大多是位数特别高的质数，上面我也讲了如何生成一个大质数，比如生成1024位的大质数，由于期望下 $log$ 次即可产生一个质数，而且我们也会快速判断一个数是否为质数，只需要花一点点时间就可以生成一个大质数。如果我们把两个大质数相乘，我们可以得到一个大整数，这样的大整数极其难分解。

当我们把大整数看做 $2^n$ 级别，即二进制下 $n$ 位的大整数，问题的规模为 $n$ ，那么对于这样的n我们就没有多项式复杂度的算法可以将其分解，这就是一个铁打的np困难问题。

一些加密算法会用到这样的原理，利用大整数分解是困难问题来确保加密算法的安全性，比如RSA。

我个人一直认为qwq，数学的规律是宇宙通用的规律，不会因任何物质而改变。对于大整数分解这样一类困难问题，你只需要将数据规模 $n$ 提高到一定算力无法达到的数值，即使是有相当高的算力的外星文明，也甚至无法去分解一个大整数。因为宇宙中没有无穷大的算力，只要没有多项式复杂度的算法，这便是一个近似于永恒的难题。