当前位置：首页 > news >正文

信息安全数学基础-第一章学习笔记

news 2026/7/3 9:59:28

1、如何判定整数为素数

应用定理1.1.7和欧几里得除法

举例：

2、a和b的最大公因数（a,b）

设p是一个素数，a为整数.如果pXa,则p与a互素.

a,b的最大公因数等于b，c的最大公因数

3、广义欧几里得除法

最大公因数为最后一个非0余数。

举例：

4、贝祖等式s a+t b=(a,b)

构造公私钥对时使用

举例

RSA密码中，n=p q , p=q取2的1024次方或者2的2048次方

公钥 e (e,(p-1)(q-1))=1

私钥d e d=1 mod(p-1)(q-1)

e d+t(p-1)(q-1)=1

将e看成a，d看成s，(p-1)(q-1)看成b

欧几里得除法用矩阵表达

数学好难呀~~~~~

5、最大公因数进一步的性质

总结

1. 最大公因数的运算性质有哪些？

设 a,b,c 为整数，且 a,b 不全为 0，记 gcd(a,b) 为 a,b 的最大公因数，其核心运算性质如下：

基本性质
- gcd(a,b)=gcd(b,a)（交换律）
- gcd(a,b)=gcd(∣a∣,∣b∣)
- gcd(a,0)=∣a∣
- gcd(a,1)=1
线性组合性质（贝祖定理）gcd(a,b) 是 a,b 的线性组合中最小的正整数，即存在整数 s,t，使得： s⋅a+t⋅b=gcd(a,b)
整除传递性
- 若 d∣a 且 d∣b，则 d∣gcd(a,b)
- 若 d∣gcd(a,b)，则 d∣a 且 d∣b
带余除法性质（欧几里得算法基础）若 a=bq+r，则 gcd(a,b)=gcd(b,r)
与倍数的关系
- gcd(ka,kb)=∣k∣⋅gcd(a,b)（k 为非零整数）
- gcd(a,b)=gcd(a,a+b)=gcd(a,a−b)
互素相关性质
- 若 gcd(a,b)=1，则称 a,b 互素
- 若 gcd(a,b)=1 且 a∣bc，则 a∣c
- 若 gcd(a,b)=1，则 gcd(a,bc)=gcd(a,c)

2. 多个整数的最大公因数的计算

设整数 a1,a2,…,an 不全为 0，其最大公因数 gcd(a1,a2,…,an) 的计算方法为迭代法： gcd(a1,a2,…,an)=gcd(gcd(a1,a2),a3,…,an) 即：先算前两个数的最大公因数，再将结果与第三个数求最大公因数，依次迭代，直到所有数都参与计算。

例子：计算 gcd(12,18,30) gcd(12,18)gcd(6,30)=6=6 所以 gcd(12,18,30)=6。

3. 多个整数的最大公因数的数学表述

定义表述设 a1,a2,…,an 是不全为 0 的整数，称整数 d 是它们的最大公因数，如果：
- d∣ai 对所有 i=1,2,…,n 成立（即 d 是所有数的公因数）
- 若 d′ 是 a1,a2,…,an 的任意一个公因数，则 d′∣d（即 d 是公因数中最大的）
贝祖定理推广存在整数 k1,k2,…,kn，使得： k1a1+k2a2+⋯+knan=gcd(a1,a2,…,an)

4. 设 a,b,c=0 是三个整数，若 c∣a⋅b，则一定有 c∣a 或 c∣b 吗？

不一定。

反例：取 a=2，b=3，c=6

a⋅b=6，显然 6∣6，即 c∣a⋅b
但 6∤2 且 6∤3，即 c 既不整除 a 也不整除 b

原因：c 可以分解为两个分别整除 a 和 b 的因子的乘积，这些因子的公共部分导致 c 本身不整除其中任何一个。

5. 设 p 是素数，若 p∣a⋅b，则一定有 p∣a 或 p∣b 吗？

一定成立。

这是素数的基本性质（欧几里得引理），证明如下：设 p 是素数，p∣ab。若 p∤a，则 gcd(p,a)=1（因为素数的正因数只有 1 和它本身）。根据互素性质：若 gcd(p,a)=1 且 p∣ab，则 p∣b。因此 p∣a 或 p∣b 必有一个成立。

6. 设 a,b,c 是三个非零整数，若 a∣c 且 b∣c，则一定有 a⋅b∣c 吗？

不一定。

反例：取 a=2，b=4，c=8

2∣8，4∣8，即 a∣c 且 b∣c
但 a⋅b=8，8∣8 成立，我们换一个更典型的反例：取 a=2，b=4，c=4
- 2∣4，4∣4
- 但 a⋅b=8，8∤4

本质原因：a,b 可能不互素，它们的乘积会重复包含公共因子，导致乘积大于 c，或 c 只包含了公共因子的一次幂，无法被乘积整除。正确的结论是：lcm(a,b)∣c（a,b 的最小公倍数整除 c），而 ab=gcd(a,b)⋅lcm(a,b)，只有当 gcd(a,b)=1 时，ab=lcm(a,b)，此时才有 ab∣c。

7. 如何编程计算整数 a,b 的最小公倍数 [a,b]？

最小公倍数（LCM）的核心公式是： lcm(a,b)=gcd(a,b)∣a⋅b∣ 因此编程的关键是先求最大公因数（GCD），再用公式计算 LCM。

示例（Python 代码）：

python运行

def gcd(a, b): # 欧几里得算法求最大公因数 while b != 0: a, b = b, a % b return abs(a) def lcm(a, b): if a == 0 or b == 0: return 0 # 0没有最小公倍数，按需求处理 return abs(a * b) // gcd(a, b) # 测试 print(lcm(12, 18)) # 输出：36