1

I watched this 2min video https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-2 and I am struggling on understanding the proof in a comment (@Cameron) below.

Basically, the author firstly proves that:

  • $(x * y) \mod z = (x \mod z) * (y \mod z) \mod z$

Then he uses this to prove $(3^b \mod 17)^a \mod 17 = 3^{(ba)} \mod 17$ .

But I just can't understand one of the steps and really doubt it:

He writes:

  1. $3^{(ba)} \mod 17 = 3^{(ba)} \mod 17$
  2. $3^{(ba)} \mod 17 = (3^{b(a-1)} * 3^b ) \mod 17$
  3. $3^{(ba)} \mod 17 = (3^{b(a-1)} \mod 17) * (3^b \mod 17) \mod 17$
  4. $3^{(ba)} \mod 17 = (3^{b(a-2)} * 3^b \mod 17) * (3^b \mod 17) \mod 17$
  5. $3^{(ba)} \mod 17 = (3^{b(a-2)} \mod 17) * (3^b \mod 17) * (3^b \mod 17) \mod 17$

From 4. to 5. ,

$(3^{b(a-2)} * 3^b \mod 17) * (3^b \mod 17) \mod 17$ should have decomposed to

$[(3^{b(a-2)} \mod 17) * (3^b \mod 17) \mod 17 ] * (3^b \mod 17) \mod 17$ .

I don't know why he drops the $\mod17$ and I think it can't be dropped.

I've been thinking this for hours and sorry if I didn't get the format right.

Rick
  • 111
  • Welcome to MSE. In order for MathJax commands to be effective, they must be enclosed in$ signs. For example, $x^2$ shows up as $x^2$. – saulspatz Jun 03 '21 at 14:21
  • @saulspatz Any tools recommended to format the formula? I will go format the post right away. – Rick Jun 03 '21 at 14:22
  • Your notation is ambiguous. What do you mean by $3$^b^a ? Use parentheses if you can't figure out how to format properly. – lulu Jun 03 '21 at 14:22
  • https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – saulspatz Jun 03 '21 at 14:22
  • 1
    Be care with 3^a^b. That is usually taken to mean $3^{(a^b)}$ but here you want $(3^a)^b.$ – Thomas Andrews Jun 03 '21 at 14:25
  • Post edit, what you are asking is false. Take $b=1$. Then $3^{(b^a)}=3$. But $\left(3^1\right)^a=3^a$. – lulu Jun 03 '21 at 14:28
  • This result is implied by the general Number Theory result that $(a + nk)^r \equiv a^r \pmod{n}.$ The result is immediate from the binomial expansion, where all but the first term have a factor of $(n)$. Here, you have that $17 ~| ~\left{(3^b) - [\text{the } ~\pmod{17} ~\text{residue of } ~(3^b)]\right}.$ – user2661923 Jun 03 '21 at 14:59
  • @user2661923 Could you make that a little bit easier to understand? And so the original proof from 4. to 5. is wrong? – Rick Jun 03 '21 at 15:03
  • Normally, I would say that you want $\left(3^b\right)^a = 3^{(a\times b)}.$ My inference is based on the idea that you want the exponents on both sides to be identical. If this is incorrect, it invalidates my previous comment. – user2661923 Jun 03 '21 at 15:04
  • Assuming that you want $\left(3^b\right)^a$, so that the exponents on the LHS and RHS are identical, you have that $(a + nk)^r = a^r + \binom{n}{1} a^{(r-1)}(nk)^1 + \cdots + \binom{n}{n-1}a^1(nk)^{(r-1)} + (nk)^r.$ In the RHS summation, $n$ divides all but the first term. – user2661923 Jun 03 '21 at 15:07
  • Again, it is not true for $3^{(b^a)}.$ It is true for $(3^b)^a.$ – Thomas Andrews Jun 03 '21 at 15:08
  • Further, you have that $(3^b)$ may be re-expressed as ${[3^b] \pmod{17}] + 17k}.$ – user2661923 Jun 03 '21 at 15:09
  • The assertion holds for $\left(3^b\right)^a = 3^{(b\times a)}.$ In general, you do not have that $\displaystyle 3^{\left(b^a\right)} \equiv \left(3^b\right)^a \pmod{17}.$ Therefore, if the RHS of the conjecture intends $\displaystyle 3^{\left(b^a\right)}$ rather than $\left(3^b\right)^a$, then the conjecture will not always be true. – user2661923 Jun 03 '21 at 15:18
  • It is not $3^{b^a}$ but $3^{ba}$ in fact , for $(b,a)=(3,2)$ we have $3^3\pmod{17}=10$ and $(3^3\pmod{17})^2=100=15\pmod{17}$. But $3^{3^2}=3^9=14\pmod{17}$. Instead $3^6=15\pmod{17}$ – Piquito Jun 03 '21 at 15:48

0 Answers0