امروز : ﺳﻪشنبه, 30 آبان 1396
الگوریتم یونان باستان اعداد اول را شناسایی می کند
3/50 امتیاز از 12 رای
 تکنولوژی  |     |   182

ریاضی دان های زیادی با موضوع اعداد اول دچار مشکل شده اند! همان اعدادی که "اتم"های دنیای ریاضی به شمار می آیند و جز بر خودشان و عدد یک بر هیچ رقم دیگری بخش پذیر نیستند.

افراد زیادی برای پیدا کردن اعداد اول دست به کار شدند و با پشتکار (و حتی انگیزه های مالی) به دنبال محاسبه ی اعداد اول بزرگ تر پرداختند. با این حال یکی از ریاضی دان های مطرح دنیا، کلید حل معما را در یکی از الگوریتم های یونان باستان به نام "غربال اراتوستن" کشف کرده است.

غربال اراتوستن، همان طور که از نامش پیدا است، یک غربال ریاضی است که کمک می کند تا اعداد اول از بین دیگر اعداد فیلتر شوند.

حدود ۲۴۰ سال قبل از میلاد مسیح، ستاره شناس و ریاضی دان یونانی به نام "سایرن" (Cyrene) این الگوریتم را بسط داد تا افراد بتوانند اعداد اول واقع در یک محدوده ی عددی مشخص را پیدا کنند.

غربال اراتوستن

روند کار به این شکل است که ترتیبی از اعداد (برای مثال ۱ تا ۱۰۰) را روی یک تکه کاغذ می نویسید. ابتدا اعداد مضرب ۲ را (به غیر از ۲) حذف می کنید. سپس به حذف اعداد مضرب ۳ (به غیر از ۳) می پردازید و این روند را برای اعداد بعد هم تکرار می کنید. هر عددی که در برگه ی چرک نویس شما جان سالم به در برد، در دسته ی اعداد اول قرار می گیرد.

البته این روش در مورد محدوده های وسیع اعداد کارآیی چندانی ندارد. (آخرین عدد اول کشف شده دارای ۲۲ میلیون رقم است). با این حال غربال اراتوستن می تواند به یک الگوریتم قابل اجرا در کامپیوتر تبدیل شود. مشکل بزرگی که در ارتباط با این الگوریتم وجود دارد این است که حجم زیادی از حافظه ی سیستم را درگیر می کند و همین امر استفاده از این روش را برای ریاضی دان های امروزی ناکارآمد جلوه می دهد.

هارالد هلفگات

در حال حاضر، یک ریاضی دان رده بالا به نام "هارالد هلفگات" (Harald Helfgott) یک راهکار ساده برای به کارگیری الگورتیم اراتوستن پیدا کرده است و احتمال می دهد که این روش بتواند در آینده کلید کشف اعداد اول باشد.

هلفگات یک ریاضی دان پرویی فعال در مرکز ملی تحقیقات علمی فرانسه ودانشگاه "گوتینگن" (Göttingen) آلمان است. وی شهرت خود را در سال ۲۰۱۳ پس از حل مسئله ای به دست آورد که ۲۷۱ سال بی پاسخ مانده بود. اکنون، هلفگات موفق شده است تا با تکنیکی به نام "روش دایره" (circle method) نسخه ای بهبود یافته از غربال اراتوستن ارایه دهد تا حجم کم تری از حافظه ی کامپیوتر را درگیر کند.

چند تن از ریاضی دان ها در خصوص این بهینه سازی می گویند:

فرض کنید که یک کامپیوتر هستید که حافظه ی شما، این اطلاعات را به صورت داده های ثبت شده در کاغذ ذخیره می کند. چنانچه بخواهید اعداد اول بین ۱ تا ۱۰۰۰/۰۰۰ را با استفاده از شکل اصلی الگوریتم به دست آورید نیاز به ۱۰/۰۰۰ ورق کاغذ خواهید داشت. حال آن که الگوریتم پیشنهادی هلفگات این رقم را به ۱۰۰ عدد می رساند.

البته این فشرده سازی تا حدی سرعت پردازش را کاهش می دهد اما هلفگات عقیده دارد که کامپیوترها با استفاده از حافظه ی کش توانستند این مورد را جبران کنند.

به غیر از روش هلفگات، تکنیک ها و الگوریتم های دیگری وجود دارند که بتوانند اعداد اول را شناسایی کنند، اما آنچه این روش را متمایز می کند، امکان اجرای عملیاتی چون تجزیه و اتحاد است که اساس "رمزگذاری مدرن" به حساب می آید.

این احتمال وجود دارد که این روش بتواند تبدیل به ابزاری برای شناسایی یک عدد اول جدید شود. به هر حال، جایزه ی ۱۵۰/۰۰۰ دلاری برای کسی که بتواند اولین عدد اول ۱۰۰ میلیون رقمی را پیدا کند، انگیزه ای قوی به شمار می آید!


برچسب ها :  

نظر خود را به اشتراک بگذارید