Nhớ lại điều đó cho $\forall x\in\mathbb N$, $\forall m,u,v\in\mathbb N^*$, nó giữ ${(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m$, ở đâu $y\equiv x\pmod m$ có nghĩa $m$ phân chia $x-y$, và $x\bmod m$ là số nguyên được xác định duy nhất $y$ như vậy mà $0\le y<m$ và $y\equiv x\pmod m$.
Bí mật được chia sẻ là $K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p$, hoặc tương đương $K=g^{a\times b}\bmod p$. Chúng tôi được giao nhiệm vụ đánh giá điều này cho $a=6$, $b=8$, $g=2$, $p=19$.
Phương pháp trong câu hỏi đi:
$$\begin{array}{}
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{mảng}$$
và điều đó (giữ cột ngoài cùng bên phải) có thể được rút gọn thành:
$$K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ do đó }\ K=11$$
Nếu tôi tính toán cái này mà không có máy tính, tôi sẽ viết cái này là $K=2^{48}\bmod19$, sau đó sử dụng Định lý nhỏ Fermat. Nó nói rằng khi $p$ là số nguyên tố và $g$ không phải là bội số của $p$, nếu giữ $g^{p-1}\bmod p=1$. Điều đó cho phép giảm modulo $(p-1)$ bất kỳ số mũ nào của $g$ khi tính modulo $p$. Tính toán đầy đủ đi:
$$\begin{array}{}
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}$$
Lưu ý: Trong $48-18\times2=12$, các $2$ được lấy dưới dạng thương số $\lfloor48/18\rfloor$, giống như trong $4096-19\times215=11$ các $215$ Là $\lfloor4096/19\rfloor$.
Mật mã thực tế sử dụng các số nguyên quá lớn để tính toán đáng tin cậy của con người; ví dụ. $p$ có thể là 2048-bit, tức là 617 chữ số thập phân.
