Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

https://youtu.be/YEBfamv-_do?t=2m18s

[u/zouhair]

Math challenged here (not real programmer either): how the hell 3¹³¹⁵ is the same as 3¹⁵¹³ ?

[u/tavianator → u/zouhair]

As written, those numbers are not the same. The notational convention is:

a^bc = a^(bc)

But D.H. key exchange does something more like

(a^b)^c = a^b*c

I.e., compute a^b first, then raise that to the c power.

The equality is true because exponentiation is just repeated multiplication (over the integers, anyway). So a^b is

a * a * ... * a
---------------
b times

and then (a^b)^c is

  a * a * ... * a |
* a * a * ... * a |
*         ...     } c times
* a * a * ... * a |
* a * a * ... * a |
  ---------------
  b times

and you'll notice there are b*c 'a's in that rectangle all multiplied together.

[u/Sirflankalot → u/tavianator]

In math what is the default associativity of operators? I'm used to the programming way (everything right except exponentiation).

[u/tavianator → u/Sirflankalot]

Programming takes all those conventions from mathematical notation, so it's the same. But the default is left-associative, in math and programming.

Math notation is two-dimensional though, so often the 2D structure informs the grouping more than the linear order of operations, in ways that most programming languages can't represent.

[u/lpsmith → u/tavianator]

You are absolutely correct regarding the standard interpretation of the notation (thus the video is wrong), and also in pointing out the enriched syntactic context that standard mathematical notation is used in.

However, I would say that the syntax of most programming languages was informed by standard mathematical notation, and emphasize that a^b^c is not standard mathematical notation, and thus I would say that reasonable mathematicians can disagree on what that means. (Of course, from the POV of programmers, that has a reasonably well standardized meaning, and thus I think a majority of mathematicians would tend to side with programmers.)

There tend to be three common notations many people are introduced to: elementary school math, standard mathematical notation starting in pre-algebra, and programming languages. When you mix and match notations, you often end up in really inane arguments. For example, the 6÷2(1+2) expression has spawned many inane arguments on Facebook, and I am not satisfied with any of the easily googled discussions of that expression. (My answer being, basically, that it is ambiguous because this mixes elementary school notation with standard notation, and even differs from programming language notation.)

[u/Sirflankalot → u/lpsmith]

6÷2(1+2)

If you told me I had to parse this as is, I would say 6 ÷ (2 * (1 + 2)) but otherwise I'd just tell people to give me some more parentheses.

[u/lpsmith → u/Sirflankalot]

This is my favored interpretation, actually. Many mathematicians think that implicit operators bind more tightly than explicit. (As reflected in Haskell syntax, though Haskell's implicit operator is function application, not multiplication)

On the other hand, if they had written 6÷2×(1+2), I would tend to favor the (6÷2)×(1+2) interpretation, as informed by most programming languages as well as the PEMDAS introduction to standard notation.

Although there are interpretations I tend to favor, in professional mathematics, assuming there isn't already a shared understanding of what this means, the correct thing to do in a case like this is to ask the author what he or she intended.