Luhn mod N algoritması - Luhn mod N algorithm

Luhn mod N algoritması bir uzantısıdır Luhn algoritması herhangi değerlerin dizileri ile çalışmalarına izin verdiği (aynı zamanda mod 10 algoritması olarak da bilinir) bir baz . Bu, harflerden, bir harf ve rakam kombinasyonundan veya herhangi bir rastgele N karakter kümesinden oluşan bir kimlik dizisini doğrulamak için bir kontrol basamağı gerektiğinde yararlı olabilir.

Gayri resmi açıklama

Luhn mod N algoritması, giriş dizesi ile aynı geçerli karakterler aralığında bir kontrol basamağı (daha kesin olarak bir kontrol karakteri) üretir. Algoritma (küçük harflerle bir dizi tatbik edilir, örneğin, bir ile z ), kontrol karakteri, aynı zamanda, bir küçük harf olacaktır. Bu ayrımın dışında orijinal algoritmaya çok benziyor.

Uzantının arkasındaki ana fikir, geçerli girdi karakterlerinin tümünün bir kod noktaları listesine (yani, sıfır ile başlayan sıralı tamsayılar) eşleştirilmesidir. Algoritma, her bir karakteri ilişkili kod noktasına dönüştürerek ve ardından hesaplamaları N modunda gerçekleştirerek (burada N , geçerli giriş karakterlerinin sayısıdır) girdi dizgesini işler . Son olarak, elde edilen kontrol kodu noktası, karşılık gelen kontrol karakterini elde etmek için geri eşlenir.

Karakterleri kod noktalarına eşleme

Başlangıçta, geçerli giriş karakterleri ve kod noktaları arasında bir eşleme oluşturulmalıdır. Örneğin, geçerli karakterler küçük harfler uzak olduklarını düşünün bir etmek f . Bu nedenle, uygun bir eşleme şöyle olacaktır:

Karakterlerin sırasının tamamen alakasız olduğuna dikkat edin. Bu diğer eşleme de kabul edilebilir (uygulanması muhtemelen daha zahmetli olsa da):

Harfleri ve rakamları (ve hatta muhtemelen diğer karakterleri) karıştırmak da mümkündür. Örneğin, bu eşleme küçük harfli onaltılık basamaklar için uygun olacaktır:

C # 'ta Algoritma

Aşağıdaki işlevlerin tanımlandığını varsayarsak:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

Bir kontrol karakteri oluşturma işlevi şudur:

char GenerateCheckCharacter(string input)
{
    int factor = 2;
    int sum = 0;
    int n = NumberOfValidInputCharacters();

    // Starting from the right and working leftwards is easier since 
    // the initial "factor" will always be "2".
    for (int i = input.Length - 1; i >= 0; i--)
    {
        int codePoint = CodePointFromCharacter(input[i]);
        int addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = IntegerValue(addend / n) + (addend % n);
        sum += addend;
    }

    // Calculate the number that must be added to the "sum" 
    // to make it divisible by "n".
    int remainder = sum % n;
    int checkCodePoint = (n - remainder) % n;

    return CharacterFromCodePoint(checkCodePoint);
}

Ve bir dizeyi doğrulama işlevi (son karakter kontrol karakteri ile):

bool ValidateCheckCharacter(string input)
{
    int factor = 1;
    int sum = 0;
    int n = NumberOfValidInputCharacters();

    // Starting from the right, work leftwards
    // Now, the initial "factor" will always be "1" 
    // since the last character is the check character.
    for (int i = input.Length - 1; i >= 0; i--)
    {
        int codePoint = CodePointFromCharacter(input[i]);
        int addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = IntegerValue(addend / n) + (addend % n);
        sum += addend;
    }

    int remainder = sum % n;

    return (remainder == 0);
}

Java'da Algoritma

Aşağıdaki işlevlerin tanımlandığını varsayarsak:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

Bir kontrol karakteri oluşturma işlevi şudur:

char generateCheckCharacter(String input) {
    int factor = 2;
    int sum = 0;
    int n = numberOfValidInputCharacters();

    // Starting from the right and working leftwards is easier since
    // the initial "factor" will always be "2".
    for (int i = input.length() - 1; i >= 0; i--) {
        int codePoint = codePointFromCharacter(input.charAt(i));
        int addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = (addend / n) + (addend % n);
        sum += addend;
    }

    // Calculate the number that must be added to the "sum"
    // to make it divisible by "n".
    int remainder = sum % n;
    int checkCodePoint = (n - remainder) % n;

    return characterFromCodePoint(checkCodePoint);
}

Ve bir dizeyi doğrulama işlevi (son karakter kontrol karakteri ile):

boolean validateCheckCharacter(String input) {
    int factor = 1;
    int sum = 0;
    int n = numberOfValidInputCharacters();

    // Starting from the right, work leftwards
    // Now, the initial "factor" will always be "1"
    // since the last character is the check character.
    for (int i = input.length() - 1; i >= 0; i--) {
        int codePoint = codePointFromCharacter(input.charAt(i));
        int addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = (addend / n) + (addend % n);
        sum += addend;
    }

    int remainder = sum % n;

    return (remainder == 0);
}

JavaScript'te Algoritma

Aşağıdaki işlevlerin tanımlandığını varsayarsak:

const codePoints = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//This can be any string of permitted characters

function numberOfValidInputCharacters() {
    return codePoints.length;
}

function codePointFromCharacter(character) {
    return codePoints.indexOf(character);
}

function characterFromCodePoint(codePoint) {
    return codePoints.charAt(codePoint);
}

Bir kontrol karakteri oluşturma işlevi şudur:

function generateCheckCharacter(input) {
    let factor = 2;
    let sum = 0;
    let n = numberOfValidInputCharacters();

    // Starting from the right and working leftwards is easier since
    // the initial "factor" will always be "2".
    for (let i = input.length - 1; i >= 0; i--) {
        let codePoint = codePointFromCharacter(input.charAt(i));
        let addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = (Math.floor(addend / n)) + (addend % n);
        sum += addend;
    }

    // Calculate the number that must be added to the "sum"
    // to make it divisible by "n".
    let remainder = sum % n;
    let checkCodePoint = (n - remainder) % n;
    return characterFromCodePoint(checkCodePoint);
}

Ve bir dizeyi doğrulama işlevi (son karakter kontrol karakteri ile):

function validateCheckCharacter(input) {
    let factor = 1;
    let sum = 0;
    let n = numberOfValidInputCharacters();

    // Starting from the right, work leftwards
    // Now, the initial "factor" will always be "1"
    // since the last character is the check character.
    for (let i = input.length - 1; i >= 0; i--) {
        let codePoint = codePointFromCharacter(input.charAt(i));
        let addend = factor * codePoint;

        // Alternate the "factor" that each "codePoint" is multiplied by
        factor = (factor == 2) ? 1 : 2;

        // Sum the digits of the "addend" as expressed in base "n"
        addend = (Math.floor(addend / n)) + (addend % n);
        sum += addend;
    }
    let remainder = sum % n;
    return (remainder == 0);
}

Misal

Nesil

Yukarıdaki geçerli giriş karakterleri kümesini ve abcdef örnek giriş dizesini göz önünde bulundurun . Kontrol karakterini oluşturmak için dizedeki son karakterle başlayın ve her diğer kod noktasını iki katına çıkararak sola hareket edin. 6 tabanında yazılan kod noktalarının "rakamları" (çünkü 6 geçerli giriş karakteri olduğundan) özetlenmelidir:

Toplam basamak toplamı 14'tür (0 + 2 + 2 + 1 + 4 + 5). 6'nın bir sonraki katını (bu durumda 18 ) elde etmek için eklenmesi gereken sayı 4'tür . Bu, sonuçta ortaya çıkan kontrol kod noktasıdır. İlişkili kontrol karakteri e'dir .

Doğrulama

Elde edilen abcdefe dizisi daha sonra benzer bir prosedür kullanılarak doğrulanabilir:

Toplam basamak toplamı 18'dir . 6'ya bölünebildiği için kontrol karakteri geçerlidir .

Uygulama

Karakterlerin kod noktalarına ve geriye eşleştirilmesi çeşitli yollarla uygulanabilir. En basit yaklaşım (orijinal Luhn algoritmasına benzer) ASCII kod aritmetiğini kullanmaktır. Örneğin, 0'dan 9'a kadar bir girdi kümesi verildiğinde , kod noktası, istenen karakterin ASCII kodundan '0' için ASCII kodunu çıkararak hesaplanabilir. Tersine işlem, ters eşleme sağlayacaktır. Ek karakter aralıkları koşullu ifadeler kullanılarak ele alınabilir.

Sıralı olmayan kümeler, sabit kodlu bir anahtar / durum ifadesi kullanılarak her iki şekilde eşlenebilir . Daha esnek bir yaklaşım, ilişkisel diziye benzer bir şey kullanmaktır . Bunun çalışması için, iki yönlü haritalama sağlamak üzere bir çift dizi gereklidir.

Ek bir olasılık, dizi indekslerinin her karakterle ilişkili kod noktaları olduğu bir karakter dizisi kullanmaktır. Karakterden kod noktasına eşleştirme daha sonra doğrusal veya ikili arama ile gerçekleştirilebilir. Bu durumda, ters eşleme sadece basit bir dizi aramasıdır.

Zayıflık

Orijinal algoritma gibi bu uzantı hisseleri aynı zayıflık, yani o dizi aktarılması çalışmalarını algılayamaz <birinci geçerli-karakteri> <son geçerli karakterli> için <son geçerli karakter> <birinci geçerli karakterli> (ya da tam tersi). Bu aktarılması eşdeğerdir 09 için 90 (geçerli sinyalin karakter kümesi varsayarak , 0 ile 9 sırayla). Olumlu bir kayda göre, geçerli giriş karakterleri kümesi ne kadar büyükse, zayıflığın etkisi o kadar azdır.

Ayrıca bakınız

• Uluslararası Menkul Kıymetler Kimlik Numarası (ISIN)