الگوریتم لان

الگوریتم لان یا فرمول لان، که به الگوریتم "پیمانه ۱۰" نیز مشهور است، یک فرمول ساده برای درستی یابی تعداد زیادی شماره شناسایی است، مانند شماره کارت های اعتباری، شماره های IMEI و شماره ملی. این روش توسط Hans Peter Luhn ابداع شد و در U.S. Patent No. ۲،۹۵۰،۰۴۸ توصیف شده. این الگوریتم به وفور استفاده می شود و به منظور یک تابع درهم‌ساز رمزنگارانه استفاده نمی شود. در واقع این روش برای حفاظت در برابر خطاهای تصادفی می باشد نه حملات عمدی. بسیاری از شماره های کارت های اعتباری و شناسه های دولتی از این روش برای متمایز کردن شماره های معتبر از هر جایگشت نا معتبری از اعداد استفاده می شود.

نفاط قوت و ضعف

الگوریتم لان همه خطاهای تک رقمی را تشخیص می دهد، و همینطور جابجا شدن دو رقم کنار هم را. ولی جابجایی ۰۹ به ۹۰ و برعکس را نمی تواند تشخیص بدهد. و همینطور ۷ تا از ۱۰ تا خطای دوقلو را می تواند تشخیص دهد(این موارد را تشخیص نمی دهد: ۲۲ به ۵۵و ۳۳ به ۶۶ یا ۴۴ به ۷۷). الگوریتم های پیچیده تر مانند الگوریتم Verhoeff می توانند خطاهای جابجایی بیشتری را تشخیص دهند. الگوریتم Luhn mod N‌ تعمیم این الگوریتم برای رشته های غیر عددی می باشد. به دلیل اینکه این الگوریتم به ترتیب راست به چپ روی ارقام عمل می کند و رقم های صفر فقط در صورتی که باعث تغییر مکان شوند نتیجه را تغییر می دهند، اضافه کردن صفر به اول یک رشته عددی محاسبات را تغییر نمی دهد. بنابراین، اجرای الگوریتم لان قبل و بعد از اضافه کردن چند رقم صفر به اول رشته نتیجه یکسانی خواهد داشت.

توضیح غیر رسمی

این فرمول یک عدد را در برابر رقم تطبیق آن درستی یابی می کند،‌ که عموما به بک شماره حساب پاره ای به منظور تولید شماره حساب کامل اضافه می شود. این شماره حساب باید تست زیر را پاس کند:

1. با شروع از اولین رقم سمت راست و حرکت به سمت چپ،‌ یکی در میان رقم های شماره زوج را دو برابر کند.
2. ارقام اعداد دو برابر شده را با اعدادی که دو برابر نشده اند جمع کند.
3. اگر جواب جمع در پیمانه ی ۱۰ صفر شود،‌ این شماره حساب درست می باشد، در غیر این صورت اعتبار ندارد.

Account number	7	9	9	2	7	3	9	8	7	1	x
Double every other	7	18	9	4	7	6	9	16	7	2	x
Sum of digits	7	9	9	4	7	6	9	7	7	2	=67

رقم تطبيق (x) بوسيله ي محاسبه ي ضرب جمع ارقام در 9 در پيمانه 10 بدست مي‌ آيد. به بيان Layman:

1. مجموع ارقام 67 را محاسبه كن(67).
2. در 9 ضرب كن (603).
3. رقم آخر را بگير(3).
4. نتيجه رقم تطبيق مي باشد.

روش جايگزين:‌ رقم تطبيق بوسيله ي محاسبه تفريق رقم اول مجموع ارقام از 10 بدست مي آيد.

1. مجموع ارقام 67 را محاسبه كن(67).
2. رقم يكان آن را در نظر بگير(7).
3. رقم يكان را از 10 كم كن.
4. نتيجه 3 مي شود كه رقم تطبيق است.

همه ي اين اعداد 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 بود،‌ شماره حساب احتمالا معتبر مي باشد. 3 تنها رقم معتبر است كه مجموع 70 را توليد مي كند كه مضربي از 10 مي باشد.
4. بنابراين همه شماره حساب ها نا معتبر هستند بجز 79927398713 كه داراي رقم تطبيق درست مي باشد.

پياده سازي درستي يابي رقم تطبيق

در پايتون:

def is_luhn_valid(cc):
    num = map(int, str(cc))
    return sum(num[::-2] + [sum(divmod(d * 2, 10)) for d in num[-2::-2]]) % 10 == 0

محاسبه رقم تطبيق

پياده سازي بالا درستي يك شماره ورودي را با يك شماره تطبيق چك مي كند. براي محاسبه رقم تطبيق تغيير كوچكي در پياده سازي نياز است:

1. سوييج كردن بين ضرب فرد و زوج.
2. اگر مجموع به پيمانه 10 صفر شد آنگاه رقم تطبيق صفر است.
3. در غير اين صورت رقم تطبيق برابر رقم اول مجموع - 10 مي باشد.

در پايتون:

def calculate_luhn(cc):
    num = map(int, str(cc))
    check_digit = 10 - sum(num[-2::-2] + [sum(divmod(d * 2, 10)) for d in num[::-2]]) % 10
    return 0 if check_digit == 10 else check_digit

پياده سازي هاي ديگر

• Luhn implementations in Javascript
• Luhn generation and validation in php
• Validation of Luhn in PHP
• Implementation of the above php class regarding alphanumerics
• Ruby: Luhn validation, Luhn generation

همچنين نگاه كنيد

• شماره كارت بانكي
• Luhn checking bank card numbers

منابع

• U.S. Patent ۲٬۹۵۰٬۰۴۸, Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.