تجزیه اعداد بزرگ به عوامل اول یکی از مشکلترین مسائل ریاضی است که تا حالا راه حل تحلیلی برای آن پیدا نشده. به همین دلیل موفقترین الگوریتمهای رمزنگاری امروزه از روشهایی استفاده میکنند که به نوعی به دانستن عاملهای اول یک عدد بزرگ بعنوان کلید رمزگشایی احتیاج دارند. یکی از این الگوریتمها RSA است که اسمش مخفف اولین حرف اسامی مخترعین آن است.
آزمایشگاه RSA که برروی روشهای رمزنگاری و امنیت اطلاعات کار میکند برای آنکه نشان دهد استفاده از این سیستم رمزنگاری به اندازه کافی کارآمد است، مسابقههایی را ترتیب داده و به افرادی که بتوانند اعداد بزرگ را به عوامل اولشان تجزیه کنند جایزههای نقدی میدهد. این اعداد توسط الگوریتمهای RSA ایجاد شده اند و دو عامل اول بزرگ دارند. طول این اعداد در سیستم باینری از ۵۷۶ تا ۲۰۴۸ بیت متغیر است. عدد ۱۰۲۴ بیتی (۳۰۹ رقم در سیستم اعشاری) با جایزه یکصدهزار که برای تجزیه به مسابقه گذاشته شده این است:
13506641086599522334960321627880596993888147560566
70275244851438515265106048595338339402871505719094
41798207282164471551373680419703964191743046496589
27425623934102086438320211037295872576235850964311
05640735015081875106765946292055636855294752135008
52879416377328533906109750544334999811150056977236
890927563
در حال حاضر آخرین عددی که تجزیه شده ۶۴۰ بیتی بوده که معادل ۳۰ سال برروی یک پروسسور AMD Opteron 2.2GHz زمان برده. البته تجزیه این عدد به دلیل استفاده از چندین پروسسور بطور موازی در عمل پنج ماه زمان برده. تیم برنده در واقع نشان دادند:
31074182404900437213507500358885679300373460228427
27545720161948823206440518081504556346829671723286
78243791627283803341547107310850191954852900733772
=4822783525742386454014691736602477652346609
16347336458092538484431338838650908598417836700330
92312181110852389333100104508151212118167511579
X
1900871281664822113126851573935413975471896789968
515493666638539088027103802104498957191261465571
و ۲۰ هزار دلار بردند! ظاهراً ساده به نظر میرسه ولی در عمل خیلی مشکل است. برای امتحان این عدد را به نرمافزار Mathematica دادم تا تجزیه کند ولی نتیجهای حاصل نشد!
اگر کسی بتواند برنامهای بنویسد که از قابلیت پردازش موازی برروی کامپیوترهای مختلف متصل به اینترنت استفاده کند (در زمان بیکاری پروسسور، چیزی شبیه برنامه SETI at Home یا برنامههای مشابه)، میشود این مسئله را حل کرد. کسانی که در این کار مشارکت کردهاند هم بعداً به نسبت زمانی که در اختیار این برنامه گذاشتهاند از جایزه سهم خواهند برد.
یکی از کاندیداهای قوی برای حل این قبیل مسائل کامپیوترهای کوانتمی هستند که بطور بنیادی قابلیت انجام محاسبات موازی را دارند. در ضمن چند هفته قبل شرکتی با اسم D-Wave اولین کامپیوتر کوانتمی با ۱۶ Qbit را آزمایش کرد.
لینکها:
اعداد اول مسابقه RSA
اطلاعات بیشتری درباره الگوریتم RSA
چه جالب! ایدهی برنامهی توزیعشده هم خیلی خوب بود.
سلام و خسته نباشيد .
من وهاب نوتاش هستم
آيا تمامي اعداد را مي توان به عوامل اول تجزيه كرد
ثانيا آيا منظور از تجزيه كردن يافتن بزرگترين عدد اول ممكن و يك عدد ديگر كه ضربشان عدد مذكور شود
_
