本周进行了密码学的相关学习，以下是记录内容同时也供日后复习使用。
本次密码学使用的教材是《公钥密码学的数学基础》，一看名字就知道了这其中需要很强的数学功底，例如数论知识等。本周主要内容以整除为主。
什么是公钥密码？
通俗来说，加密和解密用的钥匙不同：通常一个是公开的，称为公钥；另一个保密，称为私钥。所以任何人都可以使用预期接收者的公钥对消息进行加密，但该加密消息只能使用接收者的私钥解密，如此公钥密码学也另称为非对称密码。
使用公钥加密，稳健的身份验证也是可能的。发件人可以将消息与私钥结合起来，在消息上创建一个简短的数字签名。
整除重要知识点（部分）
基本的定义定理请参考最后的笔记截图，此处只放重要知识点。
1.b=aq, 则a|b
2.若a为合数，则a最小真因子为素数。
这个怎么证明呢？显然，这个使用反证法，假设最小的因子d是合数，那么必定存在d‘使得d’|d(因为合数可再分解）故矛盾。
3.素数有无穷多个。
在这里需要提几个知识点，首先是P(n),指的是第n个素数，其次是Pi(x),指的是不超过x的素数。
P
n
≤
2
2
n
?
1
P_n\le 2^{2^{n-1}}
Pn?≤22n?1
π
(
x
)
>
l
o
g
2
(
l
o
g
2
x
)
\pi(x)>log_2(log_2x)
π(x)>log2?(log2?x)
这两个是限定范围的，当然这里就有必要再对PI(x)近似值做个说明了.
π
(
x
)
≈
x
l
n
x
\pi(x) \approx \frac{x}{lnx}
π(x)≈lnxx?
4.带余除法（重点）
b=aq+r,则有唯一a,r使得上式式子成立，并且a|b 等价于r=0
关于唯一性与存在性见后面。
5.最大公因数与最小公倍数
最大公因数 d=(a,b)
最小公倍数 d=[a,b]
遇到这里就需要介绍辗转相除法求他们了。
几个重要性质
(
a
(
a
,
b
)
,
b
(
a
,
b
)
)
=
1
(\frac{a}{(a,b)} ,\frac{b}{(a,b)} )=1
((a,b)a?,(a,b)b?)=1
[
a
,
b
]
(
a
,
b
)
=
a
b
[a,b](a,b)=ab
[a,b](a,b)=ab
下面将介绍费马数。
F
n
=
2
2
n
+
1
F_n=2^{2^{n}}+1
Fn?=22n+1
费马数是两两互素，（证法具体见截图）
6.证明：p是素数，sqrt§不是有理数。
这个也是很好证明的，设a/b=sqrt§, 且（a,b)=1，两式平方很容易得出p*b方=a方，那么p必定是一个数的平方，故矛盾。
7.Euclid算法
本质就是辗转相除法,这里就放一个关于求最大公因数的算法，具体证明方法见截图。
int gcd(int a,int b){
return a%b==0?b:gcd(b,a%b)
}
8.Fib数列相邻互素。
9.求解一次不定方程
a
1
x
1
+
a
2
x
2
+
.
.
.
+
a
k
x
k
=
c
a_1x_1+a_2x_2+...+a_kx_k=c
a1?x1?+a2?x2?+...+ak?xk?=c
使上述有解的充要条件是 （a1,…ak)=c
下面给出二元一次的不定方程通解：
a
1
x
1
+
a
2
x
2
=
c
a_1x_1+a_2x_2=c
a1?x1?+a2?x2?=c如果xt和xn是其中的一组解，那么
{
x
1
=
x
t
+
a
2
(
a
1
,
a
2
)
m
m=0,-1,1,-2,2,3,-3...
x
2
=
x
n
?
a
1
(
a
1
,
a
2
)
m
\begin{cases} x_1=x_t+\frac{a_2}{(a_1,a_2)}m & \text{m=0,-1,1,-2,2,3,-3...} \\ x_2=x_n-\frac{a_1}{(a_1,a_2)}m \end{cases}
{x1?=xt?+(a1?,a2?)a2??mx2?=xn??(a1?,a2?)a1??m?m=0,-1,1,-2,2,3,-3...
10.整数的素分解
基本算术定理：
设a>1,则a=p1p2p3*p4…ps （pi为素数）【数学归纳法易得出】
for(int i=2;i<=n;i++){
if(n%i==0){
cout<<i<<" ";
n/=i;
i=1;
if(n==1) break;
}
}
标准素因数分解式
a
=
p
1
α
1
p
2
α
2
.
.
.
p
s
α
s
a=p_1^{\alpha_1}p_2^{\alpha _2}...p_s^{\alpha _s}
a=p1α1??p2α2??...psαs??
推论：
若a是合数，则必有p|a, p<=sqrt(a)
11.Eratoschenes筛选法
什么叫筛选法，就是列出n之间的素数。这和我们之前的P(n)、Pi(x)中是一个道理，不过这两个式子都是近似运算，远远达不到我们需要的点。
那么什么叫筛选法，类似于直接删去不必要的数字，例如从2开始，直接删去2的倍数，下面附主要c++代码帮助理解。
a[1]=false;
memset(a,true,sizeof(a));
for(int i=2;i<=n;i++){
if(a[i]){
int m=2;
for(int j=i*i;j<=n;j+=i){
a[j]=false;
}
}
}
12.数论函数
数论函数指的是[x]:表示不超过x最大整数
[x]<=x<[x]+1,则小数部分{x}=x-[x]
对任意m属于整数，有[x+m]=[x]+m,{x+m}={x}
13.整除关系
设k属于自然数，则a^{k} || b 表示b恰好被a ^{k}整除。
设n是正整数，p是素数，且有p^{a} || n!
α
=
α
(
p
,
n
)
=
∑
j
=
1
∞
[
n
p
j
]
\alpha =\alpha (p,n)=\sum_{j=1 }^{\infty } [\frac{n}{p^{j}} ]
α=α(p,n)=j=1∑∞?[pjn?]
设n属于正整数
n
!
=
∏
p
≤
n
p
α
(
p
,
n
)
n!=\prod_{p\le n}^{} p^{\alpha (p,n)}
n!=p≤n∏?pα(p,n)
这个公式有什么用呢？
例如计算80！结尾为0的个数。
其实本质就是求k 使得 10 ^{k} || 80！
则
α
=
α
(
5
,
80
)
=
∑
j
=
1
∞
[
80
5
j
]
\alpha =\alpha (5,80)=\sum_{j=1 }^{\infty } [\frac{80}{5^{j}} ]
α=α(5,80)=j=1∑∞?[5j80?]
易得数为19，故结尾为0有19个。
总结
在这一周中也除了接触密码学的数学基础部分以外，同时也接触了在ctf中的密码学部分，以此进行巩固学习。
同时也对古典密码、数字签名有了了解，但是深入不多，日后需要补上。这周的主要学习在密码学上面同时也对数论部分有所了解，接下来加大训练强度，以学习为主，同时适当接触题目来训练，当然web开发这一块也需要同步跟上！期待后续！
下面章节加题目的write up,敬请期待！
笔记截图
