Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm a resident of Kuwait and I just learnt that the CIVIL ID numbers allotted to us follow a checksum. The ID is 12 digit number following the algorithm below -

11 – Mod(( c1 * 2 ) + ( c2 * 1 ) + ( c3 * 6 ) + ( c4 * 3 ) + ( c5 * 7 ) +
( c6 * 9 ) + ( c7 * 10 ) + ( c8 * 5 ) + ( c9 * 8 ) + ( c10 * 4 ) + ( c11 * 2 )),11) = 
The 12th Digit

Here, Cx are the digits in the Civil ID number.

Can someone tell me what is the reasoning behind the coefficients used in the checksum? The Bulgarian civil number also uses a checksum but the algorithm used there uses powers of 2 modulus 11. More info here.

Thanks

share|improve this question
    
I don't know about the system in Kuwait, but the similar one in Norway is designed to be an efficient error-detection scheme. That is, the most common typing errors (a single wrong digit and/or insertion/omission of a single digit) are guaranteed to be detected. I have dined with the guy who designed the Norwegian system (according to other colleagues sharing the table) :-). I believe the system we have here in Finland is somewhat similar, but not quite as robust as the Norwegian one. I would guess that the details of the analysis of the error events is quite messy. –  Jyrki Lahtonen Feb 11 at 14:06
    
Oh, and you should have read the tag description of scheme before using it (or any other tag). It was quite the wrong tag here, for scheme has a technical meaning in algebraic geometry - a much deeper part of math. –  Jyrki Lahtonen Feb 11 at 14:08
    
the idea behind the diffeent coeffcients is i think to combat misswitings, so 123 456 789 12x gives a different checksum than 123 546 789 12y (4 and 5 exchanged), if all coefficients were the same then the two numbers would get the same checksum) –  Willemien Feb 11 at 14:10
    
I get the use of the coefficients here and how a checksum would prevent a typing error. However, I am interested in knowing why this particular set of coeff were chosen. I'm sure there's a reasoning behind it. –  Prakhar Feb 11 at 14:11
2  
This is very similar to the ISBN-10 check digit scheme (which you can Google). The essential features are that the coefficients don't repeat and that 11 is prime, so that the integers mod 11 are a field. The one weakness of the Kuwait system is that it will not notice if you swap digits 2 and 12. –  Nate Eldredge Feb 11 at 15:17
show 1 more comment

2 Answers 2

up vote 1 down vote accepted

Rephrasing your equation slightly, the check condition is $$(2,1,6,3,7,9,10,5,8,4,2)\cdot c_{1\ldots 11} + c_{12} \equiv 0\pmod {11}$$

If you take first differences of that vector modulo 11 you get $(10,5,8,4,2,1,6,3,7,9)$, which is $(2^5,2^4,2^3,2^2,2^1,2^0,2^9,2^8,2^7,2^6)$.

share|improve this answer
    
So I get how (10,5,8,4,..) comes from (2^5,2^4,) mod 11, Can you please explain how did the vector (2,1,6,3,7,9,10..) got transformed into (10,5,8,4,2,1..) ? –  Prakhar Feb 11 at 15:24
    
@Prakhar, "take first differences" means taking each adjacent pair and subtracting one from the other. So $1 - 2 \equiv 10, 6 - 1 \equiv 5, 3 - 6 \equiv 8, \ldots$. –  Peter Taylor Feb 11 at 15:29
    
Oh nice! If you don't mind me asking.. how did you figure this out? :D I mean, is it common to take first differences modulo 11 to a checksum algorithm? –  Prakhar Feb 11 at 15:36
    
@Prakhar, it's one of the first things I do when trying to understand a mystery sequence of numbers. It's a good way of identifying polynomials (if you repeat the operation $n$ times then an order-$n$ polynomial will give a constant vector). –  Peter Taylor Feb 11 at 15:50
add comment

Check out the discussion on the Luhn algorithm and the Verhoeff algorithm. The idea is to catch simple transcription errors (mistaken digits, leftouts, switched digits) that are common when copying long numbers by hand. The mathematics behind the Verhoeff algorithm is a bit unusual (it takes each digit to be an operation in a dihedral group, and applies to the digit in position $i$ the permutation $\sigma^i$, where $\sigma$ is a given permutation, and then operates the results) it is not hard to see it catches all simple errors (digit changes, transpositions).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.