Докажите правильность RSA для $GCD(m_i,n)=1$ и $GCD(m_i,n) \neq1$

Как сделать доказательство правильности формулы шифрования и дешифрования RSA для $GCD(m_i,n)=1$ и $НОД(m_i,n) \neq1$ где шифрование определяется как $c_i = m_{i}^e$ мод н и расшифровка $m_i = c_{i}^d$ мод н.

Итак, спасибо @poncho за советы, я написал следующее доказательство:

Напомним, что целые числа $е > 0$ и $к > 0$ выбираются так, что $ ed = 1 + k(p = 1)(q = 1)$

Достаточно показать, что два сравнения

$(m^e)^d \equiv m\textrm{mod}\ p $ и $(m^e)^d \equiv m\textrm{mod}\q $ держать. p и q — различные простые числа, поэтому $gcd(p,q) = 1$ а из приведенных выше сравнений следует, что

$(m^e)^d \equiv m\textrm{mod}\n $ по китайской теореме об остатках. Если $m \equiv 0\textrm{mod}\ p $, то конечно $(m^e)^d \equiv m\textrm{mod}\ p $. Если $m \not\equiv 0\ \textrm{mod}\ p $, тогда $m^{p-1} \equiv 1\textrm{mod}\ p $ из-за малой теоремы Ферма ($a^{p-1} \equiv 1\textrm{mod}\ p $) следовательно,

$$ (m^e)^d \equiv m^{1 + k(p - 1)(q - 1)} \equiv m(m^{p-1})^{k(q-1)} \ эквивалент m 1^{k(q-1)} \equiv m\ \textrm{mod}\ p $$

Следовательно $(m^e)^d \equiv m\textrm{mod}\ p $ выполняется для всех целых чисел m. Замена p на q в предыдущем аргументе показывает, что $m \equiv (m^e)^d \textrm{mod}\ q $ выполняется для всех целых чисел m

Любые комментарии о правильности моего доказательства приветствуются!

Это, очевидно, проблема с домашним заданием, поэтому я только дам подсказку:

• Можете ли вы доказать это по модулю $р$ (куда $р$ является одним из главных факторов $n$)? То есть вы можете доказать, что $(m^e \bmod p)^d \bmod p \equiv m \pmod p$, для любой $м$?

• Одобрит ли это же доказательство по модулю $q$?

• Учитывая два приведенных выше, как вы можете показать, что это применимо по модулю $p \cdot q = n$?