مقایسه چهار طرح ضرب کننده RNS : پایان نامه کارشناسی ارشد معماری کامپیوتر

شرح مختصر مقایسه چهار طرح ضرب کننده RNS

همانطور که می دانیم ضرب پیمانه ای در علم رمزنگاری نقش مهمی ایفا می کند. از جمله روشهای رمزنگاری که به ضرب کننده پیمانه ای سریع نیاز دارد، روش رمزنگاری RSA می باشد که در آن نیاز به توان رساندن اعداد بزرگ در پیمانه های بزرگ می باشد. معمولاً برای نمایش اعداد در این حالات از سیستم باقی مانده (RNS) استفاده می شود و ضرب (به عنوان هسته توان رسانی) در این سیستم به کار می رود.

در اینجا برای آشنایی بیشتر به توضیح سیستم عددی باقی مانده می پردازیم و به کاربردها و فواید آن اشاراتی خواهیم داشت.

1-1 سیستم عددی باقیمانده (Residue Number System (RNS))

در حدود 1500 سال پیش معمایی به صورت شعر توسط یک شاعر چینی به صورت زیر بیان شد. «آن چه عددی است که وقتی بر اعداد 3،5و7 تقسیم می شود باقیمانده های 2،3و2 بدست می آید؟» این معما یکی از قدیمی ترین نمونه های سیستم عددی باقی مانده است.

در RNS یک عدد توسط لیستی از باقیمانده هایش برn  عدد صحیح مثبت m₁ تا m_n که این اعداد دو به دو نسبت به هم اولند (یعنی بزرگترین مقسوم علیه مشترک دوبدوشان یک است) به نمایش در می آید. به اعداد m₁ تا m_n پیمانه (moduli)
می گویند. حاصلضرب این nعدد،  تعداد اعدادی که می توان با این پیمانه ها نشان داد را بیان می کند. هر باقیمانده x_i را به صورت x_i=Xmod m_i نمایش می دهند. در مثال بالا عدد مربوطه به صورت X=(2/3/2)_RNS(7/5/3) به نمایش در می آید که X mod7=2 و X mod5=3 و X mod3=2. تعداد اعداد قابل نمایش در این مثال  می باشد. می توان هرمجموعه 105 تایی از اعداد صحیح مثبت یا منفی متوالی را با این سیستم عددی باقیمانده نمایش داد.

اثبات این که هر عدد صحیح موجود در محدوده، نمایش منحصر به فردی در این سیستم دارد به کمک قضیه باقی‌مانده های چینی(Chinese Remainder Theorem (CRT)) امکان پذیر است. این قضیه به صورت زیر بیان می شود:

1-2 قضیه باقی مانده های چینی:

اعداد صحیح مثبت  را که نسبت به هم دو به دو اول هستند در نظر بگیرید و M را حاصلضرب  فرض کنید. همچنین اعداد  را فرض کنید. اثبات می شود که فقط و فقط یک عدد صحیح U وجود دارد که شرایط زیر دارد:

فهرست مطالب مقایسه چهار طرح ضرب کننده RNS

1- مقدمه1

1-1 سیستم عددی باقیمانده 1

1-2 قضیه باقی مانده های چینی2

1-3 کاربردهای RNS 3

2- روشهای ضرب پیمانه ای 5

2-1 روش مونتگمری5

2-2 بررسی اجمالی روشهای موجود پیاده سازی ضرب در RNS 6

2-3 نکاتی پیرامون چهار طرح مورد نظر 7

3- طرح اول8

3-1 مقدمه8

3-2 بررسی سوابق8

3-3 الگوریتم9

3-4 پیاده سازی سخت افزاری 10

3-5 محاسبه پیچیدگی مساحت و تأخیر طرح اول 13

4- طرح دوم15

4-1 مقدمه15

4-2 بررسی سوابق15

4-3 الگوریتم15

4-4 پیاده سازی سخت افزاری 18

4-5 محاسبه پیچیدگی مساحت و تأخیر طرح دوم 20

5- طرح سوم21

5-1 تبدیل سیستم RNS (Residue Conversion) 28

5-2 پیاده سازی سخت افزاری30

5-2-1 پیاده سازی تبدیل RNS 31

5-2-2 پیاده سازی بخش اصلی الگوریتم (الگوریتم مونتگمری با RNS)  34

5-3- محاسبه پیچیدگی مساحت و تأخیر طرح سوم    36

5-3-1 عناصر وابسته به ROM36

5-3-2 عناصر ریاضی36

5-3-3 تأخیر و مساحت تبدیل کننده RNS استاندارد  37

5-3-4 محاسبه مساحت و تأخیر تبدیل کننده RNS سریع    44

5-3-5 مساحت و تأخیر طرح سوم 50

5-4 نتایج پیاده سازی در طرح سوم . 56

6- طرح چهارم. 58

6-1 بیان مقاله در مورد سیستم RNS  59

6-2 بیان مقاله از ضرب پیمانه ای بدون تقسیم (روش مونتگمری)60

6-3 بررسی صحت الگوریتم62

6-4 روش تبدیل RNS 66

6-5 پیاده سازی سخت افزاری 67

6-5-1 تبدیل RNS ناقص68

6-5-2 پیاده سازی بخش اصلی طرح چهارم (الگوریتم مونتگمری) 68

6-6 محاسبه پیچیدگی تأخیر و مساحت طرح چهارم   70

6-6-1 محاسبه تأخیر و مساحت تبدیل RNSناقص   70

6-6-2 محاسبه تأخیر و مساحت در طرح چهارم 72

6-7 نتایج شبیه سازی در طرج چهارم. 80

7- مقایسه  طرح ها وجمع بندی . 81

7-1- مقایسه چهار طرح. 81

7-2- جمع بندی . 98

8- مراجع

9- ضمائم

الف – کدهای VHDL طرح اول

ب – کدهای VHDL طرح دوم

ج – کدهای VHDL طرح سوم

د – کدهای VHDL طرح چهارم

هـ – MOMA