پایان نامه جهت اخذ درجه کارشناسی
عنوان کامل: پروژه بررسی و مقایسهچهار طرح ضرب کننده RNS
فرمت فایل: فایل Word ورد 2007 یا 2003 (Docx یا Doc) قابل ویرایش
تعداد صفحات پروژه: 125
______________________________________________________
مقدمه
همانطور
که می دانیم ضرب پیمانه ای در علم رمزنگاری نقش مهمی ایفا می کند. از جمله
روشهای رمزنگاری که به ضرب کننده پیمانه ای سریع نیاز دارد، روش رمزنگاری
RSA می باشد که در آن نیاز به توان رساندن اعداد بزرگ در پیمانه های بزرگ
می باشد. معمولاً برای نمایش اعداد در این حالات از سیستم باقی مانده (RNS)
استفاده می شود و ضرب (به عنوان هسته توان رسانی) در این سیستم به کار می
رود. در اینجا برای آشنایی بیشتر به توضیح سیستم عددی باقی مانده می پردازیم و به کاربردها و فواید آن اشاراتی خواهیم داشت.
سیستم عددی باقیمانده (Residue Number System (RNSدر
حدود 1500 سال پیش معمایی به صورت شعر توسط یک شاعر چینی به صورت زیر بیان
شد. «آن چه عددی است که وقتی بر اعداد 3، 5و7 تقسیم می شود باقیمانده های
2، 3و2 بدست می آید؟» این معما یکی از قدیمی ترین نمونه های سیستم عددی باقی
مانده است. در RNS یک عدد توسط لیستی از باقیمانده هایش برn
عدد صحیح مثبت m1 تا mn که این اعداد دو به دو نسبت به هم اولند (یعنی
بزرگترین مقسوم علیه مشترک دوبدوشان یک است) به نمایش در می آید. به اعداد
m1 تا mn پیمانه (moduli) می گویند. حاصلضرب این nعدد، تعداد
اعدادی که می توان با این پیمانه ها نشان داد را بیان می کند. هر باقیمانده
xi را به صورت xi=Xmod mi نمایش می دهند. در مثال بالا عدد مربوطه به صورت
X= (2/3/2) RNS (7/5/3) به نمایش در می آید که X mod7=2 و X mod5=3 و X
mod3=2. تعداد اعداد قابل نمایش در این مثال می باشد. می توان هرمجموعه
105 تایی از اعداد صحیح مثبت یا منفی متوالی را با این سیستم عددی
باقیمانده نمایش داد. اثبات این که هر عدد صحیح موجود در محدوده،
نمایش منحصر به فردی در این سیستم دارد به کمک قضیه باقی مانده های
چینی (Chinese Remainder Theorem (CRT)) امکان پذیر است.