4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Feb 11, 2014 at 14:06
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Feb 11, 2014 at 14:08
  • $\begingroup$ 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) $\endgroup$
    – Willemien
    Feb 11, 2014 at 14:10
  • $\begingroup$ 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. $\endgroup$
    – Prakhar
    Feb 11, 2014 at 14:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Nate Eldredge
    Feb 11, 2014 at 15:17

2 Answers 2

Reset to default
2
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ 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..) ? $\endgroup$
    – Prakhar
    Feb 11, 2014 at 15:24
  • $\begingroup$ @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$. $\endgroup$
    – Peter Taylor
    Feb 11, 2014 at 15:29
  • $\begingroup$ 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? $\endgroup$
    – Prakhar
    Feb 11, 2014 at 15:36
  • $\begingroup$ @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). $\endgroup$
    – Peter Taylor
    Feb 11, 2014 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .