غربال توزیع شده اعداد اول

اعداد اول را سازنده های سایر اعداد می گویند، به این معنا که با استفاده از این اعداد می توان سایر اعداد دیگر را تولید کرد، به همین دلیل در علوم ریاضیات اهمیت فراوانی دارند. از این اعداد جهت تامین امنیت محتوای الکترونیکی نیز استفاده می شود لذا در علوم کامپیوتر نیز دارای اهمیت فراوانی می باشد. برای تامین امنیت الکترونیک به اعداد اول بسیار بزرگ نیاز بیشتری وجود دارد، هر اندازه عدد اول مورد استفاده بزرگتر باشد امنیت بیشتری را برای محتوای الکترونیک ایجاد خواهد کرد.اعداد اول امروزی دارای هزاران رقم می باشند مثلا 257,885,161-1 یک عدد اول می باشد این عدد دارای17,425,170 رقم می باشد به همین دلیل امروزه تولید و محاسبه اعداد اول با استفاده از ابزار قدیمی و بدون کمک گرفتن از رایانه ها مقدور نیست. حتی رایانه های معمولی برای محاسبه این اعداد دچار مشکل خواهند شد. از جملات مشکلات مطرح برای اعداد اول کمبود حافظه و همچنین سرعت پردازشی رایانه های مورد استفاده می باشد. لذا باید الگوریتم های مناسبی برای تولید اعداد اول ارائه داده شود.در این پژوهش برای تولید اعداد اول از سیستم های پردازش موازی توزیع شده استفاده شده است. در این سیستم ها چندین پردازنده با استفاده از شبکه های با پهنای باند بالا به یکدیگر متصل شده اند. این سیستم ها قادرند به صورت همزمان از همه توان پردازشی برای مدیریت و پاسخ دادن به یک مسئله با یکدیگر همکاری کنند.یکی از قدیمی ترین و کارآمدترین الگوریتم های موجود برای تولید اعداد اول الگوریتم غربالگر اراتستن است. در این پژوهش یک نسخه موازی شده از این الگوریتم را با استفاده از چهارچوب MPI ارائه داده ایم الگوریتم ارائه شده قادر است در بازه زمانی کمتری نسبت به سایر الگوریتم های مشابه و همچنین با استفاده از حافظه کمتر اعداد اول را تولید نماید.

کلیدواژه ها:

عدد اول ، اعداد مرکب ، اعداد زوج ، برنامه نویسی موازی ، واسط انتقال پیام(MPI) ، مدیریت حافظه