Для данного $n>1$, пусть целое $f>0$ быть таким, чтобы для всех $м$ в $[0,n)$ с $\gcd(m,n)\ne1$ это держит $m^f\bmod n=1$. Одно такое целое число $f$ это Эйлер тотиент из $n$, $\operatorname{фи}(п)$ он же $\varphi(n)$, $\Фи(п)$ или же $\фи(п)$. Среди множества теорем Эйлера, скорее всего, речь идет об этом свойстве эйлерова тотиента. Самый маленький такой $f$ является $\лямбда(п)$, куда $\лямбда$ это Функция Кармайкла.
Предполагать $е$ и $д$ были выбраны так, что $e\cdot d\bmod f=1$. По определению¹ того, что оператор$\bmod$ это когда слева нет открывающей скобки, это означает: существует целое число $к$ такой, что $e\cdot d=k\cdot f+1$ (и $0\le1<f$, который стоит).
Теперь, предполагая $\gcd(m,n)=1$,
$$\begin{выравнивание}
\left(m^e\right)^d\bmod n&=m^{e\cdot d}&\bmod n\
&=m^{k\cdot f+1}&\bmod n\
&=m^{k\cdot f}\cdot m^1&\bmod n\
&=m^{f\cdot k}\cdot m&\bmod n\
&=\left(m^f\right)^k\cdot m&\bmod n\
&=1^k\cdot m&\bmod n\
&=1\cdot m&\bmod n\
&=м&\bмод п\
\end{выравнивание}
$$
Мы доказали это при условии $\gcd(m,n)=1$, что и оригинальная бумага RSA делает, и многие введения в RSA делают. Но это оказывается правдой при условии, не включающем $м$: что $n$ является без квадратов, видеть это.
Этот «бесквадратный $n$"состояние гораздо более удовлетворительное, чем $\gcd(m,n)=1$ в контексте шифрования произвольного сообщения $м$, особенно когда мы используем искусственно малые $n$, так как мы не можем полностью исключить $\gcd(m,n)\ne1$ как маловероятно. В вопросе $n=33$, таким образом $\gcd(m,n)\ne1$ происходит для $м$ один из $0$, $3$, $6$, $9$, $11$, $12$, $15$, $18$, $21$, $22$, $24$, $27$, $30$, тем самым включая $м=15$ обдуманный!
¹ Для целого числа $s$ и целое число $t>0$, эквивалентные определения того, что оператор$\bmod$ это когда нет открывающей скобки слева от нее.
- $s\bмод т$ однозначно определенное целое число $г$ с $0\le r<t$ и $s-r$ кратное $t$
- $s\bмод т$ однозначно определенное целое число $г$ с $0\le r<t$ такое, что существует целое число $к$ с $s=k\cdot t+r$
- в зависимости от знака $s$, $s\bмод т$ является
- если $s\ge0$, остаток от евклидова деления $s$ к $t$
- если $s<0$, либо
- $t-((-s)\bmod t)$ если это не $t$
- $0$, в противном случае
Это не следует путать с обозначением² $r\equiv s\pmod t$ с открывающей скобкой сразу слева от$\bmod$, эквивалентные определения которого включают:
- $s-r$ является кратным $t$
- существует целое число $к$ с $s=k\cdot t+r$
² $r\equiv s\pmod t$ предпочтительно читать с любым из возможных нескольких $\экв$ слева от$\pмод т$ читать как конгруэнтный или же эквивалент скорее, чем равный, и с паузой там, где стоит открывающая скобка. Эта пауза должна отметить, что$\pмод т$ уточняет сказанное. Это обычное использование $=$ вместо $\экв$, опустить$\pмод т$, или опустите открывающую скобку перед$\bmod$. Это также частая причина путаницы, когда разница между$\bмод т$ и$\pмод т$ вопросам, включая вычисление зашифрованного текста в RSA.
