I like Bash, but it isn’t well suited for some tasks. For fun I sometimes ignore that. Occasionally people seem to find this useful.

In that spirit, here is my implementation of the popular Luhn / mod10 algorithm used in credit card, IMEI, and other number sequences.

# Returns Luhn checksum for supplied sequence
luhn_checksum() {
sequence="\$1"
sequence="\${sequence//[^0-9]}" # numbers only plz
checksum=0
table=(0 2 4 6 8 1 3 5 7 9)

# Quicker to work with even number of digits
# prepend a "0" to sequence if uneven
i=\${#sequence}
if [ \$((\$i % 2)) -ne 0 ]; then
sequence="0\$sequence"
((++i))
fi

while [ \$i -ne 0 ];
do
# sum up the individual digits, do extra stuff w/every other digit
checksum="\$((\$checksum + \${sequence:\$((i - 1)):1}))" # Last digit
# for every other digit, double the value before adding the digit
# if the doubled value is over 9, subtract 9
checksum="\$((\$checksum + \${table[\${sequence:\$((i - 2)):1}]}))" # Second to last digit
i=\$((i - 2))

done
checksum="\$((\$checksum % 10))" # mod 10 the sum to get single digit checksum
echo "\$checksum"
}

# Returns Luhn check digit for supplied sequence
luhn_checkdigit() {
check_digit=\$(luhn_checksum "\${1}0")
if [ \$check_digit -ne 0 ]; then
check_digit=\$((10 - \$check_digit))
fi
echo "\$check_digit"
}

# Tests if last digit is the correct Luhn check digit for the sequence
# Returns true if valid, false if not
luhn_test() {
if [ "\$(luhn_checksum \$1)" == "0" ]; then
return 0
else
return 1
fi
}

To maximize the enjoyment I’ve optimized the script a little bit in two ways:

1) Normally every other digit of the sequence to be computed is multiplied by 2. If that result is greater than 9, then 9 is subtracted. There are only 10 single digits in base-10, so it seemed reasonable to precompute these values. This saves not only the multiplication step, but also the conditional branch (on greater/less than 9), and the occasional subtraction operation (when values were greater than 9).
2) I prepend a 0 to the submitted sequence if there are an uneven number of digits in the sequence. The leading 0 doesn’t affect the end result, but being assured of having pairs of digits available in the while loop of our luhn_checksum() function saves us from needing to keep track of which digits should be added directly and which should be handled as described in optimization #1 above.

If for some reason you are actually using this script, you probably will be most interested in luhn_checkdigit() and luhn_test().

Here is an example of how this can be used:

#!/bin/bash
source luhn.sh

# Example IMEI number from Wikipedia
sample_imei="352152097374972"
if luhn_test "\$sample_imei"; then
echo "\$sample_imei might be a valid IMEI"
else
echo "\$sample_imei is an invalid IMEI"
fi

# Same number with the last two digits transposed
sample_imei="352152097374927"
if luhn_test "\$sample_imei"; then
echo "\$sample_imei might be a valid IMEI"
else
echo "\$sample_imei is an invalid IMEI"
fi

# Creating a check digit for a set of numbers
echo "35215209737497 would be a valid looking IMEI if you added a \$(luhn_checkdigit "35215209737497") to the end"

# Many credit card types also use this checksum
sample_mastercard="5105105105105100"
if luhn_test "\$sample_mastercard"; then
echo "\$sample_mastercard might be a valid card number"
else
echo "\$sample_mastercard in an invalid card number"
fi
user@host:~\$ ./demo.sh
352152097374972 might be a valid IMEI
352152097374927 is an invalid IMEI
35215209737497 would be a valid looking IMEI if you added a 2 to the end
5105105105105100 might be a valid card number
Categories:Bash
Published on :Posted on

### 2 thoughts on “Bash Snippet: Luhn Algorithm” #### Love·

Very nice! I’ve wrapped this in a script on my github, hope that is OK:
https://github.com/lovef/.lovef/blob/master/bin/luhn 