上午就磨着rec，直到在实验室搬完砖后与rec成功结合为recain，被进行了一场启发式教学
题目
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
代码中的 \(dp = d\mod (p-1)\) 和 \(dq = d \mod (q-1)\)
dp，dq的实际意义：出现与RSA私钥文件中，加速RSA解密
大致思路\(dp,dq \rightarrow d \rightarrow pow(c,d,n)\)
第一步的推导根据中国剩余定理CRT进行
中国剩余定理Chinese Remainder Theorem
孙子定理
《孙子算经》其卷下的第26题为：
今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
答曰：‘二十三’。
术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三，七七数之剩二，置三十，并之。得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上以一百五减之即得。
看不懂？懂得都懂，不懂得我只能说可惜
即求满足以下条件的整数：除以3余2，除以5余3，除以7余2。
(顺便插一嘴rec提到的韩信点兵：韩信让士兵排队，站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。)
现代数学
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 \(m_1,m_2,...,m_n\) 两两互质)：
\[\left\{\begin{array} {c} x \equiv a_1 \pmod {m_1} \\\\ x \equiv a_2 \pmod {m_2} \\\\ \vdots \\\\ x \equiv a_n \pmod {m_n} \end{array} \right. \]上面的「物不知其数」和韩信点兵的问题都是一元线性同余方程组的一个实例。
CRT给出了有解的判定条件（模数两两互质），并用构造法给出了在有解情况下解的具体形式。
通解可以用如下方式构造得到：
-
令 \(M=m_1×m_2×\dots×m_n=\prod\limits_{i=1}^{n} m_i\) 是整数 \(m_1,m_2,…,m_n\) 的乘积，并有 \(M_i=\cfrac{M}{m_i},\forall i \in \{1,2,…,n\}\)，即 \(M_i\) 是除了 \(m_i\) 以为的 \(n-1\) 个整数的乘积。
-
设 \(M_i^{-1}\) 为 \(M_i\) 模 \(m_i\) 的数论倒数：\(M_i^{-1}\ M_i \equiv 1 \pmod {m_i},\forall i \in \{1,2,…,n\}\)。
-
通解为： \(x=a_1M_1^{-1}M_1+a_2M_2^{-1}M_2+\dots+a_nM_n^{-1}M_n+kM=kM+\sum\limits_{i=1}^{n}a_iM_i^{-1}M_i,\quad k\in \mathbb{Z}\)
在模 \(M\) 的意义下，方程组只有一个解：\(x=\sum\limits_{i=1}^{n}a_iM_i^{-1}M_i\)。
验证
中国剩余定理给出的解是通过巧妙构造得出的，我们来验证一下：
在 \(\mod M\) 的意义下，存在唯一解 \(x=\sum\limits_{i=1}^{n}a_iM_i^{-1}M_i\)
带入同余方程组其一可得 \(a_i = \sum\limits_{i=1}^{n}a_iM_i^{-1}M_i \mod m_n\)
分类讨论累加的每一项，发现
- 当 \(i \ne n\) 时，每一项 \(a_iM_i^{-1}M_i\) 中的 \(M_i = \cfrac{M}{m_i}\) 都含有因子 \(m_n\) ，即 \(a_iM_i^{-1}M_i \mod m_n = 0,i \ne n\)
- 当 \(i = n\) 时，\(a_nM_n^{-1}M_n\) 中的逆元对乘积为1，即 \(a_nM_n^{-1}M_n = a_n \mod m_n\)
题解
通过对题目的了解，我们可以构造如下的同余方程组
\[\left\{\begin{array} {c} d \equiv d_p \pmod {p-1}\\ d \equiv d_q \pmod {q-1} \end{array} \right. \]所以只需要使用CRT即可快速求出d
CRT([dp,dq],[(p-1),(q-1)])
\(p-1\) 和 \(q-1\) 不互素
rec：p,q是素数对吧，那么 \(p-1\) 和 \(q-1\) 一定是偶数，那么必定不互质
但为什么CRT出来的结果是正确的？
我们考虑将方程组变形：
\[\begin{array} 求解g = gcd[(p-1),(q-1)] \\遂有 p-1 = g\cdot k_p \ , q-1 = g \cdot k_q,\quad k\in \mathbb{Z} \\思考d \equiv d_p \pmod g是否成立 \\由dp = d \pmod {p-1}可得 \\dp \mod g = (d \mod {p-1}) \mod {g} = (d \mod {g \cdot k_q}) \mod g \\对于 (d \mod {g \cdot k_q}) \mod g 和 d \mod g 二式 \\因为{g \cdot k_q} 是 g 的正整数倍 ，所以两式相等 \\于是我们可以构造这样的同余方程组\left\{\begin{array} {s} d \equiv d_{p|d} \pmod {g} \\d \equiv dp \pmod {k_p} \\d \equiv dq \pmod {k_q} \end{array}\right. \\显然g,k_q,k_q满足两两互质 \end{array} \] 标签：剩余,pmod,定理,中国,array,mod,dq,dp,equiv From： https://www.cnblogs.com/cainyzb/p/18123959