Luhnアルゴリズム

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

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

説明

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

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

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

口座番号1789372997（「ペイロード」のみ、チェックデジットはまだ含まれていない）の例を想定します。

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

チェックディジットはです $(10-(56{\bmod {1}}0)){\bmod {1}}0=4$

これにより、口座番号全体は17893729974になります。

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

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

長所と短所

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

Other, more complex check-digit algorithms (such as the Verhoeff algorithm and the Damm algorithm) can detect more transcription errors. The Luhn mod N algorithm is an extension that supports non-numerical strings.

Because the algorithm operates on the digits in a right-to-left manner and zero digits affect the result only if they cause shift in position, zero-padding the beginning of a string of numbers does not affect the calculation. Therefore, systems that pad to a specific number of digits (by converting 1234 to 0001234 for instance) can perform Luhn validation before or after the padding and achieve the same result.

The algorithm appeared in a United States Patent^[1] for a simple, hand-held, mechanical device for computing the checksum. The device took the mod 10 sum by mechanical means. The substitution digits, that is, the results of the double and reduce procedure, were not produced mechanically. Rather, the digits were marked in their permuted order on the body of the machine.

Pseudocode implementation

The following function takes a card number, including the check digit, as an array of integers and outputs true if the check digit is correct, false otherwise.

function isValid(cardNumber[1..length])
    sum := 0
    parity := length mod 2
    for i from 1 to (length - 1) do
        if i mod 2 == parity then
            sum := sum + cardNumber[i]
        elseif cardNumber[i] > 4 then
            sum := sum + 2 * cardNumber[i] - 9
        else
            sum := sum + 2 * cardNumber[i]
        end if
    end for
    return cardNumber[length] == ((10 - (sum mod 10)) mod 10)
end function

Uses

The Luhn algorithm is used in a variety of systems, including:

Credit card numbers
IMEI numbers
CUSIP numbers for North American financial instruments
National Provider Identifier numbers in the United States
Canadian social insurance numbers
Israeli ID numbers
South African ID numbers
South African Tax reference numbers
Swedish Personal identity numbers
Swedish Corporate Identity Numbers (OrgNr)
ギリシャの社会保障番号（AMC）
SIMカードのICCID
欧州特許出願番号
マクドナルド、タコベル、トラクターサプライ社のレシートに記載されている調査コード
米国郵便公社の荷物追跡番号は、修正されたLuhnアルゴリズムを使用しています^[3]
イタリアのVAT番号（Partita Iva）^[4]

参考文献

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

注釈

^ 1960年8月23日に付与された 米国特許2950048Aに記載されています。 ^[1]

外部リンク

Rosettaコードにおけるクレジットカード番号のLuhnテスト：2024年7月22日現在、160のプログラミング言語におけるLuhnアルゴリズム／式の実装^[ref]