الگوریتم لان

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

نقاط قوت و ضعف[ویرایش]

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

توضیح غیر رسمی[ویرایش]

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

  1. با شروع از اولین رقم سمت راست و حرکت به سمت چپ، یکی در میان رقم های شماره زوج را دو برابر کند.
  2. ارقام اعداد دو برابر شده را با اعدادی که دو برابر نشده اند جمع کند.
  3. اگر جواب جمع در پیمانه ی ۱۰ صفر شود، این شماره حساب درست می باشد، در غیر این صورت اعتبار ندارد.
Account number ۷ ۹ ۹ ۲ ۷ ۳ ۹ ۸ ۷ ۱ x
Double every other ۷ ۱۸ ۹ ۴ ۷ ۶ ۹ ۱۶ ۷ ۲ x
Sum of digits ۷ ۹ ۹ ۴ ۷ ۶ ۹ ۷ ۷ ۲ ۷

رقم تطبیق (x) بوسیله ی محاسبه ی ضرب جمع ارقام در ۹ در پیمانه ۱۰ بدست می آید. به بیان Layman:

  1. مجموع ارقام ۶۷ را محاسبه کن(۶۷).
  2. در ۹ ضرب کن (۶۰۳).
  3. رقم آخر را بگیر(۳).
  4. نتیجه رقم تطبیق می باشد.

روش جایگزین: رقم تطبیق بوسیله ی محاسبه تفریق رقم اول مجموع ارقام از ۱۰ بدست می آید.

  1. مجموع ارقام ۶۷ را محاسبه کن(۶۷).
  2. رقم یکان آن را در نظر بگیر(۷).
  3. رقم یکان را از ۱۰ کم کن.
  4. نتیجه ۳ می شود که رقم تطبیق است.

همه ی این اعداد ۷۹۹۲۷۳۹۸۷۱۰, ۷۹۹۲۷۳۹۸۷۱۱, ۷۹۹۲۷۳۹۸۷۱۲, ۷۹۹۲۷۳۹۸۷۱۳, ۷۹۹۲۷۳۹۸۷۱۴, ۷۹۹۲۷۳۹۸۷۱۵, ۷۹۹۲۷۳۹۸۷۱۶, ۷۹۹۲۷۳۹۸۷۱۷, ۷۹۹۲۷۳۹۸۷۱۸, ۷۹۹۲۷۳۹۸۷۱۹ به صورت زیر درستی یابی می شوند.

  1. همه ارقام را یکی در میان از سمت راست دو برابر کن: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = ۱۸
  2. مجموع همی ارقام را محاسبه کن (ارقام داخل پرانتز جواب ضرب های مرحله ۱ هستند): + x(رقم تطبیق) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
  3. اگر مجموع مضربی از ۱۰ بود، شماره حساب احتمالاً معتبر می باشد. ۳ تنها رقم معتبر است که مجموع ۷۰ را تولید می کند که مضربی از ۱۰ می باشد.
  4. بنابراین همه شماره حساب ها نا معتبر هستند بجز ۷۹۹۲۷۳۹۸۷۱۳ که دارای رقم تطبیق درست می باشد.

پیاده سازی درستی یابی رقم تطبیق[ویرایش]

در پایتون:

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 == ۰

محاسبه رقم تطبیق[ویرایش]

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

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

در پایتون:

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

پیاده سازی های دیگر[ویرایش]

همچنین نگاه کنید[ویرایش]

منابع[ویرایش]