Luhn Algorithm Beregner

Introduktion

Luhn-algoritmen, også kendt som "modulus 10" eller "mod 10" algoritmen, er en simpel kontrolsumformel, der bruges til at validere en række identifikationsnumre, såsom kreditkortnumre, canadiske socialforsikringsnumre, IMEI-numre og nationale udbyderidentifikationsnumre i USA. Denne beregner giver dig mulighed for at validere numre ved hjælp af Luhn-algoritmen og generere gyldige numre, der består Luhn-kontrollen.

Hvordan Luhn-algoritmen fungerer

Luhn-algoritmen fungerer som følger:

1. Start fra den højre kant (eksklusive kontrolcifret) og bevæg dig til venstre, fordoble værdien af hver anden cifre.
2. Hvis resultatet af denne fordoblingsoperation er større end 9, træk 9 fra resultatet.
3. Summer alle cifrene i den resulterende sekvens.
4. Hvis totalen modulo 10 er lig med 0 (hvis totalen ender med nul), så er nummeret gyldigt i henhold til Luhn-formlen; ellers er det ikke gyldigt.

Her er en visuel repræsentation af Luhn-algoritmen:

Formel

Luhn-algoritmen kan udtrykkes matematisk som følger:

Lad $d_i$ være den $i$-te cifre, tællende fra den højre cifre (eksklusive kontrolcifret) og bevæge sig til venstre. Så vælges kontrolcifret $d_0$, så:

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

Anvendelsesområder

Luhn-algoritmen har forskellige anvendelser inden for forskellige områder:

1. Kreditkortvalidering: De fleste kreditkortnumre valideres ved hjælp af Luhn-algoritmen.
2. Canadiske socialforsikringsnumre: Luhn-algoritmen bruges til at verificere gyldigheden af disse identifikationsnumre.
3. IMEI-numre: Mobiltelefon IMEI-numre indeholder et kontrolciffer, der valideres af Luhn-algoritmen.
4. Nationale udbyderidentifikationsnumre (NPI): Bruges i det amerikanske sundhedssystem, disse numre valideres ved hjælp af Luhn-algoritmen.
5. ISBN'er: Nogle ISBN-10-numre bruger en variant af Luhn-algoritmen til validering.

Alternativer

Selvom Luhn-algoritmen er meget anvendt, findes der andre kontrolsumalgoritmer til forskellige formål:

1. Damm-algoritmen: En anden kontrolciffer-algoritme, der opdager alle enkeltcifrede fejl og alle tilstødende transpositionsfejl.
2. Verhoeff-algoritmen: En mere kompleks kontrolsumalgoritme, der fanger alle enkeltcifrede fejl og de fleste transpositionsfejl.
3. ISBN-13 kontrolciffer: Bruger en anden algoritme end ISBN-10, som er baseret på Luhn-algoritmen.

Historie

Luhn-algoritmen blev skabt af Hans Peter Luhn, en IBM-datavidenskabsmand, i 1954. Luhn var en pioner inden for informationsvidenskab og krediteres med flere innovationer, herunder KWIC (Key Word In Context) indekseringssystemet.

Algoritmen blev oprindeligt designet til at beskytte mod utilsigtede fejl, ikke ondsindede angreb. Det er vigtigt at bemærke, at selvom Luhn-algoritmen kan opdage mange almindelige fejl, er det ikke en sikker form for kryptering og bør ikke stole på til databeskyttelsesformål.

På trods af sin alder forbliver Luhn-algoritmen meget anvendt på grund af sin enkelhed og effektivitet til at fange almindelige transkriptionsfejl.

Implementeringseksempler

Her er nogle kodeeksempler til at implementere Luhn-algoritmen i forskellige programmeringssprog:

1import random
2
3def luhn_validate(number):
4    digits = [int(d) for d in str(number)]
5    checksum = 0
6    for i in range(len(digits) - 1, -1, -1):
7        d = digits[i]
8        if (len(digits) - i) % 2 == 0:
9            d = d * 2
10            if d > 9:
11                d -= 9
12        checksum += d
13    return checksum % 10 == 0
14
15def generate_valid_number(length):
16    digits = [random.randint(0, 9) for _ in range(length - 1)]
17    checksum = sum(digits[::2]) + sum(sum(divmod(d * 2, 10)) for d in digits[-2::-2])
18    check_digit = (10 - (checksum % 10)) % 10
19    return int(''.join(map(str, digits + [check_digit])))
20
21## Eksempel på brug:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Genererer et gyldigt 16-cifret nummer
25

1function luhnValidate(number) {
2    const digits = number.toString().split('').map(Number);
3    let checksum = 0;
4    for (let i = digits.length - 1; i >= 0; i--) {
5        let d = digits[i];
6        if ((digits.length - i) % 2 === 0) {
7            d *= 2;
8            if (d > 9) d -= 9;
9        }
10        checksum += d;
11    }
12    return checksum % 10 === 0;
13}
14
15function generateValidNumber(length) {
16    const digits = Array.from({length: length - 1}, () => Math.floor(Math.random() * 10));
17    const checksum = digits.reduce((sum, digit, index) => {
18        if ((length - 1 - index) % 2 === 0) {
19            digit *= 2;
20            if (digit > 9) digit -= 9;
21        }
22        return sum + digit;
23    }, 0);
24    const checkDigit = (10 - (checksum % 10)) % 10;
25    return parseInt(digits.join('') + checkDigit);
26}
27
28// Eksempel på brug:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Genererer et gyldigt 16-cifret nummer
32

1import java.util.Random;
2
3public class LuhnValidator {
4    public static boolean luhnValidate(long number) {
5        String digits = String.valueOf(number);
6        int checksum = 0;
7        boolean isEven = true;
8        for (int i = digits.length() - 1; i >= 0; i--) {
9            int digit = Character.getNumericValue(digits.charAt(i));
10            if (isEven) {
11                digit *= 2;
12                if (digit > 9) digit -= 9;
13            }
14            checksum += digit;
15            isEven = !isEven;
16        }
17        return checksum % 10 == 0;
18    }
19
20    public static long generateValidNumber(int length) {
21        Random random = new Random();
22        long[] digits = new long[length - 1];
23        for (int i = 0; i < length - 1; i++) {
24            digits[i] = random.nextInt(10);
25        }
26        long checksum = 0;
27        for (int i = digits.length - 1; i >= 0; i--) {
28            long digit = digits[i];
29            if ((length - 1 - i) % 2 == 0) {
30                digit *= 2;
31                if (digit > 9) digit -= 9;
32            }
33            checksum += digit;
34        }
35        long checkDigit = (10 - (checksum % 10)) % 10;
36        long result = 0;
37        for (long digit : digits) {
38            result = result * 10 + digit;
39        }
40        return result * 10 + checkDigit;
41    }
42
43    public static void main(String[] args) {
44        System.out.println(luhnValidate(4532015112830366L));  // true
45        System.out.println(luhnValidate(4532015112830367L));  // false
46        System.out.println(generateValidNumber(16));  // Genererer et gyldigt 16-cifret nummer
47    }
48}
49

Kanttilfælde og særlige overvejelser

Når du implementerer Luhn-algoritmen, skal du overveje følgende kanttilfælde og særlige overvejelser:

1. Indtastningsvalidering: Sørg for, at indtastningen er en gyldig nummerstreng. Ikke-cifrede tegn skal håndteres passende (enten fjernes eller behandles som ugyldig indtastning).

2. Førende nuller: Algoritmen skal fungere korrekt med numre, der har førende nuller.

3. Store numre: Vær forberedt på at håndtere meget lange numre, der kan overstige kapaciteten for standard heltalstyper i nogle programmeringssprog.

4. Tom indtastning: Definer, hvordan din implementering skal håndtere tomme strenge eller null-indgange.

5. Ikke-standard tegnsæt: I nogle applikationer kan du støde på numre, der er repræsenteret med tegn uden for standard 0-9-området. Definer, hvordan disse skal håndteres.

6. Ydelsesovervejelser: For applikationer, der skal validere mange indgange hurtigt, skal du overveje at optimere algoritmeimplementeringen.

Numeriske eksempler

1. Gyldigt kreditkortnummer:

   • Nummer: 4532015112830366
   • Luhn-tjek: Gyldig

2. Ugyldigt kreditkortnummer:

   • Nummer: 4532015112830367
   • Luhn-tjek: Ugyldig

3. Gyldigt canadisk socialforsikringsnummer:

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

4. Ugyldigt IMEI-nummer:

   • Nummer: 490154203237518
   • Luhn-tjek: Ugyldig

Testcases

For at verificere implementeringen af Luhn-algoritmen kan du bruge følgende testcases:

1def test_luhn_algorithm():
2    assert luhn_validate(4532015112830366) == True
3    assert luhn_validate(4532015112830367) == False
4    assert luhn_validate(79927398713) == True
5    assert luhn_validate(79927398714) == False
6    
7    # Test genererede numre
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Alle tests bestået!")
12
13test_luhn_algorithm()
14

Referencer

1. Luhn, H. P. (1960). "Computer for Verifying Numbers". US Patent 2,950,048.
2. Gallian, Joseph. "The Mathematics of Identification Numbers." The College Mathematics Journal, vol. 22, no. 3, 1991, pp. 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.