ویرگول
ورودثبت نام
SMAH1
SMAH1
خواندن ۴ دقیقه·۴ سال پیش

الگوریتم یافتن وارون ضربی به روش بسط اقلیدسی

تصمیم گرفتم کمی در مورد الگوریتم یافتن وارون پیمانه‌ای یا وارون ضربی بنویسم.من فرض می‌کنم که شما در مورد «همنهشتی» و «باقیمانده در پیمانه» اطلاع دارید.قبل از ورود به بحث یک نمونه‌ی کاربرد «یافتن وارون ضربی» را مثال می‌زنم.

در الگوریتم RSA،که برای رمزنگاری با کلید خصوصی و عمومی به کار می‌رود،پس از مشخص کردن کلید عمومی شامل دو مقدار n و e، باید کلید خصوصی رو محاسبه کنید که همان وارون ضربی e در پیمانه‌ی φ(n) است.

قبل از اینکه در موردالگوریتم بنویسم، کمی در مورد مفهوم وارون ضربی اطلاعات کسب کنیم.

کمی ریاضی

تعریف: وارون ضربی e به پیمانه‌ی n برابر عدد صحیح مثبت d است اگر d*e ≡ 1 (mod n)

به عبارت فارسی، اگر عدد e رو در d ضرب کنیم، مقدار آن به پیمانه‌ی n با یک برابر است.به عبارت دیگر باقیمانده‌ی حاصلضرب e*d به n برابر یک است.

البته تمام اعداد ممکن برای e دارای وارون ضربی نیستند! شرط «لازم و کافی» برای اینکه e دارای وارون ضربی به پیمانه‌ی n باشد این است که این دو عدد نسبت به هم اول باشند.در نتیجه مثلا عدد ۶ وارون ضربی برای پیمانه‌ی ۳۳ ندارد (چون ب‌م‌م آنها ۳ است) ولی عدد ۱۰ می‌تواند وارون ضربی در پیمانه‌ی ۳۳ داشته باشد.جالب است بدانید که وارون ضربی عدد ۱۰ به پیمانه‌ی ۳۳، خوده عدد ۱۰ است.یعنی ۱۰*۱۰ که ۱۰۰ می‌شود، دارای باقیمانده‌ی ۱ به پیمانه‌ی ۳۳ است.

توصیف الگوریتم بسط اقلیدسی برای یافتن وارون ضربی

فرض کنید در دو فرمول زیر:

r = r1 - q * r2
t = t1 - q * t2

مقادیر r1،r2،t1،t2 معلوم باشند و هدف یافتن مقادیر q و r و t است (به همین ترتیب نوشته شده یافته خواهند شد).

فرض کنید می‌خواهیم وارون ضربی e به پیمانه‌ی n را محاسبه کنیم، داریم:

  • گام اول) مقدار دهی اولیه متغیرهای معلوم: r1=n و r2=e و t1=0 و t2=1
  • گام دوم) اگر مقدار r2 صفر است، مقدار t1 را به عنوان وارن ضربی معرفی کرده و الگوریتم پایان می‌یابد.
  • گام سوم)‌ مقدار q و r که به ترتیب خارج قسمت و باقیمانده حاصل تقسیم r1 به r2 هستند را محاسبه کنید (فرمول اول)
  • گام چهارم) مقدار t را با توجه به مقدار محاسبه شده‌ی q حساب کنید (فرمول دوم)
  • گام پنجم)‌ مقادیر r2 و r و t2 و t را به ترتیب به مقادیر r1 و r2 و t1 و t2 منتقل کنید.
  • گام ششم) به گام دوم بروید.

اگر نوشته‌های فوق کمی پیچیده به نظر می‌رسد، اصلا نترسید! در اینجا با مثال نمونه‌ای را با هم حل می‌کنیم.

یک نمونه بسط اقلیدسی

می‌خواهیم وارون ضربی ۷ به پیمانه‌ی ۱۶۰ را محاسبه کنیم.پیشنهاد می‌کنم که جدول زیر را بکشید:

به چینش ستون‌ها توجه کنید. فرمول‌ها برای راحتی در بالای جدول نشان داده شده‌اند.البته جدول را هم مقدار دهی اولیه کرده‌ایم و اعداد با رنگ قرمز مقادیر اولیه (مطابق با گام اول) هستند.

سپس عدد ۱۶۰ را به ۷ تقسیم می‌کنیم که خارج قسمت ۲۲ است:

مقدار دهی اولیه جدول
مقدار دهی اولیه جدول

و باقیمانده آن ۶ است:

حالا با داشتن مقدار q می‌توانیم مقدار t را (مطابق فرمول دوم) محاسبه کنیم(t = ۰ - ۲۲ * ۱ = -۲۲):

پس از تکمیل این ردیف به سراغ ردیف بعد می‌رویم.برای این کار باید برخی مقادیر ردیف اول را به ردیف دوم منتقل کنیم:

مطابق عملیات‌هایی که برای یافتن q و r و سپس t برای ردیف یک انجام داده‌ایم، به تکمیل این ردیف می‌پردازیم:

همین طور هر ردیف را پر کرده و محاسبه می‌کنیم تا جایی که r2 صفر شود:

پس میتوانیم مقدار t1 را به عنوان وارون ضربی مشخص کنیم:

وضعیت نهایی جدول
وضعیت نهایی جدول

در نتیجه وارون ضربی ۷ به پیمانه‌ی ۱۶۰ عدد ۲۳ است.

فرآیند محاسبات بالا را در تصویر متحرک زیر می‌توانید ببینید:

نحوه محاسبه وارون ضربی عدد ۷ به پیمانه ۱۶۰
نحوه محاسبه وارون ضربی عدد ۷ به پیمانه ۱۶۰

نکته مهم

در ردیف آخر (که r2 صفر شده است) مقدار t2 به عدد پیمانه‌ی فرض شده (در اینجا ۱۶۰) بخش‌پذیر است.تاکید می‌کنم که این نکته همواره برقرار است. یعنی همیشه در آخرین ستون که عدد t1 را به عنوان وارون ضربی معرفی می‌کنید، عدد t2 «باید» به عدد n شما بخش‌پذیر باشد.از این نکته برای تایید محاسبات می‌توانید استفاده کنید. یعنی اگر r2 صفر شد و t2 به n بخش‌پذیر «نبود»، مطمئن باشید که در محاسبات «اشتباه» کرده‌اید.

یک نمونه‌ی دیگر

فرض کنید می‌خواهیم وارون ضربی عدد ۵ به پیمانه‌ی ۱۰۰۸ را محاسبه کنیم. نتیجه محاسبات را در تصویر زیر مشاهده می‌کنید:

نحوه محاسبه وارون ضربی عدد ۵ به پیمانه ۱۰۰۸
نحوه محاسبه وارون ضربی عدد ۵ به پیمانه ۱۰۰۸

همانطور که می‌بیند وارون ضربی محاسبه شده عدد «منفی» است. البته این عدد درست است ولی همواره ما مقدار مثبت آن را لازم داریم و چون این عدد در پیمانه‌ی ۱۰۰۸ محاسبه شده است پس برای مثبت کردن آن کافیست مقدار ۱۰۰۸ را به عدد منفی بیافزاییم یعنی:

d = ۱۰۰۸ +(- ۴۰۳)= ۶۰۵

پس وارون ضربی عدد ۵ به پیمانه‌ی ۱۰۰۸ مقدار ۶۰۵ است.

نکته تکمیلی

بر اساس قضیه اویلر، اگر n و e نسبت به هم اول باشند و d وارون ضربی e به پیمانه‌ی n باشد، می‌توان نتیجه گرفت:

محاسبه وارون ضربی بر اساس قضیه اویلر
محاسبه وارون ضربی بر اساس قضیه اویلر

در نتیجه به این روش هم می‌توان وارون ضربی را محاسبه نمود.توجه کنید که هر کدام از روش‌های بالا در پیاده سازی برنامه نویسی، مزایا و معایب خود را دارند.

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