信息安全数学基础复习要点陈恭亮第二版.pdfVIP

信息安全数学基础复习要点陈恭亮第⼆版

来还愿！！！信安数学考了100！！！舒服！！！

问题

第章

如何证明个数是素数：

如何证明个数是素数：

1.⽤Eratosthenes筛法（平凡判别P7）具体：对于个数n，所有pn1/2，均⽆法整除n，则n是个素数

2.其欧拉函数即φ(m)=m−1的时候，m是个素数P68

3.对于模m的最⼩正数完全剩余系等于其最⼩正数简化剩余系的时候，m是个素数

4.利⽤Wilson定理，如果个整数n，(n−1)!+1≡0modn时，n是个素数P118

N的B进制的表⽰：P9

N=Ak−1Bk−1+……+AB+A

10

如何确定个整数d是an…..a0的最⼤公因数：P20

（1）D∣a,d∣an−1…,d∣a

n0

（2）对于个数e，若e∣a…e∣a,则e|d

n0

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

1.⼴义欧⼏⾥得除法：P22

利⽤（a，b）=（b，c），步步缩⼩

2.通过贝祖等式：P25

贝祖等式sa+tb=（a，b）证明在P27

如何求s和t？

另r−2=a,r−1=b

jjj−1j−2

s=(−q)s+s

jjj−1j−2jj−2j−1

t=(−q)t+t其中q是[r/r]的不完全商

初始值：s−2=1s−1=0t−2=0t−1=1

图在P31，技法：俄罗斯⽅块+单位阵，从-3开始，q，r是j+1

3.如果形式为（2a−1，2b−1），那么其最⼤公因数为2（a，b）−1P37

4.如果知道这两个数的最⼩公倍数，则（a，b）=a*b/[a，b]P39

如何确定个整数D是a1…an的最⼩公倍数：P39

（1）a|D

i

（2）若a|D’，则D|D’

i

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

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

如何构造两个互素的数：

1.通过（a，b）的性质：P33

（a/（a，b），b/（a，b））=1

2.通过贝祖等式：P33

构造个ad-bc=1，则（a，b）=1

3.通过已知的（u，v）=1，构造出（a，b）=1P35

只要qrst是单位阵，也就是qt-sr=1，即等式成⽴

所以对于a=qu+rvb=su+tv

4.通过已知的（a，b）=1，构造出（2a−1，2b−1）=1P37

第⼆章

如何判断两个数是否同余：P54

1.根据定理：m|(a-b)，则a≡b（modm）

2.a≡b（modm）的充要条件是a=b+q*m

3.a,b对于m除的余数相同

dk

4.若(a,m)=1,d≡kmodordm(a).等价于a≡amodmP170

如何判断个数n能否被3,7,9,11,13,整除：P57

（1）对于9和3：

将n转化为10进制的科学计数法，n=ak∗10k+..