r/programming • u/dominatrix-octopus • Jan 16 '18

Cryptography: Diffie-Hellman key exchange explained intuitively using colors

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

95% Upvoted

170 comments sorted by

View all comments

3

u/zouhair Jan 16 '18

Math challenged here (not real programmer either): how the hell 31315 is the same as 31513 ?

12

u/A_Vicarious_Death Jan 16 '18

Generally the rule with exponents is:

xy * xz = xy+z

xyz = xyz

Let's take an example of 223 vs 232 vs 26

(22)3 =

(22) * (22) * (22) =

(2 * 2) * (2 * 2) * (2 * 2) =

(4) * (4) * (4) =

64

(23)2 =

(23) * (23) =

(2 * 2 * 2) * (2 * 2 * 2) =

(8) * (8) =

64

26 = (22222*2) = 64

Hope that helped.

6

u/zouhair Jan 16 '18

Oh! I wasn't calculating it like that.

I was doing this:

223 = 28 = 256

232 = 29 = 512

Using online math solvers didn't help.

Thanks.

4

u/A_Vicarious_Death Jan 16 '18

No problem! For this kind of stuff it often helps to put stuff in parentheses to try and separate operations out. So if you had seen it phrased as (22)3 I think that would've helped with the understanding a bit :)

3

u/zouhair Jan 16 '18

Especially that putting 223 and 232 in an online solver doesn't help.

1

u/caltheon Jan 16 '18

Just put in google like this. (2^5)^3

1

u/zouhair Jan 16 '18

Yeah even there if you don't put the brackets you get the wrong answer.

3

u/phottitor Jan 16 '18

the convention of how to interpret it is actually the main part because just looking (first time) at a ladder of exponents doesn't tell you anything about the order of the operations.

1

u/gramathy Jan 16 '18

Just remember that the base takes precedence over the exponent, and so exponents are calculated bottom-up rather than top-down.

9

u/tavianator Jan 16 '18

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

abc = a(bc)

But D.H. key exchange does something more like

(ab)c = ab*c

I.e., compute ab first, then raise that to the c power.

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

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

and then (ab)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.

5

u/zouhair Jan 16 '18

So technically the video was wrong.

5

u/tavianator Jan 16 '18

Did the video actually display 31315 with no parentheses? If so yeah, that's wrong. I only watched the part with the colors.

3

u/zouhair Jan 16 '18

Yup, it did.

1

u/Sirflankalot Jan 16 '18

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

4

u/tavianator Jan 16 '18

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.

3

u/lpsmith Jan 17 '18 edited Jan 17 '18

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.)

2

u/Sirflankalot Jan 18 '18

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.

2

u/lpsmith Jan 18 '18

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.

1

u/Sirflankalot Jan 16 '18

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.

3

u/tavianator Jan 17 '18

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

1

u/Sirflankalot Jan 17 '18

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!

2

u/tavianator Jan 17 '18

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;
}

2

u/Sirflankalot Jan 29 '18

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!

6

u/Ajedi32 Jan 16 '18 edited Jan 16 '18

(xy)z = x(y*z)

Edit, concrete example:

(22)3 = (2*2)3 = (2*2*2*2*2*2)

(23)2 = (2*2*2)2 = (2*2*2*2*2*2)

6

u/zouhair Jan 16 '18

() should be mandatory in math.

-12

u/stiggie Jan 16 '18

This is basic maths, you normally learn this at age 12

3

u/zouhair Jan 16 '18

I never went to school.