一个好用的乘法逆元扩展结论
tags: ctf,writeup,crypto
一个好用的乘法逆元扩展结论
比赛中遇到的一个好用的定理，不知道有没有名字，记录一下
$$ \begin{align} & p^{-1} \cdot p \equiv 1 \mod q \newline & q^{-1} \cdot q \equiv 1 \mod p \newline & \Longleftrightarrow \newline & p^{-1}\cdot p+q^{-1}\cdot q \equiv 1 \mod p\cdot q \end{align} $$
1. 证明
(1)
$$
\begin{align}
& 1 \equiv p^{-1} \cdot p \mod q \
& 1 \equiv q^{-1} \cdot q \mod p
\end{align}
$$
由中国剩余定理： $$ \begin{align} 1 & = \sum^{k}_{i=1}a_ic_i \mod p\cdot q \newline & =1\cdot q\cdot q^{-1} + 1\cdot p\cdot p^{-1} \mod p\cdot q \newline & =q\cdot q^{-1} + p\cdot p^{-1} \mod p\cdot q \end{align} $$
(2)
$$ \begin{align} & C_p\cdot p + C_q \cdot q \equiv 1 \mod p\cdot q \newline & \Longrightarrow \newline \end{align} $$
$$
\begin{equation}
\left\lbrace
\begin{array}{lr}
C_p\cdot p \equiv 1 \mod p & \newline
C_q\cdot q \equiv 1 \mod q &
\end{array}
\right.
\end{equation}
$$
2. 特别地
当满足以下条件 $$ \begin{align} & p^{-1} = p^{-1} \mod q \tag{1} \newline & q^{-1} = q^{-1} \mod p \tag{2} \newline \end{align} $$
存在等式： $$ \begin{align} p^{-1}\cdot p + q^{-1}\cdot q = 1 + p\cdot q \end{align} $$
(1) 证明如下：
由(1)(2)式，可以确定 $$ \begin{align} & p^{-1} < q \tag{3} \newline & q^{-1} < p \tag{4} \newline & \Longrightarrow \newline & 1 < p^{-1}\cdot p+q^{-1}\cdot q < 2p\cdot q \newline & \Longrightarrow \newline & p^{-1}\cdot p + q^{-1}\cdot q = 1 + p\cdot q \end{align} $$
(2) 其他结论
由(1)(2)式，可以确定 $$ \begin{align} & p^{-1}\cdot p -1 =w_1\cdot q \newline & q^{-1}\cdot q -1 =w_2\cdot q \end{align} $$
两式左右相乘： $$ \begin{align} & (p^{-1}\cdot p -1)(q^{-1}\cdot q -1) =w_1\cdot w_2\cdot p\cdot q \newline & \Longrightarrow \newline & p^{-1}\cdot p\cdot q^{-1}\cdot q-p^{-1}\cdot p -q^{-1}\cdot q +1 =w_1\cdot w_2\cdot p\cdot q \newline & \Longrightarrow \newline & p\cdot q \cdot(p^{-1}\cdot q^{-1}-w_1\cdot w_2)=p\cdot p^{-1}+q\cdot q^{-1}-1 < 2p\cdot q \newline & \Longrightarrow \newline & p^{-1}\cdot q^{-1}-w_1\cdot w_2 = 1 \end{align} $$