素数定理-欧几里得算法-乘法逆元

作者: 章鱼丸砸汤 | 来源:发表于2020-04-07 15:37 被阅读0次

素数定理-欧几里得算法-乘法逆元
组合数求解
AcWing 886. 求组合数 II
资格赛 A题
ComSec作业三--编程题(AES)
乘法逆元
组合数模板
【总结】逆元的求法
逆元
乘法逆元的计算

一、素数定理

素数定理给出的是估计素数个数的方法：

设π(x)是小于x的素数的个数，则

π(x)≈x/lnx

eg：

64位二进制表示的素数的个数为

$\frac{2^{64}}{ln2^{64}}- \frac{2^{63}}{ln2^{63}}≈2.05×10^{17}个$

二、是否为素数的判定方法

(*)判断素数的必要条件

(1)欧拉定理

提及欧拉定理，需要先引出欧拉函数的定义：

欧拉函数Φ(n)是定义在正整数上的函数，Φ(n)的值等于序列0,1,2,3,…,n-1中与n互素的数的个数

欧拉函数的性质：

(1)m的素数时，有Φ(m)=m-1

(2)m=pq,且p和q均是素数时，有Φ(m)=Φ(p)Φ(q)=(p-1)(q-1)

(3)若m和n互素，则Φ(m×n)=Φ(m)×Φ(n)

(4)若p是一个素数，则Φ(p^e)=p^e-p^(e-1)

(5) $n=p_{1}^{q_{1}}p_{2}^{q_{2}}...p_{i}^{q_{i}}(p_{1},p_{2},...,p_{i}为素数),则 \varphi(n)=n(1-\frac{1}{p_{1}} )(1-\frac{1}{p_{2}} )...(1-\frac{1}{p_{i}} )$

由欧拉函数可以延伸出欧拉定理的内容：

欧拉定理:

对于任何互素的两个整数a和n，有

$a^{\varphi(n)}\equiv$ 1(mod n)

如果n=p是素数,则有

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

显然欧拉定理可以看成是费马定理的推广形式。

欧拉定理可以用来简化幂的模运算

Eg：

求 $7^{803}$ 的后三位数字

解： $7^{803}$ (mod 1000)的结果

$\Phi (1000)=1000(1-\frac{1}{2} )(1-\frac{1}{5} )=400$

有 $7^{803}\equiv (7^{400} )^27^3 \equiv 343$ (mod 1000)

(2)费马定理

如果p是素数，a是正整数，且gcd(a,p)=1，那么

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

另一种形式：

如果p是素数，a是任意正整数，则对gcd(a,p)=1,有

$a^p\equiv a$ (mod p)

(3)二次探测定理

如果p是一个素数，且0<x<p,则方程 $x^2\equiv$ 1(mod p)的解为 x = -1、p-1。

即如果符合 $(p-1)^2\equiv$ 1(mod p)，那么p很有可能是素数，但是仍不能肯定p就是素数。

(*)判断素数的充要条件

(1)Wilson定理

对于给定的正整数n，判断n是一个素数的充要条件是 $(n-1)!\equiv$ -1(mod n)。

虽然是充要条件，且Wilson的定理有很高的的理论介质。因为带有阶乘，在检测的时候计算量大，不适合检测较大素数的检测。

(2)米勒-拉宾算法

米勒-拉宾算法是一个多项式算法，能以接近概率1保证判断结果的正确性。

Miller-Rabin(n)

把n-1写成 $n-1=2^km$ ，其中m是一个奇数

选取随机整数a，使得 $1\leq a\leq n-1$

$b=a^m$ (mod n)

If $b\equiv 1$ (mod n)

Return (‘n是素数’)

End

For i=0到k-1

If b≡-1(mod n)

Return (‘n是素数’)

Else

b=b^2(mod n)

End

Return(‘n是合数’)

三、求最大公约数算法-欧几里得算法

欧几里得算法描述：

两个整数用a，b表示，商用q表示，余数用r表示

Step1 取a，b较大者为a，较小者为b

Step2 做除法，计算并保留余数r=mod(a,b)

Step3 将原来的除数改做被除数，余数作为除数a=b,b=r

重复Step1和Step2直到r=0,返回b

四、用欧几里得扩展算法求乘法逆元

乘法逆元的定义：

假设gcd(a,n)=1,则存在整数s，使得 $as\equiv 1$ (mod n)，即s是a(mod n)的乘法逆元素。

关于ax+by=d

设a和b是两个正整数(至少有一个非零)，d=gcd(a,b),则存在整数x和y使得ax+by=d成立，如果a、b互素，那么存在整数x和y使得ax+by=1成立，此时可以求出ax≡1(mod b)中的x，即为逆元。

扩展欧几里得算法：

构造两个数列：

Eg：

求28mod75的乘法逆元(a=75,b=28)

gcd(28,75)=1 所以存在逆元

75=2×28+19

28=1×19+9

19=2×9+1

9=9×1+0

3×78+(-8)×28=1

所以28mod75的乘法逆元为-8

五、中国剩余定理求解同余方程组

中国剩余定理完整版

Eg：

已知下列同余方程组，求解x

第一步：求M

M=2×3×5×7=210

第二步：求 $\frac{M}{m_{i}}(i=1,2,...,k)$

$M_{1} =103,M_{2} =70,M_{3} =42,M_{4} =30$

第三步：求 $e_{i}$

$e_{i}满足 \frac{M}{m_{i}} e_{i} \equiv$ 1(mod $m_{i}$ )(i=1,2,...,k)

第四步:

$x\equiv [ \frac{M}{m_{1}}e_{1}a_{1}+\frac{M}{m_{2}}e_{2}a_{2}+...+\frac{M}{m_{i}}e_{k}a_{k} ]$ (mod M)

$x\equiv$ (105×1×1+70×1×2+42×3×3+30×4×5)(mod 210)

$x\equiv$ 173(mod 210)

网友评论

本文标题：素数定理-欧几里得算法-乘法逆元

本文链接：https://www.haomeiwen.com/subject/mjltwxtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！