我爱数学!

数论是计算机领域的基础,包括ACM、CTF都会用到。我的数学底子一般,曾经参加过数竞培训,但是已经荒废了很久。应用能力比证明能力强。但是我想做踏踏实实走攻数论这条路的人,因为我坚信数学的威力是无穷的。毕竟经济基础决定上层建筑。(大雾)

密码学之数论基础

以下内容部分引自境外之王’s blog,感谢~

素数

素数,又叫质数,定义是除了1和它本身以外不再有其他的因数。

整数p>1是素数当且仅当它只有因子+(-)1和+(-)p。

任意整数a>1都可以唯一地因子分解为:

其中p1,p2,…,pt均是素数,p1<p2<…<pt,且所有的ai都是正整数。这就是算术基本定理。

设P是所有素数的集合,则任意正整数a可唯一地表示为:

上式右边是所有素数之积。对某一整数a,其大多数指数ap为0.

两数相乘即是指数对应相加。设,定义k=ab。我们知道整数k可以表示为素数方幂的乘积:。可以推出对于所有的p属于P,有kp=ap+bp成立。

我们通过这个定义,可以写如下程序判断一个数是不是质数

1
2
3
4
5
6
7
8
bool prime(int x)//判断x是不是质数,是返回true,不是返回false 
{
if(x <= 1) return false;
for(int i = 2; i < x; i ++){
if(x % i == 0) return false;
}
return true;
}

这个程序的时间复杂度是O(n),有没有更快的方法,当然

看这个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool prime(int x)//判断x是不是质数,是返回true,不是返回false 
{
if(x <= 1) return false;
for(int i = 2; i <= sqrt(x + 0.5); i ++)//0.5是防止根号的精度误差
{
if(x % i == 0) return false;
}
return true;
}
//另一种方法,不需要根号
bool prime(int x)//判断x是不是质数,是返回true,不是返回false
{
if(x <= 1) return false;
for(int i = 2; i * i <= x; i ++)//用乘法避免根号的精度误差
{
if(x % i == 0) return false;
}
return true;
}
//根据题目不同,如果i*i会爆int,记得开longlong

这个复杂度是O(√n),速度快多了

根据题目不同,有可能你需要先预处理出1~N这N个数是否是素数

如果用刚刚的方法,复杂度就是O(n√n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
const int N = 100000 + 5;
bool prime[N];
bool is_prime(int x)
{
if(x <= 1) return false;
for(int i = 2; i * i <= x; i ++)
{
if(x % i == 0) return false;
}
return true;
}
void init()
{
for(int i = 0; i < N; i ++)
{
prime[i] = is_prime(i);
}
}
int main()
{
init();
}

如果n大一点,就太慢了

介绍一种新方法,埃筛

埃筛————–埃拉托斯特尼筛法,或者叫埃氏筛法

原理:如果找到一个质数,那么这个质数的倍数都不是质数

比如2是质数,那么4,6,8,10,12…都不是质数

然后看3是质数,那么6,9,12,15,18,21…都不是质数

然后看4,4已经被2标记为合数了,所以跳过

然后看5……这样一直筛下去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
const int N = 100000 + 5;
bool prime[N];
void init()
{
for(int i = 2; i < N; i ++) prime[i] = true;//先全部初始化为质数
for(int i = 2; i < N; i ++)
{
if(prime[i])//如果i是质数
{
for(int j = 2*i; j < N; j += i)//从i的两倍开始的所有倍数
{
prime[j] = false;
}
}
}
}
int main()
{
init();
}

因为一些数字,比如6既被2的for循环经过又被3的for循环经过,所以复杂度不是O(n)

这个复杂度经过专业人士检验,复杂度O(nloglogn)(学过高数的小朋友可以自己证明≖‿≖✧当然也可以去百度)

知道原理后,我们再稍微优化一下就更快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
const int N = 100000 + 5;
bool prime[N];
void init()
{
for(int i = 2; i < N; i ++) prime[i] = true;
for(int i = 2; i*i < N; i ++)//判断改成i*i<N
{
if(prime[i])
{
for(int j = i*i; j < N; j += i)//从i*i开始就可以了
{
prime[j] = false;
}
}
}
}
int main()
{
init();
}

快速幂

a的b次方怎么求

pow(a, b)是数学头文件math.h里面有的函数

可是它返回值是double类型,数据有精度误差

那就自己写for循环咯

1
2
3
4
5
6
7
8
9
LL pow(LL a, LL b)//a的b次方
{
LL ret = 1;
for(LL i = 1; i <= b; i ++)
{
ret *= a;
}
return ret;
}

完美

可是题目是b的范围是1 <= b <= 1e9

超时,妥妥的。。。

看个例子

1
2
3
4
5
6
7
8
9
10
11
比如计算

2*2*2*2*2*2*2*2*2*2*2

可以这样算

原式=4*4*4*4*4*2

=8*8*4*2

=16*4*2

你看,相同的可以先合并,减少计算步骤

如果题目说数据很大,还需要求余,那么代码就可以这么写

1
2
3
4
5
6
7
8
LL pow_mod(LL a, LL b)//a的b次方
{
if(b == 0) return 1;
LL ret = pow_mod(a, b/2);
ret = ret * ret % MOD;
if(b % 2 == 1) ret = ret * a % MOD;
return ret;
}

这是递归写法

然后还有递推写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LL pow_mod(LL a, LL b)//a的b次方
{
LL ret = 1;
while(b != 0)
{
if(b % 2 == 1)
{
ret = (ret * a) % MOD ;
}
a = (a * a ) % MOD ;
b /= 2;
}
return ret;
}

对于位运算熟的小盆友,还可以写成位运算形式,速度又快,又好理解,在加一个求余p,代码如下

1
2
3
4
5
6
7
8
9
10
11
LL pow_mod(LL a, LL b, LL p)//a的b次方求余p 
{
LL ret = 1;
while(b)
{
if(b & 1) ret = (ret * a) % p;
a = (a * a) % p;
b >>= 1;
}
return ret;
}

有了快速幂,于是,快速乘诞生了

1
2
3
4
5
6
7
8
9
10
11
LL mul(LL a, LL b, LL p)//快速乘,计算a*b%p 
{
LL ret = 0;
while(b)
{
if(b & 1) ret = (ret + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ret;
}

最大公约数gcd和最小公倍数lcm

gcd(a, b),就是求a和b的最大公约数

lcm(a, b),就是求a和b的最小公倍数

然后有个公式

ab = gcd lcm ( gcd就是gcd(a, b), ( •̀∀•́ ) 简写你懂吗)

解释(不想看就跳过)
{

  首先,求一个gcd,然后。。。

  a / gcd 和 b / gcd 这两个数互质了,也就是 gcd( a / gcd ,b / gcd ) = 1,然后。。。

  lcm = gcd (a / gcd) (b / gcd)

  lcm = (a * b) / gcd

  所以。。ab = gcd lcm

}

所以要求lcm,先求gcd

辣么,问题来了,gcd怎么求

辗转相除法

while循环

1
2
3
4
5
6
7
8
9
10
11
LL gcd(LL a, LL b)
{
LL t;
while(b)
{
t = b;
b = a % b;
a = t;
}
return a;
}

还有一个递归写法

1
2
3
4
5
6
7
8
9
10
11
LL gcd(LL a, LL b)
{
if(b == 0) return a;
else return gcd(b, a%b);
}

LL gcd(LL a, LL b)
{
return b ? gcd(b, a%b) : a;
}
//两种都可以

辣么,lcm = a * b / gcd

(注意,这样写法有可能会错,因为a * b可能因为太大 超出int 或者 超出 longlong)

所以推荐写成 : lcm = a / gcd * b

然后几个公式自己证明一下

gcd(ka, kb) = k * gcd(a, b)

lcm(ka, kb) = k * lcm(a, b)

上次做题碰到这个公式

lcm(S/a, S/b) = S/gcd(a, b)

S = 9,a = 4,b = 6,小数不会lcm,只好保留分数形式去通分约分。

扩展欧几里德算法

度娘百科说:

首先, ax+by = gcd(a, b) 这个公式肯定有解 (( •̀∀•́ )她说根据数论中的相关定理可以证明,反正我信了)

所以 ax+by = gcd(a, b) * k 也肯定有解 (废话,把x和y乘k倍就好了)

所以,这个公式我们写作ax+by = d,(gcd(a, b) | d)

gcd(a, b) | d,表示d能整除gcd,这个符号在数学上经常见

那么已知 a,b 求 一组解 x,y 满足 ax+by = gcd(a, b) 这个公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
typedef long long LL;
void extend_Eulid(LL a, LL b, LL &x, LL &y, LL &d)
{
if (!b) {d = a, x = 1, y = 0;}
else
{
extend_Eulid(b, a % b, y, x, d);
y -= x * (a / b);
}
}
int main()
{
LL a, b, d, x, y;
while(~scanf("%lld%lld", &a, &b))
{
extend_Eulid(a, b, x, y, d);
printf("%lld*a + %lld*b = %lld\n", x, y, d);
}
}

有些人喜欢极度简化,这是病,得治(,,• ₃ •,,)

1
2
3
4
5
void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if(!b){d = a; x = 1; y = 0;}
else{ex_gcd(b, a%b, d, y, x); y -= x*(a/b);}
}

数论四大定理

(提示:以后出现(mod p)就表示这个公式是在求余p的条件下成立)

威尔逊定理

当且仅当p为素数时:( p -1 )! ≡ -1 ( mod p )

或者这么写( p -1 )! ≡ p-1 ( mod p )

或者说

若p为质数,则p能被(p-1)!+1整除

在初等数论中

这是威尔逊给出了判定一个自然数是否为 素数 的 充分必要条件

但是由于阶乘是呈爆炸增长的,其结论对于实际操作意义不大。(´・ω・`)(威尔逊表示很伤心)

欧拉定理

欧拉定理,也称费马-欧拉定理

若n,a为正整数,且n,a互质,即gcd(a,n) = 1,则

a^φ(n) ≡ 1 (mod n)

φ(n) 是欧拉函数

欧拉函数是求小于等于n的数中与n互质的数的数目

(o>▽<)太长看不懂?我来帮你断句

欧拉函数是求 (小于n的数 )中 (与n互质的数 )的数目

或者说

欧拉函数是求 1到n-1 中 与n互质的数 的数目

如果n是质数

那么1到n-1所有数都是与n互质的,

所以φ(n) = n-1

如果n是合数。。。自己算吧

例如φ(8)=4,因为1,3,5,7均和8互质

顺便一提,这是欧拉定理

φ(n)是欧拉函数

还有一个欧拉公式

eix = cosx + isinx

把x用π带进去,变成

eiπ= -1

大部分人写成 eiπ + 1 = 0

这是一个令万人膜拜的伟大公式

一定要分清 欧拉定理,欧拉函数和欧拉公式这3个东西,要不然你就百度不到你想要的东西了

孙子定理(中国剩余定理)

孙子定理,又称中国剩余定理。

公元前后的《孙子算经》中有“物不知数”问题:“今有物不知其数,三三数之余二 ,五五数之余三 ,七七数之余二,问物几何?”答为“23”。

就是说,有一个东西不知道有多少个,但是它求余3等于2,求余5等于3,求余7等于2,问这个东西有多少个?”答为“23”。

用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:

中国剩余定理说明:假设整数m1,m2, … ,mn两两互质,则对任意的整数:a1,a2, … ,an,方程组 (S)有解

剩余类

定义比n小的非负整数集合为Zn:

Zn={0,1,….,(n-1)}

这个集合被成为剩余类集,或模n的剩余类。更准确地说,Zn中每一个整数都代表一个剩余类,我们可以将模n的剩余类表示为[0],[1],[2],…,[n-1],其中

[r]={a:a是一个整数,a与r模n同余}

在剩余类的所有整数中,我们通常用最小非负整数来代表这个剩余类。寻找与k是模n同余的最小非负整数的过程,称为模n的k约化。

比如:当k=8,n=4时,寻找8 mod4同余的最小非负整数为0,当k=7,n=4时,寻找7 mod4 同余的最小非负整数为3.

笛卡尔积

笛卡尔积又叫笛卡尔乘积,是一个叫笛卡尔的人提出来的。简单的说就是两个集合相乘的结果。

举个例子:

集合A={a1,a2,a3}

集合B={b1,b2}

他们的笛卡尔积是

A*B={(a1,b1),(a1,b2),(a2,b1),(a2,b2),(a3,b1),(a3,b2)}

即任意两个元素结合在一起

CRT

中国剩余定理(CRT)是数论中最有用的定理之一。CRT说明某一范围内的整数可通过它的一组剩余类来重构,这组剩余类数是对该整数用一组两两互素的整数取模得到的。
CRT可有几种不同的表示形式,这里我们给出其中一种最有用的表示形式:

其中mi是两两互素的,即对1<=i,j<=k, i!=j 有gcd(mi,mj)=1。我们可将ZM中的任一整数对应一个k元组,该k元组的元素均在Zmi中,这种对应关系即为:

其中A属于ZM,对于1<=i<=k, ai属于Zmi,且ai=A mod mi。

CRT 说明下列两个断言成立:

(1)上面的映射是ZM到笛卡尔积Zm1Zm2….*Zmk的一一对应(称为双射),也就是说,对任何A,0<=A<=M,有唯一的k元组(a1,a2,…,ak)与之对应,其中0<=ai<mi,并且对任何这样的k元组(a1,a2,…,ak),ZM中有唯一的A与之对应。

(2)ZM中元素上的运算可等价于对应的k元组上的运算,即在笛卡尔积的每一个分量上独立地执行运算。

中国剩余定理的用途之一是,它给出了一种方法,使得模M的大数运算转化到更小的数上来进行运算,当M为150位或150位以上时,这种方法非常有效。

费马小定理

假如p是质数,若p不能整除a,则 a^(p-1) ≡1(mod p),若p能整除a,则a^(p-1) ≡0(mod p)。

或者说,若p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1。

你看你看你看o(*≧▽≦)ツ,是不是和欧拉定理很像

因为欧拉定理是费马小定理的推广,所以欧拉定理也叫费马-欧拉定理

顺便一提,费马大定理

费马大定理,又被称为“费马最后的定理”,由法国数学家费马提出。

它断言当整数n >2时,关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。

被提出后,经历多人猜想辩证,历经三百多年的历史,最终在1995年被英国数学家安德鲁·怀尔斯证明。

离散对数

大部分摘录于《密码编码学与网络安全》

离散对数是包括Diffie-Hellman密钥交换和数字签名算法(DSA)在内的许多公钥算法的基础。

模n的整数幂

本原根

模算术对数

未完待续QAQ

最后更新: 2019年04月01日 16:58

原始链接: http://yisin.top/2019/04/01/密码学之数论基础/

× 请我吃糖~
打赏二维码