برنامه‌نویس بلژیکی موفق به حل پازل فراموش‌شده‌ MIT شد

حل پازل MIT که حتی مدیران آزمایشگاه CSAIL هم آن را فراموش کرده بودند، قرار بود ۳۵ سال طول بکشد. ولی در کمال شگفتی، برنامه‌نویسی جوان و بدون تحصیلات آکادمیک، تنها در عرض ۳.۵ سال پازل را حل کرد.

در ابتدای آوریل ۱۹۹۹، یک کپسول زمان برای معمار سرشناس آن زمان، فرانک جیری (Frank Gehry) به همراه دستورالعملی فرستاده شد که نحوه‌ی استفاده از آن در طراحی ساختمانی که درنهایت تبدیل به آزمایشگاه هوش مصنوعی و علوم کامپیوتر MIT موسوم به CSAIL شد، را توضیح داده بود. این کپسول زمان در اصل موزه‌ی تاریخ کامپیوتر محسوب می‌شد که شامل ۵۰ مورد از اقلامی بود که توسط افرادی مانند بیل گیتس و تیم برنرز-لی (Tim Berners-Lee)، خالق دنیای وب، استفاده شده است.

در پازل ریوست، پس از ۸۰ تریلیون بار محاسبه‌ی مجذور اعداد و چند عملیات کوچک دیگر، عبارتی تبریک‌آمیز تولید خواهد شد

قرار نبود که این کپسول زمان را زودتر از ۳۵ سال باز کنند، مگر اینکه کسی بتواند پازل رمزنگاری‌شده‌ای (cryptographic) که در طراحی آن تعبیه شده بود را حل کند. پازل مذکور را ران ریوست (Ron Rivest) طراحی کرده بود که حرف آر (R) ابتدایی در کلمه‌ی اختصاری RSA اشاره به او دارد. RSA، بدون شک، یکی از مهم‌ترین پروتکل‌های رمزنگاری تاریخ است که تاکنون ساخته شده است. او می‌گوید قرار نبود این پازل خیلی پیچیده باشد؛ بلکه فقط هدفش این بود طوری طراحی شود که حل آن توسط کامپیوتر دقیقا ۳۵ سال طول بکشد؛ نه کمتر و نه بیشتر.

۱۵ آوریل ۲۰ سال پس از روزی که ریوست این پازل را معرفی کرد، برنارد فابروت (Bernard Fabrot)، یک برنامه‌نویس بلژیکی بدون تحصیلات آکادمیک، موفق به حل آن شد. دستورالعمل اصلی پازل می‌گوید که راه‌حل آن را باید به مدیر آزمایشگاه علوم کامپیوتر ارسال کرد، ولی فابروت از اینکه می‌دید این آزمایشگاه دیگر وجود ندارد، بسیار شگفت‌زده بود. در حقیقت، آزمایشگاه نامبرده در سال ۲۰۰۳ با آزمایشگاه هوش مصنوعی دانشگاه MIT ادغام شد تا CSAIL شکل بگیرد. او می‌گوید که دانیلا راس (Daniela Rus)، مدیر فعلی آزمایشگاه CSAIL، روحش هم از وجود چنین معمایی خبر نداشت.

معمای کریپتوی فراموش شده

در پازل ریوست، باید نتیجه‌ی ۸۰ تریلیون بار محاسبه‌ی مجذور یک عدد را محاسبه کرد. به‌عنوان مثال، مجذور عدد دو برابر است با چهار؛ مجذور چهار برابر است با ۱۶ و به همین منوال این عملیات را باید ۸۰ تریلیون بار تکرار کرد. در پایان، عدد حاصل و عددی که در دستورالعمل به آن اشاره شده است را باید در عملیات دیگری به کار برد تا به عدد جدیدی دست یافت که بتوان آن را به شکل یک عبارت کوتاه تبریک‌آمیز ترجمه کرد. ریوست و فابروت این عبارت را فاش نکرده‌اند؛ عبارت صحیح در زمان بازگشایی کپسول زمان در روز ۱۵ می اعلام خواهد شد.

نکته‌ی مهم در این معما، لزوم اجرای عملیات‌های ترتیبی است؛ یعنی، نباید انتظار داشت که با انجام محاسبات به‌صورت موازی، سریع‌تر به پاسخ صحیح دست یافت. برای رسیدن به پاسخ، در هر لحظه فقط می‌توان یکی از مراحل فرایند مجذورسازی را تنها با استفاده از پاسخی که از مرحله‌ی پیش به دست آمده است، انجام داد؛ بنابراین، استفاده از کامپیوترهای بیشتر یا حتی یک ابرکامپیوتر هیچ کمکی به حل مسئله نخواهد کرد. براساس قانون مور و باتوجه‌به مدت زمان موردنیاز برای اجرای عملیات مجذورکردن اعداد در سال ۱۹۹۹، ریوست اینچنین برآورد کرده بود که محاسبه‌ی پاسخ این پازل تقریبا باید ۳۵ سال طول بکشد.

فابروت که به‌عنوان یک برنامه‌نویس و توسعه‌دهنده‌ی مستقل کار می‌کند، می‌گوید سال ۲۰۱۵ به‌طور تصادفی با این پازل برخورد کرد. اگرچه ریوست کد پازل را در ابتدا به‌صورت جاوا منتشر کرده بود، ولی فابروت به این نتیجه رسید که اگر از کتابخانه گنو (GNU Multiple Precision Arithmetic Library) استفاده کند بهتر می‌تواند آن را حل کند. این ابزار، نرم‌افزاری رایگان و غنی از توابع مختلف است که با استفاده از زبان برنامه‌نویسی C و برای انجام دقیق محاسبات ریاضی طراحی شده است. بنابراین او یکی از هسته‌های پردازنده‌ی مرکزی کامپیوتر شخصی خود را به انجام عملیات مجذورسازی اعداد اختصاص داد تا بتواند این پازل را حل کند. او می‌گوید کامپیوتر او به‌صورت ۲۴ ساعته در تمام طول هفته مشغول اجرای این عملیات بود و تنها وقفه‌هایی که در روند کار اتفاق می‌افتد، زمانی بود که او به مسافرت می‌رفت یا جریان برق قطع می‌شد.

وی می‌گوید:

به هیچکس جز دوستان نزدیکم نگفته بودم که دارم این پازل را حل می‌کنم. می‌دانستم که یک شانس بیشتر ندارم، اما اگر این حرف را به دیگران می‌گفتم آن‌ها می‌توانستند یک پردازنده‌ی قوی‌تر استفاده کنند و من را شکست بدهند.

سه و نیم سال بعد، فابروت درنهایت توانست ۸۰ تریلیون عملیات مجذورسازی را به اتمام برساند و راه‌حلی برای پازل پیدا کند. او، در بهترین زمان ممکن توانسته بود به این مرحله برسد. خودش از این موضوع خبر نداشت، ولی گروهی از دانشمندان علوم کامپیوتر و کارشناسان کریپتوگرافی در حال کار روی پروژه‌ای به نام کریپتوفاژ (Cryptophage) بودن که از سخت‌افزارهای ویژه‌ای بهره می‌بردند که به‌طور خاص برای حل پازل MIT طراحی شده بودند.

معمای کریپتوی فراموش شده

گروه کریپتوفاژ به رهبری سایمون پیفرز (Simon Peffers)، مهندس سابق اینتل، مشغول جست‌وجو برای یافتن توابع تأخیر معتبری بودند که بتوانند از آن‌ها به‌عنوان یک مکانیسم امنیتی برای بلاک‌چین‌هایی مانند اتریوم استفاده کنند. توابع تأخیر قابل تأیید، تحلیل مدرنی از کار اولیه‌ی ریوست درباره‌ی کریپتوگرافی دارای تأخیر زمانی است و راه‌حل آن‌ها تنها با استفاده از اجرای عملیات‌های ترتیبی به دست می‌آید. پیفرز می‌گوید گروه کریپتوفاژ در جریان پژوهش‌های خود به پازل ریوست برخورد کرد و فکر کردند که این معما، بستر خوبی برای آزمایش یافته‌های حاصل از پژوهش‌های آن‌ها است.

آن‌ها از ابتدای ماه مارس شروع به اجرای الگوریتمی کردند که اردینک ازتورک (Erdinc Ozturk)، پژوهشگری از دانشگاه Sabanci، آن را طراحی کرده بود و طوری بهینه‌سازی شده بود تا میزان وقفه‌های بین عملیات‌های مجذورسازی را کاهش بدهد. این الگوریتم با استفاده از یک آرایه‌ی دروازه‌ی برنامه‌پذیر در محل (FPGA) اجرا شد که تراشه‌ای چندمنظوره است که با هدف اجرای تنها یک الگوریتم خاص برنامه‌ریزی و طراحی شده است و همین عامل باعث می‌شود که نسبت به پردازنده‌های عمومی، از کارایی بیشتری برخوردار باشد. این مدار FPGA در زمان استفاده از الگوریتم ازتورک، عملکردی ۱۰ برابر سریع‌تر از پردازنده‌های گران‌قیمت تجاری دارند که نرم‌افزارهای غیربهینه‌سازی‌شده را اجرا می‌کنند.

فابروت زمانی به پاسخ رسید که کریپتوفاژها با استفاده از ابزارهایی که به این منظور طراحی شده‌‌اند، تازه درصدد یافتن پاسخ برآمده بودند

گروه کریپتوفاژ باتوجه‌به کارایی محاسبات این تراشه برآورد کرده بودند که عصر روز دهم مه به پاسخ صحیح پازل MIT دست خواهند یافت؛ یعنی، دقیقا دو ماه بعد از آنکه محاسبات را شروع کردند؛ ولی، زمانی‌که به MIT رفتند تا آن‌ها را از این موضوع آگاه کنند، ریوست به آن‌ها گفت که از فابروت شکست سختی خورده‌اند.

ریوست می‌گوید:

پیش از اینکه این دو نفر دقیقا در یک روز بیایند و بگویند سؤال شما را حل کردیم، هیچ کس پیش ما نیامده بود. تصادف شگفت‌انگیزی است.

ریوست به این نکته اعتراف می‌کند که میزان سختی پازل خود را اشتباه برآورده کرده است. پیش‌بینی پیشرفت‌های فناوری برای آینده‌های نسبتا دور کار مشکلی است و ریوست می‌گوید او به احتمال وقوع پیشرفت‌های غیرمنتظره‌ای مانند ابداع تراشه‌های EPGA توجه نکرده بود. این تراشه‌ها در گذشته به اندازه‌ی زمان حال پیچیده و در دسترس نبودند.

اگرچه کریپتوفاژها نتوانستند اولین کسانی باشند که این پازل را حل می‌کنند،‌ ولی پیفرز می‌گوید آن‌ها هم در مراسم بازگشایی کپسول زمان که ۱۵ مه برگزار می‌شود، شرکت خواهند کرد. تنها طراحان کپسول هستند که از همه‌ی محتوای آن آگاه هستند و دیگران تنها می‌دانند که آن کپسول با مشارکت و همیاری افرادی مانند تیم برنرز-لی (مخترع شبکه‌ی جهانی وب)، باب متکالفی (مخترع اترنت)، بیل گیتس (یکی از سازندگان نسخه‌ی اصلی Altair BASIC، اولین محصول مایکروسافت) ساخته شده است. فابروت می‌گوید به‌شدت مشتاق است که نسخه‌ی اصلی Zork که یکی از اولین بازی‌های کامپیوترهای خانگی است و در این کپسول قرار دارد، را ببیند.

منبع wired

از سراسر وب

  دیدگاه
کاراکتر باقی مانده

بیشتر بخوانید