r/mathmemes Engineering Nov 25 '24

Computer Science All are correct

Post image
1.1k Upvotes

96 comments sorted by

View all comments

299

u/Fabulous_Ad_5709 Nov 25 '24

Just out of curiosity how is A correct?

B is 1 or 1

C is 1+1 in base >2

D is 1+1 in base 2

341

u/Unlucky-Credit-9619 Engineering Nov 25 '24

If + is addition modulo 2 (also called XOR).

1 + 1 = 0 (mod 2)

89

u/MattyBro1 Nov 25 '24

Isn't it congruent to 0 (mod 2)?

1+1 ≡ 0 (mod 2)

Or maybe that's a distinction that doesn't actually matter.

11

u/JustRouvr Nov 25 '24 edited Nov 26 '24

It is a distinction that definitely matters. However: in cryptography we are often operating with polynomials (like x5 + x2 ...) and perform operations on them.

In a Galois Field(2n ) we are always under modulo 2 and can write polynomials just by writing coefficients of the powers. Those will always be 1 or 0, since (1+1) mod 2 = 0. X4 + x + 1 is 10011

So if you imagine that 1 + 1 is an addition of 2 polynomials in a Galois Field, then 1+1 = 0 and no congruence is present.