チェックディジット：Luhn、バーコード、ISBNと見逃される間違い

1234567890 + チェックを押してください。9と0を入れ替えた12345678093も検証を通過します。Luhn方式では一つおきに数字を2倍し、それが二桁になった場合は各桁の数を足し合わせます。つまり、9は18になりその後9に、0は0のままです。隣り合う二つの数字を入れ替えると、2倍する操作によってそれぞれの数字に加えられる値の差だけ、合計値が変動します。この操作によって、0には0が、1には1が、4には4が、5には−4が、8には−1が、そして9には0が加えられます。まったく同じように処理されるのは0と9の二つの数字だけです。左側のグリッドで赤くなっているセルが09と90の二つだけなのはこのためであり、この方式は隣り合う数字の入れ替えの97.8%を検出します。IMEIを押してみてください。0の隣に9はなく、13個ある隣り合う数字の入れ替えは一つも通過しません。

UPCバーコードを押してください。九つある隣り合う数字の入れ替えのうち、3と8、そして0と5の二つが通過します。バーコードでは一つおきに数字を3倍および1倍するため、aとbを入れ替えると合計値は2(a − b)だけ変化します。これは差が5になるたびに10の倍数となります。90組あるペアのうち10組がこれに該当します。他の重みを使っても結果は良くなりません。一つの数字の間違いをすべて検出するには、重みがmod 10で1、3、7、あるいは9である必要がありますが、これらのうちどの二つを取っても差は偶数になります。そして偶数に5を掛ければ10の倍数になるため、どのような重み付けであっても検出率の上限は88.9%となります。Luhn方式の2倍する操作は重み付けではなく、その検出率は97.8%に達します。しかし、100%には届きません。各桁の数字を最初にどのように変換しようとも、モジュラスが偶数の場合は、数字を足し合わせる方式ですべての数字の間違いや隣り合う数字の入れ替えを検出することは不可能であるとH. P. Gummが1985年に証明したことをGallianが紹介しています。J. Verhoeffは1969年に、かける順序が影響する五角形の二面体群での乗算を用いることで、その両方の検出を実現しました。

IMEIを押してください。12個ある一つ飛ばしでの入れ替えは、すべて検証を通過します。この二つの数字はパリティが同じ位置にあるため、Luhn方式では両方を2倍するか両方ともそのままにするかのどちらかになり、バーコードでは両方に同じ重みが与えられます。したがって、これらを入れ替えても合計値は変わらず、比較表でも両方式の検出率は0.0%となっています。ISBN-10では10から1まで各桁に独自の重みを与えるため、入れ替えると合計値は「二つの重みの差」に「二つの数字の差」を掛けた分だけ変化します。11は素数であるため、その積が11の倍数になることはありません。ISBN-13を押してからISBN-10を押してみてください。同じ番号でも、前者は9個あるそのような入れ替えの9個すべてを通過させてしまうのに対し、後者は6個中0個です。これは珍しい間違いであり、Verhoeffの集計による実際の入力ミスでは、隣り合う数字の入れ替えが10.2%であるのに対し、この間違いはわずか0.8%です。しかし、mod 11にも欠点があります。チェックディジットの10を表すためにXという記号を使う必要があり、さらに重みの和が11になる6と5の位置では、連続する数字の入力ミスをすべて通過させてしまいます。