Luhn mod N -algoritmi - Luhn mod N algorithm

Luhn mod N-algoritmi on laajennus Luhn algoritmi (tunnetaan myös nimellä mod 10 algoritmi), jonka avulla se työtä arvosekvenssien tahansa emäs . Tästä voi olla hyötyä, kun tarkistusnumero tarvitaan kirjaimista, kirjainten ja numeroiden yhdistelmästä tai mistä tahansa mielivaltaisesta N merkistä koostuvan tunnistemerkkijonon vahvistamiseksi.

Epävirallinen selitys

Luhn mod N -algoritmi luo tarkistusnumeron (tarkemmin tarkistusmerkin) samalla alueella kelvollisia merkkejä kuin syöttömerkkijono. Esimerkiksi, jos algoritmia käytetään pieniä kirjaimia sisältävään merkkijonoon ( a - z ), tarkistusmerkki on myös pieni kirjain. Tämän eron lisäksi se muistuttaa hyvin läheisesti alkuperäistä algoritmia.

Laajennuksen pääajatuksena on, että koko kelvollisten syötemerkkien joukko yhdistetään luetteloon koodipisteitä (ts. Peräkkäisiä kokonaislukuja, jotka alkavat nollasta). Algoritmi käsittelee syötemerkkijonon muuntamalla jokaisen merkin siihen liittyvään koodipisteeseen ja suorittamalla sitten laskelmat mod N: ssä (missä N on kelvollisten syötemerkkien lukumäärä). Lopuksi tuloksena oleva tarkistuskoodipiste kartoitetaan takaisin vastaavan tarkistusmerkin saamiseksi.

Merkkien yhdistäminen koodipisteisiin

Aluksi on luotava kartoitus kelvollisten syötemerkkien ja koodipisteiden välillä. Ajattele esimerkiksi, että kelvolliset merkit ovat pieniä kirjaimia a: sta f: hen . Siksi sopiva kartoitus olisi:

Huomaa, että merkkien järjestys on täysin merkityksetön. Tämä muu kartoitus olisi myös hyväksyttävä (vaikkakin mahdollisesti hankalampi toteuttaa):

On myös mahdollista sekoittaa kirjaimia ja numeroita (ja mahdollisesti jopa muita merkkejä). Esimerkiksi tämä kartoitus sopisi pienille kirjaimille heksadesimaaliluvuille:

C # -algoritmi

Olettaen, että seuraavat toiminnot on määritelty:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

Tarkistusmerkin luominen on seuraava toiminto:

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

Ja merkkijonon vahvistus (tarkistusmerkin ollessa viimeinen merkki) on:

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-algoritmi

Olettaen, että seuraavat toiminnot on määritelty:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

Tarkistusmerkin luominen on seuraava toiminto:

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

Ja merkkijonon vahvistus (tarkistusmerkin ollessa viimeinen merkki) on:

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

Algoritmi JavaScriptissä

Olettaen, että seuraavat toiminnot on määritelty:

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

Tarkistusmerkin luominen on seuraava toiminto:

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

Ja merkkijonon vahvistus (tarkistusmerkin ollessa viimeinen merkki) on:

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

Esimerkki

Sukupolvi

Harkitse yllä olevaa kelvollisten syötemerkkien joukkoa ja esimerkki syötemerkkijonosta abcdef . Luo tarkistusmerkki aloittamalla merkkijonon viimeisestä merkistä ja siirtymällä vasemmalle kaksinkertaistamalla kaikki muut koodipisteet. Koodipisteiden "numerot", jotka on kirjoitettu tukiasemaan 6 (koska kelvollisia syötemerkkejä on 6), tulee sitten laskea yhteen:

Numeroiden kokonaissumma on 14 (0 + 2 + 2 + 1 + 4 + 5). Numero, joka on lisättävä seuraavan 6: n kerrannaisen (tässä tapauksessa 18 ) saamiseksi, on 4 . Tämä on tuloksena oleva tarkistuskoodipiste. Tähän liittyvä tarkistusmerkki on e .

Vahvistus

Tuloksena oleva merkkijono abcdefe voidaan sitten vahvistaa samanlaisella menettelyllä:

Numeroiden kokonaissumma on 18 . Koska se on jaettavissa 6: lla, tarkistusmerkki on kelvollinen .

Toteutus

Merkkien yhdistäminen koodipisteisiin ja takaisin voidaan toteuttaa monin tavoin. Yksinkertaisin lähestymistapa (samanlainen kuin alkuperäinen Luhn-algoritmi) on käyttää ASCII-koodiaritmetiikkaa. Esimerkiksi, kun syötesarja on 0 - 9 , koodipiste voidaan laskea vähentämällä '0: n' ASCII-koodi halutun merkin ASCII-koodista. Käänteinen toiminta antaa käänteisen kartoituksen. Muita merkistöjä voidaan käsitellä ehdollisten lauseiden avulla.

Ei-peräkkäiset sarjat voidaan kartoittaa molempiin suuntiin käyttämällä kovakoodattua kytkintä / tapauslauseketta. Joustavampi lähestymistapa on käyttää jotain vastaavaa kuin assosiatiivinen taulukko . Jotta tämä toimisi, tarvitaan kaksi matriisiparia kaksisuuntaisen kartoituksen aikaansaamiseksi.

Lisämahdollisuus on käyttää merkistöä, jossa taulukkoindeksit ovat kuhunkin merkkiin liittyviä koodipisteitä. Kartoitus merkistä koodipisteeseen voidaan sitten suorittaa lineaarisella tai binäärisellä haulla. Tässä tapauksessa käänteinen kartoitus on vain yksinkertainen taulukon haku.

Heikkous

Tämä laajennus on samaa heikkous kuin alkuperäinen algoritmi, eli se ei voi havaita osaksi sekvenssin <ensimmäisen voimassa-merkki> <viime voimassa-merkki> ja <viimeksi voimassa-merkki> <ensimmäisen voimassa-merkki> (tai päinvastoin). Tämä vastaa 09: n ja 90: n välistä siirtämistä (olettaen, että joukko kelvollisia syötemerkkejä on 0 - 9 järjestyksessä). Positiivinen asia on, että mitä suurempi kelvollisten syötemerkkien joukko, sitä pienempi heikkouden vaikutus.

Katso myös

• Kansainvälinen arvopaperien tunnistenumero (ISIN)