世界总决赛选手带你玩转数论 1——素数及素性检测

ACM算法日常

发布于 2021-06-16 16:03:55

89700

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

笔者

笔者曾获得 ICPC 2020 世界总决赛资格，ICPC 2020 亚洲区域总决赛第五名。

系列介绍

我们将从最简单、最基础的数论开始，由浅入深，逐步介绍在 ACM 算法竞赛以及密码学中常用的数论知识。

自然数

自然数是整数的一部分，最简单的数学模型。

Peano 自然数公理

如果有一些对象（可数集），除了它们的数目之外其它性质我们不予考虑的话，我们就可以用自然数来数它们。

整除

若整数

除以非零整数

，商为整数，且余数为零，我们就说

能被

整除（或说

能整除

），

为被除数，

为除数，即

a\mid b

（ “

\mid

”是整除符号）。

注意

是任何非零整数的倍数。

素数

又称质数，指在大于

的自然数中，除了

和该数自身外，无法被其他自然数整除的数（也可定义为只有

与该数本身两个正因数的数）。大于

的自然数若不是素数，则称之为合数（也称为合成数）。

一些结论

质数的密度大约为

\frac{1}{\text{log}n}

，即小于等于

的质数大约有

\frac{n}{\text{log}n}

个。

\sum_{p=1}^n\frac{1}{p}=O(\text{log}\text{log}n)

，其中

为质数。

欧拉定理

欧拉函数是小于或等于

的正整数中与

互质的数的数目，用

\varphi (n)

表示。

其中

\varphi(n)

有通项公式

\varphi(n) = n\prod _{i=1}^{x}(1-\frac{1}{p_i})

其中

p_1,p_2,\cdots ,p_x

为

的所有质因数。

利用通项公式，我们可以直接求解欧拉函数的值：

#define LL long long
LL phi(LL x)
{
    LL res=x;
    for(LL i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

欧拉定理

如果

(a,m)=1

，则

a^{\varphi(m)}\equiv 1 (mod \;m)

；

扩展欧拉定理

如果

(a,m)\neq 1

，则

a^b\equiv a^{\text{min}(b,b\; mod\; \varphi(m)+\varphi(m))} (mod \;m)

。

【例题】

https://www.lydsy.com/JudgeOnline/problem.php?id=3884

BZOJ3884 上帝与集合的正确用法

题意

求

2^{2^{2^{2^{\cdots }}}}\; mod\; p

的结果。

分析

利用拓展欧拉定理：

a^b\equiv a^{\text{min}(b,b\; mod\; \varphi(m)+\varphi(m))} (mod \;m)

，可以得到：

2^{2^{2^{2^{\cdots }}}}\equiv 2^{(2^{2^{2^{2^{\cdots }}}} \; mod \; \varphi(p) + \varphi(p) )}(mod\; p)

；而

2^{2^{2^{2^{\cdots }}}} \equiv 2^{(2^{2^{2^{2^{\cdots }}}} \; mod \; \varphi(\varphi(p)) + \varphi(\varphi(p)) )}(mod\; \varphi)

。

显然这是一个不断变成

2^{2^{2^{2^{\cdots }}}}\; mod\; \varphi(\varphi(\cdots p))

子问题的过程。

经过不断的

\varphi(\varphi(\cdots p))

迭代，最终一定会变成

，而显然，

2^{2^{2^{2^{\cdots }}}}\; mod\; 1=0

，此时可以开始回溯。考虑需要进行多少次迭代。

如果

是奇数，那么

\varphi(p)

一定为偶数；

如果

是偶数，那么

\varphi(p)

一定满足

\varphi(p)\le \frac{p}{2}

。

于是可以得到

\varphi(\varphi(p))\le \frac{p}{2}

，所以递归次数级别是

log_2n

的。时间复杂度为

O(Tlog_2p)

。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define inf 0x3fffffff

LL phi(LL x)
{
    LL res=x;
    for(LL i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

LL bin(LL x,LL n,LL MOD)
{
    LL ret=MOD!=1;
    for (x%=MOD;n;n>>=1,x=x*x%MOD)
        if (n&1) ret=ret*x%MOD;
    return ret;
}

int T;
LL p;

LL solve(LL x)
{
    if (x==1) return 0;
    LL p=phi(x);
    return bin(2LL,solve(p)+p,x);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&p);
        printf("%lld\n",solve(p));
    }
    return 0;
}

素数个数

令

\pi (n)

表示

\le n

的素数个数。

最前面提到了，素数个数大约是

O(\frac{n}{logn})

级别的。

可以用欧拉筛在

O(n)

的时间复杂度内求得

\pi (n)

。

考虑更优的做法。

我们用

f(n,m)

表示

\le n

的正整数中因子不含有

p_1,p_2, \cdots ,p_m

的个数，其中

p_1,p_2,\cdots ,p_m

是按照顺序从小到大排列的质数。

容易发现

f(n,m)=f(n,m-1)-f(\left \lfloor \frac{n}{p_m} \right \rfloor,m-1)

，即去掉能被

p_m

整除但是不能被

p_1,p_2, \cdots ,p_{m-1}

整数的部分。而且

f(n,1)=n-\left \lfloor \frac{n}{p_1} \right \rfloor

；当

p_m^2 > n

的时候，

f(\left \lfloor \frac{n}{p_m} \right \rfloor,m-1)=1

（因为只包含

p_m

）本身。

这样来做，可以保证时间复杂度是

O(n^{\frac{3}{4}})

。

素性检测

暴力判断

从

开始尝试是否是

的约数，直到

\sqrt{x}

。

bool isPrime(LL p){
    for (LL i=2;i*i<=p;i++)
        if (p%i==0) return false;
    return true;
}

费马质数判定法

根据费马小定理，

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

，其中

是质数，

是整数。

于是我们可以考虑随机一个

，计算

a^{n-1}\; mod\; n

是否为

，如果不为

，那么肯定不是质数，否则需要继续尝试数次。

如果

a\equiv 1(mod\; n),a_1\equiv a_2\equiv \cdots \equiv a_s \not\equiv 1(mod \; n)

，则有

(a\cdot a_{i})^{{n-1}}\equiv a^{{n-1}}\cdot a_{i}^{{n-1}}\equiv a^{{n-1}}\not \equiv 1{\pmod {n}}

，也就是说所有的

a\cdot a_i(1\le i\le s)

都满足

a\cdot a_i\not\equiv 1 (mod\; n)(1\le i\le s)

。

于是可以得到，对于一个合数而言，我们找到一个

使得

a^n\equiv 1(mod \;n)

的概率是小于

\frac{1}{2}

，这样的单次检验正确率已经比较可观了。

不过费马质数判定法有一个致命的弱点，即 Carmichael number 如果用费马质数判定法来检验的话，会被误判。

MiLLer Rabin

基于 Fermat 质数检验法的改进。

Fermat 质数检验法，每次都是检验

a^{n-1}\equiv 1(mod\; n)

是否成立，现在假设

n-1=2^k\cdot t

。

我们考虑先检验

a^t

，然后不断翻倍验证。

因为对于一个质数

有

x^2\equiv 1(mod \; p)\Leftrightarrow x\equiv \pm 1 (mod \; p)

。于是有从

a^t

开始往上倍增的时候一定一直满足

mod \; p

为

\pm 1

。

可以证明检验的单次正确率大于

\frac{1}{2}

。证明太复杂，省略了。

对于不同范围数的 MiLLer-Rabin 检验可以使用不同的

，具体是：

int 范围内只需检查

2, 7, 61

long long 范围

2, 325, 9375, 28178, 450775, 9780504, 1795265022

3\cdot 10^{15}

内

2, 2570940, 880937, 610386380, 4130785767

4\cdot 10^{13}

内

2, 2570940, 211991001, 3749873356

const LL m=7, aa[m]={2, 3, 5, 7, 11, 13, 17};
LL n, p;

LL fmul(LL a, LL b, LL p){  //将b分解为二进制，返回a*b%p
    LL ans=0;
    for (; b; b>>=1, a+=a, a%=p)
        if (b&1) ans+=a, ans%=p;
    return ans;
}

LL fpow(LL a, LL x, LL p){
    LL ans=1, base=a;
    for (; x; x>>=1, base=fmul(base, base, p))
        if (x&1) ans=fmul(ans, base, p);
    return ans;
}

bool MR(LL a, LL x, LL p){
    LL t=fpow(a, x, p);
    if (t!=1&&t!=p-1) return false;
    if (t==1&&x&1||t==p-1) return true;
    return MR(a, x>>1, p);
}

bool isPrime(LL p){
    if (p < 2) return false;
    if (p == 2) return true;
    if (p&1==0) return false;
    for (LL i=0; i<m; ++i){
        if (p==aa[i]) return true;
        if (fpow(aa[i], p-1, p)!=1) return false;
        if (!MR(aa[i], (p-1)>>1, p)) return false;
    }
    return true;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

int

登录后参与评论

0 条评论

热度