شماره دانشجویی : 91133017
نام و نام خانوادگی : مریم مؤیدی
عنوان پایان نامه : بهبود عملکرد عملیات ضرب همنهشتی مونتگمری
رشته تحصیلی : مهندسی برق – الکترونیک
مقطع تحصیلی : کارشناسی ارشد ناپیوسته
استاد راهنما :
چکیده : الگوریتم ضرب مونتگمری یکی از روشهای انجام ضرب هم نهشتی است. این الگوریتم ضرب عمل تقسیم که عمل سختی است را با عمل شیفت انجام میدهد.کاربرد ضرب مونتگمری بیشتر وقتی برای ضرب هم نهشتی با تکرار زیاد است؛ دلیل این امر نیاز به پیش محاسبه و پس محاسبه برای استفاده از ضرب مونتگمری است. یکی از جاهایی که در آن ضرب هم نهشتی مکررا انجام میشود عملیات رمزنگاری کلید عمومی است. برخی از روشهای رمزنگاری کلید عمومی مثل RSA به طور گسترده از ضرب مونتگمری استفاده میکنند. از دهه های قبل تا به امروز تلاشهای فراوانی در جهت بهبود عملکرد ضرب مونتگمری شده و الگوریتمها و روشهای مختلفی برای پیاده‌سازی آن ارائه شده است. در همین راستا در این پایان نامه هم سعی شد تا پس از بررسی روشهای مختلف، روش جدیدی برای پیاده‌سازی آن ارائه شود که مزایایی را در برداشته باشد. در این پایان نامه چند الگوریتم جدید برای بهبود عملکرد ضرب مونتگمری ارائه شده است که به آنها اشاره ای میشود. در ابتدا روش شمارش صفر و پارتیشن بندی برای عملوند مضروب با تعداد بیت کمتر از تعداد بیت عدد همنهشتی تعمیم یافته، سپس دو روش جدید برای شمارش صفر و بخش بندی برای عملوند مضروب و بر اساس آنها الگوریتم هایی برای عملیات ضرب هم نهشتی ارائه شده است. در یکی از این روشها شمارش و پارتیشن بندی (تبدیل چند بیت به یک رقم) از کم‌ارزش ترین بیت و در دیگری از بیت پر‌ارزش شروع میشود. نتایج شبیه سازی این دو الگوریتم نسبت به الگوریتم مربوط به روش تعمیم یافته در محیط ISE نشان میدهد که بدون تغییر در حداکثر فرکانس مدار، حافظه مورد استفاده کاهش می یابد. در ادامه و به طور مجزا از روش اول ارائه شده، سعی شد مبتنی بر کارهای قبلی روشی برای بالا بردن سرعت پیدا شود که در عین حال مجبور به استفاده از ضرب مبنای بالا با پیچیدگی های نباشد. در این راستا عملوند مضروبِ بازکدگذاری شده با تقسیم کلمات آن بطور یک در میان به چند عملوند و جایگزینی کلمه صفر بجای کلمات جاافتاده به چند عملوند تقسیم شد که امکان پردازش موازی آنها باعث افزایش سرعت میشود؛ از طرف دیگر بازکدگذاری و کلمات صفر تعداد متوسط بیتهای غیر صفر هر عملوند را کاهش میدهد. برای پیاده‌سازی سخت افزاری این الگوریتم سه روش مختلف پیشنهاد میشود. آنالیز پیچیدگی آنها نشان میدهد که در دو مورد تعداد پالس ساعت مورد نیاز کاملا وابسته به طول کلمات عملوندهای جدید(در یکی نزدیک به n/(k.w) و در دومی اگر طول کلمات به قدر کافی بزرگ باشد به طور تقریبی حدود n/kw w/3) است، ولی استفاده از روش های جایگزینِ ضرب مبنای بالا باعث میشود تا افزایش طول کلمات منجر به پیچیدگیهای مفرط در طراحی سخت افزاری نشود؛ در سومی صرفنظر از طول کلمات تعداد پالس مورد نیاز با دقت بیشتری در حدود (n )/3k است. تفاوت دیگر این سه روش در پیچیدگی مرحله طراحی مدار و نیز مساحت مورد نیاز است.
کلمات کلیدی : ضرب مونتگمری- بازکدگذاری متعارف- رمزنگاری کلید عمومی- سخت افزار
تاریخ دفاع : 1395