中国剩余定理

孙子定理， Chinese remainder theorem(CRT)

参考 ： 百度百科-中国剩余定理

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

x=2mod3
x=3mod5
x=2mod7
// 求解得: x = 23 

模算术和数论有相关算法可以解决这个问题，参考资料：《密码学原理与实践第三版》5.2章节 更多数论知识

1. Euclidean欧几里得算法

Euclidean算法的基本形式，可以给出两个正整数a、b的最大公因子Greatest Common Divisor(GCD)。

举例计算 ：$gcd(99，63)$
$99=1\cdot 63+36$
$63=1\cdot 36+27$
$36=1\cdot 27+9$
$27=3\cdot 9+0$
$gcd(99,63)=(63,36)=(36,27)=(27,9)=9$

2. 扩展欧几里得算法，求模乘逆：$b^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}a)$

1. 是否存在整数s，t，使得$sa+tb=(a,b)$？
   如果存在， 且$(a,b)=1$，则有 $sa+tb=1$
   两边模a之后，得到$tb\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}a)$，即
   $$t=b^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}a)$$

2. 书上例5.1计算$28^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}75)$，如何计算s、t?
   定义 $t_j=\{\begin{array}{ll}0,& \text{if }j=0;\\ 1,& \text{if }j=1;\\ t_{j-2}-q_{i-1}{t}_{j-1},& \text{if }j\ge 2;\end{array}$

   定义 $s_j=\{\begin{array}{ll}1,& \text{if }j=0;\\ 0,& \text{if }j=1;\\ s_{j-2}-q_{i-1}{s}_{j-1},& \text{if }j\ge 2;\end{array}$
   

3. 书上模乘逆算法
   

4. Js版本模乘逆算法

题目：利用求逆算法，计算$1047298^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}15484863)=6926637$

function MultiplicativeInverse(a, b) {
    let a0 = a
    let b0 = b
    let t0 = 0
    let t = 1
    let q = Math.floor(a0 / b0)
    let r = a0 - q * b0
    let j = 0
    // console.log("j", "rj", "qj", "tj")
    // console.log(j, a0, "-", t0)
    let qtemp = q

    while (r > 0) {
        const temp = (t0 - q * t) % a
        t0 = t
        t = temp
        a0 = b0
        b0 = r
        q = Math.floor(a0 / b0)
        r = a0 - q * b0
        j++
        console.log(j, a0, qtemp, t0)
        qtemp = q
    }

    if (b0 !== 1) {
        return false
    } else {
        console.log(j + 1, b0, a0, t)
        return t
    }
}

5. 测试结果

console.log(MultiplicativeInverse(75, 28))
j rj qj tj
0 75 - 0
1 28 2 1
2 19 1 -2
3 9 2 3
4 1 9 -8
-8
console.log(MultiplicativeInverse(15485863, 104729))
j rj qj tj
0 15485863 - 0
1 104729 147 1
2 90700 1 -147
3 14029 6 148
4 6526 2 -1035
5 977 6 2218
6 664 1 -14343
7 313 2 16561
8 38 8 -47465
9 9 4 396281
10 2 4 -1632589
11 1 2 6926637
6926637

3. 求解同余方程组

中国剩余定理，是求解以下的一元线性同余方程组的过程：

$x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$
$x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)$
$⋮$
$x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$

中国剩余定理断言这个方程组有模$M=m_1\times m_2\times ...\times m_r$的唯一解， 其解为：
$$x=\sum _{i=1}^r{a}_i{M}_i{y}_i(\mathrm{m}\mathrm{o}\mathrm{d}M)$$
其中$M_i=M/m_i，y_i=m_i^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i),1\le i\le r$

现在求解：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

1. $M=3\ast 5\ast 7=105,M_1=5\ast 7=35,M_2=3\ast 7=21,M_3=3\ast 5=15$
2. $y_1=M_1逆模m_1=35逆模3=2,y_2=21逆模5=1,y_3=15逆模7=1$
3. $x=(a_1{M}_1{y}_1+a_2{M}_2{y}_2+a_3{M}_3{y}_3)modM=(2\ast 35\ast 2+3\ast 21\ast 1+2\ast 15\ast 1)(\mathrm{m}\mathrm{o}\mathrm{d}105)=23$

JS算法：

// 输入：[[2,3],[3,5],[2,7]]
function CRT(array) {
    let x = 0,
        M = 1
    for (let i = 0; i < array.length; i++) {
        const element = array[i]; // [2,3]
        M = M * element[1]
    }
    for (let i = 0; i < array.length; i++) {
        const element = array[i]; // [2,3]
        let Mi = M / element[1]
        let yi = MultiplicativeInverse(element[1], Mi)
        if (yi < 0) {
            yi = element[1] + yi
        }
        console.log(element[0], Mi, yi)
        x = x + element[0] * Mi * yi
    }
    console.log(x + "mod" + M + "=" + x % M)
    return x % M
}

书上习题5.6：求解同余方程组
$\{\begin{array}{l}x\equiv 12(\mathrm{m}\mathrm{o}\mathrm{d}25),\\ x\equiv 9(\mathrm{m}\mathrm{o}\mathrm{d}26),\\ x\equiv 23(\mathrm{m}\mathrm{o}\mathrm{d}27),\end{array}$

答案：14387。 测试结果：

console.log(CRT([
    [2, 3],
    [3, 5],
    [2, 7]
]))
result: 
2 35 2
3 21 1
2 15 1
233mod105=23
23

console.log(CRT([
    [12, 25],
    [9, 26],
    [23, 27]
]))
result:
12 702 13
9 675 25
23 650 14
470687mod17550=14387
14387

——End——