ルーンアルゴリズム計算機

はじめに

ルーンアルゴリズムは、「モジュラス10」または「モッド10」アルゴリズムとしても知られ、クレジットカード番号、カナダの社会保障番号、IMEI番号、アメリカ合衆国の国家提供者識別番号など、さまざまな識別番号を検証するために使用されるシンプルなチェックサムの公式です。この計算機を使用して、ルーンアルゴリズムを使用して番号を検証し、ルーンチェックを通過する有効な番号を生成することができます。

ルーンアルゴリズムの仕組み

ルーンアルゴリズムは次のように機能します：

右端の数字（チェックデジットを除く）から始めて、左に移動し、2番目の数字の値を2倍にします。
この倍加操作の結果が9を超える場合は、結果から9を引きます。
得られた数列のすべての数字を合計します。
合計のモジュロ10が0に等しい場合（合計が0で終わる場合）、その番号はルーン公式に従って有効であり、そうでない場合は無効です。

以下は、ルーンアルゴリズムの視覚的表現です：

数式

ルーンアルゴリズムは次のように数学的に表現できます：

$d_i$ を右端の $i$ 番目の数字（チェックデジットを除く）として数え、左に移動します。次に、チェックデジット $d_0$ は次のように選択されます：

$(2d_{2n} \bmod 9 + d_{2n-1} + 2d_{2n-2} \bmod 9 + d_{2n-3} + \cdots + 2d_2 \bmod 9 + d_1 + d_0) \bmod 10 = 0$

ここで、 $\bmod$ はモジュロ操作です。

使用例

ルーンアルゴリズムには、さまざまな分野での応用があります：

クレジットカードの検証：ほとんどのクレジットカード番号はルーンアルゴリズムを使用して検証されます。
カナダの社会保障番号：ルーンアルゴリズムは、これらの識別番号の有効性を検証するために使用されます。
IMEI番号：携帯電話のIMEI番号は、ルーンアルゴリズムで検証されるチェックデジットを含みます。
国家提供者識別番号（NPI）番号：アメリカの医療システムで使用されるこれらの番号は、ルーンアルゴリズムを使用して検証されます。
ISBN：一部のISBN-10番号は、検証のためにルーンアルゴリズムの変種を使用します。

代替手段

ルーンアルゴリズムは広く使用されていますが、さまざまな目的のために他のチェックサムアルゴリズムもあります：

ダムアルゴリズム：すべての1桁のエラーとすべての隣接転置エラーを検出する別のチェックデジットアルゴリズム。
ヴェルホーフアルゴリズム：すべての1桁のエラーとほとんどの転置エラーを捕捉するより複雑なチェックサムアルゴリズム。
ISBN-13チェックデジット：ISBN-10とは異なるアルゴリズムを使用し、ルーンアルゴリズムに基づいています。

歴史

ルーンアルゴリズムは、1954年にIBMのコンピュータ科学者ハンス・ピーター・ルーンによって作成されました。ルーンは情報科学の分野の先駆者であり、KWIC（キーワードインコンテキスト）インデックスシステムを含むいくつかの革新を行ったことで知られています。

このアルゴリズムは、悪意のある攻撃ではなく、偶発的なエラーから保護するために設計されました。ルーンアルゴリズムは多くの一般的なエラーを検出できますが、安全な暗号化形式ではなく、データセキュリティ目的で依存すべきではないことに注意することが重要です。

その年齢にもかかわらず、ルーンアルゴリズムはその単純さと一般的な転写エラーを捕捉する効果的な方法のために広く使用されています。

実装例

さまざまなプログラミング言語でルーンアルゴリズムを実装するためのコード例を以下に示します：

import random

def luhn_validate(number):
    digits = [int(d) for d in str(number)]
    checksum = 0
    for i in range(len(digits) - 1, -1, -1):
        d = digits[i]
        if (len(digits) - i) % 2 == 0:
            d = d * 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def generate_valid_number(length):
    digits = [random.randint(0, 9) for _ in range(length - 1)]
    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
    check_digit = (10 - (checksum % 10)) % 10
    return int(''.join(map(str, digits + [check_digit])))

## 使用例：
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # 有効な16桁の番号を生成

function luhnValidate(number) {
    const digits = number.toString().split('').map(Number);
    let checksum = 0;
    for (let i = digits.length - 1; i >= 0; i--) {
        let d = digits[i];
        if ((digits.length - i) % 2 === 0) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        checksum += d;
    }
    return checksum % 10 === 0;
}

function generateValidNumber(length) {
    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
    const checksum = digits.reduce((sum, digit, index) => {
        if ((length - 1 - index) % 2 === 0) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        return sum + digit;
    }, 0);
    const checkDigit = (10 - (checksum % 10)) % 10;
    return parseInt(digits.join('') + checkDigit);
}

// 使用例：
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // 有効な16桁の番号を生成

import java.util.Random;

public class LuhnValidator {
    public static boolean luhnValidate(long number) {
        String digits = String.valueOf(number);
        int checksum = 0;
        boolean isEven = true;
        for (int i = digits.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(digits.charAt(i));
            if (isEven) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
            isEven = !isEven;
        }
        return checksum % 10 == 0;
    }

    public static long generateValidNumber(int length) {
        Random random = new Random();
        long[] digits = new long[length - 1];
        for (int i = 0; i < length - 1; i++) {
            digits[i] = random.nextInt(10);
        }
        long checksum = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            long digit = digits[i];
            if ((length - 1 - i) % 2 == 0) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            checksum += digit;
        }
        long checkDigit = (10 - (checksum % 10)) % 10;
        long result = 0;
        for (long digit : digits) {
            result = result * 10 + digit;
        }
        return result * 10 + checkDigit;
    }

    public static void main(String[] args) {
        System.out.println(luhnValidate(4532015112830366L));  // true
        System.out.println(luhnValidate(4532015112830367L));  // false
        System.out.println(generateValidNumber(16));  // 有効な16桁の番号を生成
    }
}

エッジケースと特別な考慮事項

ルーンアルゴリズムを実装する際には、次のエッジケースと特別な考慮事項を考慮してください：

入力検証：入力が有効な数字文字列であることを確認します。非数字文字は適切に処理する必要があります（削除するか無効な入力として扱う）。
先頭のゼロ：先頭にゼロがある番号でも正しく動作する必要があります。
大きな数：一部のプログラミング言語では標準の整数型の容量を超える非常に長い番号を処理する準備をしてください。
空の入力：空の文字列やnull入力をどのように処理するかを定義します。
非標準文字セット：一部のアプリケーションでは、標準の0-9範囲外の文字で表現された番号に遭遇することがあります。これらをどのように処理するかを定義します。
パフォーマンスの考慮事項：大量の入力を迅速に検証する必要があるアプリケーションの場合、アルゴリズムの実装を最適化することを検討してください。

数値例

有効なクレジットカード番号：
- 番号：4532015112830366
- ルーンチェック：有効
無効なクレジットカード番号：
- 番号：4532015112830367
- ルーンチェック：無効
有効なカナダの社会保障番号：
- 番号：046 454 286
- ルーンチェック：有効
無効なIMEI番号：
- 番号：490154203237518
- ルーンチェック：無効

テストケース

ルーンアルゴリズムの実装を検証するために、次のテストケースを使用できます：

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # 生成された番号のテスト
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("すべてのテストが合格しました！")

test_luhn_algorithm()

参考文献

Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
Gallian, Joseph. "The Mathematics of Identification Numbers." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 194–202. JSTOR, www.jstor.org/stable/2686878.
"ISO/IEC 7812-1:2017". International Organization for Standardization. Retrieved August 2, 2024.
Knuth, Donald. "The Art of Computer Programming, Volume 2: Seminumerical Algorithms". Addison-Wesley, 1997.