شکار اعداد اول

سال پیش از این G. H. Hardy‌ نظریه اعداددان بزرگ در دفاعیه یک ریاضیدان نوشت: «ریاضیات واقعی ریاضیدانان واقعی، ریاضیات فرما، اویلر، گاوس و ریمان تقریبا به طور کامل بی‌فایده است. توجیه زندگی هیچ ریاضیدان حرفه‌ای اصیل بر مبنای سودمندی کارش ممکن نیست».
در این مقاله می‌خواهیم نشان دهیم که چطور ریاضیات واقعی و اصیل فرما و اویلر که روزگاری حتی در تصور یک ریاضیدان طراز اول بی‌فایده بودند، این روزها کفیل امنیت اطلاعات روی اینترنت شده‌اند.
در بخش اول بعضی خواص اعداد اول را که برای ادامه بحث لازم هستند بررسی می‌کنیم.
در بخش دوم مفهوم `رمزنگاری با کلید همگانی را که کاربردهای گسترده‌ای در تضمین امنیت اطلاعات و تایید هویت افراد و سازمان‌ها روی اینترنت دارد، شرح می‌دهیم.
در بخش سوم جزییات الگوریتم RSA که یکی از مشهورترین الگوریتم‌های رمزنگاری با کلید باز است را توصیف می‌کنیم و در آزمایشگاه رمزنگاری می‌توانید به صورت عملی با الگوریتم RSA کار کنید.
● شکار اعداد اول
یکی از اولین و در عین حال درخشانترین کارهای بشر در نظریه اعداد، اثبات اقلیدس از نامتناهی بودن اعداد اول در کتاب اصول است که امروزه می توان آن را در کتاب های درسی دبیرستانی خواند. نمونه ای عالی از زیبایی و سادگی ریاضیات. یونانی ها اعداد اول را می شناختند و از نقش آن ها به عنوان بلوک های سازنده دیگر اعداد آگاه بودند. بعد از این دستاوردهای بزرگ طبیعی ترین سوالی که به ذهن بشر رسید این بود که چه نظمی بر دنباله اعداد اول حاکم است، چگونه می توان اعداد اول را یافت و چطور می توان اعدادی را که اول نیستند به عوامل اول شان تجزیه کرد. شاید اولین پاسخ به این سوال غربال اراتستن بوده باشد. تا امروز تلاش های زیادی برای یافتن یک فرمول تولید کننده اعداد اول و یا الگویی برای ظهور اعداد اول در میان دیگر اعداد انجام شده است که هر چند کمک های زیادی به گسترش نظریه اعداد کرده اند اما ساختار پیچیده اعداد اول همچنان در مقابل این تلاش ها مقاومت می کند.
● جستجو برای الگوهایی از نظم در اعداد اول
یک نمونه ساده: ۳۱-۳۳۱-۳۳۳۱-۳۳۳۳۱-۳۳۳۳۳۱-۳۳۳۳۳۳۱-۳۳۳۳۳۳۳۱ همه اولند اما ۳۳۳۳۳۳۳۳۱ حاصلضرب دو عدد اول ۱۷ و ۱۹۶۰۷۸۴۳ است.
▪اعداد اول مرسن: اگر p اول باشد اعدادی به شکل ۲p-۱ را عدد مرسن میگوییم. اگر این اعداد اول باشند به آن ها عدد اول مرسن می گوییم. به ازای p برابر ۲ و ۳ و ۵ و ۷ عدد مرسن اول است اما اگر p را ۱۱ بگیریم مرکب است. تا امروز ۳۹ عدد اول مرسن شناخته شده اند که آخرینشان به ازای p=۱۳۴۶۶۹۱۷ به دست می‌آید و ۴۰۵۳۹۴۶ رقم دارد. یعنی بین همه اعداد اول کوچکتر از ۱۳۴۶۶۹۱۷ تنها ۳۹ تا عدد اول مرسن تولید می کنند.
▪ اعداد اول دوقلو: به اعداد اولی که پشت سر هم هستند اعداد اول دوقلو می گوییم مثلا ۳ و ۵ و یا ۱۱ و ۱۳. هیچ کس نمی داند که پراکندگی این اعداد در میان سایر اعداد چگونه است و آیا تعداشان متناهی است یا نه بزگترین جفت شناخته شده ۱-۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ و ۱+۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ هستند.
برای پیدا کردن اطلاعاتی راجع به جستجوی اعداد اول می توانید به سایت پروژه GIMPS سر بزنید.
در نظر گذشتگان آزمایش اول بودن یک عدد و یافتن عوامل اول آن یک سوال بودند. کافی بودن عدد مورد نظر را به ترتیب به همه اعداد کوچکتر از آن تقسیم کنیم. اگر به هیچ کدام بخشپذیر نبود اول است و اگر بخشپذیر بود به این ترتیب عوامل اول آن معلوم می شوند. کم کم این فرایند ساده تر شد، مثلا حالا می دانیم که تقسیم کردن به همه اعداد کوچکتر از جذر عدد مورد نظر کافیست ( چرا؟ )، همچنین در صورتیکه اعداد اول کوچکتر از عدد مورد نظر شناخته شده باشند، تقسیم کردن به این اعداد کافیست. این روش ها برای اعداد نسبتا کوچک کار می کنند اما وقتی با عددی مثلا ۱۰۰ رقمی طرف باشیم اوضاع فرق می کند. حتی با سریع ترین کامپیوترها هم تقسیم کردن یک عدد ۱۰۰ رقمی به همه اعداد کوچکتر از آن خیلی بیشتر از عمر عالم طول می کشد.
● یک محاسبه سرانگشتی
فرض کنید بخواهیم یک عدد ۱۰۰ رقمی را به همه اعداد کوچکتر از خودش تقسیم کنیم. برای این کار باید حدود ۱۰۹۹ تقسیم انجام دهیم اگر کامپیوتر ما بتواند در هر ثانیه ۱۰۰۰ میلیارد یعنی ۱۰۱۲ تقسیم انجام دهد برای انجام کل کار ۱۰۸۷ ثانیه وقت لازم است.
یک سال ۲۴×۳۶۰۰×۳۶۵=۳۱۵۳۶۰۰۰ ثانیه است یعنی حدود ۱۰۸ ثانیه و این یعنی کار ما ۱۰۷۹ سال طول خواهد کشید. عمر عالم دست بالا ۱۵ میلیارد سال تخمین زده می شود. حتی یک دهم یا یک صدم یا یک هزارم این محاسبه هم غیر قابل انجام است.
حوالی قرن هفدهم توجه ریاضیدانان به این نکته جلب شد که شاید راه های ساده تری برای آزمایش اول بودن یا نبودن یک عدد وجود داشته باشد چرا که روش تقسیم مقدار زیادی اطلاعات اضافی ( لیست عوامل اول، وقتی که جواب سوال منفی است ) تولید می کند که برای پاسخ گفتن به این سوال نیازی به آن ها نیست. فرما مدتی بعد نشان داد که این حدس صحیح بوده است. فرما (۱۶۰۱-۱۶۶۵) قضیه ای را ثابت کرد که تا امروز اساس همه روش های آزمایش اول بودن اعداد است و ما آن را با نام قضیه کوچک فرما می شناسیم.
▪ قضیه کوچک فرما: اگر p عددی اول و b عدد دلخواهی باشد که p و b نسبت به هم اول باشند، آن گاه باقیمانده تقسیم بر p و باقیمانده تقسیم b بر p همیشه برابرند.
بنابراین برای اینکه بدانیم عددی مثل a اول است یا نه کافیست عدد دلخواهی مثل b که نسبت به a اول باشد انتخاب کنیم و باقیمانده تقسیم بر a را بیابیم اگر این باقیمانده برابر b نباشد عدد ما اول نیست.
تنها مشکلی که وجود دارد این است که از آنجا که عکس قضیه فرما لزوما درست نیست - یعنی ممکن است بعضی از اعداد مرکب هم این خاصیت را داشته باشند - اگر باقیمانده b باشد نمی توان در مورد اول بودن یا نبودن a اظهارنظری کرد. این مشکل هم ۳۰۰ سال بعد در تابستان ۲۰۰۲ بوسیله سه ریاضیدان هندی به نام‌های Agrawal، Kayal و Saxena حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقم اظهارنظر کنیم.
▪ قضیه کوچک فرما: اگر p عددی اول و b عدد دلخواهی باشد که p و b نسبت به هم اول باشند، آن گاه باقیمانده تقسیم بر p و باقیمانده تقسیم b بر p همیشه برابرند.
بنابراین برای اینکه بدانیم عددی مثل a اول است یا نه کافیست عدد دلخواهی مثل b که نسبت به a اول باشد انتخاب کنیم و باقیمانده تقسیم بر a را بیابیم اگر این باقیمانده برابر b نباشد عدد ما اول نیست.
تنها مشکلی که وجود دارد این است که از آنجا که عکس قضیه فرما لزوما درست نیست - یعنی ممکن است بعضی از اعداد مرکب هم این خاصیت را داشته باشند - اگر باقیمانده b باشد نمی توان در مورد اول بودن یا نبودن a اظهارنظری کرد. این مشکل هم ۳۰۰ سال بعد در تابستان ۲۰۰۲ بوسیله سه ریاضیدان هندی به نام‌های Agrawal، Kayal و Saxena حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقم اظهارنظر کنیم.
بعد از ۲۰۰۰ سال مساله آزمایش اول بودن اعداد پاسخ خوبی پیدا کرد اما مساله دوقلو یعنی یافتن عوامل اول همچنان مقاومت می کند و کسی نمی داند آیا این مساله راه حل ساده تری دارد یا نه؟
وقتی تلاش برای ساده تر کردن راه حل این مساله به جایی نرسیده ریاضیدانان تصمیم گرفتند از پیچیدگی این مساله برای ساختن روش های رمز نگاری استفاده کنند. حالا، کمتر از ۳۰ سال از آغاز این تلاش، امنیت پیچیده ترین و امن ترین سیستم های رمزنگاری عالم وابسته به سختی تجزیه اعداد بزرگ است و امن تر کردن این روش ها بخش عمده ای از وقت نظریه اعداد دان های دنیا را پر می کند. جالب است بدانید بزرگ ترین استخدام کننده ریاضیدان ها در دنیا آژانس ملی امنیت ایالات متحده آمریکاست که بیشتر نظریه اعداددان‌ها را استخدام می کند. شاید دیگر کمتر نظریه اعداددانی مایل به حل کردن مساله تجزیه اعداد بزرگ باشد

منبع : سازمان آموزش و پرورش استان خراسان