سمینار

صفحه 1:
عنوان پروژه: طراحی و پیاده سازی یک ضرب کننده پیمانه ای کارا استادراهنما :سر کار خانم دکتر سالاری فرد دانشحو: نبره عباسی-۹۹46۳۱۵۵ تاریخ ارانه:۱۵۰۱/۰۳/۰۹ پروژه درس طراحی سیستم دانشگاه : شهید بهشتی 

صفحه 2:
an طراحی واحد های محاسبات میدلنی موثر در پردازنده و به خصوص واحد محاسباتی ضرب میدانی ۳۳3۸۸ ها به دلیل قابلیت استفاده مجدد دارای زمان پردازش سریعتری بوده وهمچنین مقدار نسبتا کوچکی از فضا را اشغال می کند. منحضی بیضوی در ریاضیات نوعى منحنى جبريست: منحنی های بیضوی به صورت خاص در نظریه اعداد مهم بوده و در تحقیقات جاری نقش بزرگی دارند: استفاده از منحنی های بیضوی در رمزنگاری به طور جداگانه توسط نیل کوبلیتز و ویکتور س- میلر در سال ۱۹۸۵ پيشنهاد شدباوجودی که مقایسه نرم افزار و سخت افزار مى تولند گمراه کننده باشد . ضرب یکی از عملیات اساسی مهم بای همه نم برنامه های کاربردی ارتباطات بی سیم ضروری است.ضرب به طور وسیعی در الکوریتم های تولید سیگنال دیجیتال به عنوان واحد های محاسباتی پایه در ریزپردازنده ها مورد توجه قرار گرفته اند. ضرب در بسیاری الگوریتم ها در زمینه های مختلف همانند پردازش تصویر, روشهای رم زگذاری در پردازنده ها مورد استفاده است. ضرب طراحی اصلی را برحسب سرعت. توان» مساحت و پیچیدگی نشان می دهد. در ! ‎epee Mos ey‏ ‎LIS‏ = پیاده سازی شله اسب 

صفحه 3:
فازاول مطالعاتی مروری بر مطالعات 4 درپژوهشی که توسط پاسکال ساسدریچ وهمکارانش در دانشگاه آلمان صورت گرفت نمونه بسیار کارآمد 120 نهاد داد که یک معماری گسترده با مرحله اینورتر اختصاصی بود که عملکرد بیش از ۳۲۰۰۰ ضرب نقطه در ثانيه در واحدزمان اين به وضوح بهتر از نتایج سرعت عمل می نمودودرواقع هدف طراحی سخت افزاری ارزان که برای آینده بسیار مناسب است. در سال ۲۰۱۸ کاراتسوباه الگوریتمی برای انجام عملیات ضرب از تجزیه استفاده می کنددر مراحل جزئی که به دلیل کوچکتر بودن مطلوب تر هستنداندازه های عملوند این روش اجازه می دهد تا برای کاهش اندازه واحد ضرب (از نظر مساحت اشغال شده) اما درهزینه تأخیر اضافی و سربار کنترل. با توجه به اولین ؛ مشترکک است ضرب را می توان با یک تر کیب کردمرحله کاهش سطح بر اساس این واقعیت است که این رو ؛ هر مرحله ضرب جزئی تولید شوند . کاهش می یابدجمع آوری شد» فیلیپ کوپرمن وهمکارانش درسال ۲۰۱۷ از ایتکه تحصولات يكك ضرب مدولار رابا استفاده از چند ضریب کوچک و موازی موجود در برشهای 125۳ از قبل ساخته شده ؛ كه می توانند در فررکانسهای ساعت بسیار بالا كار کنند » ایجاد نمودندو از منطق استاندارد برای ساختن درخت جمع کننده و مدارهای کاهشر استفاده نمودند. وبا وارد کردن ثبت مختلفی این امکان فراهم شد به طور مداوم عملوندهای ورودی را بدست آورده در حالی که ضرب های دیگر را پردازش نمودند که این ؛ یعنی منجر به افزايش کارایی گردید. 

صفحه 4:
Multiunit -) Pipelining Parallel Process -2 نوع اول 11111611111115 مى باشد . چون به سخت افزار وهزي ونوع دوم براساس 310611116 می باشد که یک واحد به چند تکه تقسیم می شود بطورکلی برای پیاده سازی پردازش موازی به سخت افزار بیشتری نیاز است که این نیازمندی در روش 101131111111111 مشهودتر است. مجتبی پيشه نیاسر وهمکاران تکنیک های کارآمدی را برای هر برنامه پیشنهادمی کنند که شامل موارد کاهش متقاطع ۰ ضرب متوالی؛ و معماری خط لوله. این معماری ها می توانند عملیات 21011 در ثانیه برای عملکرد بالا» زمان و منطقه به ترتیب و سبکک وزن تصدیق نردبان مونتگومری با استفاده از برنامه ریزی دقیق حساب اجرا می شودواحد این شامل ۸ جمع (يا تفريق) و ۰ ضرب (با مجذور) است. نمودار وابستگی داده ها را برای اجرای يكك مرحله مونتكومرى نشان داد معمارى آن كارآمد بوده با كارايى بالا. 

صفحه 5:
2 ۲0۱16 2:0 0 @ Group operation M@ Point addition and point Doubling N¢ P 9 ۶ ۵ for i from 0 to m do if dj = 1 then Q + point_add(Q, N) N © point_double(N) return Q 

صفحه 6:
WGroup operation ((Group 09,5 ‏هر گروه )شامل مجموعه ای از عناصر همراه با یک عمل دوتایی ۰ است‎ * ‏عمل دوتایی ۰-جمعء ضرب و یره‎ * ‏ویژکی ها‎ * ot * (Closure) برای هر 6 0,و 3 6 0 3 شرکت پذیری (6 ۸۵55061311۷ براى هر 3 © 9 ‎a0(b0c)=(a0b)0c‏ عنصر همانى يا خنثى ‎(Identity element)‏ فرض كنيد 3) مجموعهاى ناتهى و * یک عمل دوتایی تعریف در 3) باشد. در این صورت عضو © متعلق مجموعه 3) را عضء ختثی یا همانی 3) نسبت به عمل * می‌گویيم ه رگاه برای هر 0 متعلق به مجموعه 3) داشته باشیم: 3*60 < 6*۵ 

صفحه 7:
P+Q=Q+P * P+a=P* P+(Q+R)=(P+Q)+R 7 لما يمر ۳ a PES Re | EP || P+Q+R=0 P+Q+Q=0 P+Q+0=0 P+P+o=0 در این شکل به برخی از اشکال جمع روی منحنی بیضوی اشاره شده است. منظور از ۰ عضو خنثی يا همان بینهایت است 

صفحه 8:
مروری برمنحنی بیضوی منحنی بیضوی یک منحنی با معادله مشخصه +:+2-23 است به صورت زیر است: yp? = (x? +7)over(F,) y? mod p=(x'+7) mod p p = 2255. 232. 29- 28-27. 26- 24-1 به عبارت دیگر ضرب و جمع و.. در آن به پیملنه عدد اول ۳ انجام ميشود. در منحنی بیضوی میتوان بین نقاط منحنی عمل جمع تعریف کرد. 

صفحه 9:
اين جمع به این صورت است دو نقطه منحنی را با خطی به هم وصل میکنیم. إن خط مقط ‎LS eyo ORS yy‏ خواهد کرد. قرینه این نقطه نسبت به محور افقی حاصل جمع دو نقطه آغازین ‎«Sal‏ واضح است که این جمع خاصیت جابجایی دارد و نقطه خنثی ن در بی نهایت است. به همین دلیل میتوان آنرا یک گروه جبری تلقی کرد. +0 

صفحه 10:
Point addition and point Doubling اضافه نمودن نقطه : روشی است که از طریق اضافه نمودن دو نقطه 0۱,۳0۲ که درمنحنی بیضی صدق می کند ونقطه ی سوم 0۲را تولید می کند . Q=kP=P+P+P+.....+P (k times) Col ety LUN=P+)-t S46 4GF(p) در یک منحنی بیضوی تحت میدان متناهی برای هر عضو منحنی نظیر "آعدد مج عدد را مرتبه "در منحنی میگویيم. بزرگترین مرتبه ممکن در یک منحنی بیضوی را مرتبه منحنی میگوییم اثبات ۵ تعریف شده ذیل میدان متناهی (3۳)0)به صورت 9-0+۱-۲قابل نوشتن است که در آن |غ|< ‏ ۲3 که به قضیه هاسه موسوم است. به همین صورت میتوانیم بگوییم که مرتبه منحنی بیضوی عددی ۲۵۶ بیتی است و منحنی بیضوی آن تا 225 نقطه قایل استفاده دارد. 

صفحه 11:
مضاعف سازی نقطه : با فرض این که نقطه داده شده باشد. هدف ‎BL‏ ‏<نقطه لعمانند‌آلستسه طوری‌که ‎y‏ P+P=R جمع‌و مضاعخس ازع قطه روعمیدن‌هاعایل(6۲)۳ پارامتر 5 (شیب خط) ‎mod p‏ و رن شرع وه م له بر (وت مدع و ‎where ‎BL mod p + if P 4 Q (point addition) ‎3" mod p + if P= Q (point doubling) ‎ ‎of 

صفحه 12:
جهت ضرب اسکالر 11۱۴ <0) ۰ میتوان اسکالر را بر مبنای دو و به صورت مجموع توانهای دو نوشت. همچنین به صورت پیشینی ۴و 4۳و 8۳ و... را محاسبه کرد و ۲۳ را به صوردشهجوع چند 

صفحه 13:
مسئله به این شرح است که فرض کنید 0-1 که ‎OP‏ نقاطی روی نحنی بیضوی باشند. چگینه با دانستن آنهلبه ‏ برسیم؟ لین مسئله دشوار است و بهترین الگوریتم حل آن زمانی در مرتبه 7 ۷نیاز دارد كه 2 مرتبه 8 در منحنی است. ظرا طوری انتخاب میکنند که مرتبه آن با مرتبه منحنی یکی باشد و بشتری مره ممکن را داشته باشد. ر((نقطه مولد میناميم و به طور عمومی منتشر میکنیم. سپس 020.۳ را حساب میکنند و ۵ را به عنوان کلید عمومی منتشر میکنندو ۵۰را بعنوان کلید خصوصی در نزد خود نگه میدارند و کسی نمیتولند از 0به .0برسد. بخاطر اينکه افزايش دشواری با جذر « مرتبط است برای حصول ۱۲۸ بیت مطلبق با آن « , « بایستی کلید طولی به اندازه ۲۵۶ داشته باشد. 

صفحه 14:
ساختار پیشنهادی و محاسبات میدان گالوا ‎cee ee‏ و مجذور کردن در میدان گالوا انجام هزین محاسبهةٌ عملیات مجذور (۴)20 در ميدان كردن در مقايسه با هزينة محاسبة عملیات ضرب کردن قابل صرفنظر ميباشد[ 17 ]. لذا نحوة بيادهسازى عمليات ضرب در دارد. يكك روش )2)0] ميدان كالوا تاثير زيادى روى بازده اف بازده عمليات ضرب در ميدان كالوا استفاده ازساختارهاى موازى ميباشد. يكى از ساختارهای موازی برای انجام عمليات ضرب استفاده از ساختار كاراتسوبا- افمن ميباشد. با فرض اينكه عناصر ( 8)7(,8)0<(©)031:0)210 جند جملهاى ساده نشدنى باشد» آنگاه در ساختار (6)"پیشنهادی عملیات ضرب در ميدان كالوا در دو مرحله انجام ميشود: يعنى: ()8 و ‎te Gs aby A(X)‏ جمله ایهای< 0700 («)8()للمرحله كاهش با استفاده از جند جملهاى ساده يعنى: ()2 نشدنى (8)© ‎C(x) mod P(x)‏ = 52 ساختار بيشتهادى در مرحله ضرب جند جملهايها از ضرب كننده بايئرى كاراتسويا استفاده شده است. 

صفحه 15:
pur: ‏اام ۱ ۲ الست عق‎ ey. ‏این الگوریتم مطابق رابطه عمل می کند و پس از و‎ 0 ‏محاسية‎ 11 10 ‏مط‎ aoe Ma= A+ Aut, Parallel begin Ms= B+ B Mae بصورت همزمان هر سه عملیات ضرب را بصورت ‎ae‏ ‏همزمان انجام و :۸.8 :۸۵.8 -.0مى دهد تا + ‎Parallel ond‏ End for ‏حاصل‎ ‎Parallel Begin Malle ABB, 1۷-۷۷ ‏بدست آید. سپس حاصل‎ Mull MAME) 9 2 ‏ون‎ M =M — Cu ale yo ‏را محاسبه نموده و در آخرین‎ MieMi Cc cH Gs 1 End for را محاسبه ميکند. بعد از 6 +216 +,2.0 6 ‎sil‏ اي ‎End for‏ توسط الگوریتم شکل ۵ برای ۸00۳800 - 000 ;¢ ‎Return‏ ‏محاسبة جل وگیری از افزايش طول حاصلء عمل کاهش 

صفحه 16:
در زیر یک برنامه حاصلضرب 3010111012 201218 و با استفاده از 156 سنتز و شبيه سازى شده است : سنتؤا سر Ee) ‏لا‎ Santez2.txt Santez!.txt 

صفحه 17:
کارآیی و مقیسه ی نیازهای پیاده سازی این تحلیل کارآیی در کاربردهای واقعی در آن ها از اهمیت بالایی برخوردار است.با توجه به اينکه در مقایسه ی ما روش نقطه ای در نظر گرفته شده بنابراین مقایسه را با توجه به الگوی منحنی بیضوی بیتی با میدان معین بطوری که حاصل ضرب اسکالر. دستیابی به این عملیات از الگوریتم مونت گومری استفاده نموده ايم كه جل وكيرى از افزايش طول حاصل منجربه کاهش مساحت درواحد زمان گردیده است. 

صفحه 18:
References » K. Demir, H. Ismail, T. Gurova, N. Suri, “Securing the cloud- assisted smart grid”, International Journal ofCritical Infrastructure Protection, pp. 100-111, Dec. 2018 (doi:10.1016(.ijcip.2018.08.004). >A. O. Otuoze, M. W. Mustafa, R. M. Larik, “Smart grid security challenges: Classification by sources ofthreat”, Journal of Electrical Systems and Information Technology, Vol. 5, No. 3, pp. 468-483, Dec. 2018. » Salarifard, Raziyeh, and SiavashBayat-Sarmadi. "An efficient low-latency point-multiplication over curve25519." IEEE Transactions on Circuits and Systems I: Regular Papers66.10 (2019): 3854-3862.