The Verhoeff-Gumm Check Digit Algorithm
HTML-код
- Опубликовано: 5 авг 2024
- Rediscover and explore the Verhoeff-Gumm algorithm, a check digit formula which is more resilient to common errors than the Luhn algorithm, which is widely used in credit card numbers, IMEI numbers and more.
Historical Notes:
"Error Detecting Decimal Codes" [1], a PhD thesis by J Verhoeff was published in 1969. It showed how the vast majority of digit typos were single digit or transposition errors, traditional "modulo 10" algorithms always missed some transposition errors, and introduced a novel class of algorithms based on "the dihedral group of order 10" (pentagon flips and rotations). In section 4.4, Verhoeff outlines using "search program" to find a permutation function that is optimal for detecting errors. A formal proof of the permutation's correctness is omitted. I found Verhoeff's writing to be difficult to approach, so I recommend a section in "Contemporary Abstract Algebra" (seventh edition) by Joseph A Gallian (pg 111-114) for a clearer write-up. A witty quote from Verhoeff in the introduction made me chuckle: "[I believe] that the codes explained in chapter 4 provide the first practical application of the dihedral group. This would illustrate the old saying that all beautiful mathematics will find an application, sooner or later."
In 1985, H. Peter Gumm published "A new class of check-digit methods for arbitrary number systems" [2]. It starts with a dense proof that "modulo 10" (indeed modulo 2k) formulas will always be flawed. The paper then justifies the use of the dihedral group, which to me sounded like a mathematician walking around a store looking for the right outfit ("needs cancellation", "should be associative", "finite members", "can generalize for any even number"). Gumm then proves an algorithm using D_s works, using the number pair notation and a permutation function tau.
Gumm claims to have been unaware of Verhoeff's work. Additionally, Gumm adds a proof and a way to scale it beyond 10 digits, so I decided to credit them both with discovering the algorithm in this video.
A variant of the algorithm saw use (an may still see use) on German Banknotes [4].
Felix Klein (same as the Klein bottle) was an important contributor to group theory [3], and was chosen to be the cardholder in the intro. Likewise, Évariste Galois coined the term "group" and was thus chosen to be the online vendor.
[1] ir.cwi.nl/pub/13046/13046D.pdf
[2] www.researchgate.net/publicat...
[3] archive.org/details/vergleich...
[4] ocs.ef.jcu.cz/index.php/inprof...
Expanding the Mathematical Toolbox:
A key concept in Group Theory is the idea of sets, which is covered very well in [4]. Groups are introduced well in [5] and I hope the author continues the series.
The Rubix cube can be analyzed using group theory [6] or with "graphs" [7], which are both useful when dealing with so many possible states.
[4] • What IS a Number? As E... "What IS a Number? As Explained by a Mathematician" by Another Roof
[5] • Researchers Use Group ... "Researchers Use Group Theory to Speed Up Algorithms - Introduction to Groups" by Nemean
[6] • Group theory 101: How ... "Group theory 101: How to play a Rubik’s Cube like a piano - Michael Staff" by TED-Ed
[7] • The trick that solves ... "The algorithmic trick that solves Rubik’s Cubes and breaks ciphers" by polylog
Animations were made with Manim Community edition (www.manim.community/) taking about 7k lines of Python code to make.
Sound effects from RUclips Audio Library
- Battle Crowd Celebrate Stutter
- Punchline Drum
This was Kevin Lubick's entry into Summer of Math Exposition 3 #SoME3
- some.3b1b.co/
0:00 Luhn Algorithm (and its flaw)
1:39 How could we fix the flaw?
2:21 Basic Integer Operations (how they don't help)
3:12 Rotating and Flipping Shapes is order dependent
4:16 Combining Pentagons (function composition)
5:30 "Packing the box" with pentagons (associativity/inverses)
6:56 Do our pentagons work for all transpositions? (Cayley Table)
8:29 Adding a preprocessing step (sigma function)
9:30 How to prove if sigma works (converting to integer pairs)
11:56 Proving Gumm's sigma function does work
13:12 Expanding sigma into digit permutation
13:38 Scaling up to 3 or more digits/pentagons
15:06 Summarizing the Verhoeff-Gumm Algorithm (and the variants)
16:00 Group theory is all about surprising symmetries
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!
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
This is hands down the best video I've seen about a practical application to group theory! Really impressive!
Easily one of the best SoME 3 video I have seen yet! Love the different visual language presented!
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
I'm in awe of how you presented this topic in such a comprehensible way. Loved the video, hope you win!
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 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?
Knowing about the semi-direct product from group theory made identifying the pentagons with pairs of numbers alot more satisfying for me
This video flows so well! You are an excellent storyteller!
Great captioning, clarified the pronunciation of a the name of the algorithm. More content creators should act like this!
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!
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
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.
Amazing video! cant wait for this channel to pop off
This is a great video, I love the visualization of this concept
Awesome channel. So many incredible lectures. Thank you❤
One of the best #SoME3 videos!
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
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...
Great content ! underrated channel
FANTASTIC SoME3 entry!!!
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.
Great video! Just shared it with 2 of my mates!
Great video!!
what a delightful video
such an awesome video!!! loved it! subscribed :)
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.
Love the "quacks like a duck..." joke
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!
Amazing work! This is a good candidate to get a prize.
Just phenomenal!
Great work! 👏
These colorful pentagons are CUTE! 😍
Amazing work, hope this helps give your videos the visibility they deserve. You other videos are amazing and more people should see them.
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 :)
What a great educational video
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
nicely done :)
Thank you for this video! I always wanted to know the applications of group theory irl
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
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
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.
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..?
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!
What am I even watching that late at night, I should sleep
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.
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!
Thanks for explaining how to find valid credit card numbers for credit card theft 😂
Excellent use of a comic rimshot!
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?
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.
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!
such a great video!!!!!!!!!!!!!!1
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.😅
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.
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.
Subscribed
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 :)
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.
why is it saying "double every other number"? it was confusing for me.
Great video, would've loved to see the table representation to see that there is no symmetry anymore
ive always wondered how the card number is checked like that. thanks!
This guy does the math
A checksum video without mentioning Galois..!
144° , 216°... Ahh! They hurt my brain!
4π/5 and 6π/5 are way more intuitive when dealing with pentagons.
I will never unsee “o with a hairdo”
What if multiple numbers are transposed?
And I randomly come to this video!
A variation is used for Swedish social security number…
But the difference eg between 70 and 67 in this case is the check digit!
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.
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.
Is there an optimal algo for error correction, not just error detection?
RUclipsr @AnotherRoof did a great video recently on the error correcting algorithm that NASA uses to send images through outer space: ruclips.net/video/Tmx-v4FiP6I/видео.html
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.
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
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.
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).
@@KevinLubick Thank you!
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!
As a cuber myself, I wholeheartedly agree with your mother… sticker peelers are the worst cretins on this earth
Jacobus Verhoeff is the father of my professor Tom Verhoeff at tu/e!!!
That's so cool. What do you study? 😊
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.
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.
If it walks like a duck and it quacks like a duck, it's isomorphic to a duck
Now I want an Isomorphic duck. :P
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.
i wonder how many people went to check their credi card number after this video to see if the test works
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.
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.
@@KevinLubick what a great reply! thanks!
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 :)
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.
Doesn't mistyping a 5 as 0 in one of the doubling places (in luhn algorithm) keep it invariant? Same with 2-6, 4-7.
If you turned a 0 into a 5, the doubling takes it to a 10 or 1+0 because Luhn adds the digits together (we don't drop the leading 1).
@@KevinLubickthen it makes more sense. The operation of multiplying by two and adding the digits then becomes a bijective map from Z/Z10 to itself, which makes it resistant against such errors.
A bit brisk, but so was 3b1b back in the day.
How did i get here? Why am i learning how to forge a card
Man I wish I knew what was purple and commutes ...
I'd always heard the "What's nutritious and commutes?" version, but apparently there are multiple: math.stackexchange.com/questions/1354105/explanation-of-a-joke-on-abelian-groups-grapes
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!