الگوریتم لون

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

الگوریتم Luhn یا فرمول Luhn ، همچنین به عنوان الگوریتم " modulus 10 " یا "mod 10" شناخته می شود ، که به نام خالق آن، دانشمند IBM هانس پیتر لون ، نامگذاری شده است، یک فرمول ساده چکی است که برای اعتبارسنجی انواع اعداد شناسایی، مانند اعتبار استفاده می شود. شماره کارت ، شماره IMEI ، شماره شناسه ارائه دهنده ملی در ایالات متحده، شماره بیمه اجتماعی کانادا ، شماره شناسایی اسرائیل ، شماره شناسایی آفریقای جنوبی ، شماره شناسایی ملی سوئد ، شماره‌های هویت شرکتی سوئدی (OrgNr)، شماره‌های تامین اجتماعی یونان (ΑΜΚΑ)، شماره سیم‌کارت، شماره درخواست ثبت اختراع اروپایی و کدهای نظرسنجی که در رسیدهای مک‌دونالد ، تاکو بل ، و شرکت تامین تراکتور نمایش داده می‌شوند. این در ثبت اختراع ایالات متحده شماره 2,950,048، اعطا شده در 23 اوت 1960 توضیح داده شده است. [1]

این الگوریتم در حوزه عمومی است و امروزه به طور گسترده مورد استفاده قرار می گیرد. در ISO/IEC 7812-1 مشخص شده است . [2] در نظر گرفته نشده است که یک تابع هش رمزنگاری امن باشد . برای محافظت در برابر خطاهای تصادفی طراحی شده است، نه حملات مخرب. اکثر کارت های اعتباری و بسیاری از شماره های شناسایی دولتی از این الگوریتم به عنوان روشی ساده برای تشخیص اعداد معتبر از اعداد اشتباه تایپ شده یا نادرست استفاده می کنند.

توضیحات

رقم چک به صورت زیر محاسبه می شود:

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

مثالی برای محاسبه رقم چک

مثالی از شماره حساب "7992739871" را در نظر بگیرید (فقط "Payload"، رقم چک هنوز درج نشده است):

7 9 9 2 7 3 9 8 7 1
ضرب کننده ها 1 2 1 2 1 2 1 2 1 2
= = = = = = = = = =
7 18 9 4 7 6 9 16 7 2
مجموع ارقام 7 9 (1+8) 9 4 7 6 9 7 (1+6) 7 2

مجموع ارقام حاصل 67 است.

رقم چک برابر است با.

این باعث می شود که شماره حساب کامل 79927398713 خوانده شود.

مثالی برای اعتبارسنجی رقم چک

  1. برای اعتبارسنجی، رقم چک (آخرین رقم) عدد را رها کنید. (به عنوان مثال 79927398713 -> 7992739871)
  2. رقم چک را محاسبه کنید (به بالا مراجعه کنید)
  3. نتیجه خود را با رقم اصلی مقایسه کنید. اگر هر دو عدد مطابقت داشته باشند، نتیجه معتبر است. (به عنوان مثال).

نقاط قوت و ضعف

الگوریتم Luhn هرگونه خطای تک رقمی و همچنین تقریباً تمام جابجایی ارقام مجاور را تشخیص می دهد. با این حال، جابجایی دنباله دو رقمی 09 به 90 (یا برعکس) را تشخیص نمی دهد. اکثر خطاهای احتمالی دوقلو را شناسایی می کند ( 2255 ، 3366 یا 4477 را تشخیص نمی دهد).

سایر الگوریتم های پیچیده تر چک رقمی (مانند الگوریتم Verhoeff و الگوریتم Damm ) می توانند خطاهای رونویسی بیشتری را شناسایی کنند. الگوریتم Luhn mod N پسوندی است که رشته های غیر عددی را پشتیبانی می کند.

از آنجایی که الگوریتم روی ارقام به صورت راست به چپ عمل می‌کند و ارقام صفر تنها در صورتی بر نتیجه تأثیر می‌گذارند که باعث جابجایی در موقعیت شوند، صفر کردن ابتدای رشته‌ای از اعداد تأثیری بر محاسبه ندارد. بنابراین، سیستم‌هایی که به تعداد مشخصی از ارقام اضافه می‌کنند (مثلاً با تبدیل 1234 به 0001234) می‌توانند اعتبارسنجی Luhn را قبل یا بعد از padding انجام دهند و به همان نتیجه برسند.

این الگوریتم در یک پتنت ایالات متحده [1] برای یک دستگاه مکانیکی ساده و دستی برای محاسبه جمع کنترل ظاهر شد. دستگاه مود 10 sum را به روش مکانیکی گرفت. ارقام جایگزینی ، یعنی نتایج حاصل از دو و کاهش، به صورت مکانیکی تولید نشدند. در عوض، ارقام به ترتیب تغییر یافته خود بر روی بدنه دستگاه علامت گذاری شده بودند.

اجرای شبه کد

تابع زیر یک شماره کارت، از جمله رقم چک، را به عنوان آرایه ای از اعداد صحیح می گیرد و اگر رقم چک صحیح باشد، درست است، در غیر این صورت نادرست است.

تابع isValid(شماره کارت[1.. طول])
    مجموع: = 0
    برابری: = طول مد 2
    برای من از 1 تا طول انجام دهید
       اگر من mod 2 = برابری پس از آن
          مجموع := جمع + شماره کارت[i]
       otherif cardNumber[i] > 4 سپس
          مجموع := مجموع + 2*شماره کارت[i] - 9
       دیگر
          مجموع := مجموع + 2*شماره کارت[i]
       پایان اگر
    پایان برای
    بازگشت جمع مد 10 = 0
 عملکرد پایانی

منابع

  1. ^ a b ثبت اختراع ایالات متحده 2950048A , Luhn, Hans P. , "Computer for verifying numbers" منتشر شده در 23/08/1960 
  2. «ضمیمه B: فرمول لون برای محاسبه مدول - 10 رقم چک «دو-افزودن-دو»». کارت های شناسایی — شناسایی صادرکنندگان — قسمت 1: سیستم شماره گذاری (استاندارد). سازمان بین المللی استانداردسازی ، کمیسیون بین المللی الکتروتکنیکی . ژانویه 2017. ISO/IEC 7812 -1:2017.

پیوندهای خارجی