Luhn mod N algoritmus - Luhn mod N algorithm

A Luhn mod N algoritmus a Luhn algoritmus (más néven mod 10 algoritmus) kiterjesztése, amely lehetővé teszi, hogy bármilyen bázis értéksorozataival dolgozzon . Ez akkor lehet hasznos, ha ellenőrző számra van szükség a betűkből, betűk és számok kombinációjából vagy tetszőleges N karakterből álló azonosító karakterlánc hitelesítéséhez.

Informális magyarázat

A Luhn mod N algoritmus egy ellenőrző számot (pontosabban egy ellenőrző karaktert) generál az érvényes karakterek ugyanazon tartományán belül, mint a beviteli karakterlánc. Például, ha az algoritmust kisbetűs ( a – z ) karakterláncokra alkalmazzák, akkor az ellenőrző karakter kisbetű is lesz. Ezen a különbségtételen kívül nagyon hasonlít az eredeti algoritmusra.

A kiterjesztés alapgondolata az, hogy az érvényes beviteli karakterek teljes készletét leképezzük a kódpontok (azaz a nullával kezdődő szekvenciális egész számok) listájára. Az algoritmus úgy dolgozza fel a bemeneti karakterláncot, hogy minden karaktert átalakít a hozzá tartozó kódponthoz, majd elvégzi a számításokat az N modban (ahol N az érvényes beviteli karakterek száma). Végül a kapott ellenőrző kódpontot visszaképezzük a megfelelő ellenőrző karakter megszerzéséhez.

Karakterek hozzárendelése kódpontokhoz

Először létre kell hozni az érvényes beviteli karakterek és a kódpontok leképezését. Vegyük például, hogy az érvényes karakter a kisbetűvel származó egy a f . Ezért megfelelő térképezés lenne:

Vegye figyelembe, hogy a karakterek sorrendje teljesen lényegtelen. Ez a másik leképezés is elfogadható (bár esetleg nehezebb megvalósítani):

Lehetőség van betűk és számjegyek (és esetleg más karakterek) keverésére is. Például ez a leképezés megfelelő lenne kisbetűs hexadecimális számjegyekhez:

Algoritmus a C # számban

Feltéve, hogy a következő funkciók vannak meghatározva:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

Az ellenőrző karakter létrehozásának funkciója:

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);
}

A karaktersorozat (a check karakterrel utolsó karakterként) érvényesítésének funkciója:

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);
}

Algoritmus Java-ban

Feltéve, hogy a következő funkciók vannak meghatározva:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

Az ellenőrző karakter létrehozásának funkciója:

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);
}

A karaktersorozat (a check karakterrel utolsó karakterként) érvényesítésének funkciója:

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);
}

Algoritmus a JavaScript-ben

Feltéve, hogy a következő funkciók vannak meghatározva:

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);
}

Az ellenőrző karakter létrehozásának funkciója:

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);
}

A karaktersorozat (a check karakterrel utolsó karakterként) érvényesítésének funkciója:

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);
}

Példa

Generáció

Tekintsük a fenti érvényes beviteli karaktereket és az abcdef beviteli karakterláncot . Az ellenőrző karakter előállításához kezdje a karakterlánc utolsó karakterével, és lépjen balra duplázva minden más kódpontot. Ezután össze kell foglalni a 6. pontban leírt kódpontok "számjegyeit" (mivel 6 érvényes beviteli karakter van):

A számjegyek összege 14 (0 + 2 + 2 + 1 + 4 + 5). A szám, amelyet hozzá kell adni a következő 6-os (ebben az esetben 18 ) többszöröséhez, 4 . Ez az eredményül kapott ellenőrző kód-pont. A kapcsolódó ellenőrző karakter e .

Érvényesítés

Az így kapott abcdefe karakterlánc ezután egy hasonló eljárással érvényesíthető:

A számjegyek összege 18 . Mivel osztható 6-tal, az ellenőrző karakter érvényes .

Végrehajtás

A karakterek hozzárendelése a kódpontokhoz és a visszafelé számos módon megvalósítható. A legegyszerűbb megközelítés (az eredeti Luhn-algoritmushoz hasonlóan) az ASCII kód-aritmetika használata. Például 0 és 9 közötti beviteli halmaz esetén a kódpont kiszámítható úgy, hogy kivonja a „0” ASCII kódját a kívánt karakter ASCII kódjából. A fordított művelet biztosítja a fordított leképezést. További karaktertartományok kezelhetők feltételes utasítások használatával.

A nem szekvenciális halmazok mindkét irányba leképezhetők egy hard-kódolt switch / case utasítás segítségével. Rugalmasabb megközelítés az asszociatív tömbhöz hasonló dolog használata . Ennek működéséhez pár tömbre van szükség a kétirányú leképezéshez.

További lehetőség a karakterek tömbjének használata, ahol a tömbindexek az egyes karakterekhez társított kódpontok. Ezután a karakterről kódpontra történő leképezés lineáris vagy bináris kereséssel végezhető el. Ebben az esetben a fordított leképezés csak egy egyszerű tömbkeresés.

Gyengeség

Ez a kiterjesztés ugyanazokkal a gyengeség, mint az eredeti algoritmus, azaz, hogy nem ismeri fel az átültetés a sorozat <első érvényes karakteres> <utolsó érvényes karakteres> a <utolsó érvényes karakteres> <első érvényes karakteres> (Vagy fordítva). Ez egyenértékű átültetése 09 és a 90 (feltételezve, hogy egy sor érvényes bemeneti karakterek 0 és 9- sorrendben). Pozitívum, hogy minél nagyobb az érvényes beviteli karakterkészlet, annál kisebb a gyengeség hatása.

Lásd még

• Nemzetközi értékpapír-azonosító szám (ISIN)