Summary of RSA

标签：inverse Get Mi list RSA Summary mod

---

title: Number Theory in RSA
date: 2021-10-05 11:59:40
tags:

• Number Theory
• RSA
  categories:
• Crypto
  mathjax: true

---

CRT（Chinese remainder theory）

设正整数\(m_1,m_2,...,m_n\)两两互素，则同余方程组

\[\left\{ \begin{matrix} x \equiv a_1 (\mod m_1) \\ x \equiv a_2 (\mod m_2) \\ ... \\ x \equiv a_n (\mod m_n) \\ \end{matrix} \right. \]

有整数解。并且在模\(M=m_1*m_2*...*m_n\)下的解是唯一的，解为

\(x \equiv (a_1M_1M_1^-1 + a_2M_2M_2^-1 + ... + a_nM_nM_n^-1) \mod M\)

其中: \(M= \prod m_i\)

​ \(M_i = \frac{M}{m_i}\)

​ \(M_i^-1 = M_i \mod m_i\)

python代码实现如下：

# Chinese remainder theory
import gmpy2

#求解Mi
def Get_Mi(m_list,M):
    Mi_list = []
    for mi in m_list:
        Mi_list.append(M//mi)
    return Mi_list

# 求解Mi逆元
def Get_Mi_inverse(Mi_list,m_list):
    Mi_inverse = []
    for i in range(len(Mi_list)):
        Mi_inverse.append(gmpy2.invert(Mi_list[i],m_list[i]))
    return Mi_inverse

# 中国剩余定理
def CRT(m_list,a_list):
    """中国剩余定理"""
    M = 1
    for m in m_list:
        M *= m

    Mi_list = Get_Mi(m_list,M)
    Mi_inverse = Get_Mi_inverse(Mi_list,m_list)

    x = 0
    for i in range(len(Mi_list)):
        x += a_list[i]*Mi_list[i]*Mi_inverse[i]
    x = x % M
    return x

标签：inverse,Get,Mi,list,RSA,Summary,mod
From： https://www.cnblogs.com/J4m-OvO/p/16747026.html