تبلیغات
انجمن ریاضی پژوهشسرای جوان - روشی برای یافتن اعداد اول

انجمن ریاضی پژوهشسرای جوان

روشی برای یافتن اعداد اول

سه شنبه 20 آذر 1386

در سال  ۱۹۵۶منطق‌دان برجسته آلمانی كورت گودل این پرسش را مطرح ساخت كه آیا می‌توان این نوع روشهای تقسیم را بهبود بخشید. تلاش خود او نهایتا به كشف شماری از روشهای عملی برای یافتن اعدادی به بزرگی  ۱۰۰رقم یا بیشتر منجر شد. همه این روشها احتمالاتی هستند و بنابراین در مواردی پاسخ غلط به دست می‌دهند هرچند كه این موارد بسیار نادرند. در سال  ۱۹۸۳روشی كشف شد كه بسیار نزدیك به روشهای توانی بود. این روش كه به وسیله سه ریاضی دان به نامهای لئونارد آدلمن از دانشگاه كالیفرنیای جنوبی، كارل پومرانس از آزمایشگاهای بل در موری هیل نیو جرسی، و رابرت روملی از دانشگاه جورجیا كشف شد به نام خود آنان به روش آپی آر  APRشهرت یافت. در این روش زمان محاسبه یك عدد دارای  dرقم برای است با .(d)ln ln d در این فرمول ( (ln ln d)به معنای لگارتیم لگاریتم  dاست. به لحاظ فنی این روش غیر توانی است زیرا توان آن ثابت نیست و زیاد می‌شود. اما سرعت این ازدیاد بسیار بسیار كند است. یعنی به ازای  d ="10100میزان" ازدیاد این توان تنها  ۵.۶مرتبه است. ریاضی دانان به شوخی می‌گویند كه ثابت شده این توان به سمت بینهایت میل می‌كند اما چنین چیزی در عمل مشاهده نشده است. سوالی كه برای ریاضی دانان مطرح است آن است كه آیا می‌توان به روشی دست یافت كه به معنای دقیق و فنی كلمه روشی توانی باشد. هیچ كس تصور نمی‌كرد كه احتمال چنین موفقیتی وجود داشته باشد تا اینكه گروه آگراوال ادعا خود را مطرح كرد.ایده انقلابی این سه تن... 

ایده انقلابی این سه تن در سال  ۲۰۰۲و زمانی كه كایال و سكسنا هنوز دانشجوی دوره لیسانس بودند مطرح شد. در ابتدای سال جاری یك روایت بهبود یافته از روش پیشنهادی این سه كه به آلگوریتم آ.ك.اس شهرت یافته در نشریه "آنالز او متمتیكس "Annals of Mathematicsانتشار یافت. این آلگوریتم از نوع روشهای توانی است و علاوه برآن بسیار ساده است (لااقل برای ریاضی دانان چنین است). این روش از اعقاب یك روش آزمون قدیمی موسوم به قضیه كوچك پی‌یر فرما است. این قضیه را نباید با قضیه اصلی فرما كه چند سال قبل پس از  ۳۰۰سال اثبات شد اشتباه كرد. این قضیه مبتنی بر نوعی حساب متكی به قدر مطلق modularموسوم به "حساب ساعت "clock arithmeticاست علت آن تست كه در این روش اعداد به شكل اعداد روی صفحه ساعت جمع می‌شوند. برای آشنایی با این حساب خاص مورد زیر را در نظر بگیرید. یك عدد دلخواه انتخاب كنید و آن را قدر مطلق  modulusبنامید. در مثال ساعت، این عدد خاص كه قدر مطلق نامیده می‌شود و مبنای محاسبه قرار می‌گیرد، عدد  ۱۲است. حال در هر نوع محاسبه ریاضی با اعداد صحیح برای تبدیل آن سیستم عددی به سیستم عددی قدر مطلق  ۱۲كافی است بجای همه مضارب صحیح عدد  ۱۲عدد صفر قرار داده شود. همه اعداد دیگر بر همین اساس تغییر می‌كنند. مثلا عدد  ۲۵برابر است با  ۲۴۱بنابراین عدد  ۲۵در این سیستم قدر مطلق برابر است با " ۱به قدر مطلق 12"سیستمهای حساب متكی به قدر مطلق به تعریفی كه ذكر شد سیستمهای زیبایی هستند زیرا در آنها همه قواعد حساب متعارف كار می‌كند و درعین حال برخی از اعداد غیرصفر درآن ناپدید می‌شوند. قضیه كوچك فرما می‌گوید اگر یك عدد اول را به عنوان قدر مطلق انتخاب كنید ، دارای یك مشخصه ویژه خواهد بود. این مشخصه عبارت از آن است كه یك فرمول خاص یعنی  a)p-1)در این سیستم همواره برابر یك خواهد بود. در این فرمول  pعبارت است از عدد اولی كه به عنوان قدر مطلق انتخاب شده و aهر عدد دیگر است كه ضریب  pمحسوب نمی‌شود. اگر مقدار فرمول بالا برابر یك نباشد آنگاه عددی كه به عنوان عدد اول تصور كرده بودید یعنی  pعدد اول نیست. به این ترتیب می‌توان از این قضیه كوچك فرما به عنوان مبنایی برای تدوین آزمونی جهت تعیین اعداد اول استفاده كرد. این آزمون كاملا بی‌نقص نیست زیرا شماری از اعداد غیر اول نیز از غربال آن رد می‌شوند. اما می‌توان روایت های پیچیده تر و دقیق تری از این آزمون را تولید كرد كه بسادگی به اعداد غیر اول اجازه ورود ندهند. یك نمونه پیشرفته از این آزمونها همان روش "آ.پی.آر" است كه در بالا اشاره شد. گروه آگراوال از همین قضیه كوچك فرما استفاده كرد اما آن را به نحو دیگری بسط داد. این گروه به عوض آنكه با اعداد كار كنند از چند جمله‌ای‌ها استفاده كردند. چند جمله‌ای‌ها عباراتی جبری هستند نظیر ( .a + b(2ایده استفاده از این روش محصول كوشش آگراوال در دورانی بود كه بر روی رساله دكتری خود كار می‌كرد و به اتفاق استاد راهنمای خویش "سومنات بیسواس" در سال  ۱۹۹۹مقاله- ای را به چاپ رساند كه در آن یك روش آزمون اعداد اول پیشنهاد شده بود كه از همین چند جمله‌ای‌ها استفاده می‌كرد و به شیوه احتمالاتی محاسبات را انجام می داد. آگراوال بر این باور بود كه می‌تواند این روش پیشنهادی را دقیق‌تر و عنصر احتمالاتی آن را حذف كرد.

 

در سال  ۲۰۰۱دو تن از دانشجویان او یعنی كایال و سكسنا به یك نكته بسیار حساس و فنی توجه كردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندك اندك برایشان روشن شد كه تنها یك مانع در راه تكمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد. مانع از این قرار بود كه روش آنان تنها در صورتی كار می‌كرد كه عدد اول مورد نظر كه با  pنمایش داده می‌شود همواره در محدوده خاصی جای داشته باشد كه با اعدادی كه در آزمون شركت داده می‌شوند مرتبط باشد. مشخصه ویژه این مانع آن است كه عدد "  p-1 " باید یك مقسوم علیه یا بخشیاب بسیار بزرگ باشد. گروه سه نفر ریاضی دانان هندی برای غلبه بر مشكل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند كه در سال  ۱۹۸۵یك ریاضی‌دان فرانسوی به نام اتن فووری از دانشگاه پاریس  ۱۱این نكته را به صورت ریاضی اثبات كرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد. اما این موفقیت "مشروط" بود. به این معنی كه این روش برای اعداد اولی كه انسان در حال حاضر می‌توان به سراغ آنها برود از كارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات كه متناسب با ارقام عدد اول مورد نظر بود، با آهنگ  ۱۰۱۲ازدیاد پیدا می كرد. در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ۱۰۷.۵كاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود كه تعداد ارقام عدد اولی كه قصد شكار و یافتن آن را داریم در حدود  ۱۰۱۰۰۰باشد. اعدادی تا این اندازه بزرگ در حافظه هیچ كامپیوتر جای نمی‌گیرند و حتی آن را نمی‌توان در كل كیهان جای داد. اما حال كه ریاضی دانان توانسته‌اند یك طبقه خاص از آلگوریتمهای توانی را برای شناسایی اعداد اول مشخص كنند، این امكان پدید آمده كه به دنبال نمونه‌های بهتر این روش بگردند. پومرانس و هندریك لنسترا از دانشگاه كالیفرنیا در بركلی با تلاش در همین زمینه توانسته‌اند زمان لازم برای محاسبات را از توان  ۷.۵به توان  ۶كاهش دهند. این دو از همان استراتژی كلی گروه هندی موسسه كانپور استفاده كردند اما تاكتیهای دیگری را به كار گرفتند. اگر فرضیه‌های دیگری كه درباره اعداد اول مطرح شده درست از كار درآید آنگاه می‌توان زمان محاسبه را از توان  ۶به توان  ۳تقلیل داد كه در این حد این روش كارآیی عملی پیدا خواهد كرد. در این حالت یافتن اعداد اول با  ۱۰۰۰رقم یا بیشتر به بازی كودكان بدل خواهد شد. اما در نظر ریاضی‌دانان مهمترین و جالبترین جنبه كار گروه سه نفره آ ك اس (كانپ.ر) روشی است كه آنان به كار گرفته‌اند. اعداد اول برای ریاضیات از اهمیت بنیادین برخوردارند و هر نوع غفلت در فهم ویژگیهای آنها باعث می‌شود خللهای بزرگ در بنای ریاضیات پدیدار شود. روش این سه ریاضی دان هندی هرچند این خللها و نقصها را پر نكرده حداقل به ریاضی دانان گفته است كه در كجا به دنبال این خللها بگردند. آلگوریتم پیشنهادی این سه محقق و همه انواع بدیلی كه بر اساس آن ساخته شده متكی به وجود اعداد اولی با مشخصه های ویژه هستند. و در اغلب موارد استفاده از این روش مستلزم آن است كه ریاضی دانان اطلاعات دقیقی از نحوه توزیع این قبیل اعداد اول خاص در میان دیگر اعداد به دست آورند و به این ترتیب جغرافیای مكانی اعداد اول را مشخص سازند. روش پیشنهادی آ ك اس به ریاضی دانان این نكته را آموخته كه ویژگیهای این جغرافیای مكانی حائز اهمیت است و نیز این كه هنوز دانش كافی در این زمینه به دست نیامده است. در گذشته و در زمانی كه نظریه اعداد تنها مورد توجه یك گروه كوچك از ریاضی دانان بود ، این مساله چندان اهمیتی نداشت. اما در  ۲۰سال گذشته اعداد اول موقعیتی استثنایی در عرصه رمز نگاری و دانش طراحی و شكستن رمزها كسب كرده اند. رمزها صرفا از نظر نظامی و جاسوسی حائز اهمیت نیستند بلكه از آنها در عرصه های تجاری و نیز فعالییتهای اینترنتی در مقیاس وسیع استفاده به عمل می‌آید. هیچ كس نمی‌خواهد كه راهزنان اینترنتی به اطلاعات شخصی مربوط به حسابهای بانكی یا شماره كارتهای اعتباری آنان دست یابد. هم اكنون دزدی مشخصات شناسنامه ای افراد و جعل هویت آنان به صورت یكی از بزرگترین قلمروهای فعالییتهای تبهكارانه در سطح بین‌المللی در آمده است. سازندگان كامپیوترها و ارائه‌دهندگان خدمات اینترنتی با توجه به آنكه در حال حاضر افراد بسیاری از فعالیتهای خود را از طریق اینترنت انجام می دهند، نظیر اینكه پول قبضهای برق و آب و تلفن خود را می‌پردازند یا در كلاسهای مورد نظر ثبت نام می‌كنند، یا بلیت هواپیما و قطار رزرو می‌كنند، در تلاشند تا از خطر دستیابی تبهكاران به اطلاعات شخصی افراد جلوگیری به عمل اورند. یكی از مهمترین سیستمهایی كه در این زمینه مورد استفاده صنایع است سیستم آر اس آ نام دارد كه متكی به اعداد اول است. اعداد اول مورد استفاده در این سیستم در حدود  ۱۰۰رقمی هستند. سیستم آر اس آ در بسیاری از سیستمهای كامپیوتری مورد استفاده قرار دارد و در پروتكل اصلی برای ارتباطات امن اینرتنتی نیز گنجانده شده است و بسیاری از دولتها، شركتهای بزرگ و دانشگاهها از آن استفاده می‌كنند. جواز استفاده از این سیستم برای بیش از  ۷۰۰شركت صادر شده و بیش از نیم میلیون كپی از آن در سطح جهانی مورد استفاده قرار دارد. برای شكستن رمز آر اس آ باید مضراب اعداد  ۲۰۰رقمی یا بزرگتر را پیدا كنید. هرچند فاكتور گیری یا عامل مشترك گیری از اعداد سخت تر از آزمودن اول بودن آنهاست اما این دو مساله با یكدیگر ارتباط دارند و ریاضی دانان از یك ابزار برای حل هر دو مساله استفاده می‌كنند. همه این جنبه‌ها بر اهمیت كشف هر روشی برای محاسبه اعداد اول می‌افزاید. در سال  ۱۹۹۵زمانی كه پیتر شور از آزمایشگاههای بل اثبات كرد كه مجموعه- ای از آلگوریتمهای توانی برای فاكتور گیری وجود دارد، لرزه بر اندام بسیاری افتاد. اما خوشبختانه برای استفاده از این آلگوریتم به كامپیوترهای كوانتومی نیاز است كه هنوز در مرحله تكمیل تئوریك قرار دارند. اكنون روش تازه آگراوال و دوستانش دوباره سیستم آر اس آ را در معرض خطر قرار داده است. آگراوال اكنون این نكته را نشان داده كه می‌توان با كامپیوتر های معمولی، اعداد را از حیث اول بودن مورد آزمایش قرار داد. سوالی كه اینك مطرح شده آن است كه آیا الگوریتم مشابهی كه به صورت توانی كار كند برای فاكتورگیری اعداد غیراول نیز موجود است؟ پاسخ اغلب متخصصان به این پرسش منفی است اما متاسفانه این متخصصان همین حرف را در مورد آلگوریتم توانی مربوط به اعداد اول نیز می‌زدند در حال حاضر ریاضی دانان واقعا مطمئن نیستند كه كه آیا چنین آلگوریتمی یافت می‌شود یا نه. اگر پاسخ مثبت باشد انگاه سیستم آر اس آ دیگر از امنیت برخوردار نیست. یك عامل تخفیف‌دهنده نگرانیها آن است كه از سیستم آر اس آ برای انتقال همه محتوای پیامها استفاده نمی‌شود بلكه صرفا "كلید های رمز" را كه اندازه شان كوچك است با این سیستم انتقال می‌دهند. برای انتقال بقیه پیام از روشهای رمزنگاری متعارف بهره گرفته می‌شود. به این ترتیب جاسوسان در صدد برخواهند آمد كه به كلید رمزها دست یابند. به این ترتیب درسی كه از موفقیت گروه سه نفره هندی گرفته می‌شود آن است كه باید با احتیاط در ارسال پیامها عمل كرد. اگر اكتشافات مشابه آنچه گروه كانپور بدست اورده تكرار شود، انگاه دیگر نمی‌توان به ایمن بودن ارتباطاتی كه روی اینترنت برقرار می‌شود اطمینان داشت.



[ سه شنبه 20 آذر 1386 - 05:12 ق.ظ ]
[ویرایش شده در : - - -]

[ پیام ()|| سروش حکیمی و سروش افخمی ] [عمومی , ] [+]