Luhnアルゴリズムについて学んだのでまとめた

## 概要

Webアプリ開発をしていると招待コードやクーポンコード等の文字列を作成するという機能が必要になるケースが有るかと思います。
こういったケースでは、**打ち間違いによって想定外のコードが入力される**(悪意のある入力は除きます)のはできる限り避けたいと思うのですが、
そういったケースに適した誤入力検知アルゴリズムがLuhnアルゴリズムです。

先にアルゴリズムの特徴をまとめます。

- 1桁の誤入力を検知できる
- 隣り合う桁の順番を誤った場合も一部検出できる
- 実装がシンプル
- 実際に、クレジットカード番号や海外の社会保険番号等の作成・検証に利用されている

また、PHPにてコードの作成・検証の実装もしました。
特に作成に関する実装はあまりなかったように思えたためコードを記載しました。

今回は簡単のため、作成する文字列は数値だけとしますが、
これは簡単に拡張できて、文字列に対しても適用することができます(*Luhn mod N*アルゴリズム)。


## Luhnアルゴリズムって？

Luhnアルゴリズムは[チェックサム方式](https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF%E3%82%B5%E3%83%A0)で誤入力を検知するアルゴリズムです。
1桁の打ち間違いと、それ以外のいくつかの誤入力を検知することができます。

例えば、正しいコードが`5637`なとき、ユーザに`5631`という文字列を入力されると(7と1の見間違いによる誤入力)、これは誤入力だと検知することができます。

実際の検査の手順は以下の流れになります。

1. コードを右から数えて奇数番目、偶数番目と分類する
2. 偶数番目の数をそれぞれ2倍する
3. 2.にて数値が2桁になった場合、それぞれ別々の数字とする(9*2=18の場合、18でなく1と8とする)
4. それぞれの数をすべて加える
5. その数が10で割り切れれば正しく、そうでない場合は誤っている

先程の例を実際に検討すると、`5637`では、

奇数番目の数は7,6
偶数番目の数は3,5
2倍すると6,1,0です。
足し合わせると7+6+6+1+0=20で、10で割り切れるため正しいです。
ですが、`5631`では
奇数番目の数は1,6
偶数番目の数は3,5
2倍すると6,1,0です。
足し合わせると1+6+6+1+0=14で、10で割り切れないため誤りです。

## チェックディジット生成＆検証(PHP)

実際に実装しました。
言語はPHPです。

###検査

```php
function check_luhn(string $code) :bool
{
    $len = strlen($code);
    $even = false;
    $sum = 0;
    for ($i = 0; $i < $len; $i++) {
        $c = $code[$len - 1 - $i];
        $d = intval($c); // *
        if ($even) {
            $sum += intdiv(2 * $d, 10) + 2 * $d % 10;
        } else {
            $sum += $d;
        }
        $even = !$even;
    }
    return ($sum % 10 == 0);
}

$test_code = trim(fgets(STDIN));
echo 'code: ' . $test_code . "\n";
if (check_luhn($test_code)) {
    echo 'OK';
} else {
    echo 'NG';
}
```

###生成

はじめ付加する数を考慮せずに飛ばし、もとの文字列の各桁の総和を10で割ったあまりが0になるような数を付加しました。

```php
function createCode(string $src) :string
{
    $len = strlen($src) + 1; // チェックディジットを含む
    $even = true;
    $sum = 0;
    for ($i = 1; $i < $len; $i++) {
        $c = $src[$len - 1 - $i];
        $d = intval($c); // *

        if ($even) {
            $sum += intdiv(2 * $d, 10) + 2 * $d % 10;
        } else {
            $sum += $d;
        }
        $even = !$even;
    }

    $check_digit = (10 - ($sum % 10));
    return $src . strval($check_digit);
}

$test_src = trim(fgets(STDIN));
echo 'code: ' . $test_src . "\n";
echo createCode($test_src);
```

ソースコードに多々現れる10という数字を$Nという変数に置き換え、
数値の取り出し(コメントの\*の部分)の箇所を少し工夫すれば、
数字以外の文字列にも拡張できそうです。

## なぜ検知できるのか

まず、2倍する処理を一旦忘れた場合について考えます。
各桁の総和を10で割った余りが0のコードがあるとします。
このうち、一桁を変更して同じく総和の余りを0にすることを考えますが、
これが可能な数値は0から9までのなかで元の数値以外ありません。
よって、一桁の変更までは誤入力を検知できます。

次に、2倍する処理を考慮することにします。
実は、0から9までのどの数を2倍し、二桁になった場合は各桁を足す
という処理を行っても、0から9にそれぞれ個別の結果が得られます。


|元の数|1|2|3|4|5|6|7|8|9|
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|2倍|2|4|6|8|10|12|14|16|18|
|各桁を足す|2|4|6|8|1|3|5|7|9|

結局、2倍して各桁を足す処理は数字を一部入れ替えているだけで、
各数字は1対1対応しているので、1桁の誤入力検知ができるという仕組みです。

そこで、そもそも各桁を普通に足し合わせるだけで1桁の誤検知は可能なのに、
なぜ2倍する必要があるのか、と疑問に思われるかもしれません。
実は偶数のみを2倍することで、順番の入力ミスを防ぐことができます。
具体的には、`5637`というコードを`5367`と入力した際、
2倍する処理を行わない場合では誤入力を検知できませんが、
2倍する処理を行うことで誤入力検知ができます。

しかし、一組だけ検知できないケースがあります。

### 0と9の入れ替わりは区別できない？

実はこのアルゴリズム、0と9が入れ替わった誤入力を検知できません。
例えば`109`と`190`はどちらも正しいです。

実は、数字以外にも拡張した*luhn mod N*アルゴリズムにおいても、
0とN-1の数が入れ替わっても検知ができません。
(数字のみを扱う場合はN=10となります。)

以下のように数学的に検知不可能だとわかります。

0とN-1が入れ替わったときに、
入れ替わった0の桁とN-1の桁が両方偶数の場合、
0→N-1, N-1→0となっているだけなので総和は変化がないことがわかります。

さて、上記に該当しない、すなわち奇数番目の桁が絡んだものについて考えます。
奇数が絡んだ場合は2倍し、2桁の場合は各桁を足し合わせるということですが、これは数式として以下のように表せます。(上の桁と下の桁の和を足し合わせています)

```math
(2 (N - 1) - (2 (N - 1)) \% N) \div N + (2 (N - 1) )\%N
```

これを変形すると

```math
\begin{align}
&= (2 N  - 2 - (N + N - 2) \% N) \div N + (N + N - 2) \% N \\
&= (2 N - 2 - (N - 2)) \div N + N - 2 \\
&= N \div N + N - 2 \\
&= N - 1
\end{align}
```

となり、結局N-1の桁は2倍する処理を経てもN-1です。

以上より、0とN-1の入れ替えが発生しても、N-1増えてN-1減るだけで総和は変わりません。

すなわち、Luhnアルゴリズムにおいて、0と9の入れ替わりは検知できないということになります。