初等数论--Garner‘s 算法

0. 介绍

主要通过混合积的表示来逐步求得同余方程的解。

对于同余方程
$$\begin{array}{c}\{\begin{array}{l}x\equiv v_0(\mathrm{mod}{m}_0)\\ x\equiv v_1(\mathrm{mod}{m}_1)\\ \cdots \\ x\equiv v_{k-1}(\mathrm{mod}{m}_{k-1})\end{array}\end{array}$$

满足
$\gcd (m_0,m_1,\cdots ,m_{k-1})=1$

1. 传统构造方法

$$\begin{gathered} M=\prod _{i=0}^{k-1}{m}_i \\ {b}_i=\frac{M}{m_i},b_i\times in{v}_i\equiv 1(\mathrm{mod}{m}_i) \\ x=\sum _{i=0}^{k-1}{v}_i\times b_i\times in{v}_i \end{gathered}$$

这样构造保证了$x$的存在性，但是在计算时$b_i$比较大。

下面是示例代码

template<typename T>
T exgcd(T a, T b, T &x, T &y)  {if ( b == 0) {x = 1;y = 0;return a;}T x_0;T y_0;T d = exgcd( b, a % b, x_0, y_0);x = y_0;y = x_0 - (a / b) * y_0;return d;
}ll CRT(int cnt, ll *a, ll *b) {ll pia = 1;ll res = 0;for (int i = 0;i < cnt; i++) {pia *= a[i];}for (int i = 0;i < cnt; i++) {ll m = pia / a[i];ll inv, tmp;exgcd( m, a[i], inv, tmp);inv = (inv % a[i] + a[i])% a[i];__int128 sb = m * inv  % pia * b[i] % pia;sb %= pia;res = (res + (ll) sb ) % pia;}return res;
}

2. Garner‘s算法

由中国剩余定理，我们知道必然存在$x<{\prod }_{i=0}^{k-1}{m}_i$满足上面的同余方程组。

$x$的混合积表示为
$$x=t_0+t_1{m}_0+\cdots +t_{k-1}\prod _{i=0}^{k-2}{m}_i$$
不断对$x$和${\prod }_{i=0}^s{m}_i$应用带余除数法可以证明$t_i$的唯一性。

代入第一同余方程得到
$$t_0\equiv v_0(\mathrm{mod}{m}_0)$$
取$t_0=v_0$, 将$x$代入第二个方程
$$\begin{gathered} t_0+t_1{m}_0\equiv v_1(\mathrm{mod}{m}_1) \\ {t}_1{m}_0\equiv v_1-t_0(\mathrm{mod}{m}_1) \\ {t}_1\equiv (v_1-t_0)m_0^{-1}(\mathrm{mod}{m}_1) \end{gathered}$$
我们令$X_j={\sum }_{s=0}^{j-1}{t}_s{\prod }_{a=0}^{s-1}{m}_a$，也就是$x$的混合积表示中的前$j$

项；此时求$x$相当于，求$X_k$。

在求$X_j$时，我们必然已经求得了$X_{j-1}$。

代入到第$j$个同余方程，可以得到

$$\begin{gathered} X_{j-1}+t_j(\prod _{s=0}^{j-1}{m}_s)\equiv v_j(\mathrm{mod}{m}_j) \\ {t}_j(\prod _{s=0}^{j-1}{m}_s)\equiv (v_j-X_{j-1})(\mathrm{mod}{m}_j) \\ {t}_j\equiv (v_j-X_{j-1})(\prod _{s=0}^{j-1}{m}_s{)}^{-1}(\mathrm{mod}{m}_j) \end{gathered}$$

因此我们可以递推的来求$x$。

在应用密码学手册中给出了算法描述。

主要的解释上面已经有了，唯一需要注意的是求$({\prod }_{i=0}^{j-1}{m}_i{)}^{-1}(\mathrm{mod}{m}_j)$。

运用了乘积的逆等于逆的乘积这一性质, 证明如下

$$(\prod _{i=0}^{j-1}{m}_i)\prod _{i=0}^{j-1}(m_i{)}^{-1}\equiv \prod _{i=0}^{j-1}{m}_i{m}_i^{-1}\equiv 1(\mathrm{mod}{m}_j)$$

代码

#include <iostream>
#include <vector>using ll = long long;static constexpr int MAXN = 1e5+10;ll a[MAXN];
ll b[MAXN];template<typename T>
T exgcd(T a, T b, T &x, T &y)  {if ( b == 0) {x = 1;y = 0;return a;}T x_0;T y_0;T d = exgcd( b, a % b, x_0, y_0);x = y_0;y = x_0 - (a / b) * y_0;return d;
}ll CRT_GARNER(int cnt, ll *m, ll *v)
{std::vector<ll> C(cnt, 1);for (int i = 1; i < cnt; i++) {for (int j = 0; j < i; ++j) {ll inv;ll tmp;exgcd(m[j], m[i], inv, tmp);// printf("inv of m[%d] mod m[%d]: %d\n", j, i, inv);while ( inv < 0)inv += m[i];C[ i ] = C[ i ] * inv % m[i];}}ll u = v[ 0 ];ll x = u;ll M = m[0];for (int i = 1;i < cnt; i++) {u = (v[i] - x) * C[i] % m[i];while (u < 0)u += m[ i ];x = x + u * M; M *= m[i];}return x;
}

举个例子
$$\begin{array}{c}\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}5)\\ x\equiv 2(\mathrm{mod}7)\end{array}\end{array}$$

将$x$表示为混积的形式
$x=t_0+2t_1+15t_2$

显然$t_0=2$；

代入到第二个同余方程
$$\begin{gathered} 2+3t_1\equiv 3(\mathrm{mod}5) \\ 3t_1\equiv 1(\mathrm{mod}5) \\ {t}_1\equiv 3^{-1}(\mathrm{mod}5) \end{gathered}$$
$3^{-1}(\mathrm{mod}5)$可由扩展欧几里得算法求得
$$\begin{gathered} 3\times 2-1\times 5=1 \\ {3}^{-1}(\mathrm{mod}5)=2 \end{gathered}$$
因此$t_2=2$。

代入第三个同余方程

$$\begin{gathered} 2+3\times 2+15t_2=8+15t_2 \\ 15t_2+8\equiv 2(\mathrm{mod}7) \\ 15t_2\equiv 1(\mathrm{mod}7) \\ {t}_2\equiv 15^{-1}(\mathrm{mod}7) \end{gathered}$$
同样是利用扩展欧几里得求出逆元
$$t_2\equiv 1(\mathrm{mod}7)$$

代入到混合积形式
$$x=8+15=23$$

参考

oi-wiki-crt
handbook-of-applied-crypho