March 20, 2007
بهاریه
می خواستم مطلبی در مورد عید نوروز بنویسم ولی این نوشته بهاریه را خواندم و منقلب شدم. دیگر دست و دلم به نوشتن نمی رود.
نوروزتان خجسته!
March 14, 2007
جایزه صدهزار دلاری برای تجزیه یک عدد
تجزیه اعداد بزرگ به عوامل اول یکی از مشکلترین مسائل ریاضی است که تا حالا راه حل تحلیلی برای آن پیدا نشده. به همین دلیل موفقترین الگوریتمهای رمزنگاری امروزه از روشهایی استفاده میکنند که به نوعی به دانستن عاملهای اول یک عدد بزرگ بعنوان کلید رمزگشایی احتیاج دارند. یکی از این الگوریتمها 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
March 10, 2007
Winning and Losing
Uncle Henry:
A man learns nothing from wining. The act of losing, however, can elicit great wisdom. Not least of which is how much more enjoyable it is to win. It is inevitable to lose now and again. The trick is not to make a habit of it.
[A Good year]
