Βικιπαίδεια

Αλγόριθμος του Λουν

Ο αλγόριθμος του Λουν (Αγγλικά: Luhn algorithm) ή η συνάρτηση του Λουν, γνωστός και ως "modulus 10" ή "mod 10" αλγόριθμος, είναι μια απλή συνάρτηση ελέγχου αθροίσματος η οποία χρησιμοποιείται ευρέως για έλεγχο ορθότητας αριθμών. Για παράδειγμα χρησιμοποιείται σε έλεγχο ορθότητας αριθμών πιστωτικών καρτών [1], κώδικες IMEI κινητών [2] [3] αλλά και σε αριθμούς κοινωνικής ασφάλειας στις ΗΠΑ και στον Καναδά [4] [5]. Ο αλγόριθμος αναπτύχθηκε από τον ερευνητή της IBM Χανς Πέτερ Λουν και περιγράφεται από την αμερικανική πατέντα με αριθμό 2,950,048 η οποία κατοχυρώθηκε στις 6 Ιανουαρίου 1954 και έληξε στις 23 Αυγούστου 1960. [6]

Η πατέντα του αλγόριθμου έχει λήξει και σήμερα ο αλγόριθμος χρησιμοποιείται ευρέως ενώ στο πρότυπο ISO/IEC 7812-1 έχει τυποποιηθεί.[7] Ο αλγόριθμος αυτός δεν αναπτύχθηκε ως κρυπτογραφική συνάρτηση κατατεμαχισμού αλλά αναπτύχθηκε για προστασία από τυχαία λάθη μεταγραφής των ψηφίων (για παράδειγμα όταν ένας αγοραστής βάζει την πιστωτική κάρτα για αγορές σε μια ιστοσελίδα με τον αλγόριθμο αυτό ελέγχονται τυχόν λάθη κατά την εισαγωγή των ψηφίων της κάρτας). Οι περισσότερες πιστωτικές κάρτες και διάφοροι αριθμοί λογαριασμών, όπως αριθμοί κοινωνικών ασφαλίσεων στον Καναδά και ο Αριθμός Μητρώου Κοινωνικής Ασφάλισης (ΑΜΚΑ) στην Ελλάδα, χρησιμοποιούν αυτόν τον απλό αλγόριθμο για να ξεχωρίσουν τις έγκυρες κάρτες/αριθμούς.

Περιγραφή Επεξεργασία

Η συνάρτηση που περιγράφει ο αλγόριθμος αυτός ελέγχει την ορθότητα αριθμών σε σχέση με ένα ψηφίο ελέγχου. Το ψηφίο ελέγχου προστίθεται στο τέλος του αριθμού. [6] Τα βήματα που ακολουθούμε για τον ελέγχο ορθότητας ενός αριθμού είναι τα παρακάτω:

  1. Ξεκινάμε από το δεξιότερο ψηφίο το οποίο είναι το ψηφίο ελέγχου, πηγαίνουμε προς τα αριστερά και διπλασιάζουμε την τιμή κάθε δεύτερου ψηφίου. Εάν το αποτέλεσμα του διπλασιασμού είναι μεγαλύτερο του 9 (για παράδειγμα 8 × 2 = 16) τότε αθροίζουμε τα δύο ψηφία (για παράδειγμα στο 16: 1 + 6 = 7, στο 18: 1 + 8 = 9).
  2. Κατόπιν αθροίζουμε όλα τα ψηφία.
  3. Εάν το άθροισμα όταν το διαιρούμε με το 10 δίνει υπόλοιπο (modulo) 0 τότε ο αριθμός είναι ορθός κατά την συνάρτηση του Λουν.

Ας πάρουμε το παράδειγμα ενός λογαριασμού ο οποίος έχει τον αριθμό "7992739871", σε αυτόν τον αριθμό θέλουμε να προσθέσουμε ένα παραπάνω ψηφίο, το ψηφίο ελέγχου x, με το οποίο ο αλγόριθμος του Λουν θα ελέγχει την ορθότητα.: 7992739871x:

Αριθμός λογαριασμού 7 9 9 2 7 3 9 8 7 1 x
Διπλασιάζουμε κάθε δεύτερο ψηφίο 7 18 9 4 7 6 9 16 7 2 -
Άθροισμα των ψηφίων 7 9 9 4 7 6 9 7 7 2 =67

Το ψηφίο ελέγχου x υπολογίζεται με το άθροισμα των ψηφίων και στην συνέχεια πολλαπλασιάζουμε την τιμή αυτή με 9 και στην συνέχεια την διαιρούμε με το 10 και βρίσκουμε το υπόλοιπο (modulo) της διαίρεσης: (67 × 9 mod 10). Ο αλγόριθμος είναι ο παρακάτω:

  1. Υπολόγισε τον αριθμό των ψηφίων (είναι το 67).
  2. Πολλαπλασίασε με 9 (9*67=603).
  3. Το τελευταίο ψηφίο, το 3, είναι το ψηφίο ελέγχου. Συνεπώς x=3.

Άρα ο λογαριασμός με το ψηφίο ελέγχου στο τέλος γίνεται ο 79927398713.

Καθένας από τους παρακάτω αριθμούς 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 μπορεί να επαληθευτεί ότι είναι ορθός με τον παρακάτω τρόπο.

  1. Διπλασίασε κάθε δεύτερο ψηφίο, ξεκινώντας από το πιο δεξιά: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
  2. Άθροισε όλα τα ψηφία (τα ψηφία στις παρενθέσεις είναι οι πολλαπλασιασμοί από το βήμα 1): x (είναι το ψηφίο ελέγχου) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
  3. Εάν το άθροισμα είναι πολλαπλάσιο του 10 (αν διαιρούμε τον αριθμό με το 10 έχουμε υπόλοιπο μηδέν), ο αριθμός λογαριασμού είναι πιθανόν ορθός.

Παράδειγμα ελέγχου πιστωτικής κάρτας Επεξεργασία

Έστω ότι θέλουμε να ελέγξουμε την πιστωτική κάρτα με αριθμό 4012 8888 8888 1881 με τον αλγόριθμο Λουν. Σύμφωνα με τον αλγόριθμο τα βήματα που ακολουθούμε είναι τα παρακάτω:

Αριθμός πιστωτικής 4 0 1 2 8 8 8 8 8 8 8 8 1 8 8 1
Διπλασιάζουμε κάθε δεύτερο ψηφίο (από δεξιά) 8 0 2 2 16 8 16 8 16 8 16 8 2 8 16 1
Άθροισμα των ψηφίων 8 0 2 2 7 8 7 8 7 8 7 8 2 8 7 1 =90

Το υπόλοιπο της διαίρεσης του 90 με το 10 δίνει 0 (90 modulus 10 = 0), άρα η κάρτα είναι έγκυρη.

Υλοποίηση του αλγόριθμου Mod 10 Επεξεργασία

Η παρακάτω υλοποίηση του αλγόριθμου είναι σε γλώσσα προγραμματισμού Python.

Επαλήθευση του ψηφίου ελέγχου Επεξεργασία 

def luhn_checksum(card_number):
    def digits_of(n):
        return [int(d) for d in str(n)]
    digits = digits_of(card_number)
    odd_digits = digits[-1::-2]
    even_digits = digits[-2::-2]
    checksum = 0
    checksum += sum(odd_digits)
    for d in even_digits:
        checksum += sum(digits_of(d*2))
    return checksum % 10

def is_luhn_valid(card_number):
    return luhn_checksum(card_number) == 0

Υπολογισμός του ψηφίου ελέγχου Επεξεργασία

Ο παραπάνω αλγόριθμος ελέγχει την εγκυρότητα της εισόδου με ένα ψηφίο ελέγχου. Ο υπολογισμός του ψηφίου ελέγχου χρειάζεται την παρακάτω προσαρμογή:

  1. Πρόσθεσε ένα μηδενικό ψηφίο ελέγχου στον αριθμό και υπολόγισε το έλεγχο αθροίσματος
  2. Εάν το άθροισμα διαιρούμενο με 10 δίνει υπόλοιπο 0 (sum mod 10) == 0, τότε το ψηφίο ελέγχου είναι το 0
  3. Αλλιώς το ψηφίο ελέγχου είναι το 10 - (sum mod 10)
def calculate_luhn(partial_card_number):
    check_digit = luhn_checksum(int(partial_card_number) * 10)
    return check_digit if check_digit == 0 else 10 - check_digit

Παραπομπές Επεξεργασία

  1. ↑ Mischel, Magnus (2009). ModSecurity 2.5 : securing your Apache installation and web applications. Birmingham, U.K.: Packt Pub. σελ. 53. ISBN 9781847194749. 
  2. ↑ «IMEI Calculator». imeidata.net. Αρχειοθετήθηκε από το πρωτότυπο στις 25 Δεκεμβρίου 2014. Ανακτήθηκε στις 10 Δεκεμβρίου 2014. 
  3. ↑ «Class LuhnCheckDigit». http://commons.apache.org.  Εξωτερικός σύνδεσμος στο |publisher= (βοήθεια)
  4. ↑ Fraud and Fraud Detection + Website A Data Analytics Approach Using Idea. John Wiley & Sons Inc. 2014. ISBN 978-1-118-77965-1. 
  5. ↑ Wright, David Lovelock ; Marilou Mendel ; A. Larry (2007). An introduction to the mathematics of money : saving and investing ([Online-Ausg.]. έκδοση). New York, NY: Springer. σελ. 108. ISBN 978-0387-34432-4. 
  6. ↑ 6,0 6,1 Topics in contemporary mathematics (10 ed. έκδοση). Belmont, CA: Brooks/Cole. 2014. σελ. 534. ISBN 978-1-133-10742-2. 
  7. ↑ ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system
Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Αλγόριθμος_του_Λουν&oldid=9647499"