网络空间安全数学基础

整除

初等数论的基本研究对象是：

整数集合（包括正整数、零、负整数）
- Z={0，±1，±2，……}
自然数集合（正整数集合）
- N={1，2，……}或者Z⁺={1，2，……}

整除的概念

整除的定义

a=bc，a大b小，a是b的倍数，b是a的因数，称b整除a，记为b|a

整除的基本性质

例题

带余除法定理

例题

15能够整除255，余数为0

余数一定是≥0的

最大公因数

最大公因数的定义

互素

最小公倍数的定义

最大公因数与最小公倍数基本性质

用来化简最大公因数的主要方法

例题

最大公因数和最小公倍数的本质属性定理

最大公因数表达式定理

算术基本定理

素数

算数基本定理

正整数的素因数标准分解式

例题

Euclid算法

求到最后余数为0，最后一个不为0的余数就是它俩的最大公因数

例题⭐

求最大公因数
求二元一次方程

筛法

筛法的依据定理

考试会用，实际不用

例题

剔除2357的倍数，剩下的是素数

如果对任意的素数p≤√n，p都不是n的因数，那么n一定是素数。

同余

同余的概念

同余的定义

这四个中只要有一个成立，默认其余三个都成立

同余的等价关系定理

(3)若ab模m同余，则(a,m)=(b,m)

同余式和同余式组的关系定理

运算

先模后运算

例题

考试不让带计算器，模数不会这么大

模逆存在定理

前提条件是a和m互素

模逆运算

以上面的例子来说，虽然5和12都为3对模7的逆（看着和模逆存在的唯一性矛盾），但5和12在模7意义下相同，因为同余，所以一般说讨论比模数小的1-6和谁同余就行

例题

同余类和既约同余类

同余类和完全剩余系

完全剩余系不唯一

既约同余类和既约剩余系

既约同余类的代表元与其互素，类里面的每个元素都互素

同余类的加法和乘法运算

例题

欧拉函数

这是这章的关键

例题

欧拉定理和费马小定理

Euler定理

例题

费马小定理

例题⭐

这种题一定要会做：根据欧拉定理算大模指数运算（大指数）
模数是偶数——欧拉定理

素性检测算法

Fermat小定理

Fermat素性检测

合数100%判断，素数概率判断

例题

a可以随机选，演示用选的小

Miller-Rabin素性检测

包含模指数运算

RSA公钥加密算法

1978年，美国麻省理工学院的学者Rivest、Shamirz和Adleman提出了RSA公钥加密算法。是目前应用最广泛的公钥加密方案之一

正确性

涉及：模乘、欧拉函数、欧几里得算法、随机数生成算法、模指数算法……

同余方程

一次同余方程

二元一次不定方程

一次同余方程整数解定理

例题

自己手算一遍
例3.1.6也可用Eulide算法求模逆

基于同余方程的仿射加密算法

例题

中国剩余定理

重点

用中国剩余定理的条件：
- 模数互素
- x系数为1

例题⭐

也可以用Eulide算法求逆
同余式和同余式组是等价的，前提是同余式组的模数的最大公因数是1
59x≡27(mod 7) <=> 3x≡27(mod 7)；59/7…3
3x≡27(mod 7) <=> 3x≡6(mod 7)；27/7…6
3x≡6(mod 7) <=> x≡2(mod 7)；(3,7)=1
59x≡27(mod 13) <=> 7x≡27(mod 13)；59/13=4…7
7x≡27(mod 13) <=> 7x≡1(mod 13)；27/13=2…1
7x≡1(mod 13) <=> x≡7^-1×1(mod 13)；(7,13)=1
x≡7^-1×1(mod 13) <=> x≡7^-1(mod 13) <=> x≡2(mod 13)；2×7=14；14/13=1…1
处理后，x的系数都为1，模数两两互素
13M₁^-1≡1(mod 7) <=> M₁^-1≡6(mod 7)；13/7=1…6；6×6=36；36/7=5…1；or 13×6=78/7=11…1
7M₂^-1≡1(mod 13) <=> M₂^-1≡2(mod 13)；7/13=0…7；7×2=14；14/13=1…1；or 7×2=14/13=1…1
x≡13×6×2+7×2×2(mod 91) <=> x≡2(mod 91)；13×6×2+7×2×2=184/91=2…2

不能用中国剩余定理：x系数不是1，(12,10)≠1
5x≡7(mod 3) <=> 2x≡1(mod 3)；5/3…2；7/3…1
x≡2^-1(mod 3) <=> x≡2(mod 3)；(2×2)/3…1
2和4不互素，去掉一个方程；去掉模2的方程，因为模2方程的解为1，3，5，7，9，模4方程的解为7，11，15，19；显然模4的解包含在模2解中；但方程组的解需要满足所有方程；而模2方程的一些解不满足模4的方程，故去掉模2的方程
同余式化为同余式组是，同余式组模数的最小公倍数是同余式的模数=>[12,10]=60，所以最后的解要模60