What should I use as a check digit algorithm for a base 31 value?

Question

I'm using the following set of values to create a 9 character long base 31 value:
0123456789ABCDEFGHJKLMNPQRTUWXY

I was looking at modifying the Luhn algorithm to work with my base.

My question is:

In base 10, the Luhn algorithm doubles each value in an even position and then if the result is >10 the individual digits of the result are added together.

Should I still be doubling my even position values, or using a higher multiplier?

I'm trying to protect against transposed characters, missing characters, extra characters and just plain wrong digits.

Answer 1

Don't reinvent the wheel - use Luhn mod N instead.

Answer 2

I looked into the Luhn mod N algorithm, but it is very limited in what it can validate against.

I decided to use a modified version of the Freight Container system.

The shipping container system multiples each value by 2^[position] (position starting from 0) and then performs a modulus 11 on the result to get a base 10 check digit (a result of 10 is not recommended).

In this case, the trick is to find values in the range x^0 to x^[length] which are not evenly divisible by the figure you use on the modulus.

I've decided to use 3^[position] as the multiplier and performing a modulus 31 on the sum to get the check digit.

As an example: 0369CFJMK

Character  0     3     6     9     C     F     J     M     K
Value      0     3     6     9     12    15    18    21    19
--------------------------------------------------------------
Multiplier 1     3     9     27    81    243   729   2187
Result     0     9     54    243   972   3645  13122 45927

Total      63972 MOD 31 = 19

It seems that with these sort of algorithms, the main requirement is that the multipler is not evenly divisible by the base and that the pattern of the remainders doesn't repeat within the length of the code you want to validate.