NumberTheory2


huangx607087 学习数论的笔记2

1.素数及其计数(数论概论$12,13$章)

定理1.$2$是唯一的偶素数

定理2.素数有无穷多个,若$a,m$为任意整数,满足$\gcd(a,m)=1$,那么有无穷多个素数$p$满足$p\equiv a \mod m$.

定理3.区间$[x,2x]$内必有一个素数

定理4.设$\pi(x)$为不超过$x$的素数个数,那么$\pi(x)$接近于$\frac{x}{\ln x}$,也就是$\lim_{x \to +\infty} \frac{\pi(x) \ln(x)}{x}=1$

哥德巴赫猜想:每一个大于等于$4$的偶数都可以表示为$2$个素数之和。

孪生素数:$p,p+2$均为素数,那么$(p,p+2)$构成一对孪生素数,猜想有无限多个这样的素数组。

素数猜想3:可能存在无穷多个$n^2+1$类型的素数

2.梅森素数(形如$2^p-1$的素数)(数论概论$14,15$章)

若$a^n-1$是素数,那么$a=2$

性质1:若$n$被$m$整除,那么$2^n-1$被$2^m-1$整除。所以我们有推论:若$2^p-1$是个素数,则$p$一定是个素数。

性质2:如果$2^p-1$是素数,那么$2^{p-1}(2^p-1)$是个完全数(完全数是指除了它的本身之外,这个数的所有因子之和等于它本身,比如$6,28$)

性质3:所有大于$6$的完全数在$6$进制中均以$44$结尾

设$\sigma(x)$为$x$的所有因子之和(包括$1,x$两个数),例如:$\sigma(3)=4,\sigma(15)=24$

性质4:若$\gcd(m,n)=1$,则$\sigma(m)\sigma(n)=\sigma(mn)$。

性质5:若$p$为素数,则$\sigma(p^n)=\sum_{i=0}^{n}p^i$。也就是对于任何素数$p$,均有$\sigma(p)=p+1$。

以下为求$\sigma(a^b)$结果的后8位十进制数的代码,也就是$\sigma(a^b)$对一亿取模的值,其中用到了二分快速加,可以推导一下(等比数列里千万不不要用除法!!!!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
int n,m,T,mod=100000000;
int p[4000],c[4000],num;
void dividing(int x)
{
int i;
for(i=2;i*i<=x;i++)
{
if(x%i==0)
{
p[++num]=i;
c[num]=0;
while(!(x%i)) x/=i,++c[num];
}
}
if(x>1) p[++num]=x,c[num]=1;
}
long long pw(int x,int y)
{
if(y==0) return 1;
if(y==1) return x;
if(x==0) return 0;
long long S=pw(x,y/2)%mod;
if(y%2) return S*S*x%mod;
else return S*S%mod;
}
long long ad(int q,int k)//求以1为首项,公比为q,最高项次数为k的等比数列 之和
{
if(k==0) return 1;
if(k==1) return q+1;
long long S=ad(q,(k-1)/2);
if(k%2) return S+pw(q,(k+1)/2)*S%mod;
else return S+pw(q,k/2)*S+pw(q,k)%mod;
}
int main()
{
int i,j;
scanf("%d",&T);
while(T--)
{
int a,b;
scanf("%d%d",&a,&b);
dividing(a);
long long S=1;
for(i=1;i<=num;i++)
{
S*=ad(p[i],c[i]);
S%=mod;
}
printf("%lld\n",S);
}
return 0;
}

3.二分快速幂 (数论概论第$16$章)

二分快速幂的C++代码 (Python中直接用pow(x,y,z)函数,很方便)。

1
2
3
4
5
6
7
8
9
long long pw(int x,int y)
{
if(y==0) return 1;
if(y==1) return x;
if(x==0) return 0;
long long S=pw(x,y/2)%mod;
if(y%2) return S*S*x%mod;
else return S*S%mod;
}

4.解方程$x^e \equiv c \mod n$ (数论概论第$17$章)

前提条件:$\gcd(c,n)=1$且$\gcd(e,\phi(m))=1$。

步骤:
1.计算$\phi(n)$
2.求$e$的逆元$d$
3.计算$x=c^d \mod n$

举个例子:求$x^7 \equiv 5 \mod 39$
1.计算$\phi(39)=24$
2.$e=7$在模$24$的意义下乘法逆元为$d=7$
3.$x=c^d=5^7=78125 \equiv 8 \mod 39$

这是什么?? RSA解密 RSA解密 RSA解密!! 密码学的知识成功地跟数论联系起来了(奇怪的知识增加了)23333333


文章作者: huangx607087
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
  目录