Algorytm Luhna mod N - Luhn mod N algorithm

Algorytm Luhna mod n jest rozszerzeniem algorytmu Luhna (znany również jako mod 10) algorytm, który pozwala na pracę z sekwencji wartości w każdej bazy . Może to być przydatne, gdy cyfra kontrolna jest wymagana do sprawdzenia poprawności ciągu identyfikacyjnego składającego się z liter, kombinacji liter i cyfr lub dowolnego zestawu N znaków.

Nieformalne wyjaśnienie

Algorytm Luhn mod N generuje cyfrę kontrolną (a dokładniej znak kontrolny) w tym samym zakresie poprawnych znaków, co ciąg wejściowy. Na przykład, jeśli algorytm zostanie zastosowany do ciągu małych liter (od a do z ), znak kontrolny będzie również małą literą. Poza tym rozróżnieniem bardzo przypomina oryginalny algorytm.

Główną ideą rozszerzenia jest to, że pełny zestaw prawidłowych znaków wejściowych jest odwzorowywany na listę punktów kodowych (tj. Sekwencyjne liczby całkowite zaczynające się od zera). Algorytm przetwarza ciąg wejściowy, konwertując każdy znak na skojarzony z nim punkt kodowy, a następnie wykonując obliczenia w mod N (gdzie N to liczba prawidłowych znaków wejściowych). Na koniec wynikowy punkt kodowy kontrolny jest odwzorowywany z powrotem w celu uzyskania odpowiedniego znaku kontrolnego.

Mapowanie znaków na punkty kodowe

Na początku należy utworzyć mapowanie między prawidłowymi znakami wejściowymi a punktami kodowymi. Na przykład weźmy pod uwagę, że prawidłowe znaki to małe litery od a do f . Dlatego odpowiednim mapowaniem byłoby:

Zauważ, że kolejność znaków jest całkowicie nieistotna. To inne mapowanie również byłoby dopuszczalne (chociaż prawdopodobnie bardziej kłopotliwe w implementacji):

Możliwe jest również mieszanie liter i cyfr (a być może nawet innych znaków). Na przykład to mapowanie byłoby odpowiednie dla małych cyfr szesnastkowych:

Algorytm w C #

Zakładając, że zdefiniowano następujące funkcje:

int CodePointFromCharacter(char character) {...}

char CharacterFromCodePoint(int codePoint) {...}

int NumberOfValidInputCharacters() {...}

Funkcja generowania znaku kontrolnego to:

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

Funkcja sprawdzania poprawności ciągu (ze znakiem kontrolnym jako ostatnim znakiem) to:

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

Algorytm w Javie

Zakładając, że zdefiniowano następujące funkcje:

int codePointFromCharacter(char character) {...}

char characterFromCodePoint(int codePoint) {...}

int numberOfValidInputCharacters() {...}

Funkcja generowania znaku kontrolnego to:

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

Funkcja sprawdzania poprawności ciągu (ze znakiem kontrolnym jako ostatnim znakiem) to:

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

Algorytm w JavaScript

Zakładając, że zdefiniowano następujące funkcje:

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

Funkcja generowania znaku kontrolnego to:

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

Funkcja sprawdzania poprawności ciągu (ze znakiem kontrolnym jako ostatnim znakiem) to:

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

Przykład

Pokolenie

Rozważ powyższy zestaw prawidłowych znaków wejściowych i przykładowy ciąg wejściowy abcdef . Aby wygenerować znak kontrolny, zacznij od ostatniego znaku w ciągu i przesuń w lewo, podwajając co drugi punkt kodowy. „Cyfry” punktów kodowych zapisane w bazie 6 (ponieważ istnieje 6 ważnych znaków wejściowych) należy następnie zsumować:

Całkowita suma cyfr to 14 (0 + 2 + 2 + 1 + 4 + 5). Liczba, którą należy dodać, aby uzyskać kolejną wielokrotność 6 (w tym przypadku 18 ), to 4 . To jest wynikowy punkt kodowy sprawdzenia. Powiązany znak kontrolny to e .

Uprawomocnienie

Wynikowy ciąg abcdefe można następnie zweryfikować za pomocą podobnej procedury:

Łączna suma cyfr to 18 . Ponieważ jest podzielna przez 6, znak kontrolny jest ważny .

Realizacja

Odwzorowanie znaków na punkty kodowe iz powrotem można zaimplementować na wiele sposobów. Najprostszym podejściem (podobnym do oryginalnego algorytmu Luhna) jest użycie arytmetyki kodu ASCII. Na przykład, mając zestaw wejściowy od 0 do 9 , punkt kodowy można obliczyć, odejmując kod ASCII dla „0” od kodu ASCII żądanego znaku. Operacja odwrotna zapewni odwrotne odwzorowanie. Dodatkowe zakresy znaków można rozwiązać za pomocą instrukcji warunkowych.

Zestawy niesekwencyjne można odwzorowywać w obie strony za pomocą zakodowanej na stałe instrukcji switch / case . Bardziej elastycznym podejściem jest użycie czegoś podobnego do tablicy asocjacyjnej . Aby to zadziałało, wymagana jest para tablic, aby zapewnić dwukierunkowe mapowanie.

Dodatkową możliwością jest użycie tablicy znaków, gdzie indeksy tablic są punktami kodowymi związanymi z każdym znakiem. Mapowanie od znaku do punktu kodowego można następnie przeprowadzić za pomocą wyszukiwania liniowego lub binarnego. W tym przypadku odwrotne odwzorowanie jest po prostu prostym wyszukiwaniem tablicy.

Słabość

To rozszerzenie ma tę samą słabość co oryginalny algorytm, a mianowicie nie może wykryć transpozycji sekwencji <first-valid-character> <last-valid-character> do <last-valid-character> <first-valid-character> (lub odwrotnie). Jest to równoważne transpozycji od 09 do 90 (przy założeniu zestawu poprawnych znaków wejściowych od 0 do 9 w kolejności). Z drugiej strony, im większy zestaw prawidłowych znaków wejściowych, tym mniejszy wpływ słabości.

Zobacz też

• Międzynarodowy numer identyfikacyjny papierów wartościowych (ISIN)