Only Math
22nd December 2010, 11:39 AM
شکار اعداد اول
سال پیش از این 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 حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقماظهارنظر کنیم
سال پیش از این 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 حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقماظهارنظر کنیم