The Verhoeff-Gumm Check Digit Algorithm

[@dawiid5215]

Nit: you should show the cayley table for ( \sigma (x), y), would've been cool to show how there is no symmetry along the diagonal anymore

[@mauithedog10]

Probably the best SoME3 submission ive seen so far. The explanations are so good it's almost like a conversation and the animations are super engaging and smooth. Sucked me in to the very end.

[@RIPenemie]

what is #SoME3 ?

[@KusaneHexaku]

@@RIPenemie Stands for "Summer of Maths Expedition", basically think of a game jam, but instead of submitting games, you submit a mathematics communitcation video. Very cool event!

[@ricsixd]

Such a good video! The motivation to get that last 2% of transposition errors was so compelling, and the solution so satisfying.

[@fangjiunnewe3634]

So many math video just name drop group theory and isomorphism without explaining how the shapes actually map to some number system in a specific and useful way. This video managed to finally show me how groups can be mapped to a useable algebra, thank you!

[@thecommexokid]

I could have used some more explicit exposition at 5:05. This is the point at which you switch from treating the group elements as "10 orientations of a pentagon" to "10 operations you could do to pentagons," and you do it essentially without comment or explanation. Obviously both sets are isomorphic but first representing the group elements as themselves being pentagons, then suddenly switching to thinking of them as operations on pentagons, was disorienting. The "rotate by 1/5 turn" or "reflect about the vertical axis" operators are not pentagons themselves and I could have used more handholding when you switched from one to the other practically mid sentence.

[@ConceptsIlluminated]

That's good feedback, thank you.

[@IhabFahmy]

Totally agree

[@OldSoulClimber]

Easily one of the best SoME 3 video I have seen yet! Love the different visual language presented!

[@aidanocallaghan169]

Great captioning, clarified the pronunciation of a the name of the algorithm. More content creators should act like this!

[@applimu7992]

Knowing about the semi-direct product from group theory made identifying the pentagons with pairs of numbers alot more satisfying for me

[@lilium724]

This is hands down the best video I've seen about a practical application to group theory! Really impressive!

[@Racrdude24]

This video flows so well! You are an excellent storyteller!

[@DokterKaj]

I'm in awe of how you presented this topic in such a comprehensible way. Loved the video, hope you win!

[@K9Megahertz]

I ran into this many many years ago. I would like to suggest that rather than adding the digits together (e.g. 12 = 1+2 = 3) you subtract 9 from the number instead. You get the same value, and its a little easier to code if you're implementing this in software.

[@Voshchronos]

fascinating!

[@saiv46]

Substract not 9, as its true only for 9 < X < 20, but 9 * ((X - (X % 10)) / 10), which works for all integer numbers up to 119

[@K9Megahertz]

@@saiv46 You're doubling the original single digit number, which means it will never be greater than 18, you don't really need to handle larger cases, and even if you went ahead and did that, where do you draw the line? mod 10, mod 10000? mod 31337? more?

[@vladislav_sidorenko]

Nitpick but at 2:49, commutative is described as order not mattering. That's true only for operations that are both commutative and associative. If it's commutative and non-associative, it still may be possible to swap 2 elements amd get a different result. For example, let's say that ~ represents an arithmetic mean of the two numbers. It's a commutative operation since in an individual operation, order doesn't matter. However, 1~5~13 = 8, but 1~13~5 = 6.

[@geekjokes8458]

i get what youre saying, but in your example you are completely changing the inputs of the operations, which are necessarily binary

[@RadenVijaya]

After 10 hours of driving, i stumbled upon this video. Now i cant sleep as my mind engages in this topic 😅 nice video btw. I learnt something new here...

[@shibeinu4988]

I just took a class on group theory during my final semester of college and it’s so cool to see an application of the seemingly arbitrary concepts and rules of groups theory

[@bunniesarecute3135]

Great video! I actually took a group theory course in uni which left me quite confused about the practical applications of it, but this video was quite eye-opening to say the least :D thanks!

[@Heka2]

Loved this video! I never really thought about what the digits on a credit card might signify. This is such a clever way of foregoing basic human errors and as always I love to see practical applications for group theory. I felt very drawn into this problem and your explanations were easy to follow. Excited for more

[@f5673-t1h]

Btw, the reason we ues this group and not any other group, is because there's literally only two groups of order 10 (the amount of digits we have, 0 to 9), and the other one is commutative, which wouldn't work as noted in te video.

[@MasterHigure]

Really cool video. Very glad to see you call the group D5, which is objectively the correct naming scheme for the dihedral groups. I will personally fight anyone who thinks D10 is even remotely appropriate, with words or fists.

[@eclypze_]

Amazing video! cant wait for this channel to pop off

[@redstowen]

One of the best #SoME3 videos!

[@siddhantmisal4115]

Great content ! underrated channel

[@Vfulncchl]

FANTASTIC SoME3 entry!!!

[@mostlyokay]

Love the "quacks like a duck..." joke

[@mac_edmarco]

This video is so well done. I always love seeing group theory out in the wild! Would love to see more of this type of content

[@ahuggingsam]

Really cool video, very well done. if I can offer a small bit of feedback though (I'm not associated with SoME): sometimes I feel the screen can get very visually busy, which can be a bit overwhelming, even though it is always clear what you are talking about. Feel free to do with this as you please, thanks again for the cool video :)

[@kiliane.3266]

Would have been so nice to learn about this in University when studying about groups etc - just to show a real world example to create interest in the field.

[@Dedjkeorrn42]

Thanks for explaining how to find valid credit card numbers for credit card theft 😂

[@UCXEO5L8xnaMJhtUsuNXhlmQ]

This is a great video, I love the visualization of this concept

[@zach4505]

Amazing work, hope this helps give your videos the visibility they deserve. You other videos are amazing and more people should see them.

[@candilunio]

These colorful pentagons are CUTE! 😍

[@lunalma]

I absolutely lost it when you said to represent the pentagons we are using to represent numbers with numbers

[@categorygrp]

while i hate that notation, the capital letters for group elements, this is a wonderful idea edit: I see you switched to the much nicer notation midway. good man

[@coffeemixer4292]

Awesome channel. So many incredible lectures. Thank you❤

[@BertLeyson]

0:38 There is another major flaw with this system: It can't detect repeating digits. According to the rules, 1212 1212 1212 1210 is a valid credit card number. 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 0 = 30, which is divisible by 10.

[@adrianv.v.4445]

Amazing work! This is a good candidate to get a prize.

[@povertjes776]

I am currently writing my bachelor thesis on check digit algorithms and just wanted to say: thank you so much! I just couldn't make any sense from Verhoeffs original work.

[@ConceptsIlluminated]

It's a dense paper for sure. Took me a few attempts to really understand it.

[@greenafroninja7]

Great video! Just shared it with 2 of my mates!

[@philippberninger7726]

This content is amazing. Simply amazing. In school I wished for this Kind of content. Teachers should adapt to Teach things Visually. Wow i am amazed!

[@GauravNirala]

Just phenomenal!

[@ExplodingWaffle101]

great video! the box analogy is not “intuitive” to me, but it doesn’t matter because you didn’t use it for the rest of the video :) and you did such a good explanation of the algorithm. well done

[@YellowBunny]

At around 11 minutes you write (fg, fs+r) mod 5 which I don't really like because the first component is not mod 5 but instead from {-1,+1}. Something like (fg, fs+r mod 5) would have been better.

[@pedrocrb]

what a delightful video

[@bananya6020]

For some reason, the first thought I had upon seeing the Verhoeff-Gumm was "oh look it's tetris!" I wonder if there's some knowledge about perfect clears that can explain this too.

[@scragar]

I much prefer the idea of just having two different checksum digits using different algorithms. The first checksum can check everything before the last digit, and the last digit can remain the luhn algorithm as present, this gives us extra security and since we're not using all the digits of the card number already(there's orders of magnitude less cards than possible card numbers) it's not going to cost us anything for the additional safety that'd remain backwards compatible. If you're going to go for a solution most people can't do in their heads though I suggest going all out and just use a traditional hashing algo, they munge the data each step in such a way that communitivity is lost making transpositions as obvious as a changed value(using SHA for example that uses a grid of numbers, then every time it applies a change(by bitmasking numbers together) it applies row/column shifts such that the next number would apply differently). This also requires the least effort to add to new services, every modern programming language has access to libraries that can provide access to a bunch of pre-existing hashing algorithms.

[@ВалерийГайнанов-и5г]

Thank you for this video! I always wanted to know the applications of group theory irl

[@U.Inferno]

When I heard pentagons and group theory i for some reason thought youd be throwing the quintic at us

[@kwiky5643]

What a great educational video

[@Cobalt1911]

Great work! 👏

[@wowzande]

You got my sub. How long does it take for you to release these type of videos?

[@ConceptsIlluminated]

This video took about 80-100 hours to make once i had an idea and a rough outline of what I wanted to say. Videos happen when they happen :)

[@eric3813]

such an awesome video!!! loved it! subscribed :)

[@matheustran8009]

Jacobus Verhoeff is the father of my professor Tom Verhoeff at tu/e!!!

[@hansisbrucker813]

That's so cool. What do you study? 😊

[@juancristi376]

Great video!!

[@vladimirfokow6420]

Great! I finally received a direct practical example of how group theory can be useful, which makes it very easy to learn it if I decide to do it in the future. Thanks!🤗

[@stephnue7790]

I have a question regarding the formular at 10:26 What is the first input of the mod-operation? Is it the second number, that encodes the rotation? Then it should be (f*g,(f*s+r)mod 5) Or am I mistaken here and it is aplied to the whole tuple

[@ConceptsIlluminated]

Technically to both parts of the tuple, but because the first term is only multiplying {-1, 1}, the mod doesn't really.

[@paulschnetzler9410]

What am I even watching that late at night, I should sleep

[@FireFoxDOPE]

This video has some mad timing cause I just started my senior year in my math undergrad, and I am taking group theory this semester!

[@QuantumHistorian]

This is nice, but the middle is slightly confusing. You're sometimes using pentagons to represent a state, and sometimes to represent an operation. Could be explained more clearly that we're only ever dealing with operations, but a good way to visualise those operations is to see what state they give when applied to a given initial state. For example, at 5:00 in the formula, replacing P9 with F_5(P) and P_2 with R_288(P), and saying that this equation holds for any choice of P (so long as it's the same on both sides), would be more instructive IMO.

[@HyperFocusMarshmallow]

Nice video. Well put together. I kind of felt that you brushed past actually explaining what a “group” is in mathematics and what group theory is in mathematics. Even at the end when you were trying to recap you mostly said some pretty generic things that wasn’t very mathematical at all. But that’s acceptable I guess. I usually feel that if you want to introduce a word in mathematics you had better define it and motivate it, otherwise try to do the same thing without introducing the fancy word… But sometimes it’s also good that people just hear words so they can recognize them the next time. Overall great video!

[@ItIsJan]

is this essentially a hash function? applying some function to first n (i think n=9 in this case?) digits of a credit card number, to get the n+1th digit, so if you type it in, if the function desnt result in the last digit, they misstyped something..?

[@yesworld7292]

The video is extremely well made and entertaining. And I was surprised by number of views and subscribers. I guess, you gotta work on your video cover. I mean this wasn't bad, cuz I clicked it. But I was just curious, because I couldn't see any relations in title and images. Overall, as I said video is great. Graphics was entertaining. Continue your work buddy. It was very interesting.

[@softy8088]

15:04 Sorry but it took me way to long to see what you were trying to say here because you didn't state the conclusion. I suppose it was obvious to you but I had to think about it for a while. The follow-up should be: "Thus, following the steps we just did backwards, at each step the inequality must hold, since we are applying the same transformation to each side of the inequality, which must give another inequality. The two sides cannot be equal if we apply the same operations. That means the original inequality must also be true". This was not obvious to me at first because if you just start adding these inverses, it's not immediately clear what that does to the whole equation. You kind of mentioned it using "laws of algebra" but within this weird pentagon world it should not be taken for granted that IF a≠b THEN (a+c)≠(b+c)

[@marvinochieng6295]

This guy does the math

[@nxpnsv]

Excellent use of a comic rimshot!

[@SirNobleIZH]

If it walks like a duck and it quacks like a duck, it's isomorphic to a duck

[@simpli_A]

As a cuber myself, I wholeheartedly agree with your mother… sticker peelers are the worst cretins on this earth

[@magnusmalmborn8665]

A checksum video without mentioning Galois..!

[@evreatic3438]

144° , 216°... Ahh! They hurt my brain! 4π/5 and 6π/5 are way more intuitive when dealing with pentagons.

[@DavidLindes]

Interesting stuff. Help me understand how the tetris shapes fit in (unfortunate pun) to things? Like, you seem to equate them to the hexagons, but I don’t grok how or why, and also they don’t seem to have a consistent shape per digit, so… I’m just lost as to what they’re actually trying to represent. ?? Thanks!

[@ericsbuds]

ive always wondered how the card number is checked like that. thanks!

[@mc-not_escher]

Strangely enough, this reminds me of the subject of topology and also as an extension how tying your shoes one way vs. the "normal" 'loop-and-swoop' way is still misunderstood by the vast majority.😅

[@worldadmin9811]

nicely done :)

[@NeverSnows]

I was wondering, but couldn't quite figure out how, what if we used binary? Using the property of 1+2+4+8+... could lead into some efficient algorithm. Maybe assign a binary number to each digit, such as 0=1, 1=2 etc?

[@johnchessant3012]

Very nice! In fact the group of the ordered pairs (f, r) with that seemingly strange operation for combining them is the semidirect product Z_n ⋊ Z_2. So this means the dihedral group D_n is isomorphic to Z_n ⋊ Z_2 for all n.

[@multiarray2320]

why is it saying "double every other number"? it was confusing for me.

[@Asterism_Desmos]

I will never unsee “o with a hairdo”

[@cmilkau]

In theory, we also need to check whether flips are detected when σ is applied to the second digit, as flips can occur at any position in the credit card number, not just every other position.

[@partywumpus5267]

no, as flipping X and Y would just be the same as swapping the two sides of the not-equals sign. as in `sigma(X)*Y != sigma(Y)*X` the other way around is just `sigma(Y)*X != sigma(X)*Y`

[@ConceptsIlluminated]

Correct. This is briefly mentioned at 14:00, but I skip showing the derivation since it is very similar to before (good practice though if you want to try it).

[@SirRebrl]

@@partywumpus5267 Not quite. What's being attended to here is if you have A B C and you apply sigma to every other digit [eg sigma(A) B sigma(C)], when you prove that sigma(X) * Y != sigma(Y) * X, you account for the A B to B A transposition but not the B C to C B transposition, which needs X * sigma(Y) != Y * sigma(X). Not the same inequality because composition is not commutative.

[@partywumpus5267]

@@SirRebrl ah of course, it's not commutative. Fair enough then.

[@Dominik-K]

Great video, would've loved to see the table representation to see that there is no symmetry anymore

[@d.lawrencemiller5755]

I have no idea what you mean about intuitive sized boxes 0:53

[@ConceptsIlluminated]

Suppose you go to the post office and buy a box. They only have boxes in certain sizes, say 9 x 6 x 2 or 11 x 9 x 6. Your stuff is unlikely to fit *exactly* in one of those pre-sized boxes, but you can add packing peanuts or other filler to take up the rest of the empty space. In that analogy, the filler is the check digit because it makes the existing content conform to some rule (fit in a box) so it is more robust during shipping.

[@orichen5409]

I think you have a mistake at 10:21 when you substituted the variables you mixed up s and r.

[@ConceptsIlluminated]

Good catch. Thankfully, since we multiply by 1, the mistake is short lived :)

[@JoeyLlamaGames]

So if this is the formula to check if it is a correct number, then what is the initial formula that generates these numbers. And how do we not run out of valid numbers.

[@worldfromhome4033]

And I randomly come to this video!

[@catte_6376]

such a great video!!!!!!!!!!!!!!1

[@Hans_Magnusson]

A variation is used for Swedish social security number… But the difference eg between 70 and 67 in this case is the check digit!

[@devvy8343]

When we make the rules for the box stricter, we cut off more potential correct inputs though, right? Like the reason transposing 0 and 9 worked is because doing that provided two valid codes. Like *the best* system would just be "if the code doesn't equal x, its wrong" because ANY error to ANY digit that could be infinitely long could be detected. Verhoeff-Gumm seems to work because it just makes the rules more strict! But, I like it, very interesting!

[@mrphlip]

Not necessarily... both of these codes have 1/10 of the inputs be valid, like, if you were to pick a string of digits completely at random, you'd have a 10% chance of it being considered valid by each of these codes. What has changed is the distribution of those valid inputs, ensuring that no two inputs are neighbours by a single transposition or a single digit change. Compare to the encoding scheme that "a number is valid if the final digit is a 7"...still has a 1/10 chance of passing a random string, but now all the valid strings are closely clustered together, so any transposition or digit change is very likely to give you another valid code.

[@partywumpus5267]

nope afaict both codes could still be valid, just with different check bits

[@MasterHigure]

If you have 11 free digits and one check digit, then no matter what check digit scheme you use, you have the same number of valid codes. The trick is making sure that common errors in typing the first 11 results in a different check digit as often as possible. Which is to say, have as few as possible valid codes that are "close to one another", where "close" is defined in terms of how easy it is to type one when you mean the other.

[@blackpepper2610]

Subscribed

[@leif1075]

Why did youbchange 5 to at 2:28..seems arbitrary

[@ConceptsIlluminated]

Indeed, it was simulating a typo and the choice of typo was arbitrary.

[@alextasarov1341]

Wait I got a little lost. How would the front end know the difference between a valid and invalid card number? Does the card company only make numbers that follow a pattern? What makes swapping two numbers invalid besides producing a different result? Is it the check value? Would this value be something like the security code or just unique to the algorithm? Rewatching lol

[@ConceptsIlluminated]

Credit Card companies only put numbers on the cards that follow the Luhn algorithm. Specifically, a credit card vendor starts with their "assigned" prefix (e.g. all Visa cards start with a 4 and no other vendor does) www.ibm.com/docs/en/order-management-sw/9.3.0?topic=cpms-handling-credit-cards (see Table 1) Then, they add a certain number of digits that correspond to an account number. At this point, they have n-1 digits where n is the length (Visa, Mastercard and Discover have 16 digits but some vendors have less). Then, they perform the Luhn algorithm on all those digits and "round up" to the next multiple of 10 to get their check digit and append it to the end. With this fact (all credit card numbers follow the Luhn algorithm), a frontend can also run the Luhn algorithm to verify that what a user typed *might* be valid (passes Luhn check) before sending it off to the database. The security code on the back is likely a different algorithm and is probably secret/proprietary (so it cannot be reverse-engineered by bad actors).

[@alextasarov1341]

@@ConceptsIlluminated Thank you!

[@Xorume.]

Would any sigma table fit this algorithm, as long as no two digits mapped to the same and zero mapped to zero? If so, that step feels a bit overengineerd. But it was cool anyways. Thanks for the video!

[@tommasobanfi8133]

i wonder how many people went to check their credi card number after this video to see if the test works

[@anon_y_mousse]

Wouldn't it be easier to just use one number for each pentagon, +[0-4] for regular, -[0-4] for flipped? If you insist on using integers, scale the numbers by 1, or I suppose you could find a computer that uses 1's complement negation. Though, I can't remember which computers use that, I know they're still being made to this day. Either way, you can have a negative and a positive 0 with floating point, but it'd be easiest to just adjust the scale by 1 and remember that in your calculations.

[@rueblimaster]

What if multiple numbers are transposed?

[@canaDavid1]

Isn't it more convenient to just represent 0-9 as the 10 flips of a decagon? Then, if there are odd numbers, the check sum is the last flip, and if an even number of digits, the following check digit is the missing rotation.

[@canaDavid1]

No, this does not differentiate between two orthogonal flips. If only we used an odd base.

[@prcvl]

Doesnt the Luhns Algorithm start with the second to last number and doubles it?

[@ConceptsIlluminated]

It does, which is what is shown in the animation. The reason this is done (I believe) is so the check digit doesn't have to be doubled, which complicates the calculation.

[@cleverclover7]

i'm lacking some knowledge to understand this seemingly very interesting video. how are the number's generated in the first place? They have to be 1. unique, and 2. satisfy the algorithm(s) you give in this video. But I presume they don't just brute force increment and check?

[@ConceptsIlluminated]

A credit card vendor starts with their "assigned" prefix (e.g. all Visa cards start with a 4 and no other vendor does) www.ibm.com/docs/en/order-management-sw/9.3.0?topic=cpms-handling-credit-cards (see Table 1) Then, they add a certain number of digits that correspond to an account number. At this point, they have n-1 digits where n is the length (Visa, Mastercard and Discover have 16 digits but some vendors have less). Then, they perform the Luhn algorithm on all those digits and "round up" to the next multiple of 10 to get their check digit and append it to the end.

[@cleverclover7]

@@ConceptsIlluminated what a great reply! thanks!

[@bobbob905]

Its a great video but i dont really understand the point of the b value when it always gets cancelled out

[@ConceptsIlluminated]

The b value is important when dealing with X * sigma(Y) != Y * sigma(X), the derivation was not shown. b is also handy in making simga(0) be 0, which allows for the leading 0 trick.

[@michelefurci3506]

So now how to know if a credit card uses Luhn or Verhoeff algo? Maybe you transposed a number and it's checked with Luhn but it was using Verhoeff.

[@ConceptsIlluminated]

I believe *all* credit cards use the Luhn algorithm, as per the specification www.ibm.com/docs/en/order-management-sw/9.3.0?topic=cpms-handling-credit-cards

[@alexjohnward]

Is there an optimal algo for error correction, not just error detection?

[@ConceptsIlluminated]

KZbinr @AnotherRoof did a great video recently on the error correcting algorithm that NASA uses to send images through outer space: kzbin.info/www/bejne/ip7bXqlqe86DbKs

[@KalijahAnderson]

Now I want an Isomorphic duck. :P

[@SirRebrl]

Had fun coming up with a sigma function. Tried sigma(f, r) = (f, r + fb) but that failed on f = g = 1 && r != s, and f != g && r = s && r + b = 0 mod 5. Came up with sigma(f ,r) = (f, -fr + fb) and that did the trick on sigma(x) * y != sigma(y) * x, but it fails for some cases on x * sigma(y) != y * sigma(x), which I didn't think to check before finishing the video.

[@ConceptsIlluminated]

Great job giving it a go, though!