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

اختصاصی از یارا فایل دانلود پایان نامه مقایسه چهارطرح ضرب کننده RNS دانلود با لینک مستقیم و پرسرعت .

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

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

1-1 سیستم عددی باقیمانده (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)) امکان پذیر است. این قضیه به صورت زیر بیان می شود:

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

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

که U برابر است با:

اعمال ریاضی جمع، تفریق و ضرب به راحتی و به صورت زیر در این سیستم انجام می شود.

در فرمول بالا به جای علامت می توان هر کدام از علائم +،-،* را قرار داد.

سه عمل ریاضی (+،-،*) در این سیستم عددی راحت‌تر از سیستم نمایش عادی اعداد انجام می شود، زیرا هنگام انجام این عمل در این سیستم رقم نقلی (carry) بین بخشها رد و بدل نمی شود. در واقع انجام عملیات مربوط به مانده های هر پیمانه تاثیری روی دیگر عمل ها ندارد. یعنی محاسبه “” می تواند بطور مستقل (و در واقع موازی) انجام شود و نتیجه آن تاثیری در بقیه “”ها ندارد. بدین ترتیب عملیات ریاضی سریعتر (بعلت موازی شدن) و راحت تر (بعلت عدم تاثیرگذاری محاسبات مربوط به هر مانده برهم) انجام می شود.

1- مقدمه1
1-1 سیستم عددی باقیمانده1
1-2 قضیه باقی مانده های چینی2
1-3 کاربردهای RNS3
2- روشهای ضرب پیمانه ای 5
2-1 روش مونتگمری5
2-2 بررسی اجمالی روشهای موجود پیاده سازی ضرب در RNS6
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 پیاده سازی تبدیل RNS31
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 روش تبدیل RNS66
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

شامل 150 صفحه فایل word

به همراه تصاویر و نمودار ها

پروژه مقایسه چهار طرح ضرب کننده RNS

اختصاصی از یارا فایل پروژه مقایسه چهار طرح ضرب کننده RNS دانلود با لینک مستقیم و پرسرعت .

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:126

فهرست مطالب:
عنوان                                     صفحه
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 عناصر وابسته به ROM    36
        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     

چکیده
هدف از این پروژه مقایسه چهارطرح ضرب کننده RNS می باشد. بدین منظور با بهره گیری از پیاده سازی این چهار طرح با نرم افزار VHDL به مقایسه آنها می‌پردازیم. RNS یک روش نمایش اعداد است که در آن هر عدد به وسیله باقی مانده‌های تقسیم آن بر مجموعه ای از اعداد دو به دو نسبت به هم اول نمایش داده
می شود. با کمک قضیه باقی مانده چینی، اثبات می شود که در RNS نمایش هر عدد منحصر به فرد می باشد برای ضرب در RNS نیاز به ضرب پیمانه ای خواهد بود. روشهای ضرب پیمانه ای برحسب اینکه کاهش به پیمانه، در کدام مرحله ضرب انجام گیرد. به دو دسته «کاهش در حین ضرب (RDM)» و «کاهش بعد از ضرب (RAM)» تقسیم می شوند. دو طرح اول این پروژه با تکنیک RAM و دو طرح دوم با تکنیک RDM کار می‌کنند.

1- مقدمه

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

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

1-1 سیستم عددی باقیمانده (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)) امکان پذیر است. این قضیه به صورت زیر بیان می شود:

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

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

   ,        ,    

که U برابر است با:

اعمال ریاضی جمع، تفریق و ضرب به راحتی و به صورت زیر در این سیستم انجام می شود.

   ,  

در فرمول بالا به جای علامت می توان هر کدام از علائم +،-،* را قرار داد.

سه عمل ریاضی (+،-،*) در این سیستم عددی راحت‌تر از سیستم نمایش عادی اعداد انجام می شود، زیرا هنگام انجام این عمل در این سیستم رقم نقلی (carry) بین بخشها رد و بدل نمی شود. در واقع انجام عملیات مربوط به مانده های هر پیمانه تاثیری روی دیگر عمل ها ندارد. یعنی محاسبه “” می تواند بطور مستقل (و در واقع موازی) انجام شود و نتیجه آن تاثیری در بقیه “”ها ندارد. بدین ترتیب عملیات ریاضی سریعتر (بعلت موازی شدن) و راحت تر (بعلت عدم تاثیرگذاری محاسبات مربوط به هر مانده برهم) انجام می شود.

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

سیستم عددی باقی مانده در چند دهه اخیر مورد توجه قرار گرفته، زیرا می توان بعضی از اعمال ریاضی را تحت RNS به صورت چند مجموعه زیر عمل ریاضی تقسیم کرد. ولی به دلیل اینکه این اعمال فقط شامل ضرب، جمع و تفریق هستند از RNS در محاسبات “خاص منظوره” استفاده می شود. RNS در پیاده سازی سریع مسائلی که شامل تصحیح و تشخیص خطا در سیستم های Fault-tolerant و سیستم‌های پردازش سیگنال هستند کاربرد دارد. کاربردهایی از قبیل تبدیل فوریه سریع، فیلتر دیجیتال و پردازش تصویر از اعمال ریاضی سریع RNS استفاده می کند. RNS راه خود را در کاربردهایی مثل تبدیلات تئوری اعداد و تبدیل فوریه گسسته پیدا کرده است. همچنین مستقل بودن رقم های باقیمانده باعث می شود که رخ دادن خطا در یک رقم به رقم های بعدی منتقل نشوند که این مسأله، باعث ایجاد یک معماری Fault-tolerant خواهد شد. [35],[20]

سیستم عددی RNS در رمزنگاری و به خصوص در روش RSA کاربرد زیادی دارد[35]. البته در RSA از ضرب پیمانه ای جهت عملیات توان رسانی استفاده می‌شود.

در این پروژه سعی می شود که چهار طرح از رویکردهای ضرب RNS را پیاده‌سازی و با هم مورد مقایسه قرار دهیم. این مقایسه براساس حجم و تاخیر طرح ها می‌باشد. در پیاده سازی سعی شده است که از پیشنهادات مقالات جهت عناصر بکار رفته استفاده شود (بخصوص در دو طرح اول) و در مواقعی که پیشنهاد خاصی انجام نشده (مثل طرح های سوم و چهارم) پیشنهاد مناسب از لحاظ خود من انجام شده است.

در ادامه ابتدا به اصول ضرب RNS و روشهای بکار رفته برای اینکار اشاره می‌کنیم. سپس هر یک از چهار طرح را به تفصیل مورد بررسی قرار می دهیم و در مورد هر طرح، الگوریتم و سخت افزار بیان خواهد شد و سپس تاخیر و مساحت آن را تعیین می کنیم. در نهایت جمع بندی و مقایسه چهار طرح را انجام می دهیم. در ضمایم نیز کدهای VHDL نوشته شده را خواهید یافت.

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

این روشها را می توان به دو دسته کلی تقسیم کرد. در دسته اول ابتدا عمل ضرب به صورت کامل انجام می شود و سپس کاهش به پیمانه روی نتیجه آخر اعمال می شود. این روشها را Reduction After Multiplication (RAM) می نامند. در دسته دوم عمل کاهش به پیمانه در هر مرحله ضرب و با هر حاصلضرب جزئی انجام می شود که به این روشها Reduction During Multiplication (RDM) می گویند[38]. از میان طرحهای مورد نظر ما دو طرح اول به دسته اول و دو طرح بعدی به دسته دوم تعلق دارند.

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

در روش RDM چون روش کاهش به پیمانه به دفعات تکرار می شود باید این عمل را سرعت بخشید. یکی از تکنیک های پر طرفدار برای اینکار که در طرحهای ما نیز به کار رفته روش مونتگمری [2] در کاهش پیمانه است.

پیمانه N را در نظر بگیرید. عدد R را که نسبت به N اول است و N<R را طوری انتخاب کنید که محاسبات به پیمانه R آسان باشد. را نیز طوری انتخاب کنیدکه باشد. حال برای محاسبه به شرطی که باشد:

function REDC(T):

if

بدین ترتیب با به کارگیری عدد کمکی R، عمل کاهش T به پیمانه N سریعتر انجام می شود.

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

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

مجموعه اول:

از تعداد خاصی از پیمانه ها مثل استفاده می کنند. در این مجموعه n می تواند مقادیر کوچک، متوسط و گاهی بزرگ داشته باشد. در پیاده سازی این طرح ها عمدتاً فقط از مدارات منطقی استفاده شده و از ROM استفاده نمی شود. در هر حال این طرحها به پیمانه های خاصی محدود هستند و به همین دلیل کاربردهای محدودی دارند[3]. به طور مثال می توان به طرحهای [13],[12],[11] مراجعه کرد.