密碼學(xué) 中國剩余定理

簡介

中國剩余定理(Chinese remainder theorem, CRT)一般指孫子定理

孫子定理是中國古代求解一次同余式組（見同余）的方法。是數(shù)論中一個(gè)重要定理。又稱中國余數(shù)定理。一元線性同余方程組問題最早可見于中國南北朝時(shí)期（公元5世紀(jì)）的數(shù)學(xué)著作《孫子算經(jīng)》卷下第二十六題，叫做“物不知數(shù)”問題，原文如下：

有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？即，一個(gè)整數(shù)除以三余二，除以五余三，除以七余二，求這個(gè)整數(shù)。

《孫子算經(jīng)》中首次提到了同余方程組問題，以及以上具體問題的解法，因此在中文數(shù)學(xué)文獻(xiàn)中也會(huì)將中國剩余定理稱為孫子定理。

(S): ?x≡a1(mod m1) ?x≡a2(mod m2) ?? ?? ?x≡an(mod mn) ?

有解的判定條件，并用構(gòu)造法給出了在有解情況下解的具體形式。

中國剩余定理說明：假設(shè)整數(shù)m1,m2,...,mn 其中任兩數(shù)互質(zhì)，則對(duì)任意的整數(shù)：a1,a2,...,an，方程組(S)有解

實(shí)現(xiàn)

from functools import reduce
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod

 

 

 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1


if __name__ == '__main__':
   n = [3, 5, 7]
   a = [2, 3, 2]
   print(chinese_remainder(n, a))

運(yùn)行結(jié)果為23.