Напомним, что для $\forall x\in\mathbb N$, $\forall m,u,v\in\mathbb N^*$, он держит ${(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m$, куда $у\экв х\пмод м$ средства $м$ делит $х-у$, и $х\bмод м$ однозначно определенное целое число $у$ такой, что $0\le y<m$ и $у\экв х\пмод м$.
Общий секрет $K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p$или эквивалентно $K=g^{a\times b}\bmod p$. Нам поручено оценить это для $а=6$, $б=8$, $г=2$, $р=19$.
Метод в вопросе идет:
$$\начать{массив}{}
K&={(2^6\bmod19)}^8\bmod19&&=2^{6\times8}\bmod19\
&=2^{(3\times2)\times8}\bmod19&={(2^3)}^{2\times8}\bmod19&=8^{2\times8}\bmod19\
&={(8^2)}^8\bmod19&=64^8\bmod19\
&&=(64-19\times3)^8\bmod19&=7^8\bmod19\
&={(7^2)}^4\bmod19&=49^4\bmod19\
&&=(49-19\times2)^4\bmod19&=11^4\bmod19\
&={(11^2)}^2\bmod19&=121^2\bmod19\
&&=(121-19\times6)^2\bmod19&=7^2\bmod19\
&=49\bmod19&=49-19\times2&=11\
\end{массив}$$
и это (сохраняя крайний правый столбец) можно сжать до:
$$K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ таким образом}\ K=11$$
Если бы мне нужно было вычислить это без калькулятора, я бы написал это как $K=2^{48}\bmod19$, затем используйте малую теорему Ферма. Там сказано, что когда $р$ является простым и $г$ не кратно $р$, если выполняется $g^{p-1}\bmod p=1$. Это позволяет уменьшить по модулю $(p-1)$ любой показатель $г$ при вычислении по модулю $р$. Полный расчет идет:
$$\начать{массив}{}
K&=2^{6\times8}\bmod19&&=2^{48}\bmod19\
&=2^{48\bmod(19-1)}\bmod19&=2^{48-18\times2}\bmod19&=2^{12}\bmod19\
&=4096\bmod19&=4096-19\times215&=11\конец{массив}$$
Примечание: в $48-18\times2=12$, $2$ получается как частное $\lэтаж48/18\rэтаж$, очень похоже на $4096-19\times215=11$ в $215$ является $\lfloor4096/19\rэтаж$.
В реальной криптографии используются целые числа, слишком большие для надежных вычислений человеком; например $р$ может быть 2048-битным, то есть 617 десятичных цифр.
