CTF 中的密码学之数论

叔叔我啊

CTFCrypto

发布于：2021年10月20日

字数：1.1k字

时长：3分钟

次浏览

模逆

定义

对于一个数，他在模域下存在一个数，使得，则称为在模域下的模逆元，即
条件

与必须互质，即最大公约数为。
求法（python）
```
b = gmpy2.invert(a, n)
```

模运算法则

若，则对于任意的，都有
若，则对于任意的正整数，都有

欧几里得算法

定义

辗转相除法，是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。缩写为gcd
求解方法

求的最大公约数

所以的最大公约数为。
公式

欧拉函数

定义

对于正整数，欧拉函数是小于或等于的正整数中与互质的数的数目。此函数又称为函数。
计算方法

欧拉定理

定义

设为正整数且，则我们有：

两个推理

首先在到的数中，与互质的一共有个，所以我们把这个数拿出来，放到设出的集合中，即，那么接下来，我们可以再设出一个集合为，设中的数为：

中任意两个数都不模同余
中的数除以的余数全部与互质

命题一证明如下：

假设中存在两个数设为模同余。即

移项得到：

再将用来表示得到：

我们现在已知与互质，那么式子就可以转化为：

因为中没有与的公因子（除外）所以

所以只能是

又因为都是小于的并且不会相同，那么上述的式子自然全都不成立。

所以证得中任意两个数都不模同余。
命题二证明如下：

已知：

又因为与互质，与互质，所以可以得到与互质。带入欧几里得算法中推一步就好了。

即

首先，根据前面两个推论可以知道，中的数分别对应中的每个数模同余。

得到

现在我们把替换成的形式，就可以得到：

然后由于

所以

费马大定理

当整数时，关于的方程没有正整数解。

费马小定理

定义

如果是一个质数，而整数不是的倍数，则有
计算方法

中国剩余定理

背景

计算一个整数，使得它满足除以余、除以余、除以余。

如果能够找到三个整数，使得：

除以余、除以余、除以余；

除以余、除以余、除以余；

除以余、除以余、除以余；

那么容易验证就满足除以余、除以余、除以余。
思路

除以余、除以余、除以余

如果能够找到一个整数满足除以余、除以余、除以余，那么令，就很容易验证这时的就满足除以余、除以余、除以余。

因此又可以将问题转化为寻找整数满足除以余、除以余、除以余；

由条件可以得到既是的倍数，又是的倍数，故设

然后根据除以余可以得到：

即为在模域下的逆元，即。

所以我们能求出，也能求出，同理能求出，相加求出。

威尔逊定理

定义

当且仅当为素数时有，

离散对数问题

背景

已知，求满足条件的。

方法

暴力破解，直接穷举x，得到的值

Sage：

c = m^x mod n
x = discrete_log(c.mod(m, n))

Python:

x = sympy.discrete_log(p, h, g)

gmpy2 库

gmpy2.mpz  # 类似long类型 长度可达50位
gmpy2.mpq  # 分数类型
gmpy2.mpfr # 与float类型相同，精度可达53位
gmpy2.mpc  # 复数类型

gmpy2.iroot(a, b)     # 返回一个元组 (x, y)，其中 x 为 a 开 b 次方的值，y 是判断 x 是否为整数的布尔型变量(即是否能够完整开放)
gmpy2.gcd(a, b)       # 求a和b的最大公约数
gmpy2.lcm(a, b)       # 求a和b的最小公倍数
gmpy2.gcdext(a, b)    # ax + by = gcd(a,b) 求满足贝祖不等式的整数解
gmpy2.powmod(a, n, p) # a^n mod p

gmpy2.is_prime() # 检测素数
gmpy2.is_even()  # 检测奇数
gmpy2.is_odd()   # 检测偶数