تصمیم گرفتم کمی در مورد الگوریتم یافتن وارون پیمانه‌ای یا وارون ضربی بنویسم.من فرض می‌کنم که شما در مورد «همنهشتی» و «باقیمانده در پیمانه» اطلاع دارید.قبل از ورود به بحث یک نمونه‌ی کاربرد «یافتن وارون ضربی» را مثال می‌زنم.
در الگوریتم 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 را محاسبه کنیم، داریم:
اگر نوشته‌های فوق کمی پیچیده به نظر می‌رسد، اصلا نترسید! در اینجا با مثال نمونه‌ای را با هم حل می‌کنیم.
می‌خواهیم وارون ضربی ۷ به پیمانه‌ی ۱۶۰ را محاسبه کنیم.پیشنهاد می‌کنم که جدول زیر را بکشید:
به چینش ستون‌ها توجه کنید. فرمول‌ها برای راحتی در بالای جدول نشان داده شده‌اند.البته جدول را هم مقدار دهی اولیه کرده‌ایم و اعداد با رنگ قرمز مقادیر اولیه (مطابق با گام اول) هستند.
سپس عدد ۱۶۰ را به ۷ تقسیم می‌کنیم که خارج قسمت ۲۲ است:
و باقیمانده آن ۶ است:
حالا با داشتن مقدار q میتوانیم مقدار t را (مطابق فرمول دوم) محاسبه کنیم(t = ۰ - ۲۲ * ۱ = -۲۲):
پس از تکمیل این ردیف به سراغ ردیف بعد می‌رویم.برای این کار باید برخی مقادیر ردیف اول را به ردیف دوم منتقل کنیم:
مطابق عملیات‌هایی که برای یافتن q و r و سپس t برای ردیف یک انجام داده‌ایم، به تکمیل این ردیف می‌پردازیم:
همین طور هر ردیف را پر کرده و محاسبه می‌کنیم تا جایی که r2 صفر شود:
پس میتوانیم مقدار t1 را به عنوان وارون ضربی مشخص کنیم:
در نتیجه وارون ضربی ۷ به پیمانه‌ی ۱۶۰ عدد ۲۳ است.
فرآیند محاسبات بالا را در تصویر متحرک زیر می‌توانید ببینید:
در ردیف آخر (که r2 صفر شده است) مقدار t2 به عدد پیمانه‌ی فرض شده (در اینجا ۱۶۰) بخش‌پذیر است.تاکید می‌کنم که این نکته همواره برقرار است. یعنی همیشه در آخرین ستون که عدد t1 را به عنوان وارون ضربی معرفی می‌کنید، عدد t2 «باید» به عدد n شما بخش‌پذیر باشد.از این نکته برای تایید محاسبات می‌توانید استفاده کنید. یعنی اگر r2 صفر شد و t2 به n بخش‌پذیر «نبود»، مطمئن باشید که در محاسبات «اشتباه» کرده‌اید.
فرض کنید می‌خواهیم وارون ضربی عدد ۵ به پیمانه‌ی ۱۰۰۸ را محاسبه کنیم. نتیجه محاسبات را در تصویر زیر مشاهده می‌کنید:
همانطور که می‌بیند وارون ضربی محاسبه شده عدد «منفی» است. البته این عدد درست است ولی همواره ما مقدار مثبت آن را لازم داریم و چون این عدد در پیمانه‌ی ۱۰۰۸ محاسبه شده است پس برای مثبت کردن آن کافیست مقدار ۱۰۰۸ را به عدد منفی بیافزاییم یعنی:
d = ۱۰۰۸ +(- ۴۰۳)= ۶۰۵
پس وارون ضربی عدد ۵ به پیمانه‌ی ۱۰۰۸ مقدار ۶۰۵ است.
بر اساس قضیه اویلر، اگر n و e نسبت به هم اول باشند و d وارون ضربی e به پیمانه‌ی n باشد، می‌توان نتیجه گرفت:
در نتیجه به این روش هم می‌توان وارون ضربی را محاسبه نمود.توجه کنید که هر کدام از روش‌های بالا در پیاده سازی برنامه نویسی، مزایا و معایب خود را دارند.
