Verhoeff Algorithm (Checksum)

Verhoeff's algorithm is a check digit calculation algorithm designed to detect input errors in decimal numeric identifiers (serial numbers, administrative IDs, etc.).

Verhoeff's algorithm can detect all single-digit substitution errors and all adjacent digit transpositions, as well as some multiple errors.

The algorithm uses three tables (index 0): the multiplication table (D) based on the dihedral group D5, the permutation table (P) which permutes the digits according to their position, the inverse table (I) which allows the calculation of the final check digit.

An iterative calculation (to calculate the checksum c) is applied, with an initialization of c = 0.

The final checksum is calculated by looking in the inverse table based on the value of c.

Verhoeff's algorithm effectively detects several types of input errors:

— All simple substitution errors, where one digit is replaced by another (e.g., 1234 → 1239).

— All adjacent transpositions, where two neighboring digits are reversed (e.g., 1234 → 1324).

— Some multiple errors, where two or more digits are entered incorrectly simultaneously.

However, the algorithm does not detect certain complex permutations, such as circular permutations (e.g., 1234 → 4123) or some non-adjacent transpositions.

Developed in 1969 by the Dutch mathematician Jakob Verhoeff, it improves upon simpler methods like the checksum modulo 10 (Luhn's algorithm) by offering better detection of common human errors.