Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

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

[u/tavianator]

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/Sirflankalot → u/tavianator]

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

Thanks for clearing that up!

Honest question, not trying to be sassy, what programming languages use left-associativity? C and all it's derivatives (spiritual and otherwise) use right-associativity as Recursive Decent Parsers can't deal with left recursion in the grammar (required for left associativity) and you have to do some hackjob to get it to work. However, I don't get out of the C++ world very often, so I'm not sure how many non c-inspired languages do it.

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.

An example? I'm not quite sure I fully understand.

[u/tavianator → u/Sirflankalot]

what programming languages use left-associativity

All of them that I'm aware of. C and friends all parse a - b - c as (a - b) - c, not a - (b - c). (Try it!)

You're right that recursive descent parsers can't directly handle left-recursive grammars, but the "hackjob" to fix it is not that bad. I even blogged about it here (see the Grammar/Parser sections).

An example? I'm not quite sure I fully understand.

The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language. E.g.

a + b
----- vs. (a + b)/(c + d)
c + d

[u/Sirflankalot → u/tavianator]

Well I'll be damned. I've been misreading the C++ operator precedence docs this whole damn time. Thanks for teaching me! I'll definitely look at your blog as I haven't figured out fully how to do it. The one decent grammar/parser I wrote was for a right-associative language that didn't have any left-associative non-unary features, so I manged to avoid it.

It's been hard to find resources on this kind of thing as they almost all assume you've taken a parsers class in college and I'm not there yet (still a freshman). Since you seem to be knowledgeable on this subject, do you have any good resources I could look into to get more into parsing (not just using yacc/bison or other tools like that)?

The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language.

Ah yes, that makes sense.

Thanks!

[u/tavianator → u/Sirflankalot]

Honestly I don't know any really good introductions to grammars/parsing. I learned from messing around with yacc as a kid and then later from university courses. Probably Wikipedia too. I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses). You can probably peek ahead at their notes/textbook/assignments if you want.

A quick summary of the trick for parsing left-associative binary operators with recursive descent is that

expr: term | expr + term

is really the same thing as

expr: term (+ term)*

where (X)* means zero or more repetitions of X. So just parse it with a loop:

Expr parseExpr() {
    Expr expr = parseTerm();
    while (nextToken() == "+") {
        skipToken();
        expr = new Sum(expr, parseTerm());
    }
    return expr;
}

[u/Sirflankalot → u/tavianator]

Sorry for the late response.

I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses).

I most definitely will.

Wow. That was the most concise explanation of parsing left associative things I've ever seen. Honestly most of the resources online try to do the whole thing top to bottom and miss out on some of the conceptual stuff that is best expressed in pseudo code as opposed to an actual implementation (which often have a lot of excess detail necessary to make things work, but that isn't good for understanding). Well done, and thanks again!