Amintiți-vă că pentru $\forall x\in\mathbb N$, $\forall m,u,v\in\mathbb N^*$, tine ${(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m$, Unde $y\equiv x\pmod m$ mijloace $m$ desparte $x-y$, și $x\bmod m$ este întregul definit în mod unic $y$ astfel încât $0\le y<m$ și $y\equiv x\pmod m$.
Secretul împărtășit este $K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p$, sau echivalent $K=g^{a\times b}\bmod p$. Suntem însărcinați să evaluăm acest lucru pentru $a=6$, $b=8$, $g=2$, $p=19$.
Metoda din întrebare este:
$$\begin{matrice}{}
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{matrice}$$
și că (păstrarea coloanei din dreapta) poate fi condensată la:
$$K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ astfel }\ K=11$$
Dacă ar fi să calculez acest lucru fără calculator, aș scrie asta ca $K=2^{48}\bmod19$, apoi utilizați Mica Teoremă a lui Fermat. Se spune că atunci când $p$ este prim și $g$ nu este un multiplu al $p$, dacă ține $g^{p-1}\bmod p=1$. Asta permite reducerea modulo $(p-1)$ orice exponent al $g$ la calculul modulo $p$. Calculul complet merge:
$$\begin{matrice}{}
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\end{array}$$
Notă: În $48-18\times2=12$, cel $2$ se obține ca coeficient $\lfloor48/18\rfloor$, la fel ca în $4096-19\times215=11$ cel $215$ este $\lfloor4096/19\rfloor$.
Criptografia reală folosește numere întregi mult prea mari pentru calcule umane fiabile; de exemplu. $p$ ar putea fi de 2048 de biți, adică 617 cifre zecimale.
