מחשבון אלגוריתם לון

מחשבון אלגוריתם לון

הקדמה

אלגוריתם לון, הידוע גם כ"מודולוס 10" או "מוד 10", הוא נוסחת בדיקה פשוטה המשמשת לאימות מגוון מספרי זיהוי, כגון מספרי כרטיסי אשראי, מספרי ביטוח לאומי קנדים, מספרי IMEI ומספרי ספק לאומי בארצות הברית. מחשבון זה מאפשר לך לאמת מספרים באמצעות אלגוריתם לון וליצור מספרים חוקיים שעוברים את בדיקת לון.

איך עובד אלגוריתם לון

אלגוריתם לון עובד כך:

1. החל מהספרה הימנית ביותר (ללא ספרת הבדיקה) והזז שמאלה, הכפל את ערך כל ספרה שנייה ב-2.
2. אם התוצאה של פעולת הכפל הזו גדולה מ-9, הפחת 9 מהתוצאה.
3. סכום את כל הספרות בסדרה המתקבלת.
4. אם הסכום במודולו 10 שווה ל-0 (אם הסכום מסתיים באפס), אז המספר חוקי לפי נוסחת לון; אחרת, הוא אינו חוקי.

הנה ייצוג חזותי של אלגוריתם לון:

נוסחה

אלגוריתם לון ניתן לביטוי מתמטי כך:

יהי $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$ היא פעולה מודולו.

שימושים

לאלגוריתם לון יש יישומים שונים בתחומים שונים:

1. אימות כרטיסי אשראי: רוב מספרי כרטיסי האשראי מאומתים באמצעות אלגוריתם לון.
2. מספרי ביטוח לאומי קנדים: אלגוריתם לון משמש לאימות תקפות מספרים אלה.
3. מספרי IMEI: מספרי IMEI של טלפונים ניידים כוללים ספרת בדיקה המאומתת על ידי אלגוריתם לון.
4. מספרי ספק לאומי (NPI): בשירותי הבריאות בארצות הברית, מספרים אלה מאומתים באמצעות אלגוריתם לון.
5. ISBNs: חלק ממספרי ISBN-10 משתמשים בגרסה של אלגוריתם לון לאימות.

חלופות

בעוד שאלגוריתם לון בשימוש נרחב, ישנם אלגוריתמים אחרים לבדיקה למטרות שונות:

1. אלגוריתם דם: אלגוריתם ספרת בדיקה נוסף שמגלה את כל השגיאות עם ספרה אחת וכל השגיאות של החלפת סמוכים.
2. אלגוריתם ורהוף: אלגוריתם בדיקה מורכב יותר שתופס את כל השגיאות עם ספרה אחת ורוב השגיאות של החלפת סמוכים.
3. ספרת בדיקה ISBN-13: משתמשת באלגוריתם שונה מאשר ISBN-10, המבוסס על אלגוריתם לון.

היסטוריה

אלגוריתם לון נוצר על ידי האנס פטר לון, מדען מחשבים ב-IBM, בשנת 1954. לון היה חלוץ בתחום מדעי המידע ומיוחסות לו מספר חידושים, כולל מערכת אינדוקס KWIC (מילת מפתח בהקשר).

האלגוריתם נועד במקור להגן מפני שגיאות מקריות, ולא מפני התקפות זדוניות. חשוב לציין כי בעוד שאלגוריתם לון יכול לזהות רבות מהשגיאות הנפוצות, הוא אינו צורת הצפנה בטוחה ואין לסמוך עליו למטרות אבטחת נתונים.

למרות גילו, אלגוריתם לון נשאר בשימוש נרחב בשל הפשטות והיעילות שלו בלכידת שגיאות העתקה נפוצות.

דוגמאות יישום

הנה כמה דוגמאות קוד ליישום אלגוריתם לון בשפות תכנות שונות:

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

## דוגמת שימוש:
print(luhn_validate(4532015112830366))  # True
print(luhn_validate(4532015112830367))  # False
print(generate_valid_number(16))  # יוצר מספר חוקי בן 16 ספרות

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

// דוגמת שימוש:
console.log(luhnValidate(4532015112830366));  // true
console.log(luhnValidate(4532015112830367));  // false
console.log(generateValidNumber(16));  // יוצר מספר חוקי בן 16 ספרות

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));  // יוצר מספר חוקי בן 16 ספרות
    }
}

מקרים קצה ושיקולים מיוחדים

בעת יישום אלגוריתם לון, שקול את המקרים הקצה והשיקולים המיוחדים הבאים:

1. אימות קלט: ודא שהקלט הוא מיתר מספר חוקי. יש לטפל באותיות שאינן ספרות כראוי (או להסיר אותן או להתייחס אליהן כקלט לא חוקי).

2. אפסי מובילים: האלגוריתם צריך לעבוד כראוי עם מספרים שיש להם אפסים מובילים.

3. מספרים גדולים: היה מוכן להתמודד עם מספרים מאוד ארוכים שעשויים לחרוג מהקיבולת של סוגי מספרים סטנדרטיים בחלק משפות התכנות.

4. קלט ריק: הגדר כיצד היישום שלך צריך להתמודד עם מיתרים ריקים או קלטים null.

5. קבוצות תווים לא סטנדרטיות: בחלק מהיישומים, ייתכן שתיתקל במספרים המיוצגים עם תווים מחוץ לטווח הסטנדרטי 0-9. הגדר כיצד יש לטפל בזה.

6. שיקולי ביצועים: עבור יישומים שצריכים לאמת מספרים רבים של קלטים במהירות, שקול לייעל את יישום האלגוריתם.

דוגמאות מספריות

1. מספר כרטיס אשראי חוקי:

   • מספר: 4532015112830366
   • בדיקת לון: חוקי

2. מספר כרטיס אשראי לא חוקי:

   • מספר: 4532015112830367
   • בדיקת לון: לא חוקי

3. מספר חוקי של ביטוח לאומי קנדי:

   • מספר: 046 454 286
   • בדיקת לון: חוקי

4. מספר IMEI לא חוקי:

   • מספר: 490154203237518
   • בדיקת לון: לא חוקי

מקרים לבחינה

כדי לאמת את היישום של אלגוריתם לון, תוכל להשתמש במקרים הבאים:

def test_luhn_algorithm():
    assert luhn_validate(4532015112830366) == True
    assert luhn_validate(4532015112830367) == False
    assert luhn_validate(79927398713) == True
    assert luhn_validate(79927398714) == False
    
    # בדוק מספרים שנוצרו
    for _ in range(10):
        assert luhn_validate(generate_valid_number(16)) == True
    
    print("כל הבדיקות עברו!")

test_luhn_algorithm()

מקורות

1. לון, האנס פ. (1960). "מחשב לאימות מספרים". פטנט אמריקאי 2,950,048.
2. גאליאן, ג'וזף. "המתמטיקה של מספרי זיהוי." כתב העת למתמטיקה במכללה, כרך 22, מס' 3, 1991, עמ' 194–202. JSTOR, www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". ארגון התקנים הבינלאומי. נבדק ב-2 באוגוסט 2024.
4. קנוט, דונלד. "האמנות של תכנות מחשבים, כרך 2: אלגוריתמים סמינומיים". אדיסון-ווסלי, 1997.