NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

In the past, researchers have given "proofs" that it is impossible for a check to detect all adjacent transpositions (as well as all single errors). It is true that if one uses a simple sum of digits with weights on the individual locations, then such a check is mathematically impossible. However, the more general scheme in this section works.


---

Types of Decimal Errors.

In 1969, a Dutch mathematician named Verhoeff carried out a study of errors made by humans in handling decimal numbers. He identified the following principal types:

• single errors: a changed to b (60 to 95 percent of all errors)
• adjacent transpositions: ab changed to ba (10 to 20 percent)
• twin errors: aa changed to bb (0.5 to 1.5 percent)
• jump transpositions: acb changed to bca (0.5 to 1.5 percent)
• jump twin errors: aca changed to bcb (below 1 percent)
• phonetic errors: a0 changed to 1a (0.5 to 1.5 percent; "phonetic" because in some languages the two have similar pronunciations, as with thirty and thirteen)
• omitting or adding a digit: (10 to 20 percent)

---

The Dihedral Group D₅.

Verhoeff had the clever idea to use some other method besides addition modulo 10 for combining the integers from 0 to 9. Instead he used the operation of a group known as the dihedral group D₅, represented by the symmetries of a pentagon, which has ten elements that one can name 0 through 9. The discussion here will use # for the group operation and 0 for the identity element. This is not a commutative group, so that a # b will not always equal b # a. Here is the multiplication table for this group. (Each table entry gives the result of the bold table entry on the left combined with the bold table entry across the top, written left to right. The red italic entries show results which are not commutative.)

#		0	1	2	3	4		5	6	7	8	9
0		0	1	2	3	4		5	6	7	8	9
1		1	2	3	4	0		6	7	8	9	5
2		2	3	4	0	1		7	8	9	5	6
3		3	4	0	1	2		8	9	5	6	7
4		4	0	1	2	3		9	5	6	7	8
5		5	9	8	7	6		0	4	3	2	1
6		6	5	9	8	7		1	0	4	3	2
7		7	6	5	9	8		2	1	0	4	3
8		8	7	6	5	9		3	2	1	0	4
9		9	8	7	6	5		4	3	2	1	0

The reader should realize that D₅ is a complex entity whose elements are somewhat arbitrarily mapped to the integers from 0 to 9, and the group operation # is not at all like addition or multiplication. Keep in mind that the ten symbols 0 through 9 are the only symbols in the group. When two are combined, you get another of them. There is no number 29, but only separate group elements 2 and 9 that could be combined in two ways: 2 # 9 = 6 and 9 # 2 = 7. There is no concept of order such as < or > in this group. The five numbers 0 through 4 combine in the group just as they do with addition in the group Z₅, but the remaining numbers are quite different, since each of 5, 6, 7, 8, and 9 is its own inverse. (With ordinary addition in Z₁₀, only 5 is its own inverse.)

---

Verhoeff's Scheme.

If one just used the check equation

a₀ # a₁ # a₂ # ... # a_n-1 = 0

where # is the group operation in D₅, this would be much better than simply adding the digits modulo 10, since in both cases single errors are caught, but in D₅ two-thirds of adjacent transpositions are caught (60 out of 90, represented by the red entries in the table above), whereas ordinary addition catches no transpositions. This suggests that stirring things up a little more would give the answer.

Verhoeff considered check equations of the form

f₀(a₀) # f₁(a₁) # f₂(a₂) # ... # f_n-1(a_n-1) = 0

where each f_i is a permutation of the ten digits. He was able to get an excellent check in the special case where f_i is the ith iteration of a fixed permutation f. As the Java implementation will show, this check is not hard to program and is efficient, but it employs several tables and could not be carried out by hand as all the earlier checks could. This discussion will employ Java notation to keep the subscripts straight. First the check needs the group operation, defined as a two-dimensional array op[i][j], for i and j going from 0 to 9 giving the result of combining the two numbers in D₅ (the same as the table above):

   int[][] op= {
      {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
      {1, 2, 3, 4, 0, 6, 7, 8, 9, 5},
      {2, 3, 4, 0, 1, 7, 8, 9, 5, 6},
      {3, 4, 0, 1, 2, 8, 9, 5, 6, 7},
      {4, 0, 1, 2, 3, 9, 5, 6, 7, 8},
      {5, 9, 8, 7, 6, 0, 4, 3, 2 ,1},
      {6, 5, 9, 8, 7, 1, 0, 4, 3, 2},
      {7, 6, 5, 9, 8, 2, 1, 0, 4, 3},
      {8, 7, 6, 5, 9, 3, 2, 1, 0, 4},
      {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} };

Then comes an array Inv, where Inv[i] gives the inverse of each digit i in D₅:

   int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};

Finally, the check requires another two-dimensional array giving the special permutation and iterations of it:

   int[][] F = new int[8][];
   F[0] = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // identity permutation
   F[1] = new int[]{1, 5, 7, 6, 2, 8, 3, 0, 9, 4}; // "magic" permutation
   for (int i = 2; i < 8; i++) { // iterate for remaining permutations
      F[i] = new int[10];
      for (int j = 0; j < 10; j++)
         F[i][j] = F[i-1] [F[1][j]];
   }

Now the check equation takes the form:

   public static boolean doCheck(int[] a) {
      int check = 0;
      for (int i = 0; i < a.length; i++)
         check = op[check][ F[i % 8][a[i]] ];
      if (check != 0) return false;
      else return true;
   }

The check digit can be inserted in position a[0] using the array Inv, as is show in the actual implementation later in this section.

Verhoeff's check above catches all single errors and all adjacent transpositions. It also catches 95.555% of twin errors, 94.222% of jump transpositions and jump twin errors, and 95.3125% percent of phonetic errors (assuming a ranges from 2 to 9).

---

Java Implementation of Verhoeff's Scheme.
Use of the Dihedral Group (all but 30 transpositions detected): Java source.

Verhoeff's Scheme (all transpositions detected): Java source.