基础数论的一些知识

6 years ago 算法数学

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

逆元(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$