محاسبه الگوریتم لون

مقدمه

الگوریتم لون، که به عنوان "مدول ۱۰" یا "مد ۱۰" نیز شناخته می‌شود، یک فرمول ساده چک‌سوم است که برای اعتبارسنجی انواع شماره‌های شناسایی، مانند شماره‌های کارت اعتباری، شماره‌های بیمه اجتماعی کانادا، شماره‌های IMEI و شماره‌های شناسنده ملی ارائه‌دهندگان در ایالات متحده استفاده می‌شود. این محاسبه‌گر به شما این امکان را می‌دهد که شماره‌ها را با استفاده از الگوریتم لون اعتبارسنجی کنید و شماره‌های معتبری که از چک لون عبور می‌کنند، تولید کنید.

نحوه کار الگوریتم لون

الگوریتم لون به شرح زیر عمل می‌کند:

1. از سمت راست (به جز رقم چک) شروع کرده و به سمت چپ بروید و مقدار هر دومین رقم را دو برابر کنید.
2. اگر نتیجه این عملیات دو برابر کردن بیشتر از ۹ باشد، ۹ را از نتیجه کم کنید.
3. تمام ارقام در دنباله حاصل را جمع کنید.
4. اگر مجموع ماژولوی ۱۰ برابر با ۰ باشد (اگر مجموع به صفر ختم شود)، آنگاه شماره مطابق با فرمول لون معتبر است؛ در غیر این صورت، معتبر نیست.

در اینجا یک نمایش بصری از الگوریتم لون آورده شده است:

فرمول

الگوریتم لون می‌تواند به صورت ریاضی به شرح زیر بیان شود:

بگذارید $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. ISBNها: برخی از شماره‌های ISBN-10 از یک واریانت الگوریتم لون برای اعتبارسنجی استفاده می‌کنند.

alternatives

در حالی که الگوریتم لون به طور گسترده‌ای استفاده می‌شود، الگوریتم‌های چک‌سوم دیگری نیز برای اهداف مختلف وجود دارد:

1. الگوریتم دَم: یک الگوریتم رقم چک دیگر که تمام خطاهای یک رقمی و تمام خطاهای جابجایی مجاور را شناسایی می‌کند.
2. الگوریتم ورهوف: یک الگوریتم چک‌سوم پیچیده‌تر که تمام خطاهای یک رقمی و بیشتر خطاهای جابجایی را شناسایی می‌کند.
3. رقم چک ISBN-13: از الگوریتم متفاوتی نسبت به ISBN-10 استفاده می‌کند که بر اساس الگوریتم لون است.

تاریخچه

الگوریتم لون توسط هانس پتر لون، یک دانشمند کامپیوتر IBM، در سال ۱۹۵۴ ایجاد شد. لون پیشگام در زمینه علم اطلاعات بود و به خاطر چندین نوآوری، از جمله سیستم نمایه‌سازی KWIC (کلمه کلیدی در متن) شناخته می‌شود.

این الگوریتم در اصل برای محافظت در برابر خطاهای تصادفی طراحی شده بود، نه حملات مخرب. مهم است که توجه داشته باشید که در حالی که الگوریتم لون می‌تواند بسیاری از خطاهای رایج را شناسایی کند، این یک شکل امن از رمزنگاری نیست و نباید برای اهداف امنیت داده‌ها به آن اتکا شود.

با وجود سنش، الگوریتم لون به دلیل سادگی و کارایی‌اش در شناسایی خطاهای رایج به طور گسترده‌ای استفاده می‌شود.

مثال‌های پیاده‌سازی

در اینجا برخی از مثال‌های کد برای پیاده‌سازی الگوریتم لون در زبان‌های برنامه‌نویسی مختلف آورده شده است:

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))  # تولید یک شماره معتبر ۱۶ رقمی
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));  // تولید یک شماره معتبر ۱۶ رقمی
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));  // تولید یک شماره معتبر ۱۶ رقمی
47    }
48}
49

موارد حاشیه‌ای و ملاحظات ویژه

هنگام پیاده‌سازی الگوریتم لون، به موارد حاشیه‌ای و ملاحظات ویژه زیر توجه کنید:

1. اعتبارسنجی ورودی: اطمینان حاصل کنید که ورودی یک رشته عددی معتبر است. کاراکترهای غیر عددی باید به طور مناسب مدیریت شوند (یا حذف شوند یا به عنوان ورودی نامعتبر در نظر گرفته شوند).

2. صفرهای ابتدایی: الگوریتم باید به درستی با شماره‌هایی که دارای صفرهای ابتدایی هستند، کار کند.

3. شماره‌های بزرگ: آماده باشید که شماره‌های بسیار طولانی را که ممکن است از ظرفیت نوع‌های استاندارد عددی در برخی زبان‌های برنامه‌نویسی فراتر بروند، مدیریت کنید.

4. ورودی خالی: تعریف کنید که پیاده‌سازی شما باید چگونه با رشته‌های خالی یا ورودی‌های null برخورد کند.

5. مجموعه‌های کاراکتری غیر استاندارد: در برخی برنامه‌ها، ممکن است با شماره‌هایی روبرو شوید که با کاراکترهایی خارج از محدوده استاندارد ۰-۹ نمایش داده می‌شوند. تعریف کنید که این‌ها چگونه باید مدیریت شوند.

6. ملاحظات عملکرد: برای برنامه‌هایی که نیاز به اعتبارسنجی تعداد زیادی ورودی به سرعت دارند، به بهینه‌سازی پیاده‌سازی الگوریتم فکر کنید.

مثال‌های عددی

1. شماره معتبر کارت اعتباری:

   • شماره: 4532015112830366
   • چک لون: معتبر

2. شماره نامعتبر کارت اعتباری:

   • شماره: 4532015112830367
   • چک لون: نامعتبر

3. شماره معتبر بیمه اجتماعی کانادا:

   • شماره: 046 454 286
   • چک لون: معتبر

4. شماره نامعتبر IMEI:

   • شماره: 490154203237518
   • چک لون: نامعتبر

موارد آزمایشی

برای تأیید پیاده‌سازی الگوریتم لون، می‌توانید از موارد آزمایشی زیر استفاده کنید:

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. گالیان، جوزف. "ریاضیات شماره‌های شناسایی." نشریه ریاضیات کالج، جلد ۲۲، شماره ۳، ۱۹۹۱، صفحات ۱۹۴–۲۰۲. JSTOR، www.jstor.org/stable/2686878.
3. "ISO/IEC 7812-1:2017". سازمان بین‌المللی استانداردسازی. بازیابی شده در ۲ آگوست ۲۰۲۴.
4. کُنث، دونالد. "هنر برنامه‌نویسی کامپیوتر، جلد ۲: الگوریتم‌های نیمه عددی". ادیسون-وِسلی، ۱۹۹۷.