ルーンアルゴリズム
シンプルなチェックサムの式

LuhnアルゴリズムまたはLuhn式（作成者：IBMの科学者Hans Peter Luhn）は、「モジュラス10」または「mod 10」アルゴリズムとしても知られ、さまざまな識別番号を検証するために使用される単純なチェックディジット式です。 [a]その目的は、人間が数字を入力するときにコンピューターがすぐにエラーをチェックできるように番号体系を設計することです。

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

説明

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

  1. 番号からチェックディジットを削除します（既に存在する場合）。これでペイロードが残ります。
  2. ペイロードの桁から始めます。右から左へ進み、最後の桁から始めて、2桁目ごとに2倍にします。ある桁を2倍にした値が9を超える場合は、その桁から9を引きます（または、その桁の桁を合計します）。
  3. 結果の数字をすべて合計します（2 倍にならなかった数字も含む）。
  4. チェックデジットは で計算されます。ここで、 s は手順3の合計です。これは、 に加算して10の倍数にするために必要な最小の数値（ゼロの場合もあります）です。同じ値を与える他の有効な式は、 、、です。モジュロ演算における負数の扱い方の違いにより、この式はすべての環境で機能するとは限りません。 （ 10 − （ s モッド 1 0 ） ） モッド 1 0 {\displaystyle (10-(s{\bmod {1}}0)){\bmod {1}}0} s {\displaystyle s} 9 − （ （ s + 9 ） モッド 1 0 ） {\displaystyle 9-((s+9){\bmod {1}}0)} （ 10 − s ） モッド 1 0 {\displaystyle (10-s){\bmod {1}}0} 10 ⌈ s / 10 ⌉ − s {\displaystyle 10\lceil s/10\rceil -s} （ 10 − s ） モッド 1 0 {\displaystyle (10-s){\bmod {1}}0}

チェックディジットの計算例

口座番号 1789372997 の例を考えてみましょう (「ペイロード」のみ、チェック ディジットはまだ含まれていません)。

数字が逆さま 7 9 9 2 7 3 9 8 7 1
乗数 2 1 2 1 2 1 2 1 2 1
＝ ＝ ＝ ＝ ＝ ＝ ＝ ＝ ＝ ＝
14 9 18 2 14 3 18 8 14 1
数字の合計 5
(1+4) 		9
  		9
(1+8) 		2
  		5
(1+4) 		3
  		9
(1+8) 		8
  		5
(1+4) 		1
 

結果の数字の合計は 56 です。

チェックディジットは と等しいです。 （ 10 − （ 56 モッド 1 0 ） ） モッド 1 0 ＝ 4 {\displaystyle (10-(56{\bmod {1}}0)){\bmod {1}}0=4}

これにより、完全なアカウント番号は 17893729974 になります。

チェックディジットの検証例

  1. 検証する番号のチェックディジット（最後の桁）を削除します。（例：17893729974 → 1789372997）
  2. チェックデジットを計算する（上記参照）
  3. 計算結果を元のチェックデジットと比較します。両方の数値が一致する場合、結果は有効です。(例: (givenCheckDigit = calculatedCheckDigit) ⇔ (isValidCheckDigit))。

強みと弱み

Luhnアルゴリズムは、すべての1桁のエラーと、隣接する桁のほぼすべての転置を検出します。ただし、09から90 （またはその逆）の2桁の転置は検出しません。ただし、 22 ↔ 55、33 ↔ 66 、 44 ↔ 77といった2桁のエラーは検出しません。

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

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

このアルゴリズムは、チェックサムを計算するための簡素な携帯型機械装置に関する米国特許[1]に登場しました。この装置は、10を法とする和を機械的な手段で計算します。置換桁、つまり倍精度演算と縮約演算の結果は機械的に生成されるのではなく、機械本体に桁の順序が入れ替えられた状態で刻印されています。

擬似コードの実装

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

関数isValid(cardNumber[1..length])
    合計 := 0
    パリティ := 長さ mod 2
    i が 1 から (長さ - 1) までの場合、 i mod 2 == parityならば
        
            合計 := 合計 + カード番号[i]
        そうでない場合、 cardNumber[i] > 4 の場合
            合計 := 合計 + 2 * カード番号[i] - 9
        それ以外
            合計 := 合計 + 2 * カード番号[i]
        end if 
    end for 
    return cardNumber[length] == ((10 - (sum mod 10)) mod 10)
関数の終了

用途

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

参考文献

  1. ^ ab 米国特許 2950048A、Luhn、Hans Peter、「数値検証用コンピュータ」、1960年8月23日公開、1960年8月23日発行 
  2. ^ 「附属書B：モジュラス10の「ダブル・アド・ダブル」チェックディジットの計算のためのLuhn式」。身分証明書 - 発行者の識別 - パート1：番号体系（標準）。国際標準化機構（ISO）および国際電気標準会議（IETC）。2017年1月。ISO /IEC 7812 -1:2017。
  3. ^ 出版物199：確認サービスおよび電子決済システムのためのインテリジェント・メール・パッケージ・バーコード（IMpb）実装ガイド（PDF）（第28版）。米国：米国郵政公社。2023年10月10日。2023年11月17日時点のオリジナルよりアーカイブ（PDF） 。 2023年11月29日閲覧。
  4. ^ Albanese, Ilenia (2022年8月10日). "A cosa serve la Partita Iva? Ecco cosa sapere" [VAT番号の用途は？知っておくべきこと]. Partitaiva.it (イタリア語). 2024年6月29日時点のオリジナルよりアーカイブ。 2024年6月29日閲覧。

注記

  1. ^ これは1960年8月23日に付与された米国特許2950048Aに記載されている。[1]
  • Rosetta Codeにおけるクレジットカード番号の Luhn テスト: 2024 年 7 月 22 日現在、160 のプログラミング言語における Luhn アルゴリズム/式の実装[参照]
「https://en.wikipedia.org/w/index.php?title=Luhn_algorithm&oldid=1321323834」より取得