اعداد اول

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

اعداد اول اعداد بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌کننده ای را در برابر ریاضی دانان مطرح ساخته اند. تعریف این اعداد کاملا ساده است، رفتار آنها در سلسله اعداد و نحوه ظاهر شدنشان در آن کاملابی‌نظم و فاقد قاعده به نظر می‌آید و هرچه شمار بیشتری از آنها شکارمی‌شوند ، کار شکار عدد بعدی دشوارترمی‌شود طی قرنهای متمادی ریاضی دانان در شرق و غرب عالم به جستجوی راههایی برای دستیابی به اعداد اول برخاسته‌اند و با این همه بهترین روشهایی که تا بحال در این زمینه ابداع شده چنان کند است که حتی پر سرعت‌ترین کامپیوتر های کنونی نیز نمی‌توانند کمک چندانی در شکار این اعداد شگفت انگیز کنند. بطوریکه اگر چندین میلیون بار به سرعت کامپیوتر های کنونی افزوده شود، تنها چند رقم به شماره ارقام بزرگترین عدد اولی که تا به حال شناخته شده افزوده می‌گردد. ریاضی دانان در آرزوی دست یافته به روشی هستند که با استفاده از آن بتوانند با سرعت به یافتن اعداد اول توفیق یابند و یا اگر با عددی هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند که آیا عدد اول است ؟ یک گروه از ریاضی می‌کند. این آزمون دانان هندی مدعی شده‌اند که در آستانه دستیابی به همان آزمونی هستند که ریاضی دانان قرنها مشتاقانه در آرزویش بوده اند. مانیندرا اگراوال ,Manindra Agrawalو دانشجویانش نیراج کایالNeeraj Kayalو نیتین سکسناNitin Saxenaدر موسسه تکنولوژی کانپور مدعی شده‌اند که در آستانه تکمیل آزمونی هستند که اول بودن یا نبودن هر عدد طبیعی را با سرعت مشخص در صورتی که تکمیل شود می‌تواند تبعات و نتایج بسیار گسترده‌ای برای جهان کنونی به بار آورد. جالب به نظر میرسد که بدانید: درحال حاضر بسیاری از معاملات تجاری و نقل و انتقالات مالی و نیز مبادله اطلاعات محرمانه از طریق شبکه های مخابراتی مانند اینترنت و با بهره گیری از رمز کردن پیامها به انجام می‌رسد. اعداد اول در تنظیم این قبیل رمزها نقشی اساسی بر عهده دارند و از همین رو دستیابی به اعداد اول جدید که دیگران از آن بی‌خبر باشند برای سازندگان این رمزها و نیز مشتریان آنان از اهمیت زیاد برخوردار است. اما اگر روش این محققان هندی تکمیل شود در آن صورت امنیت این قبیل نقل و انتقالات در معرض خطر جدی قرار خواهد گرفت. سابقه قرار گرفتن ریاضی دانان تحت جاذبه اعداد اول به قرنها پیش باز می گردد. در سال 1801کارل گائوس از بزرگترین ریاضی دانان اعلام کرد که مساله تشخیص اعداد اول از اعداد غیر اول یکی از مهمترین مسائل حساب به شمار می‌آید. اعداد اول به یک معنا همان نقشی را در سلسله اعداد بازی می‌کنند که اتمها در ساختار بنای کیهان دارند- این اعداد سنگ بنای ناپیدای دیگر اعداد محسوب می‌شوند. یکی از عادی‌ترین راههای شناسایی اعداد اول تقسیم آن به دیگر اعداد است. از طرف دیگر با اندکی تامل روشن می‌شود که اعداد زوج عدد اول نیستند زیرا همگی بر 2قابل قسمتند. اعدادی که بتوان جذر آنها را به دست آورد نیز اول نیستند. اما این روشها برای شناسایی اعداد اول بزرگ به کلی بی‌فایده‌اند. به عنوان مثال اگر عدد اولی دارای 100رقم باشد در آن صورت کل عمر باقیمانده از کیهان بر اساس نظریه های جدید کیهانشناسی نیز برای مشخص کردن اول بودن یا نبودن این عدد با این شیوه های متعارف کفایت نمی‌کند. بنابراین ریاضی دانان به سراغ روشهای دیگر رفته‌اند. مهمترین سوال در مورد همه این روشها آن است که با چه سرعتی می‌توانند یک عدد اول را مشخص کنند و با ازدیاد ارقام عدد اول زمان لازم برای محاسبه چه اندازه طولانی تر می شود. اگر به عنوان مثال زمان محاسبه به توان ثابتی از شمار ارقام عدد ازدیاد شمار آورده یابد در آن صورت این روش روش قابل قبولی به شمار آورده می شود. به این نوع روشها که زمان در آنها به صورت توانی افزوده می شود "روش توانی" می گویند.


روشهای دیگر که زمان در آنها با سرعت بیشتری افزایش می یابد روشهای غیر توانی نام دارند. به عنوان مثال روش تقسیم معمولی یک روش غیر توانی برای یافتن اعداد اول است.


در سال 1956منطق‌دان برجسته آلمانی کورت گودل این پرسش را مطرح ساخت که آیا می‌توان این نوع روشهای تقسیم را بهبود بخشید. تلاش خود او نهایتا به کشف شماری از روشهای عملی برای یافتن اعدادی به بزرگی 100رقم یا بیشتر منجر شد. همه این روشها احتمالاتی هستند و بنابراین در مواردی پاسخ غلط به دست می‌دهند هرچند که این موارد بسیار نادرند. در سال 1983روشی کشف شد که بسیار نزدیک به روشهای توانی بود. این روش که به وسیله سه ریاضی دان به نامهای لئونارد آدلمن از دانشگاه کالیفرنیای جنوبی، کارل پومرانس از آزمایشگاهای بل در موری هیل نیو جرسی، و رابرت روملی از دانشگاه جورجیا کشف شد به نام خود آنان به روش آپی آر APRشهرت یافت. در این روش زمان محاسبه یک عدد دارای dرقم برای است با .(d)ln ln d در این فرمول ( (ln ln d)به معنای لگارتیم لگاریتم dاست. به لحاظ فنی این روش غیر توانی است زیرا توان آن ثابت نیست و زیاد می‌شود. اما سرعت این ازدیاد بسیار بسیار کند است. یعنی به ازای d ="10100میزان" ازدیاد این توان تنها 6.5مرتبه است. ریاضی دانان به شوخی می‌گویند که ثابت شده این توان به سمت بینهایت میل می‌کند اما چنین چیزی در عمل مشاهده نشده است. سوالی که برای ریاضی دانان مطرح است آن است که آیا می‌توان به روشی دست یافت که به معنای دقیق و فنی کلمه روشی توانی باشد. هیچ کس تصور نمی‌کرد که احتمال چنین موفقیتی وجود داشته باشد تا اینکه گروه آگراوال ادعا خود را مطرح کرد.ایده انقلابی این سه تن در سال 2002و زمانی که کایال و سکسنا هنوز دانشجوی دوره لیسانس بودند مطرح شد. در ابتدای سال جاری یک روایت بهبود یافته از روش پیشنهادی این سه که به آلگوریتم آ.ک.اس شهرت یافته در نشریه "آنالز او متمتیکس "Annals of Mathematicsانتشار یافت. این آلگوریتم از نوع روشهای توانی است و علاوه برآن بسیار ساده است (لااقل برای ریاضی دانان چنین است). این روش از اعقاب یک روش آزمون قدیمی موسوم به قضیه کوچک پی‌یر فرما است. این قضیه را نباید با قضیه اصلی فرما که چند سال قبل پس از 300سال اثبات شد اشتباه کرد. این قضیه مبتنی بر نوعی حساب متکی به قدر مطلق modularموسوم به "حساب ساعت "clock arithmeticاست علت آن تست که در این روش اعداد به شکل اعداد روی صفحه ساعت جمع می‌شوند. برای آشنایی با این حساب خاص مورد زیر را در نظر بگیرید. یک عدد دلخواه انتخاب کنید و آن را قدر مطلق modulusبنامید. در مثال ساعت، این عدد خاص که قدر مطلق نامیده می‌شود و مبنای محاسبه قرار می‌گیرد، عدد 12است. حال در هر نوع محاسبه ریاضی با اعداد صحیح برای تبدیل آن سیستم عددی به سیستم عددی قدر مطلق 12کافی است بجای همه مضارب صحیح عدد 12عدد صفر قرار داده شود. همه اعداد دیگر بر همین اساس تغییر می‌کنند. مثلا عدد25برابر است با 241بنابراین عدد 25در این سیستم قدر مطلق برابر است با "1به قدر مطلق 12"سیستمهای حساب متکی به قدر مطلق به تعریفی که ذکر شد سیستمهای زیبایی هستند زیرا در آنها همه قواعد حساب متعارف کار می‌کند و درعین حال برخی از اعداد غیرصفر درآن ناپدید می‌شوند. قضیه کوچک فرما می‌گوید اگر یک عدد اول را به عنوان قدر مطلق انتخاب کنید ، دارای یک مشخصه ویژه خواهد بود. این مشخصه عبارت از آن است که یک فرمول خاص یعنی a)p-1)در این سیستم همواره برابر یک خواهد بود. در این فرمول pعبارت است از عدد اولی که به عنوان قدر مطلق انتخاب شده و aهر عدد دیگر است که ضریب pمحسوب نمی‌شود. اگر مقدار فرمول بالا برابر یک نباشد آنگاه عددی که به عنوان عدد اول تصور کرده بودید یعنی pعدد اول نیست. به این ترتیب می‌توان از این قضیه کوچک فرما به عنوان مبنایی برای تدوین آزمونی جهت تعیین اعداد اول استفاده کرد. این آزمون کاملا بی‌نقص نیست زیرا شماری از اعداد غیر اول نیز از غربال آن رد می‌شوند. اما می‌توان روایت های پیچیده تر و دقیق تری از این آزمون را تولید کرد که بسادگی به اعداد غیر اول اجازه ورود ندهند. یک نمونه پیشرفته از این آزمونها همان روش "آ.پی.آر" است که در بالا اشاره شد. گروه آگراوال از همین قضیه کوچک فرما استفاده کرد اما آن را به نحو دیگری بسط داد. این گروه به عوض آنکه با اعداد کار کنند از چند جمله‌ای‌ها استفاده کردند. چند جمله‌ای‌ها عباراتی جبری هستند نظیر ( .a + b(2ایده استفاده از این روش محصول کوشش آگراوال در دورانی بود که بر روی رساله دکتری خود کار می‌کرد و به اتفاق استاد راهنمای خویش "سومنات بیسواس" در سال 1999مقاله- ای را به چاپ رساند که در آن یک روش آزمون اعداد اول پیشنهاد شده بود که از همین چند جمله‌ای‌ها استفاده می‌کرد و به شیوه احتمالاتی محاسبات را انجام می داد. آگراوال بر این باور بود که می‌تواند این روش پیشنهادی را دقیق‌تر و عنصر احتمالاتی آن را حذف کرد.