Luhnアルゴリズム

ルーンアルゴリズムまたはルーン式（考案者：IBMの科学者ハンス・ピーター・ルーン）は、「モジュラス10」または「mod 10」アルゴリズムとしても知られており、さまざまな識別番号を検証するために使用される単純なチェックデジット式です。 ^{[ a ]}その目的は、人間が番号を入力する際に​​、コンピュータがエラーを迅速にチェックできるような番号体系を設計することです。

このアルゴリズムはパブリックドメインであり、今日広く使用されています。ISO /IEC 7812-1で規定されています。^{[ 2 ]}これは暗号学的に安全なハッシュ関数として意図されたものではなく、悪意のある攻撃ではなく、偶発的なエラーから保護するために設計されました。ほとんどのクレジットカード番号と多くの政府識別番号は、有効な番号と入力ミスやその他の誤った番号を区別する簡単な方法としてこのアルゴリズムを使用しています。

チェックデジットは次のように計算されます。

1. （既に存在する場合は）番号からチェックデジットを削除します。これでペイロードが残ります。
2. ペイロードの数字から始め、左から番号を振ったときに2桁目（逆順で奇数番目の位置にある数字）を2倍にする。
3. ペイロードは右から左へ処理します。2桁の数字が9を超える場合は、その数字から9を引きます。
4. 結果として得られたすべての桁（2倍されなかった桁も含む​​）を合計します。
5. チェックデジットは次のように計算されます。${\displaystyle (10-(s{\bmod {10}})){\bmod {10}}}$ここで、s はステップ 4 の合計です。これは、 に加える必要がある最小の数 (場合によってはゼロ) です。${\displaystyle s}$10の倍数を作る。
6. 同じ値を与える他の有効な式は次のとおりです。${\displaystyle 9-((s+9){\bmod {10}})}$、${\displaystyle (10-s){\bmod {10}}}$、 そして${\displaystyle 10\lceil s/10\rceil -s}$式に注意してください${\displaystyle (10-s){\bmod {10}}}$剰余演算における負の数の処理方法の違いにより、すべての環境で正しく動作するとは限りません。

Luhnアルゴリズムは、1桁の誤りをすべて検出するだけでなく、隣接する桁のほぼすべての転置も検出します。ただし、2桁の数字列09から90（またはその逆）の転置は検出しません。また、考えられるほとんどの双子の誤りを検出します（ 22 ↔ 55、33 ↔ 66、44 ↔ 77は検出しません）。

より複雑なチェックデジットアルゴリズム（VerhoeffアルゴリズムやDammアルゴリズムなど）は、より多くの転記ミスを検出できます。Luhn mod Nアルゴリズムは、非数値文字列をサポートする拡張機能です。

このアルゴリズムは数字を右から左に処理し、ゼロ数字は位置ずれを引き起こす場合にのみ結果に影響を与えるため、数値列の先頭をゼロで埋めても計算結果には影響しません。したがって、特定の桁数にパディングするシステム（例えば、1234を0001234に変換するなど）は、パディングの前後にLuhnアルゴリズムによる検証を実行しても同じ結果が得られます。

このアルゴリズムは、チェックサムを計算するためのシンプルな手持ち式機械装置に関する米国特許^{[ 1 ]}に記載されていた。この装置は、機械的な手段でmod 10の合計を求めた。置換桁、つまり倍化と還元処理の結果は、機械的に生成されたものではなかった。むしろ、これらの桁は、機械本体に順列順にマークされていた。

以下の関数は、チェックデジットを含むカード番号を整数の配列として受け取り、チェックデジットが正しい場合はtrue 、そうでない場合はfalseを出力します。

function isValid(cardNumber[1..length]) 合計 := 0 パリティ := 長さ mod 2 iを1 から (length - 1) まで繰り返す。もしi mod 2 == parityならば、 sum := sum + cardNumber[i] elseif cardNumber[i] > 4 then sum := sum + 2 * cardNumber[i] - 9 それ以外 sum := sum + 2 * cardNumber[i] end if end for return cardNumber[length] == ((10 - (sum mod 10)) mod 10) end function

Luhnアルゴリズムは、以下のようなさまざまなシステムで使用されています。

• クレジットカード番号
• IMEI番号
• 北米金融商品のCUSIP番号
• 米国の国民医療提供者識別番号
• カナダの社会保険番号
• イスラエルのID番号
• 南アフリカのID番号
• 南アフリカの納税者番号
• スウェーデンの個人識別番号
• スウェーデンの法人識別番号（OrgNr）
• ギリシャの社会保障番号 (ΑΜΚΑ)
• SIMカードのICCID
• 欧州特許出願番号
• マクドナルド、タコベル、トラクターサプライ社のレシートに記載されているアンケートコード
• 米国郵便公社の荷物追跡番号は、修正されたLuhnアルゴリズムを使用しています^{[ 3 ]}
• イタリアの VAT 番号 ( Partita Iva ) ^{[ 4 ]}

• Rosetta Codeにおけるクレジットカード番号のLuhnアルゴリズムテスト： 2024年7月22日時点で160のプログラミング言語におけるLuhnアルゴリズム／数式の実装