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

یکی از درخشان ترین کارهای بشر در نظریه ی اعداد، اثبات نامتناهی بودن اعداد اول بود که توسط اقلیدس صورت گرفت. امروزه می‌توان این اثبات را در کتاب های درسی دبیرستان دید که نمونه ای عالی از زیبایی و سادگی ریاضیات است.

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

جستجو برای الگوهایی از نظم در اعداد اول

یک نمونه ساده: 31-331-3331-33331-333331-3333331-33333331 همه اول هستند. اما 333333331 حاصل ضرب دو عدد اول 17 و 19607843 است.

اعداد اول مرسن: اگرp اول باشد، اعدادی به شکل 2^p-1 را عدد مرسن می گوییم. اگر این اعداد اول باشند، آن ها را عدد اول مرسن می‌ نامیم. به ازای p برابر 2 و 3 و 5 و 7 عدد مرسن ، اول است. اما اگرp را 11 بگیریم، عدد حاصل، مرکب است. تا امروز 39 عدد اول مرسن شناخته شده اند که آخرین آن ها 1 -2^13466917است و 4053946 رقم دارد. یعنی بین 13466917 عدد، تنها 39 عدد وجود دارند که عدد اول مرسن تولید می‌کنند.

اعداد اول دوقلو : به اعداد اولی که پشت سر هم هستند، اعداد اول دوقلو می‌گوییم. مثلاً 3 و 5 و یا 11 و 13.

هیچ کس نمی داند که پراکندگی این اعداد در میان سایر اعداد چگونه است و آیا تعداشان متناهی است یا خیر. بزگ ترین جفت شناخته شده 1+33218925.2¹⁶⁹⁶⁹⁰ و 1-33218925.2¹⁶⁹⁶⁹⁰ هستند.

برای یافتن اطلاعاتی راجع به جستجوی اعداد اول می‌توانید به این جا و یا سایت پروژهGIMPS مراجعه کنید.

از گذشته تشخیص اول بودن یک عدد و یافتن عوامل اول اعداد ذهن بشر را به خود مشغول کرده بود. امروزه می دانیم که اگر عدد مورد نظر را به ترتیب به همه ی اعداد کوچک تر از آن تقسیم کنیم، در صورتی که بر هیچ یک از اعداد بخش پذیر نباشد، عدد مورد نظر عدد اول است؛ و اگر بخش پذیر بود، به این ترتیب عوامل اول آن معلوم می‌شوند. با گذشت زمان این فرایند ساده تر شد. مثلاً امروزه می‌دانیم که تنها تقسیم کردن به همه ی اعداد کوچک تر از جذر عدد مورد نظر کافی است ( چرا؟ ). هم چنین در صورتی که اعداد اول کوچک تر از عدد مورد نظر شناخته شده باشند، تقسیم کردن به این اعداد نیز کافی است. این روش‌ها برای اعداد نسبتاً کوچک کار می‌کنند. اما زمانی که عددی مثلاً 100 رقمی در اختیار داریم، نمی توان از این روش ها استفاده کرد. حتی با سریع ترین کامپیوترها هم تقسیم کردن یک عدد 100 رقمی به همه ی اعداد کوچک تر از آن فرصتی بیش تر از عمر عالم را می طلبد.

یک محاسبه ی سرانگشتی

فرض کنید بخواهیم یک عدد 100 رقمی را به همه ی اعداد کوچک تر از خودش تقسیم کنیم. برای این کار باید حدود 10⁹⁹ تقسیم انجام دهیم. اگر کامپیوتر ما بتواند در هر ثانیه 1000 میلیارد یعنی 10¹² تقسیم انجام دهد، برای انجام کل کار 10⁸⁷ ثانیه وقت لازم است.

یک سال 31536000=3600×24×365 (حدود 10⁸ ثانیه) ثانیه است. این یعنی کار ما 10⁷⁹ سال طول خواهد کشید. عمر عالم حداکثر 15 میلیارد سال تخمین زده می‌شود. بنابراین یک دهم یا یک صدم یا یک هزارم این محاسبه هم غیر قابل انجام است.

حوالی قرن هفدهم توجه ریاضی دانان به این نکته جلب شد که شاید راه های ساده تری برای تشخیص اول بودن یک عدد وجود داشته باشد. زیرا روش تقسیم اطلاعات زیادی ( لیست عوامل اول، وقتی که جواب سؤال منفی است ) به دست می دهد که برای پاسخ گفتن به این سؤال نیازی به آن‌ها نیست. فرما مدتی بعد نشان داد که این حدس صحیح بوده است. فرما قضیه ای را ثابت کرد که تا امروز اساس همه ی روش های آزمایش اول بودن اعداد است و ما آن را با نام قضیه ی کوچک فرما می‌شناسیم.

قضیه‏ی کوچک فرما:

اگرP عددی اول وb عدد دلخواهی باشد، آن گاه باقی مانده ی تقسیم b^p برP، همیشه برابرb است.

بنابراین برای این که بدانیم عددی مثل a اول است یا نه، کافیست عدد دلخواهی مانند b انتخاب کنیم. سپس باقی مانده ی تقسیم b^aبر a را بیابیم. اگر این باقی مانده برابر b نباشد، عدد ما اول نیست.

تنها مشکلی که وجود دارد این است که از آن جا که عکس قضیه ی فرما لزوماً درست نیست - یعنی ممکن است بعضی از اعداد مرکب هم این خاصیت را داشته باشند - اگر باقی مانده برابر b نباشد، نمی توان گفت a اول است. این مشکل هم 300 سال بعد در سال 2004 توسط سه ریاضی دان هندی حل شد و حال می‌توانیم در کسری از ثانیه در مورد اول بودن عددی با 100 رقم اظهار نظر کنیم.

بعد از 2000 سال مسأله ی تشخیص اول بودن اعداد حل شد. اما مسأله ی یافتن عوامل اول هم چنان وجود دارد و کسی نمی داند آیا این مسأله راه حل ساده تری دارد یا نه.

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