基础数论的一些知识

算法数学

一些基本数论相关的知识。

逆元(inverse)

若 $b$ 是 $a$关于 $m$ 的逆元则有：$ ab \equiv 1 \pmod m $，即 $ (ab) \bmod m = 1 $。

应用

求解 $ (a/b) \bmod m $：

设 $c$ 为 $b$ 关于 $m$ 的逆元，即有： $ (bc) \bmod m = 1 $ 。

那么 $ (a/b) \bmod m = (a/b*1) \bmod m = ((a/b) * (bc)) \bmod m = (a*c) \bmod m $

即：$a$ 除以 $b$ 取模等价于 $a$ 乘以 $b$ 的逆元取模。

求解

扩展欧几里得

若 $b$ 是 $a$ 关于 $m$ 的逆元则有：$ ab \equiv 1 \pmod m $。

等价于存在 k 使得 $ k*m + 1 = ab $，即求解 $ km - ab = 1 $ 中的 $b$，由于 a 和 m 已知，可将 b 和 k 看成未知数，问题转化为求解线性方程：$ mx - ay = 1 $，可以使用扩展欧几里得算法( exgcd )求解。

同时我们通过扩展欧几里得算法的限制知道：若 a 和 m 不互质（$\gcd (a, m) \neq 1$），则不存在 a 关于 m 的逆元。

ll extend_gcd(ll a, ll b, ll &x, ll &y) 
{
    if (b == 0) 
    {
        x = 1, y = 0;
        return a;
    }
    else 
    {
        ll r = extend_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}

ll inv(ll a, ll n) 
{
    ll x, y;
    extend_gcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}

费马小定理

由费马小定理可知：$ x^{p-1} \equiv 1 \pmod p $，则有：$ x * x ^{p-2} \equiv 1 \pmod p $。

即 x 的逆元是 $x^{p-2}$。

注意 x 和 p 必须互质。

const int mod = 1000000009;
long long quickpow(long long a, long long b) 
{
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) 
    {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
long long inv(long long a) 
{
    return quickpow(a, mod - 2);
}

线性逆元筛

const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;

求阶乘的逆元

const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;

快速求组合数

如果需要快速求出模 $P$ 意义下的 $ C_{n}^{m} $ ($n,m < N$)，可以先线性复杂度求出 $1$ 到 $ n $ 阶乘的逆元，然后套用组合数公式即可求出

$$ C_{n}^{m} \% P = inv[fact(n)] * inv[fact(m)] * inv[fact[n-m]] $$

欧拉定理

欧拉函数

$\phi(n)$表示小于等于 $ n $ 的正整数之中，有多少个与$n$构成互质关系。

分类讨论

n = 1，则$\phi(n) = 1$
n 为质数，则$ \phi(n) = n - 1 $
n 为质数的某个幂，即$ n = p ^ k $(p为质数)，则$ \phi(n) = p^k - p^{k-1} $
n 为两个互质的整数之积，即 $ n = p_1 \times p_2 $ ，则$ \phi(n) = \phi(p_1p_2) = \phi(p_1) \phi(p_2)$
n 分解为若干个质数的幂，即 $ n = p_1^{c1} p_2^{c2} p_3^{c3}…p_n^{cn} $，则根据4可知 $\phi(n) = n(1-\frac{1}{p1})(1-\frac{1}{p2})(1-\frac{1}{p3})…(1-\frac{1}{pr})$

欧拉定理

如果两个正整数a，n互质，则n的欧拉函数满足以下等式：

$$a^{\phi(n)} \equiv 1 \pmod n$$

费马小定理

如果a和质数p互质，因为$\phi(p) = p - 1$，则有

$$ a^{p-1} \equiv 1 \pmod p $$

RSA

秘钥生成过程

随机选择两个不相等的质数p和q
计算p和q的乘积n，n的二进制位数被称为秘钥的长度
计算n的欧拉函数$\phi(n) = (p-1)(q-1)$
随机选择整数e，$1 < e < \phi(n)$，且e与$\phi(n)$互质
计算e对于$\phi(n)$的逆元d，即$ed \equiv 1 \pmod {\phi(n)}$
其中公钥为(n, e)，私钥为(n, d)

加密与解密过程

对于小于n的整数m，加密为：

$ c = m^e \mod n$

m为需要加密的信息，e为公钥，c为加密后的密文。

$ m = c^d \mod n $

d为私钥。

Miller-Rabin 素性检测

Miller-Rabin 算法是一种判断一个数是否为质数的算法。

算法主要基于两个事实

费马小定理，即对于任意质数p以及 $p\nmid a$ ，有 $a^{p-1}\equiv 1(\bmod p)$
对于质数 $p$ ，$x^2\equiv 1(\bmod p)$ 有且只有平凡解 $x\equiv \pm 1(\bmod p)$

算法的伪代码如下

Input #1: n > 3, an odd integer to be tested for primality;
Input #2: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as (2^r)·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← (a^d) mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      x ← (x^2) mod n
      if x = 1 then
         return composite
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

可以证明，上述代码的正确率至少为 $1-2^{-k}$，即尝试的次数 $k$ 越多，出错概率越小（出错概率即把合数误判成质数的概率）。

多项式

快速傅里叶变换(FFT)

欧拉公式：$ e^{i\theta} = \cos \theta + i \sin \theta $