Luhn-algoritme Kalkulator

Luhn-algoritmen kalkulator

Innledning

Luhn-algoritmen, også kjent som "modulus 10" eller "mod 10" algoritmen, er en enkel sjekksumformel som brukes til å validere en rekke identifikasjonsnumre, som kredittkortnumre, kanadiske personnummer, IMEI-numre og nasjonale leverandøridentifikasjonsnumre i USA. Denne kalkulatoren lar deg validere numre ved hjelp av Luhn-algoritmen og generere gyldige numre som passerer Luhn-sjekken.

Hvordan Luhn-algoritmen fungerer

Luhn-algoritmen fungerer som følger:

1. Start fra den høyre mest sifret (unntatt sjekk-sifret) og gå mot venstre, doble verdien av hvert andre siffer.
2. Hvis resultatet av denne doble operasjonen er større enn 9, trekk 9 fra resultatet.
3. Summer alle sifrene i den resulterende sekvensen.
4. Hvis totalen modulo 10 er lik 0 (hvis totalen ender med null), så er nummeret gyldig i henhold til Luhn-formelen; ellers er det ikke gyldig.

Her er en visuell representasjon av Luhn-algoritmen:

Formel

Luhn-algoritmen kan uttrykkes matematisk som følger:

La $d_i$ være det $i$-te sifferet, teller fra det høyre mest sifferet (unntatt sjekk-sifret) og beveger seg mot venstre. Da velges sjekk-sifferet $d_0$ slik at:

$(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$

Hvor $\bmod$ er modulo-operasjonen.

Bruksområder

Luhn-algoritmen har ulike applikasjoner i forskjellige felt:

1. Kredittkortvalidering: De fleste kredittkortnumre valideres ved hjelp av Luhn-algoritmen.
2. Kanadiske personnummer: Luhn-algoritmen brukes til å verifisere gyldigheten av disse identifikasjonsnumrene.
3. IMEI-numre: Mobiltelefon IMEI-numre inkluderer et sjekk-siffer validert av Luhn-algoritmen.
4. Nasjonale leverandøridentifikasjonsnumre (NPI): Brukt i det amerikanske helsevesenet, disse numrene valideres ved hjelp av Luhn-algoritmen.
5. ISBN: Noen ISBN-10-numre bruker en variant av Luhn-algoritmen for validering.

Alternativer

Selv om Luhn-algoritmen er mye brukt, finnes det andre sjekksum-algoritmer for forskjellige formål:

1. Damm-algoritmen: En annen sjekk-siffer algoritme som oppdager alle enkelt-digit feil og alle nabotransposisjonsfeil.
2. Verhoeff-algoritmen: En mer kompleks sjekk-siffer algoritme som fanger opp alle enkelt-digit feil og de fleste transposisjonsfeil.
3. ISBN-13 sjekk-siffer: Bruker en annen algoritme enn ISBN-10, som er basert på Luhn-algoritmen.

Historie

Luhn-algoritmen ble laget av Hans Peter Luhn, en IBM-datavitenskapsmann, i 1954. Luhn var en pioner innen informasjonsteknologi og er kreditert med flere innovasjoner, inkludert KWIC (Key Word In Context) indekseringssystemet.

Algoritmen ble opprinnelig designet for å beskytte mot utilsiktede feil, ikke ondsinnede angrep. Det er viktig å merke seg at selv om Luhn-algoritmen kan oppdage mange vanlige feil, er det ikke en sikker form for kryptering og bør ikke stole på for databeskyttelsesformål.

Til tross for sin alder, forblir Luhn-algoritmen mye brukt på grunn av sin enkelhet og effektivitet i å fange opp vanlige transkripsjonsfeil.

Implementeringseksempler

Her er noen kodeeksempler for å implementere Luhn-algoritmen i forskjellige programmeringsspråk:

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])))

## Eksempel på bruk:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # Genererer et gyldig 16-sifret nummer

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

// Eksempel på bruk:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // Genererer et gyldig 16-sifret nummer

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));  // Genererer et gyldig 16-sifret nummer
    }
}

Kanttilfeller og spesielle hensyn

Når du implementerer Luhn-algoritmen, vurder følgende kanttilfeller og spesielle hensyn:

1. Inndata Validering: Sørg for at inndata er en gyldig nummerserie. Ikke-siffertegn bør håndteres på passende måte (enten fjernes eller behandles som ugyldige inndata).

2. Ledende nuller: Algoritmen bør fungere korrekt med numre som har ledende nuller.

3. Store tall: Vær forberedt på å håndtere veldig lange numre som kan overstige kapasiteten til standard heltallstyper i noen programmeringsspråk.

4. Tom inndata: Definer hvordan implementeringen din skal håndtere tomme strenger eller null-inndata.

5. Ikke-standard tegnsett: I noen applikasjoner kan du støte på numre representert med tegn utenfor standard 0-9 rekkevidde. Definer hvordan disse skal håndteres.

6. Ytelsesvurderinger: For applikasjoner som trenger å validere store mengder inndata raskt, vurder å optimalisere algoritmeimplementeringen.

Numeriske eksempler

1. Gyldig kredittkortnummer:

   • Nummer: 4532015112830366
   • Luhn-sjekk: Gyldig

2. Ugyldig kredittkortnummer:

   • Nummer: 4532015112830367
   • Luhn-sjekk: Ugyldig

3. Gyldig kanadisk personnummer:

   • Nummer: 046 454 286
   • Luhn-sjekk: Gyldig

4. Ugyldig IMEI-nummer:

   • Nummer: 490154203237518
   • Luhn-sjekk: Ugyldig

Testtilfeller

For å verifisere implementeringen av Luhn-algoritmen, kan du bruke følgende testtilfeller:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # Test genererte numre
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("Alle tester bestått!")

test_luhn_algorithm()

Referanser

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