Verhoeff Algorithm

The Verhoeff algorithm is a checksum formula for error detection developed by the Dutch mathematician Jacobus Verhoeff and was first published in 1969. It was the first decimal check digit algorithm which detects all single-digit errors, and all transposition errors involving two adjacent digits, which was at the time thought impossible with such a code.



									private static int[,] _multiplicationTable = {
	{ 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 }
};

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

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

public static int CheckSum(string number)
{
	int c = 0;
	int len = number.Length;

	for (int i = 0; i < len; ++i)
		c = _multiplicationTable[c, _permutationTable[((i + 1) % 8), number[len - i - 1] - '0']];

	return _inverseTable[c];
}

public static bool Validate(string number)
{
	int c = 0;
	int len = number.Length;

	for (int i = 0; i < len; ++i)
		c = _multiplicationTable[c, _permutationTable[(i % 8), number[len - i - 1] - '0']];

	return c == 0;
}
								


Example

									int c = CheckSum("58564");
bool isValid = Validate("585649");
								


Output

									c: 9
isValid: true