54 lines
1.4 KiB
Markdown
54 lines
1.4 KiB
Markdown
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
$$16^{54} \ mod \ 17=3^{24×54} \ mod \ 17 $$
|
|||
|
|
|
|||
|
|
Why?
|
|||
|
|
|
|||
|
|
[Public Key Cryptography: Diffie-Hellman Key Exchange (short version) - YouTube](https://www.youtube.com/watch?v=3QnD2c4Xovk) is a good video to understand asymmetric cryptography. There is a jump from 4:34 in the video that is not obvious to everyone.
|
|||
|
|
|
|||
|
|
The jump is from 1654mod17 to 324×54mod17, but why? From the comments of video, I’m not the only one who is supprised by this jump.
|
|||
|
|
|
|||
|
|
First let me introduce a formula:
|
|||
|
|
|
|||
|
|
$$a^b\ mod \ p=((a \ mod \ p)^b) \ mod \ p \ \ \ \ (1)$$
|
|||
|
|
|
|||
|
|
Then the proof:
|
|||
|
|
|
|||
|
|
There must be one integer `n` to have
|
|||
|
|
|
|||
|
|
$$a \ mod \ p=a−np \ \ \ \ (2)$$
|
|||
|
|
|
|||
|
|
so
|
|||
|
|
|
|||
|
|
$$((a \ mod \ p)^b) \ mod \ p=((a−np)^b) \ mod \ p$$
|
|||
|
|
|
|||
|
|
With [Binomial theorem - Wikipedia](https://en.wikipedia.org/wiki/Binomial_theorem),
|
|||
|
|
|
|||
|
|
$$(a−np)b=ab+(b1)ab−1(−np)+(b2)ab−2(−np)2+...+(−np)b$$
|
|||
|
|
|
|||
|
|
We could see that all items are times of `p` except $a^b$,
|
|||
|
|
|
|||
|
|
$$((a−np)bmodp)=(ab+(b1)ab−1(−np)+(b2)ab−2(−np)2+...+(−np)b)modp=abmodp+0+0+...+0$$
|
|||
|
|
|
|||
|
|
Now we got
|
|||
|
|
|
|||
|
|
$$((a−np)^b \ mod \ p)=a^b \ mod \ p$$
|
|||
|
|
|
|||
|
|
Use formula (2)
|
|||
|
|
|
|||
|
|
$$((amodp)b)modp=abmodp$$
|
|||
|
|
|
|||
|
|
Now let a as $3^{24}$, and b as 54 in formula (1):
|
|||
|
|
|
|||
|
|
$$
|
|||
|
|
\\
|
|||
|
|
|
|||
|
|
\\begin{align}
|
|||
|
|
3^{24×54}\ mod \ 17=((3^{24})^{54}) \ mod \ 17 \\ \\&= ((3^{24} \ mod \17)^{54})mod 17
|
|||
|
|
|
|||
|
|
|
|||
|
|
\end{align}
|
|||
|
|
= 16^{54}mod17$$
|
|||
|
|
|
|||
|
|
via [BrookHongs github](https://brookhong.github.io/2018/05/22/proof-of-a-formula-for-modulo.html)
|