信息安全数学基础笔记


#整除

定义:

性质:

  1. 传递性:
  2. 线性组合中整除保持:

#素数

定义: 对于整数,若,则称为素数,否则为合数

定理:

  1. 为正合数,的一个非最小因子,则为素数且

    证明:使用反证法,若p为合数,则,又有,则由整除传递性得到,因此不是的最小非因子,与题设相矛盾。

    又由n为合数,则,由于p为最小非1因子,故,此时有,显然

#素数无穷

证明:基本思想是先假设素数有无限多个,然后证明可能在一个素数在这有限多个素数构成的集合之外。

假设素数有有限多个,则可以将其枚举为,假设有那么必定有

假设为素数,那么说明前提不正确,素数有无限多个。 假如为合数。那么必定存在的非最小子。因此存在使。若,则

因此有

此时

因此不是整数,这与的一个因子相盾,因此(更准确的来说,此时的所素因子都要比中最大的元素还要大),因此素数有无多个。

上述证明过程利用了一类特殊的数——素数阶乘素数

扩展:证明形如的素数有无限多个

从上面对素数无限的证明,我们可以看到证明集合无限的核心思想是先去一个有限集合,然后证明总存在一个有限集合外的元素。这一过程需要通过构造来实现。

证明:假设有有限多个,那么这些素数可枚举为。考虑,易知

为素数,则与开头假设相矛盾,可得形式的素数有无限多个。

为合数,假设m的所有素因子为

首先证明引理。由于Q中元素皆为素数,故中的一个元素要么满足的形式,要么满足的形式,假设所有满足的形式,易得也一定满足形式,这与定义相矛盾。引理得证。

有上述引理可知存在的素因子具有的形式,若,则与开头假设相矛盾,可得形式的素数有无限多个。

,假设,则存在使 有:

不是整数,这与假设相矛盾,故。与开头的假设相矛盾,证毕。(有问题,参见这里

#素数的算术基本定理

素数的算术基本定理:任何一个大于1的整数都可以写成素数的乘积,且该乘积唯一。

证明:

假设该整数为,利用数学归纳法证明:

为素数时,有为素数使,定理成立

为合数时,将分解为,其中的非1最小因子,有前面素数定理1我们可以得知为素数。此时将作同样的分解,最终我们可以得到,因此定理前半部分得证,后半部分可利用反证法证明,此处省略。

性质:

  1. 将整数分解式写作

    则对于,当且仅当

    时,的一个因子

#最大公因数

定义: 几个整数的最大公因数记为。若,则称它们互质。

性质:

  1. 证明:假设,则

    由于是b与c的最大公因数,得到,同 理可得,因此

  2. 假设,且,那么

    证明:

    假设,那么,因此

    假设,则,由于,易知。由式联立得,即,因此的公因数,因此

    综上所述,

    证毕(p.s. 也可以用广义欧几里得除法证)

    由上述定理我们可以得到:

    一个特殊情况是为素数时,必成立,此时

  3. 假设

    此性质描述了最大公因数在可逆变换(剪切,旋转)下的不变性。

#欧几里得除法

#算法实现

注意到在上述定理中,我们可以得到一种逐步逼近a与b的最大公因数的方法——将计算的问题转换成计算的问题,从而保证每次迭代中c总会减小,最终减小到0,算法停机,代码实现如下:

1
2
3
4
5
6
pub fn gcd(a: u64, b: u64) -> u64 {
if b == 0 {
return a;
}
gcd(b, a % b)
}

或者

1
let rec gcd a b = if b == 0 then a else gcd b (a mod b);;

#贝祖等式

假设整数的最大公约数为,则等式

有整数解当且仅当的倍数,且只要等式有解,它必然有无穷多解。

证明:

,假设有,其中中的最小正元素,以及,假设

其中为非负整数,,则有

,又因为,注意中的最小正整数,因此,因此,因此,特别的,,因此为a与b的公约数,又因为对于a,b的任意一个公约数,假设,得到,即,因此的最大公约数。

#扩展欧几里得算法

有了贝祖等式后,我们可以得到,所谓扩展欧几里得算法即是求上述等式中值的方法。

假设现在我们要求的最大公约数,假设有:

由于便是我们要求的最大公约数,我们只需要求出中的即可。假设,我们首先可以导出:

因此有

可以看到,我们可以通过逐级上推最终确定的值,这一过程可以通过递归来完成:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#[derive(Debug)]
pub struct ExtGCD {
pub p: i64,
pub q: i64,
pub m: i64
}

pub fn ext_gcd(a: i64, b: i64) -> ExtGCD {
if b == 0 {
return ExtGCD {
p: 1,
q: 0,
m: a
}
}

let next = ext_gcd(b, a % b);

ExtGCD {
p: next.q,
q: next.p - a / b * next.q,
m: next.m
}
}

#最小公倍数

几个整数的最小公倍数记为

性质:

  1. 假设的最小公倍数,则

  2. 证明:使用归纳法证明:

    时,显然成立。

    假设对结论成立,则有

    对于,假设,由于,可得,进而

    同时又易知的公倍数,因此

    综上所述,,证毕。

  3. 证明:省略,利用数学归纳法以及上面的性质2即可证明。

#群(group)

定义:

群由一个集合和定义在该集合上的运算组成

使用表示该集合,使用表示该运算。那么当代数结构满足下面的四条群公理时,该结构可以被称为群:

  1. 封闭性:
  2. 结合律:
  3. 单位元存在性:,可以将单位元(identity element)记为
  4. 逆元存在性:,其中为单位元,此时称的逆元,记为

将二元运算称为该群上的乘法,那么由此可以导出该群上的除法:

假设有,现定义群上的除法。要证明除法的存在性即证明的存在性。

那么根据群的逆元存在性可知一定存在的逆元使。因此由单位元的性质以及结合律有

因此

#群同态(Homomorphism)

定义:

假设为两个群,有映射,假如

那么称为群到群的一个同态。

为单射,则该同态为单同态,若为满射,那么该同态是满同态。当为一一对应(双射),那么该同态称为同构,记为

当两个群同构时,这两个群拥有完全相同的群结构,本质上可以认为是同一个群。

一个群到其自身的同态/同构称为自同态/自同构。

性质:

  1. 的一个同态,且这两个群的单位元分别为,那么

    证明:// TODO

#子群(subgroup)

定义:

对于群,若的一个非空子集且同时与的二元运算构成一个群,那么称的一个子群,群被称为该子群的母群,记为

性质:

  1. 对于每个群,一元群以及自身都是它的子群,这两个子群被称为平凡子群。

  2. 证明:只需证是一个群即可。

    1. 单位元:假设的单位元,那么令,则,因此的单位元为
    2. 逆元:令,则,因此中的每个元素都有逆元。
    3. 封闭性:即证。令(逆元存在性),则