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 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!
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!
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.
@@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?
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.
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
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.
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...
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.
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!
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.
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.
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
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.
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.
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 :)
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.
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
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)
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
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.
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.
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.
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!🤗
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.😅
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..?
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!
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.
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.
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`
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).
@@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.
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.
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!
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.
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.
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.
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.
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?
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!
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!
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.
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
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.
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
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).
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.
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
CZcamsr @AnotherRoof did a great video recently on the error correcting algorithm that NASA uses to send images through outer space: czcams.com/video/Tmx-v4FiP6I/video.html
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.
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?
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.
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.
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
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.
what is #SoME3 ?
@@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!
Such a good video! The motivation to get that last 2% of transposition errors was so compelling, and the solution so satisfying.
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!
Easily one of the best SoME 3 video I have seen yet! Love the different visual language presented!
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.
fascinating!
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
@@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?
This is hands down the best video I've seen about a practical application to group theory! Really impressive!
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.
That's good feedback, thank you.
Totally agree
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
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.
i get what youre saying, but in your example you are completely changing the inputs of the operations, which are necessarily binary
Knowing about the semi-direct product from group theory made identifying the pentagons with pairs of numbers alot more satisfying for me
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...
I'm in awe of how you presented this topic in such a comprehensible way. Loved the video, hope you win!
Great captioning, clarified the pronunciation of a the name of the algorithm. More content creators should act like this!
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.
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!
This video flows so well! You are an excellent storyteller!
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.
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.
Love the "quacks like a duck..." joke
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
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
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.
It's a dense paper for sure. Took me a few attempts to really understand it.
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.
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 :)
Great content ! underrated channel
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.
When I heard pentagons and group theory i for some reason thought youd be throwing the quintic at us
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
These colorful pentagons are CUTE! 😍
Amazing video! cant wait for this channel to pop off
What am I even watching that late at night, I should sleep
Amazing work, hope this helps give your videos the visibility they deserve. You other videos are amazing and more people should see them.
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)
Thanks for explaining how to find valid credit card numbers for credit card theft 😂
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
FANTASTIC SoME3 entry!!!
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.
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.
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.
This is a great video, I love the visualization of this concept
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!
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!🤗
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.😅
One of the best #SoME3 videos!
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!
Awesome channel. So many incredible lectures. Thank you❤
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..?
Excellent use of a comic rimshot!
144° , 216°... Ahh! They hurt my brain!
4π/5 and 6π/5 are way more intuitive when dealing with pentagons.
Thank you for this video! I always wanted to know the applications of group theory irl
A variation is used for Swedish social security number…
But the difference eg between 70 and 67 in this case is the check digit!
Amazing work! This is a good candidate to get a prize.
A checksum video without mentioning Galois..!
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!
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.
As a cuber myself, I wholeheartedly agree with your mother… sticker peelers are the worst cretins on this earth
Great video! Just shared it with 2 of my mates!
You got my sub. How long does it take for you to release these type of videos?
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 :)
why is it saying "double every other number"? it was confusing for me.
what a delightful video
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.
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`
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).
@@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.
@@SirRebrl ah of course, it's not commutative. Fair enough then.
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.
No, this does not differentiate between two orthogonal flips. If only we used an odd base.
Just phenomenal!
And I randomly come to this video!
If it walks like a duck and it quacks like a duck, it's isomorphic to a duck
Jacobus Verhoeff is the father of my professor Tom Verhoeff at tu/e!!!
That's so cool. What do you study? 😊
This guy does the math
Great video!!
ive always wondered how the card number is checked like that. thanks!
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!
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.
nope afaict both codes could still be valid, just with different check bits
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.
Great video, would've loved to see the table representation to see that there is no symmetry anymore
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.
I will never unsee “o with a hairdo”
nicely done :)
i wonder how many people went to check their credi card number after this video to see if the test works
such an awesome video!!! loved it! subscribed :)
A bit brisk, but so was 3b1b back in the day.
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.
What a great educational video
Great work! 👏
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?
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!
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!
Now I want an Isomorphic duck. :P
What if multiple numbers are transposed?
Its a great video but i dont really understand the point of the b value when it always gets cancelled out
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.
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.
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
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.
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
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).
@@ConceptsIlluminated Thank you!
Doesnt the Luhns Algorithm start with the second to last number and doubles it?
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.
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
Technically to both parts of the tuple, but because the first term is only multiplying {-1, 1}, the mod doesn't really.
Is there an optimal algo for error correction, not just error detection?
CZcamsr @AnotherRoof did a great video recently on the error correcting algorithm that NASA uses to send images through outer space: czcams.com/video/Tmx-v4FiP6I/video.html
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.
Great job giving it a go, though!
How did i get here? Why am i learning how to forge a card
Subscribed
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?
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.
@@ConceptsIlluminated what a great reply! thanks!
such a great video!!!!!!!!!!!!!!1
I think you have a mistake at 10:21 when you substituted the variables you mixed up s and r.
Good catch. Thankfully, since we multiply by 1, the mistake is short lived :)
I have no idea what you mean about intuitive sized boxes 0:53
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.