Υπολογιστής Αλγορίθμου Luhn

Εισαγωγή

Ο αλγόριθμος Luhn, γνωστός και ως "αλγόριθμος υπολοίπου 10" ή "mod 10", είναι μια απλή φόρμουλα ελέγχου που χρησιμοποιείται για την επικύρωση διαφόρων αριθμών ταυτοποίησης, όπως αριθμοί πιστωτικών καρτών, Καναδικοί αριθμοί κοινωνικής ασφάλισης, αριθμοί IMEI και αριθμοί Εθνικού Παρόχου Ταυτοποίησης στις Ηνωμένες Πολιτείες. Αυτός ο υπολογιστής σας επιτρέπει να επικυρώνετε αριθμούς χρησιμοποιώντας τον αλγόριθμο Luhn και να δημιουργείτε έγκυρους αριθμούς που περνούν τον έλεγχο Luhn.

Πώς Λειτουργεί ο Αλγόριθμος Luhn

Ο αλγόριθμος Luhn λειτουργεί ως εξής:

1. Ξεκινώντας από το δεξιότερο ψηφίο (εξαιρώντας το ψηφίο ελέγχου) και κινούμενοι προς τα αριστερά, διπλασιάστε την τιμή κάθε δεύτερου ψηφίου.
2. Εάν το αποτέλεσμα αυτής της διαδικασίας διπλασιασμού είναι μεγαλύτερο από 9, αφαιρέστε 9 από το αποτέλεσμα.
3. Αθροίστε όλα τα ψηφία στην προκύπτουσα ακολουθία.
4. Εάν το συνολικό υπόλοιπο 10 είναι ίσο με 0 (εάν το συνολικό καταλήγει σε μηδέν), τότε ο αριθμός είναι έγκυρος σύμφωνα με τον τύπο Luhn. Διαφορετικά, δεν είναι έγκυρος.

Ακολουθεί μια οπτική αναπαράσταση του αλγορίθμου Luhn:

Τύπος

Ο αλγόριθμος Luhn μπορεί να εκφραστεί μαθηματικά ως εξής:

Έστω $d_i$ το $i$-οστό ψηφίο, μετρώντας από το δεξιότερο ψηφίο (εξαιρώντας το ψηφίο ελέγχου) και κινούμενοι αριστερά. Τότε το ψηφίο ελέγχου $d_0$ επιλέγεται έτσι ώστε:

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

Όπου $\bmod$ είναι η λειτουργία υπολοίπου.

Χρήσεις

Ο αλγόριθμος Luhn έχει διάφορες εφαρμογές σε διαφορετικά πεδία:

1. Επικύρωση Αριθμών Πιστωτικών Καρτών: Οι περισσότεροι αριθμοί πιστωτικών καρτών επικυρώνονται χρησιμοποιώντας τον αλγόριθμο Luhn.
2. Καναδικοί Αριθμοί Κοινωνικής Ασφάλισης: Ο αλγόριθμος Luhn χρησιμοποιείται για την επαλήθευση της εγκυρότητας αυτών των αριθμών ταυτοποίησης.
3. Αριθμοί IMEI: Οι αριθμοί IMEI κινητών τηλεφώνων περιλαμβάνουν ένα ψηφίο ελέγχου που επικυρώνεται από τον αλγόριθμο Luhn.
4. Αριθμοί Εθνικού Παρόχου Ταυτοποίησης (NPI): Χρησιμοποιούμενοι στο σύστημα υγειονομικής περίθαλψης των Ηνωμένων Πολιτειών, αυτοί οι αριθμοί επικυρώνονται χρησιμοποιώντας τον αλγόριθμο Luhn.
5. ISBNs: Ορισμένοι αριθμοί ISBN-10 χρησιμοποιούν μια παραλλαγή του αλγορίθμου Luhn για επικύρωση.

Εναλλακτικές

Ενώ ο αλγόριθμος Luhn είναι ευρέως χρησιμοποιούμενος, υπάρχουν και άλλοι αλγόριθμοι ελέγχου για διαφορετικούς σκοπούς:

1. Αλγόριθμος Damm: Ένας άλλος αλγόριθμος ψηφίου ελέγχου που ανιχνεύει όλα τα σφάλματα ενός ψηφίου και όλα τα σφάλματα διπλής μετατόπισης.
2. Αλγόριθμος Verhoeff: Ένας πιο πολύπλοκος αλγόριθμος ελέγχου που ανιχνεύει όλα τα σφάλματα ενός ψηφίου και τις περισσότερες διπλές μετατοπίσεις.
3. Ψηφίο ελέγχου ISBN-13: Χρησιμοποιεί έναν διαφορετικό αλγόριθμο από το ISBN-10, ο οποίος βασίζεται στον αλγόριθμο Luhn.

Ιστορία

Ο αλγόριθμος Luhn δημιουργήθηκε από τον Hans Peter Luhn, έναν επιστήμονα υπολογιστών της IBM, το 1954. Ο Luhn ήταν πρωτοπόρος στον τομέα της επιστήμης των πληροφοριών και πιστώνεται με πολλές καινοτομίες, συμπεριλαμβανομένου του συστήματος ευρετηρίασης KWIC (Key Word In Context).

Ο αλγόριθμος σχεδιάστηκε αρχικά για να προστατεύει από τυχαία σφάλματα, όχι από κακόβουλες επιθέσεις. Είναι σημαντικό να σημειωθεί ότι ενώ ο αλγόριθμος Luhn μπορεί να ανιχνεύσει πολλά κοινά σφάλματα, δεν είναι μια ασφαλής μορφή κρυπτογράφησης και δεν θα πρέπει να βασίζεστε σε αυτόν για σκοπούς ασφάλειας δεδομένων.

Παρά την ηλικία του, ο αλγόριθμος Luhn παραμένει ευρέως χρησιμοποιούμενος λόγω της απλότητας και της αποτελεσματικότητάς του στην ανίχνευση κοινών σφαλμάτων καταγραφής.

Παραδείγματα Υλοποίησης

Ακολουθούν μερικά παραδείγματα κώδικα για την υλοποίηση του αλγορίθμου Luhn σε διάφορες γλώσσες προγραμματισμού:

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## Παράδειγμα χρήσης:
22print(luhn_validate(4532015112830366))  # True
23print(luhn_validate(4532015112830367))  # False
24print(generate_valid_number(16))  # Δημιουργεί έναν έγκυρο 16-ψήφιο αριθμό
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// Παράδειγμα χρήσης:
29console.log(luhnValidate(4532015112830366));  // true
30console.log(luhnValidate(4532015112830367));  // false
31console.log(generateValidNumber(16));  // Δημιουργεί έναν έγκυρο 16-ψήφιο αριθμό
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));  // Δημιουργεί έναν έγκυρο 16-ψήφιο αριθμό
47    }
48}
49

Άκρες και Ειδικές Σκέψεις

Κατά την υλοποίηση του αλγορίθμου Luhn, εξετάστε τις παρακάτω άκρες και ειδικές σκέψεις:

1. Επικύρωση Εισόδου: Βεβαιωθείτε ότι η είσοδος είναι μια έγκυρη ακολουθία αριθμών. Μη ψηφιακοί χαρακτήρες θα πρέπει να αντιμετωπίζονται κατάλληλα (είτε να αφαιρούνται είτε να θεωρούνται ως μη έγκυρη είσοδος).

2. Ηγετικά Μηδενικά: Ο αλγόριθμος θα πρέπει να λειτουργεί σωστά με αριθμούς που έχουν ηγετικά μηδενικά.

3. Μεγάλοι Αριθμοί: Να είστε προετοιμασμένοι να χειριστείτε πολύ μεγάλους αριθμούς που μπορεί να υπερβαίνουν την ικανότητα των τυπικών τύπων ακέραιων αριθμών σε ορισμένες γλώσσες προγραμματισμού.

4. Κενή Είσοδος: Ορίστε πώς θα πρέπει να χειρίζεται η υλοποίησή σας κενές ακολουθίες ή null εισόδους.

5. Μη Τυποποιημένα Σύνολα Χαρακτήρων: Σε ορισμένες εφαρμογές, μπορεί να συναντήσετε αριθμούς που αναπαρίστανται με χαρακτήρες εκτός του τυπικού εύρους 0-9. Ορίστε πώς θα πρέπει να χειρίζονται αυτοί.

6. Σκέψεις Απόδοσης: Για εφαρμογές που χρειάζονται γρήγορα να επικυρώνουν μεγάλους αριθμούς εισόδου, εξετάστε την πιθανότητα βελτιστοποίησης της υλοποίησης του αλγορίθμου.

Αριθμητικά Παραδείγματα

1. Έγκυρος Αριθμός Πιστωτικής Κάρτας:

   • Αριθμός: 4532015112830366
   • Έλεγχος Luhn: Έγκυρος

2. Μη Έγκυρος Αριθμός Πιστωτικής Κάρτας:

   • Αριθμός: 4532015112830367
   • Έλεγχος Luhn: Μη Έγκυρος

3. Έγκυρος Καναδικός Αριθμός Κοινωνικής Ασφάλισης:

   • Αριθμός: 046 454 286
   • Έλεγχος Luhn: Έγκυρος

4. Μη Έγκυρος Αριθμός IMEI:

   • Αριθμός: 490154203237518
   • Έλεγχος Luhn: Μη Έγκυρος

Δοκιμαστικές Περιπτώσεις

Για να επαληθεύσετε την υλοποίηση του αλγορίθμου Luhn, μπορείτε να χρησιμοποιήσετε τις παρακάτω δοκιμαστικές περιπτώσεις:

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    # Δοκιμάστε τους παραγόμενους αριθμούς
8    for _ in range(10):
9        assert luhn_validate(generate_valid_number(16)) == True
10    
11    print("Όλες οι δοκιμές πέρασαν!")
12
13test_luhn_algorithm()
14

Αναφορές

1. Luhn, H. P. (1960). "Υπολογιστής για την Επαλήθευση Αριθμών". Δίπλωμα ευρεσιτεχνίας ΗΠΑ 2,950,048.
2. Gallian, Joseph. "Τα Μαθηματικά των Αριθμών Ταυτοποίησης." Το Περιοδικό Κολλεγίων Μαθηματικών, τόμος 22, αριθμός 3, 1991, σελ. 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". Διεθνής Οργάνωση Τυποποίησης. Ανακτήθηκε 2 Αυγούστου 2024.
4. Knuth, Donald. "Η Τέχνη του Υπολογιστικού Προγραμματισμού, Τόμος 2: Αλγόριθμοι Ημι-Αριθμητικοί". Addison-Wesley, 1997.