模逆

• 定义

  对于一个数 $a$，他在模 $n$ 域下存在一个数 $b$，使得 $(a\times b)\mod n=1$，则称 $b$ 为 $a$ 在模 $n$ 域下的模逆元，即 $a^{-1}=b$

• 条件

  $a$ 与 $n$ 必须互质，即最大公约数为 $1$。

• 求法（python）

  b = gmpy2.invert(a, n)

模运算法则

1. $(a + b) \mod p = (a \mod p + b \mod p) \mod p$

2. $(a \times b) \mod p = (a \mod p \times b \mod p) \mod p$

3. $(a - b) \mod p = (a \mod p - b \mod p ) \mod p$

4. $((a +b)\mod p \times c) \mod p = ((a \times c) \mod p + (b \times c) \mod p) \mod p$

5. $a^b \mod p = (a \mod p)^b \mod p$

6. 若 $a\equiv b \pmod p$，则对于任意的 $c$，都有 $(a + c) \equiv (b + c) \pmod p$

7. 若 $a\equiv b \pmod p$，则对于任意的正整数 $c$，都有 $(a \times c) \equiv (b \times c) \pmod p$

欧几里得算法

• 定义

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

• 求解方法

  求 $10,25$ 的最大公约数

  $25 \div 10 = 2 \implies 5$

  $10 \div 5 = 2 \implies 0$

  所以 $10,25$ 的最大公约数为 $5$ 。

• 公式

  $\gcd(a,b)=\gcd(b,a \mod b)$

欧拉函数

• 定义

  对于正整数 $n$，欧拉函数 $\varphi(n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。此函数又称为 $\varphi$ 函数。

• 计算方法

  $n=p_1^{k_1}\times p_2^{k_2} \times p_3^{k_3}\times\cdots\times p_n^{k_n}$

  \varphi(n)=\prod_\limits{i=1}^r p_i^{k_i-1}(p_i-1)=\varphi(n)=\prod_\limits{p|n} p^{\alpha_p-1}(p-1)=n\prod_\limits{p|n}(1-\frac1p)

  $\varphi(72)=\varphi(2^3 \times 3^2)= 2^{(3-1)}\times (2-1) \cdot 3^{(2-1)} \times (3-1)=72\times(1-\frac12)\times(1-\frac13)=24$

欧拉定理

• 定义

  设 $m,n$ 为正整数且 $\gcd(a,n)=1$ ，则我们有：$a^{\varphi{(n)}}\equiv1\pmod n$

两个推理

首先在 $1$ 到 $n$ 的数中，与 $n$ 互质的一共有 $\varphi(n)$ 个，所以我们把这 $\varphi(n)$ 个数拿出来，放到设出的集合 $X$ 中，即 $x_1,x_2,\cdots,x_{\varphi(n)}$ ，那么接下来，我们可以再设出一个集合为 $M$，设 $M$ 中的数为：$m_1 = a \times x_1,m_2 = a \times x_2,m_{\varphi(n)}=a \times x_{\varphi(n)}$

1. $M$ 中任意两个数都不模 $n$ 同余

2. $M$ 中的数除以 $n$ 的余数全部与 $n$ 互质

• 命题一证明如下：

  假设 $M$ 中存在两个数设为 $m_a, m_b$ 模 $n$ 同余。即 $m_a \mod n \equiv m_b \mod n$

  移项得到：$m_a - m_b = n \times k$

  再将 $m$ 用 $x$ 来表示得到：$a \times(x_a -x_b) = n \times k$

  我们现在已知 $a$ 与 $n$ 互质，那么式子就可以转化为：$x_a - x_b \equiv 0 \pmod 0$

  因为 $a$ 中没有与 $n$ 的公因子（$1$ 除外）所以 $a \not\equiv 0 \pmod n$

  所以只能是 $x_a - x_b \equiv 0 \pmod n$

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

  所以证得 $m$ 中任意两个数都不模 $n$ 同余。

• 命题二证明如下：

  已知：$m_i = a \times x_i$

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

  即 $\gcd(m_i , n)=\gcd(n , m_i \mod n)$

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

  得到 $m_1 \times m_2 \times\cdots\times m_{\varphi(n)}\equiv x_1 \times x_2 \times\cdots\times x_{\varphi(n)} \mod n$

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

  $a \times x_1 \times a \times x_2\times\cdots\times a\times x_{φ(n)}\equiv x_1 \times x_2 \times\cdots\times x_{\varphi{(n)}}\mod n$

  $a^{\varphi(n)}\times(x_1 \times x_2 \times\cdots\times x_{\varphi(n)})\equiv x_1 \times x_2 \times\cdots\times x_{φ(n)} \mod n$

  $(a^{\varphi(n)}-1)\times(x_1 \times x_2 \times\cdots\times x_{φ(n)}) \equiv0 \mod n$

  然后由于 $x_1 \times x_2 \times\cdots\times x_{φ(n)}\not\equiv0 \mod n$

  所以 $a^{φ(n)}\equiv1 \mod n$

费马大定理

当整数 $n>2$ 时，关于 $x^n + y^n = z^n$ 的方程没有正整数解。

费马小定理

• 定义

  如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数，则有 $a^{p-1}\equiv1\pmod p$

• 计算方法

  $2^{100} \mod 13$

  $\equiv2^{12\times8+4} \mod 13$

  $\equiv2^{(13-1)\times8+4} \mod 13$

  $\equiv (2^{(13-1)}) ^ 8 \times 2^4 \mod 13$

  $\equiv1^8 \times 2^4 \mod 13$

  $\equiv 16 \mod 13$

  $\equiv3 \mod 13$

中国剩余定理

• 背景

  计算一个整数 $x$，使得它满足除以 $3$ 余 $2$、除以 $5$ 余 $3$、除以 $7$ 余 $2$。

  如果能够找到三个整数 $x_1,x_2,x_3$，使得：

  $x_1$ 除以 $3$ 余 $2$、除以 $5$ 余 $0$、除以 $7$ 余 $0$；

  $x_2$ 除以 $3$ 余 $0$、除以 $5$ 余 $3$、除以 $7$ 余 $0$；

  $x_3$ 除以 $3$ 余 $0$、除以 $5$余 $0$、除以 $7$ 余 $2$；

  那么容易验证 $x = x_1+x_2+x_3$ 就满足除以 $3$ 余 $2$、除以 $5$ 余 $3$、除以 $7$ 余 $2$。

• 思路

  $x_1$ 除以 $3$ 余 $2$、除以 $5$ 余 $0$、除以 $7$ 余 $0$

  如果能够找到一个整数 $y$ 满足 $y$ 除以 $3$ 余 $1$、除以 $5$ 余 $0$、除以 $7$ 余 $0$，那么令 $x1=2\times y$，就很容易验证这时的 $x_1$ 就满足除以 $3$ 余 $2$、除以 $5$ 余 $0$、除以 $7$ 余 $0$。

  因此又可以将问题转化为寻找整数 $y$ 满足 $y$ 除以 $3$ 余 $1$、除以 $5$ 余 $0$、除以 $7$ 余 $0$；

  由条件可以得到 $y$ 既是 $5$ 的倍数，又是 $7$ 的倍数，故设 $y = 35k$

  然后根据除以 $3$ 余 $1$ 可以得到：$35K \equiv 1 \mod 3$

  $K$ 即为 $35$ 在模 $3$ 域下的逆元，即 $\texttt{invert(35,3)}$。

  所以我们能求出 $y$，也能求出 $x_1$，同理能求出 $x_2,x_3$，相加求出 $x$。

  $x_1 = 2 \times (35 \times \texttt{invert(35,3)})$

威尔逊定理

• 定义

  当且仅当 $p$ 为素数时有，$(p-1)\not\equiv-1\pmod p$

离散对数问题

• 背景

  已知 $p,g,h$，求满足条件的 $x$。

  $g^x\equiv h \mod p$

• 方法

  暴力破解，直接穷举x，得到 $g^x≡h \mod p$ 的值

  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()   # 检测偶数