信息安全数学基础学习笔记

第一章

对于整数abc,有 $a=q*b+c$ ，q为整数，则 $(a,b)=(b,c)$ 可以推出广义欧几里得除法
$(0,b)=b$
贝祖等式： $s*a+t*b=(a,b)$
任何一个整数 $n>1$ 都可以表示为素数的乘积
如果a是一个大于1的整数，则a大于1的最小因数一定是素数
如果a是一个大于1的整数 $\le\sqrt{a}$ 的素数都除不尽a，则a是素数
$\pi(x)$ 表示不大于x的素数的个数
最大公因数：先分解为几个素因数的乘积，然后在公有素因素取出指数最小的相乘
{a,b},可以分解为素因数后取指数最大的相乘
$(a,b)=d$ ,{a,b}=m,则 $ab=dm$ 可求最小公倍数
标准分解式：
$N = p _1 k_1 … p_ s k_ s , k_ i > 0 N=p_1^{k_1}…p_s^{k_s} , k_i>0 N=p_1k_1…p_sk_s,ki>0且 p_i < p_ j ( i < j ) p_i < p_j (i<j) p_i<p_j(i<j) 是素数$

Q

如何证明一个数是素数：
1.用Eratosthenes筛法（平凡判别P7）具体：对于一个数n，所有 p < n 1 / 2 p< n^{1/2} p<n1/2，均无法整除n，则n是一个素数
2.其欧拉函数即 $φ ( m ) = m − 1 \varphi(m)=m-1 φ(m)=m−1$ 的时候，m是一个素数 P68
3.对于模m的最小正数完全剩余系等于其最小正数简化剩余系的时候，m是一个素数
4.利用Wilson定理，如果一个整数n， $( n − 1 ) ! + 1 ≡ 0 m o d n (n-1)!+1\equiv \ 0\ mod\ n (n−1)!+1≡ 0 mod n$ 时，n是一个素数 P118

如何计算两个数的最大公因数：

1.广义欧几里得除法：P22
利用 $（a，b）=（b，c）$ ，一步一步缩小直到0
2.通过贝祖等式： P25
贝祖等式 $s*a + t*b=（a，b）$ 证明在P27

图片.png

3.如果形式为 $（ 2 a − 1 ， 2 b − 1 2^a-1，2^b-1 2a−1，2b−1）$ ，那么其最大公因数为 2 （ a ， b ） − 1 2^{（a，b）}-1 2（a，b）−1 P37
4.如果知道这两个数的最小公倍数，则（a，b）=a*b/[a，b] P39

如何求两个数的最小公倍数： P39

$[a，b]=a*b/（a，b）$

如何构造两个互素的数：

通过（a，b）的性质：P33
$（a/（a，b），b/（a，b））$ =1
通过贝祖等式： P33
构造一个ad-bc=1，则（a，b）=1
通过已知的（u，v）=1，构造出（a，b）=1 P35

在这里插入图片描述

只要qrst是单位阵，也就是qt-sr=1，即等式成立
所以对于 $a=q*u+r*v b=s*u+t*v$
4.通过已知的（a，b）=1，构造出 $（ 2 a − 1 ， 2 b − 1 2^a-1，2^b-1 2a−1，2b−1）=1$ P37