ルーンアルゴリズム

ルーンアルゴリズムまたはルーン式は、「モジュラス10」または「mod 10」アルゴリズムとも呼ばれ、その作成者であるIBMの科学者ハンス・ピーター・ルーンにちなんで名付けられ、さまざまな識別番号を検証するために使用される単純なチェックディジット式です。これは、1960年8月23日に付与された米国特許2950048Aに記載されています。^[1]

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

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

1. 番号にすでにチェック ディジットが含まれている場合は、その桁を削除して「ペイロード」を形成します。チェック ディジットは、ほとんどの場合、最後の桁になります。
2. ペイロードでは、右端の桁から開始します。左に移動しながら、2 桁目ごとに (右端の桁を含む) 値を 2 倍にします。
3. 結果の数字の値を合計します。
4. チェック ディジットは で計算されます。ここで、 は手順 3 の合計です。これは、 に加えて10 の倍数にする必要がある最小の数値 (ゼロの場合もあります) です。同じ値を返す他の有効な式は、、 、 です。モジュロ演算による負数の扱い方の違いにより、この式はすべての環境で機能するわけではないことに注意してください。${\displaystyle (10-(s{\bmod {1}}0))}$${\displaystyle s}$${\displaystyle 9-((s+9){\bmod {1}}0)}$${\displaystyle (10-s){\bmod {1}}0}$${\displaystyle 10\lceil s/10\rceil -s}$${\displaystyle (10-s){\bmod {1}}0}$

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

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

チェックディジットは と等しいです。 ${\displaystyle (10-(56\operatorname {mod} 10))=4}$

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

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

Luhn アルゴリズムは、すべての 1 桁のエラーと、隣接する桁のほぼすべての転置を検出します。ただし、2 桁のシーケンス09から90 (またはその逆) の転置は検出しません。考えられる双子エラーのほとんどを検出します (22 ↔ 55、33 ↔ 66 、または44 ↔ 77は検出しません)。

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

アルゴリズムは数字を右から左に処理し、ゼロの数字は位置のずれを引き起こす場合にのみ結果に影響するため、数字の文字列の先頭にゼロを埋め込んでも計算には影響しません。したがって、特定の桁数に埋め込むシステム (たとえば、1234 を 0001234 に変換する) では、埋め込む前または埋め込んだ後に Luhn 検証を実行して、同じ結果を得ることができます。

このアルゴリズムは、チェックサムを計算するためのシンプルで手持ち式の機械装置に関する米国特許^{[1]に登場しました。この装置は機械的な手段で mod 10 の合計を計算しました。}置換桁、つまり倍数化と減算の手順の結果は機械的に生成されたものではありません。むしろ、桁は機械本体に順序を変えてマークされていました。

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

関数isValid(cardNumber[1..length])
    合計:= 0
    パリティ := 長さ mod 2
    iが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))
関数の終了

luhn?:関数[ n ][  
    秒: 0 
    ds:数字n  
    パリティ: (サイズds ) % 2    
    loop .with: 'i ds ' d [    
        スイッチパリティ<> i % 2 [      
            s: s + d   
        ][
            スイッチd > 4 [    
                s: s + ( 2 * d ) - 9       
            ][
                s: s + 2 * d     
            ]
        ]
    ]
    戻り値(最後のds ) = ( 10 - s % 10 ) % 10          
]

bool IsValidLuhn ( int []桁数)  
{
    チェックディジット= 0 ;   
    for ( int i =数字.長さ- 2 ; i >= 0 ; -- i )          
    {
        チェックディジット+= 
            ( i & 1 ) == (桁数.長さ& 1 )      
                ?数字[ i ] > 4 ?数字[ i ] * 2 - 9 :数字[ i ] * 2             
                :数字[ i ]; 
    }

    戻り値( 10 - checkDigit % 10 ) % 10 ==桁数[ ^ 1 ];         
}

パブリック静的ブール値isValidLuhn (文字列数値) {     
    int n =数値.長さ();   
    整数合計= 0 ;   
    ブール値even = true ;   
    // 右から左へ繰り返し、すべての「偶数」の値を2倍にする
    ( int i = n - 2 ; i > = 0 ; i -- ) {           
        int digit =数値.charAt ( i ) - '0 ' ;     
        if (数字< 0 ||数字> 9 ) {        
            // 値には数字のみを含めることができます
            falseを返します。 
        }
        もしも（偶数）{  
            digit <<= 1 ; // double 値   
        }
        偶数= !偶数;  
        合計+=数字> 9 ?数字- 9 :数字;          
    }
    intチェックサム=数値. charAt ( n - 1 ) - '0' ;       
    return (合計+チェックサム) % 10 == 0 ;       
}

関数luhnCheck (入力:数値) :ブール値{    
  const cardNumber =入力.toString ( );   
  const digits = cardNumber . replace ( /\D/g , '' ). split ( '' ). map ( Number );    
  合計を0とします。   
  isSecond = falseとします。   
  for ( i =数字.長さ- 1とします; i >= 0 ; i -- ) {           
    digit = digits [ i ]とします。   
    if ( isSecond ) {  
      数字* = 2 ;  
      if (数字> 9 ) {    
        数字-= 9 ;  
      }
    }
    合計+=数字;  
    isSecond = ! isSecond ;  
  }
  合計% 10 === 0を返します。     
}

関数luhnCheck (入力) {  
  const数値=入力.toString ( );   
  const digits = number . replace ( /\D/g , "" ). split ( "" ). map ( Number );    
  合計を0とします。   
  isSecond = falseとします。   
  for ( i =数字.長さ- 1とします; i >= 0 ; i -- ) {           
    digit = digits [ i ]とします。   
    if ( isSecond ) {  
      数字* = 2 ;  
      if (数字> 9 ) {    
        数字-= 9 ;  
      }
    }
    合計+=数字;  
    isSecond = ! isSecond ;  
  }
  合計% 10 === 0を返します。     
}

「チェックサム桁計算のための Verhoeff アルゴリズムの実装」


クラス LuhnAlgorithm ( BaseChecksumAlgorithm ):
    「」
    Luhn アルゴリズムを使用して数値を検証するクラス。

    引数:
        input_value (str): 検証する入力値。

    戻り値:
        bool: 数値が有効な場合は True、そうでない場合は False。
    「」
    def  __init__ ( self 、 input_value :  str )  ->  None :
        self.input_value = input_value.replace ( ' ' , '' )を置き換えます。   

    def  last_digit_and_remaining_numbers ( self )  -> タプル:
        「最後の桁と残りの数字を返します」
         int ( self . input_value [ - 1 ]) を返す、 self . input_value [: - 1 ]

    def  __checksum ( self )  ->  int :
        最後の桁、 残りの数字 =  self.last_digit_and_remaining_numbers ( )
        nums  =  [ int ( num )  if  idx  %  2  !=  0  else  int ( num )  *  2  if  int ( num )  *  2  <=  9
                そうでない場合 int (数値)  *  2  %  10  +  int (数値)  *  2  //  10
                idx  、numのenumerate (逆順(残りの数))]   

        戻り値 (合計(数値)  + 最後の桁)  %  10  ==  0

    def  verify ( self )  ->  bool :
        「Luhn アルゴリズムを使用して数値を検証する」
         自分自身を返します。__ checksum ()

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

• クレジットカード番号
• IMEI番号
• 米国の国家プロバイダー識別番号
• カナダの 社会保険番号
• イスラエルのID番号
• 南アフリカのID番号
• 南アフリカの納税参照番号
• スウェーデンの 国民識別番号
• スウェーデンの法人番号 (OrgNr)
• ギリシャ社会保障番号 (ΑΜΚΑ)
• SIMカードのICCID
• 欧州特許出願番号
• マクドナルド、タコベル、トラクターサプライ社のレシートに記載されている調査コード
• 米国郵便公社の荷物追跡番号は改良されたルーンアルゴリズムを使用している^[4]
• イタリアのVAT番号（Partita Iva）^[5]

• Rosetta Codeでのクレジットカード番号の Luhn テスト: 2024 年 7 月 22 日現在、160 のプログラミング言語での Luhn アルゴリズム/式の実装^[ref]