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

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

۱- مقدمه

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

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

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

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

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

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

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

۳- طرح اول

    3-1 مقدمه

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

    3-3 الگوریتم

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

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

۴- طرح دوم

    4-1 مقدمه

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

    4-3 الگوریتم

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

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

۵- طرح سوم

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

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

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

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

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

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

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

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

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

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

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

۶- طرح چهارم

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

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

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

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

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

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

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

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

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

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

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

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

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

    7-2- جمع بندی

۸- مراجع

۹- ضمائم

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

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

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

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

    هـ – MOMA

مقدمه

همانطور که می دانیم ضرب پیمانه ای در علم رمزنگاری نقش مهمی ایفا می کند. از جمله روشهای رمزنگاری که به ضرب کننده پیمانه ای سریع نیاز دارد، روش رمزنگاری RSA می باشد که در آن نیاز به توان رساندن اعداد بزرگ در پیمانه های بزرگ می باشد. معمولاً برای نمایش اعداد در این حالات از سیستم باقی مانده (RNS) استفاده می شود و ضرب (به عنوان هسته توان رسانی) در این سیستم به کار می رود.
در اینجا برای آشنایی بیشتر به توضیح سیستم عددی باقی مانده می پردازیم و به کاربردها و فواید آن اشاراتی خواهیم داشت.
۱-۱ سیستم عددی باقیمانده (Residue Number System (RNS))
در حدود ۱۵۰۰ سال پیش معمایی به صورت شعر توسط یک شاعر چینی به صورت زیر بیان شد. «آن چه عددی است که وقتی بر اعداد ۳،۵و۷ تقسیم می شود باقیمانده های ۲،۳و۲ بدست می آید؟» این معما یکی از قدیمی ترین نمونه های سیستم عددی باقی مانده است.