Borna66
03-16-2009, 04:54 PM
اعداد اول بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌كننده ای را در برابر ریاضی دانان مطرح ساخته اند: تعریف این اعداد كاملا ساده است، رفتار آنها در سلسله اعداد و نحوه ظاهر شدنشان در آن كاملا بی‌نظم و فاقد قاعده به نظر می‌آید و هرچه شمار بیشتری از آنها شكارمی‌شوند، كار شكار بعدی‌ها دشوارتر می‌شود.
طی قرنهای متمادی ریاضی دانان در شرق و غرب عالم به جستجوی راههایی برای دستیابی به اعداد اول برخاسته‌اند و با این همه بهترین روشهایی كه تا بحال در این زمینه ابداع شده چنان كند است كه حتی پر سرعت‌ترین كامپیوتر های كنونی نیز نمی‌توانند كمك چندانی در شكار این اعداد شگفت انگیز كنند.
اعداد اول بر طبق تعریف اعدادی هستند كه تنها به ۱و بر خودشان تقسیم پذیرند. به عنوان نمونه اعداد ۲،۳،۵،۷،۱۱،۱۳،۱۷،۱۹اعدا � اول كمتر از ۲۰ در سلسله اعداد طبیعی هستند. اما هرچه در این سلسله پیش تر برویم اعداد اول نایاب تر می‌شوند.
بطوریكه اگر چندین میلیون بار به سرعت كامپیوتر های كنونی افزوده شود، تنها چند رقم به شماره ارقام بزرگترین عدد اولی كه تا به حال شناخته شده افزوده می‌گردد.
ریاضی دانان در آرزوی دست یافته به روشی هستند كه با استفاده از آن بتوانند با سرعت به یافتن اعداد اول توفیق یابند و یا اگر با عددی هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند كه آیا عدد اول است ؟ - اما یافتن چنین روشی به فسفر مغز نیاز دارد و نه سرعت كامپیوتر. -
اما یك گروه از ریاضی دانان هندی مدعی شده‌اند كه در آستانه دستیابی به همان آزمونی هستند كه ریاضی دانان قرنها مشتاقانه در آرزویش بوده اند.
مانیندرا اگراوال ,Manindra Agrawalو دانشجویانش نیراج كایال Neeraj Kayalو نیتین سكسنا Nitin Saxenaدر موسسه تكنولوژی كانپور مدعی شده‌اند كه در آستانه تكمیل آزمونی هستند كه اول بودن یا نبودن هر عدد طبیعی را با سرعت مشخص می‌كند. این آزمون در صورتی كه تكمیل شود می‌تواند تبعات و نتایج بسیار گسترده‌ای برای جهان كنونی به بار آورد.
درحال حاضر بسیاری از معاملات تجاری و نقل و انتقالات مالی و نیز مبادله اطلاعات محرمانه از طریق شبكه های مخابراتی مانند اینترنت و با بهره گیری از رمز كردن پیامها به انجام می‌رسد.
اعداد اول در تنظیم این قبیل رمزها نقشی اساسی بر عهده دارند و از همین رو دستیابی به اعداد اول جدید كه دیگران از آن بی‌خبر باشند برای سازندگان این رمزها و نیز مشتریان آنان از اهمیت زیاد برخوردار است.
اما اگر روش این محققان هندی تكمیل شود در آن صورت امنیت این قبیل نقل و انتقالات در معرض خطر جدی قرار خواهد گرفت.
سابقه قرار گرفتن ریاضی دانان تحت جاذبه اعداد اول به قرنها پیش باز می گردد. در سال ۱۸۰۱كارل گائوس از بزرگترین ریاضی دانان اعلام كرد كه مساله تشخیص اعداد اول از اعداد غیر اول یكی از مهمترین مسائل حساب به شمار می‌آید.
اعداد اول به یك معنا همان نقشی را در سلسله اعداد بازی می‌كنند كه اتمها در ساختار بنای كیهان دارند- این اعداد سنگ بنای ناپیدای دیگر اعداد محسوب می‌شوند.
یكی از عادی‌ترین راههای شناسایی اعداد اول تقسیم آن به دیگر اعداد است.
از طرف دیگر با اندكی تامل روشن می‌شود كه اعداد زوج عدد اول نیستند زیرا همگی بر ۲قابل قسمتند.
اعدادی كه بتوان جذر آنها را به دست آورد نیز اول نیستند. اما این روشها برای شناسایی اعداد اول بزرگ به كلی بی‌فایده‌اند. به عنوان مثال اگر عدد اولی دارای ۱۰۰رقم باشد در آن صورت كل عمر باقیمانده از كیهان بر اساس نظریه های جدید كیهانشناسی نیز برای مشخص كردن اول بودن یا نبودن این عدد با این شیوه های متعارف كفایت نمی‌كند.
بنابراین ریاضی دانان به سراغ روشهای دیگر رفته‌اند. مهمترین سوال در مورد همه این روشها آن است كه با چه سرعتی می‌توانند یك عدد اول را مشخص كنند و با ازدیاد ارقام عدد اول زمان لازم برای محاسبه چه اندازه طولانی تر می شود. اگر به عنوان مثال زمان محاسبه به توان ثابتی از شمار ارقام عدد ازدیاد یابد در آن صورت این روش روش قابل قبولی به شمار آورده می‌شود .
به این نوع روشها كه زمان به صورت توانی در آنها افزوده می‌شود "روشهای توانی" می‌گویند. روشهای دیگر كه زمان در آنها با سرعت بیشتری افزایش می‌یابد روشهای غیرتوانی نام دارند.
به عنوان مثال روش تقسیم معمولی یك روش غیرتوانی برای یافتن اعداد اول است. در این روش زمان لازم برای تعیین اول بودن یك عدد با dرقم، برابر با /۱۰d/2این نوع روشها بسیار نامناسبند.
در سال ۱۹۵۶منطق‌دان برجسته آلمانی كورت گودل این پرسش را مطرح ساخت كه آیا می‌توان این نوع روشهای تقسیم را بهبود بخشید. تلاش خود او نهایتا به كشف شماری از روشهای عملی برای یافتن اعدادی به بزرگی ۱۰۰رقم یا بیشتر منجر شد. همه این روشها احتمالاتی هستند و بنابراین در مواردی پاسخ غلط به دست می‌دهند هرچند كه این موارد بسیار نادرند.
در سال ۱۹۸۳روشی كشف شد كه بسیار نزدیك به روشهای توانی بود. این روش كه به وسیله سه ریاضی دان به نامهای لئونارد آدلمن از دانشگاه كالیفرنیای جنوبی، كارل پومرانس از آزمایشگاهای بل در موری هیل نیو جرسی، و رابرت روملی از دانشگاه جورجیا كشف شد به نام خود آنان به روش آپی آر APRشهرت یافت.
در این روش زمان محاسبه یك عدد دارای dرقم برای است با .(d)ln ln d
در این فرمول
( (ln ln dبه معنای لگارتیم لگاریتم dاست. به لحاظ فنی این روش غیر توانی است زیرا توان آن ثابت نیست و زیاد می‌شود. اما سرعت این ازدیاد بسیار بسیار كند است. یعنی به ازای d =10100میزان ازدیاد این توان تنها ۵.۶مرتبه است. ریاضی دانان به شوخی می‌گویند كه ثابت شده این توان به سمت بینهایت میل می‌كند اما چنین چیزی در عمل مشاهده نشده.
سوالی كه برای ریاضی دانان مطرح است آن است كه آیا می‌توان به روشی دست یافت كه به معنای دقیق و فنی كلمه روشی توانی باشد. هیچ كس تصور نمی‌كرد كه احتمال چنین موفقیتی وجود داشته باشد تا اینكه گروه آگراوال بمب خود را منفجر كرد.
ایده انقلابی این سه تن در سال ۲۰۰۲و زمانی كه كایال و سكسنا هنوز دانشجوی دوره لیسانس بودند مطرح شد. در ابتدای سال جاری یك روایت بهبود یافته از روش پیشنهادی این سه كه به آلگوریتم آ.ك.اس شهرت یافته در نشریه "آنالز او متمتیكس "Annals of Mathematicsانتشار یافت.
این آلگوریتم از نوع روشهای توانی است و علاوه برآن بسیار ساده است (لااقل برای ریاضی دانان چنین است). این روش از اعقاب یك روش آزمون قدیمی موسوم به قضیه كوچك پی‌یر فرما است.
این قضیه را نباید با قضیه اصلی فرما كه چند سال قبل پس از ۳۰۰سال اثبات شد اشتباه كرد. این قضیه مبتنی بر نوعی حساب متكی به قدر مطلق modularموسوم به "حساب ساعت "clock arithmeticاست علت آن تست كه در این روش اعداد به شكل اعداد روی صفحه ساعت جمع می‌شوند.
برای آشنایی با این حساب خاص مورد زیر را در نظر بگیرید. یك عدد دلخواه انتخاب كنید و آن را قدر مطلق modulusبنامید. در مثال ساعت، این عدد خاص كه قدر مطلق نامیده می‌شود و مبنای محاسبه قرار می‌گیرد، عدد ۱۲است.
حال در هر نوع محاسبه ریاضی با اعداد صحیح برای تبدیل آن سیستم عددی به سیستم عددی قدر مطلق ۱۲كافی است بجای همه مضارب صحیح عدد ۱۲عدد صفر قرار داده شود. همه اعداد دیگر بر همین اساس تغییر می‌كنند.
مثلا عدد ۲۵برابر است با . + ۲۴۱بنابراین عدد ۲۵در این سیستم قدر مطلق برابر است با " ۱به قدر مطلق ."۱۲سیستمهای حساب متكی به قدر مطلق به تعریفی كه ذكر شد سیستمهای زیبایی هستند زیرا در آنها همه قواعد حساب متعارف كار می‌كند و درعین حال برخی از اعداد غیرصفر درآن ناپدید می‌شوند.
قضیه كوچك فرما می‌گوید اگر یك عدد اول را به عنوان قدر مطلق انتخاب كنید ، دارای یك مشخصه ویژه خواهد بود. این مشخصه عبارت از آن است كه یك فرمول خاص یعنی (a)p-1در این سیستم همواره برابر یك خواهد بود.
در این فرمول pعبارت است از عدد اولی كه به عنوان قدر مطلق انتخاب شده و aهر عدد دیگر است كه ضریب pمحسوب نمی‌شود.
اگر مقدار فرمول بالا برابر یك نباشد آنگاه عددی كه به عنوان عدد اول تصور كرده بودید یعنی pعدد اول نیست.
به این ترتیب می‌توان از این قضیه كوچك فرما به عنوان مبنایی برای تدوین آزمونی جهت تعیین اعداد اول استفاده كرد. این آزمون كاملا بی‌نقص نیست زیرا شماری از اعداد غیر اول نیز از غربال آن رد می‌شوند.
اما می‌توان روایت های پیچیده تر و دقیق تری از این آزمون را تولید كرد كه بسادگی به اعداد غیر اول اجازه ورود ندهند. یك نمونه پیشرفته از این آزمونها همان روش "آ.پی.آر" است كه در بالا اشاره شد.
گروه آگراوال از همین قضیه كوچك فرما استفاده كرد اما آن را به نحو دیگری بسط داد. این گروه به عوض آنكه با اعداد كار كنند از چند جمله‌ای‌ها استفاده كردند.
چند جمله‌ای‌ها عباراتی جبری هستند نظیر ( .a + b(2ایده استفاده از این روش محصول كوشش آگراوال در دورانی بود كه بر روی رساله دكتری خود كار می‌كرد و به اتفاق استاد راهنمای خویش "سومنات بیسواس" در سال ۱۹۹۹مقاله- ای را به چاپ رساند كه در آن یك روش آزمون اعداد اول پیشنهاد شده بود كه از همین چند جمله‌ای‌ها استفاده می‌كرد و به شیوه احتمالاتی محاسبات را انجام می داد.
آگراوال بر این باور بود كه می‌تواند این روش پیشنهادی را دقیق‌تر و عنصر احتمالاتی آن را حذف كرد.
در سال ۲۰۰۱دو تن از دانشجویان او یعنی كایال و سكسنا به یك نكته بسیار حساس و فنی توجه كردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندك اندك برایشان روشن شد كه تنها یك مانع در راه تكمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد.
مانع از این قرار بود كه روش آنان تنها در صورتی كار می‌كرد كه عدد اول مورد نظر كه با pنمایش داده می‌شود همواره در محدوده خاصی جای داشته باشد كه با اعدادی كه در آزمون شركت داده می‌شوند مرتبط باشد.
مشخصه ویژه این مانع آن است كه عدد " "p-1باید یك مقسوم علیه یا بخشیاب بسیار بزرگ باشد.
گروه سه نفر ریاضی دانان هندی برای غلبه بر مشكل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند كه در سال ۱۹۸۵یك ریاضی‌دان فرانسوی به نام اتن فووری از دانشگاه پاریس ۱۱این نكته را به صورت ریاضی اثبات كرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد.
اما این موفقیت "مشروط" بود. به این معنی كه این روش برای اعداد اولی كه انسان در حال حاضر می‌توان به سراغ آنها برود از كارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات كه متناسب با ارقام عدد اول مورد نظر بود، با آهنگ ۱۰۱۲ازدیاد پیدا می كرد.
در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ۱۰۷.۵كاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود كه تعداد ارقام عدد اولی كه قصد شكار و یافتن آن را داریم در حدود ۱۰۱۰۰۰باشد.
اعدادی تا این اندازه بزرگ در حافظه هیچ كامپیوتر جای نمی‌گیرند و حتی آن را نمی‌توان در كل كیهان جای داد.
اما حال كه ریاضی دانان توانسته‌اند یك طبقه خاص از آلگوریتمهای توانی را برای شناسایی اعداد اول مشخص كنند، این امكان پدید آمده كه به دنبال نمونه‌های بهتر این روش بگردند. پومرانس و هندریك لنسترا از دانشگاه كالیفرنیا در بركلی با تلاش در همین زمینه توانسته‌اند زمان لازم برای محاسبات را از توان ۷.۵به توان ۶كاهش دهند.
این دو از همان استراتژی كلی گروه هندی موسسه كانپور استفاده كردند اما تاكتیهای دیگری را به كار گرفتند.
اگر فرضیه‌های دیگری كه درباره اعداد اول مطرح شده درست از كار درآید آنگاه می‌توان زمان محاسبه را از توان ۶به توان ۳تقلیل داد كه در این حد این روش كارآیی عملی پیدا خواهد كرد.
در این حالت یافتن اعداد اول با ۱۰۰۰رقم یا بیشتر به بازی كودكان بدل خواهد شد.
اما در نظر ریاضی‌دانان مهمترین و جالبترین جنبه كار گروه سه نفره آ ك اس (كانپ.ر) روشی است كه آنان به كار گرفته‌اند.
اعداد اول برای ریاضیات از اهمیت بنیادین برخوردارند و هر نوع غفلت در فهم ویژگیهای آنها باعث می‌شود خللهای بزرگ در بنای ریاضیات پدیدار شود.
روش این سه ریاضی دان هندی هرچند این خللها و نقصها را پر نكرده حداقل به ریاضی دانان گفته است كه در كجا به دنبال این خللها بگردند.
آلگوریتم پیشنهادی این سه محقق و همه انواع بدیلی كه بر اساس آن ساخته شده متكی به وجود اعداد اولی با مشخصه های ویژه هستند. و در اغلب موارد استفاده از این روش مستلزم آن است كه ریاضی دانان اطلاعات دقیقی از نحوه توزیع این قبیل اعداد اول خاص در میان دیگر اعداد به دست آورند و به این ترتیب جغرافیای مكانی اعداد اول را مشخص سازند.
روش پیشنهادی آ ك اس به ریاضی دانان این نكته را آموخته كه ویژگیهای این جغرافیای مكانی حائز اهمیت است و نیز این كه هنوز دانش كافی در این زمینه به دست نیامده است.
در گذشته و در زمانی كه نظریه اعداد تنها مورد توجه یك گروه كوچك از ریاضی دانان بود ، این مساله چندان اهمیتی نداشت. اما در ۲۰سال گذشته اعداد اول موقعیتی استثنایی در عرصه رمز نگاری و دانش طراحی و شكستن رمزها كسب كرده اند.
رمزها صرفا از نظر نظامی و جاسوسی حائز اهمیت نیستند بلكه از آنها در عرصه های تجاری و نیز فعالییتهای اینترنتی در مقیاس وسیع استفاده به عمل می‌آید. هیچ كس نمی‌خواهد كه راهزنان اینترنتی به اطلاعات شخصی مربوط به حسابهای بانكی یا شماره كارتهای اعتباری آنان دست یابد.
هم اكنون دزدی مشخصات شناسنامه ای افراد و جعل هویت آنان به صورت یكی از بزرگترین قلمروهای فعالییتهای تبهكارانه در سطح بین‌المللی در آمده است.
سازندگان كامپیوترها و ارائه‌دهندگان خدمات اینترنتی با توجه به آنكه در حال حاضر افراد بسیاری از فعالیتهای خود را از طریق اینترنت انجام می دهند، نظیر اینكه پول قبضهای برق و آب و تلفن خود را می‌پردازند یا در كلاسهای مورد نظر ثبت نام می‌كنند، یا بلیت هواپیما و قطار رزرو می‌كنند، در تلاشند تا از خطر دستیابی تبهكاران به اطلاعات شخصی افراد جلوگیری به عمل اورند.
یكی از مهمترین سیستمهایی كه در این زمینه مورد استفاده صنایع است سیستم آر اس آ نام دارد كه متكی به اعداد اول است.
اعداد اول مورد استفاده در این سیستم در حدود ۱۰۰رقمی هستند. سیستم آر اس آ در بسیاری از سیستمهای كامپیوتری مورد استفاده قرار دارد و در پروتكل اصلی برای ارتباطات امن اینرتنتی نیز گنجانده شده است و بسیاری از دولتها، شركتهای بزرگ و دانشگاهها از آن استفاده می‌كنند. جواز استفاده از این سیستم برای بیش از ۷۰۰شركت صادر شده و بیش از نیم میلیون كپی از آن در سطح جهانی مورد استفاده قرار دارد.
برای شكستن رمز آر اس آ باید مضراب اعداد ۲۰۰رقمی یا بزرگتر را پیدا كنید. هرچند فاكتور گیری یا عامل مشترك گیری از اعداد سخت تر از آزمودن اول بودن آنهاست اما این دو مساله با یكدیگر ارتباط دارند و ریاضی دانان از یك ابزار برای حل هر دو مساله استفاده می‌كنند.
همه این جنبه‌ها بر اهمیت كشف هر روشی برای محاسبه اعداد اول می‌افزاید.
در سال ۱۹۹۵زمانی كه پیتر شور از آزمایشگاههای بل اثبات كرد كه مجموعه- ای از آلگوریتمهای توانی برای فاكتور گیری وجود دارد، لرزه بر اندام بسیاری افتاد.
اما خوشبختانه برای استفاده از این آلگوریتم به كامپیوترهای كوانتومی نیاز است كه هنوز در مرحله تكمیل تئوریك قرار دارند.
اكنون روش تازه آگراوال و دوستانش دوباره سیستم آر اس آ را در معرض خطر قرار داده است. آگراوال اكنون این نكته را نشان داده كه می‌توان با كامپیوتر های معمولی، اعداد را از حیث اول بودن مورد آزمایش قرار داد.
سوالی كه اینك مطرح شده آن است كه آیا الگوریتم مشابهی كه به صورت توانی كار كند برای فاكتورگیری اعداد غیراول نیز موجود است؟ پاسخ اغلب متخصصان به این پرسش منفی است اما متاسفانه این متخصصان همین حرف را در مورد آلگوریتم توانی مربوط به اعداد اول نیز می‌زدند
در حال حاضر ریاضی دانان واقعا مطمئن نیستند كه كه آیا چنین آلگوریتمی یافت می‌شود یا نه.
اگر پاسخ مثبت باشد انگاه سیستم آر اس آ دیگر از امنیت برخوردار نیست.
یك عامل تخفیف‌دهنده نگرانیها آن است كه از سیستم آر اس آ برای انتقال همه محتوای پیامها استفاده نمی‌شود بلكه صرفا "كلید های رمز" را كه اندازه شان كوچك است با این سیستم انتقال می‌دهند.
برای انتقال بقیه پیام از روشهای رمزنگاری متعارف بهره گرفته می‌شود. به این ترتیب جاسوسان در صدد برخواهند آمد كه به كلید رمزها دست یابند.
به این ترتیب درسی كه از موفقیت گروه سه نفره هندی گرفته می‌شود آن است كه باید با احتیاط در ارسال پیامها عمل كرد. اگر اكتشافات مشابه آنچه گروه كانپور بدست اورده تكرار شود، انگاه دیگر نمی‌توان به ایمن بودن ارتباطاتی كه روی اینترنت برقرار می‌شود اطمینان داشت.
ماخذ :
كد - لینک:
ایستنا | آخرین اخبار و تحلیل های حوزه فناوری اطلاعات و ارتباطات (http://www.ictna.ir)
:104:
گردآونده:طه-Borna66
طی قرنهای متمادی ریاضی دانان در شرق و غرب عالم به جستجوی راههایی برای دستیابی به اعداد اول برخاسته‌اند و با این همه بهترین روشهایی كه تا بحال در این زمینه ابداع شده چنان كند است كه حتی پر سرعت‌ترین كامپیوتر های كنونی نیز نمی‌توانند كمك چندانی در شكار این اعداد شگفت انگیز كنند.
اعداد اول بر طبق تعریف اعدادی هستند كه تنها به ۱و بر خودشان تقسیم پذیرند. به عنوان نمونه اعداد ۲،۳،۵،۷،۱۱،۱۳،۱۷،۱۹اعدا � اول كمتر از ۲۰ در سلسله اعداد طبیعی هستند. اما هرچه در این سلسله پیش تر برویم اعداد اول نایاب تر می‌شوند.
بطوریكه اگر چندین میلیون بار به سرعت كامپیوتر های كنونی افزوده شود، تنها چند رقم به شماره ارقام بزرگترین عدد اولی كه تا به حال شناخته شده افزوده می‌گردد.
ریاضی دانان در آرزوی دست یافته به روشی هستند كه با استفاده از آن بتوانند با سرعت به یافتن اعداد اول توفیق یابند و یا اگر با عددی هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند كه آیا عدد اول است ؟ - اما یافتن چنین روشی به فسفر مغز نیاز دارد و نه سرعت كامپیوتر. -
اما یك گروه از ریاضی دانان هندی مدعی شده‌اند كه در آستانه دستیابی به همان آزمونی هستند كه ریاضی دانان قرنها مشتاقانه در آرزویش بوده اند.
مانیندرا اگراوال ,Manindra Agrawalو دانشجویانش نیراج كایال Neeraj Kayalو نیتین سكسنا Nitin Saxenaدر موسسه تكنولوژی كانپور مدعی شده‌اند كه در آستانه تكمیل آزمونی هستند كه اول بودن یا نبودن هر عدد طبیعی را با سرعت مشخص می‌كند. این آزمون در صورتی كه تكمیل شود می‌تواند تبعات و نتایج بسیار گسترده‌ای برای جهان كنونی به بار آورد.
درحال حاضر بسیاری از معاملات تجاری و نقل و انتقالات مالی و نیز مبادله اطلاعات محرمانه از طریق شبكه های مخابراتی مانند اینترنت و با بهره گیری از رمز كردن پیامها به انجام می‌رسد.
اعداد اول در تنظیم این قبیل رمزها نقشی اساسی بر عهده دارند و از همین رو دستیابی به اعداد اول جدید كه دیگران از آن بی‌خبر باشند برای سازندگان این رمزها و نیز مشتریان آنان از اهمیت زیاد برخوردار است.
اما اگر روش این محققان هندی تكمیل شود در آن صورت امنیت این قبیل نقل و انتقالات در معرض خطر جدی قرار خواهد گرفت.
سابقه قرار گرفتن ریاضی دانان تحت جاذبه اعداد اول به قرنها پیش باز می گردد. در سال ۱۸۰۱كارل گائوس از بزرگترین ریاضی دانان اعلام كرد كه مساله تشخیص اعداد اول از اعداد غیر اول یكی از مهمترین مسائل حساب به شمار می‌آید.
اعداد اول به یك معنا همان نقشی را در سلسله اعداد بازی می‌كنند كه اتمها در ساختار بنای كیهان دارند- این اعداد سنگ بنای ناپیدای دیگر اعداد محسوب می‌شوند.
یكی از عادی‌ترین راههای شناسایی اعداد اول تقسیم آن به دیگر اعداد است.
از طرف دیگر با اندكی تامل روشن می‌شود كه اعداد زوج عدد اول نیستند زیرا همگی بر ۲قابل قسمتند.
اعدادی كه بتوان جذر آنها را به دست آورد نیز اول نیستند. اما این روشها برای شناسایی اعداد اول بزرگ به كلی بی‌فایده‌اند. به عنوان مثال اگر عدد اولی دارای ۱۰۰رقم باشد در آن صورت كل عمر باقیمانده از كیهان بر اساس نظریه های جدید كیهانشناسی نیز برای مشخص كردن اول بودن یا نبودن این عدد با این شیوه های متعارف كفایت نمی‌كند.
بنابراین ریاضی دانان به سراغ روشهای دیگر رفته‌اند. مهمترین سوال در مورد همه این روشها آن است كه با چه سرعتی می‌توانند یك عدد اول را مشخص كنند و با ازدیاد ارقام عدد اول زمان لازم برای محاسبه چه اندازه طولانی تر می شود. اگر به عنوان مثال زمان محاسبه به توان ثابتی از شمار ارقام عدد ازدیاد یابد در آن صورت این روش روش قابل قبولی به شمار آورده می‌شود .
به این نوع روشها كه زمان به صورت توانی در آنها افزوده می‌شود "روشهای توانی" می‌گویند. روشهای دیگر كه زمان در آنها با سرعت بیشتری افزایش می‌یابد روشهای غیرتوانی نام دارند.
به عنوان مثال روش تقسیم معمولی یك روش غیرتوانی برای یافتن اعداد اول است. در این روش زمان لازم برای تعیین اول بودن یك عدد با dرقم، برابر با /۱۰d/2این نوع روشها بسیار نامناسبند.
در سال ۱۹۵۶منطق‌دان برجسته آلمانی كورت گودل این پرسش را مطرح ساخت كه آیا می‌توان این نوع روشهای تقسیم را بهبود بخشید. تلاش خود او نهایتا به كشف شماری از روشهای عملی برای یافتن اعدادی به بزرگی ۱۰۰رقم یا بیشتر منجر شد. همه این روشها احتمالاتی هستند و بنابراین در مواردی پاسخ غلط به دست می‌دهند هرچند كه این موارد بسیار نادرند.
در سال ۱۹۸۳روشی كشف شد كه بسیار نزدیك به روشهای توانی بود. این روش كه به وسیله سه ریاضی دان به نامهای لئونارد آدلمن از دانشگاه كالیفرنیای جنوبی، كارل پومرانس از آزمایشگاهای بل در موری هیل نیو جرسی، و رابرت روملی از دانشگاه جورجیا كشف شد به نام خود آنان به روش آپی آر APRشهرت یافت.
در این روش زمان محاسبه یك عدد دارای dرقم برای است با .(d)ln ln d
در این فرمول
( (ln ln dبه معنای لگارتیم لگاریتم dاست. به لحاظ فنی این روش غیر توانی است زیرا توان آن ثابت نیست و زیاد می‌شود. اما سرعت این ازدیاد بسیار بسیار كند است. یعنی به ازای d =10100میزان ازدیاد این توان تنها ۵.۶مرتبه است. ریاضی دانان به شوخی می‌گویند كه ثابت شده این توان به سمت بینهایت میل می‌كند اما چنین چیزی در عمل مشاهده نشده.
سوالی كه برای ریاضی دانان مطرح است آن است كه آیا می‌توان به روشی دست یافت كه به معنای دقیق و فنی كلمه روشی توانی باشد. هیچ كس تصور نمی‌كرد كه احتمال چنین موفقیتی وجود داشته باشد تا اینكه گروه آگراوال بمب خود را منفجر كرد.
ایده انقلابی این سه تن در سال ۲۰۰۲و زمانی كه كایال و سكسنا هنوز دانشجوی دوره لیسانس بودند مطرح شد. در ابتدای سال جاری یك روایت بهبود یافته از روش پیشنهادی این سه كه به آلگوریتم آ.ك.اس شهرت یافته در نشریه "آنالز او متمتیكس "Annals of Mathematicsانتشار یافت.
این آلگوریتم از نوع روشهای توانی است و علاوه برآن بسیار ساده است (لااقل برای ریاضی دانان چنین است). این روش از اعقاب یك روش آزمون قدیمی موسوم به قضیه كوچك پی‌یر فرما است.
این قضیه را نباید با قضیه اصلی فرما كه چند سال قبل پس از ۳۰۰سال اثبات شد اشتباه كرد. این قضیه مبتنی بر نوعی حساب متكی به قدر مطلق modularموسوم به "حساب ساعت "clock arithmeticاست علت آن تست كه در این روش اعداد به شكل اعداد روی صفحه ساعت جمع می‌شوند.
برای آشنایی با این حساب خاص مورد زیر را در نظر بگیرید. یك عدد دلخواه انتخاب كنید و آن را قدر مطلق modulusبنامید. در مثال ساعت، این عدد خاص كه قدر مطلق نامیده می‌شود و مبنای محاسبه قرار می‌گیرد، عدد ۱۲است.
حال در هر نوع محاسبه ریاضی با اعداد صحیح برای تبدیل آن سیستم عددی به سیستم عددی قدر مطلق ۱۲كافی است بجای همه مضارب صحیح عدد ۱۲عدد صفر قرار داده شود. همه اعداد دیگر بر همین اساس تغییر می‌كنند.
مثلا عدد ۲۵برابر است با . + ۲۴۱بنابراین عدد ۲۵در این سیستم قدر مطلق برابر است با " ۱به قدر مطلق ."۱۲سیستمهای حساب متكی به قدر مطلق به تعریفی كه ذكر شد سیستمهای زیبایی هستند زیرا در آنها همه قواعد حساب متعارف كار می‌كند و درعین حال برخی از اعداد غیرصفر درآن ناپدید می‌شوند.
قضیه كوچك فرما می‌گوید اگر یك عدد اول را به عنوان قدر مطلق انتخاب كنید ، دارای یك مشخصه ویژه خواهد بود. این مشخصه عبارت از آن است كه یك فرمول خاص یعنی (a)p-1در این سیستم همواره برابر یك خواهد بود.
در این فرمول pعبارت است از عدد اولی كه به عنوان قدر مطلق انتخاب شده و aهر عدد دیگر است كه ضریب pمحسوب نمی‌شود.
اگر مقدار فرمول بالا برابر یك نباشد آنگاه عددی كه به عنوان عدد اول تصور كرده بودید یعنی pعدد اول نیست.
به این ترتیب می‌توان از این قضیه كوچك فرما به عنوان مبنایی برای تدوین آزمونی جهت تعیین اعداد اول استفاده كرد. این آزمون كاملا بی‌نقص نیست زیرا شماری از اعداد غیر اول نیز از غربال آن رد می‌شوند.
اما می‌توان روایت های پیچیده تر و دقیق تری از این آزمون را تولید كرد كه بسادگی به اعداد غیر اول اجازه ورود ندهند. یك نمونه پیشرفته از این آزمونها همان روش "آ.پی.آر" است كه در بالا اشاره شد.
گروه آگراوال از همین قضیه كوچك فرما استفاده كرد اما آن را به نحو دیگری بسط داد. این گروه به عوض آنكه با اعداد كار كنند از چند جمله‌ای‌ها استفاده كردند.
چند جمله‌ای‌ها عباراتی جبری هستند نظیر ( .a + b(2ایده استفاده از این روش محصول كوشش آگراوال در دورانی بود كه بر روی رساله دكتری خود كار می‌كرد و به اتفاق استاد راهنمای خویش "سومنات بیسواس" در سال ۱۹۹۹مقاله- ای را به چاپ رساند كه در آن یك روش آزمون اعداد اول پیشنهاد شده بود كه از همین چند جمله‌ای‌ها استفاده می‌كرد و به شیوه احتمالاتی محاسبات را انجام می داد.
آگراوال بر این باور بود كه می‌تواند این روش پیشنهادی را دقیق‌تر و عنصر احتمالاتی آن را حذف كرد.
در سال ۲۰۰۱دو تن از دانشجویان او یعنی كایال و سكسنا به یك نكته بسیار حساس و فنی توجه كردند. ابتدا این مساله سبب شد تا گروه سه نفره در آبهای عمیق نظریه اعداد غوطه ور شوند، اما اندك اندك برایشان روشن شد كه تنها یك مانع در راه تكمیل روشی جهت آزمودن دقیق و سریع اعداد اول وجود دارد.
مانع از این قرار بود كه روش آنان تنها در صورتی كار می‌كرد كه عدد اول مورد نظر كه با pنمایش داده می‌شود همواره در محدوده خاصی جای داشته باشد كه با اعدادی كه در آزمون شركت داده می‌شوند مرتبط باشد.
مشخصه ویژه این مانع آن است كه عدد " "p-1باید یك مقسوم علیه یا بخشیاب بسیار بزرگ باشد.
گروه سه نفر ریاضی دانان هندی برای غلبه بر مشكل به هر دری زدند و با بررسی مقالات مختلف بالاخره دریافتند كه در سال ۱۹۸۵یك ریاضی‌دان فرانسوی به نام اتن فووری از دانشگاه پاریس ۱۱این نكته را به صورت ریاضی اثبات كرده است. به این ترتیب آخرین بخش معما حل شد و آلگوریتم پیشنهادی این سه نفر با موفقیت پا به عرصه گذارد.
اما این موفقیت "مشروط" بود. به این معنی كه این روش برای اعداد اولی كه انسان در حال حاضر می‌توان به سراغ آنها برود از كارآیی چندانی برخوردار نیست. در روایت اولیه روش پیشنهادی، زمان لازم برای محاسبات كه متناسب با ارقام عدد اول مورد نظر بود، با آهنگ ۱۰۱۲ازدیاد پیدا می كرد.
در روایتهای بهبود یافته اخیر این روش، سرعت ازدیاد زمان لازم برای محاسبات به ۱۰۷.۵كاهش یافته اما حتی در این حالت نیز این روش در مقایسه با روش آ پی آر تنها در هنگامی موثر تر خواهد بود كه تعداد ارقام عدد اولی كه قصد شكار و یافتن آن را داریم در حدود ۱۰۱۰۰۰باشد.
اعدادی تا این اندازه بزرگ در حافظه هیچ كامپیوتر جای نمی‌گیرند و حتی آن را نمی‌توان در كل كیهان جای داد.
اما حال كه ریاضی دانان توانسته‌اند یك طبقه خاص از آلگوریتمهای توانی را برای شناسایی اعداد اول مشخص كنند، این امكان پدید آمده كه به دنبال نمونه‌های بهتر این روش بگردند. پومرانس و هندریك لنسترا از دانشگاه كالیفرنیا در بركلی با تلاش در همین زمینه توانسته‌اند زمان لازم برای محاسبات را از توان ۷.۵به توان ۶كاهش دهند.
این دو از همان استراتژی كلی گروه هندی موسسه كانپور استفاده كردند اما تاكتیهای دیگری را به كار گرفتند.
اگر فرضیه‌های دیگری كه درباره اعداد اول مطرح شده درست از كار درآید آنگاه می‌توان زمان محاسبه را از توان ۶به توان ۳تقلیل داد كه در این حد این روش كارآیی عملی پیدا خواهد كرد.
در این حالت یافتن اعداد اول با ۱۰۰۰رقم یا بیشتر به بازی كودكان بدل خواهد شد.
اما در نظر ریاضی‌دانان مهمترین و جالبترین جنبه كار گروه سه نفره آ ك اس (كانپ.ر) روشی است كه آنان به كار گرفته‌اند.
اعداد اول برای ریاضیات از اهمیت بنیادین برخوردارند و هر نوع غفلت در فهم ویژگیهای آنها باعث می‌شود خللهای بزرگ در بنای ریاضیات پدیدار شود.
روش این سه ریاضی دان هندی هرچند این خللها و نقصها را پر نكرده حداقل به ریاضی دانان گفته است كه در كجا به دنبال این خللها بگردند.
آلگوریتم پیشنهادی این سه محقق و همه انواع بدیلی كه بر اساس آن ساخته شده متكی به وجود اعداد اولی با مشخصه های ویژه هستند. و در اغلب موارد استفاده از این روش مستلزم آن است كه ریاضی دانان اطلاعات دقیقی از نحوه توزیع این قبیل اعداد اول خاص در میان دیگر اعداد به دست آورند و به این ترتیب جغرافیای مكانی اعداد اول را مشخص سازند.
روش پیشنهادی آ ك اس به ریاضی دانان این نكته را آموخته كه ویژگیهای این جغرافیای مكانی حائز اهمیت است و نیز این كه هنوز دانش كافی در این زمینه به دست نیامده است.
در گذشته و در زمانی كه نظریه اعداد تنها مورد توجه یك گروه كوچك از ریاضی دانان بود ، این مساله چندان اهمیتی نداشت. اما در ۲۰سال گذشته اعداد اول موقعیتی استثنایی در عرصه رمز نگاری و دانش طراحی و شكستن رمزها كسب كرده اند.
رمزها صرفا از نظر نظامی و جاسوسی حائز اهمیت نیستند بلكه از آنها در عرصه های تجاری و نیز فعالییتهای اینترنتی در مقیاس وسیع استفاده به عمل می‌آید. هیچ كس نمی‌خواهد كه راهزنان اینترنتی به اطلاعات شخصی مربوط به حسابهای بانكی یا شماره كارتهای اعتباری آنان دست یابد.
هم اكنون دزدی مشخصات شناسنامه ای افراد و جعل هویت آنان به صورت یكی از بزرگترین قلمروهای فعالییتهای تبهكارانه در سطح بین‌المللی در آمده است.
سازندگان كامپیوترها و ارائه‌دهندگان خدمات اینترنتی با توجه به آنكه در حال حاضر افراد بسیاری از فعالیتهای خود را از طریق اینترنت انجام می دهند، نظیر اینكه پول قبضهای برق و آب و تلفن خود را می‌پردازند یا در كلاسهای مورد نظر ثبت نام می‌كنند، یا بلیت هواپیما و قطار رزرو می‌كنند، در تلاشند تا از خطر دستیابی تبهكاران به اطلاعات شخصی افراد جلوگیری به عمل اورند.
یكی از مهمترین سیستمهایی كه در این زمینه مورد استفاده صنایع است سیستم آر اس آ نام دارد كه متكی به اعداد اول است.
اعداد اول مورد استفاده در این سیستم در حدود ۱۰۰رقمی هستند. سیستم آر اس آ در بسیاری از سیستمهای كامپیوتری مورد استفاده قرار دارد و در پروتكل اصلی برای ارتباطات امن اینرتنتی نیز گنجانده شده است و بسیاری از دولتها، شركتهای بزرگ و دانشگاهها از آن استفاده می‌كنند. جواز استفاده از این سیستم برای بیش از ۷۰۰شركت صادر شده و بیش از نیم میلیون كپی از آن در سطح جهانی مورد استفاده قرار دارد.
برای شكستن رمز آر اس آ باید مضراب اعداد ۲۰۰رقمی یا بزرگتر را پیدا كنید. هرچند فاكتور گیری یا عامل مشترك گیری از اعداد سخت تر از آزمودن اول بودن آنهاست اما این دو مساله با یكدیگر ارتباط دارند و ریاضی دانان از یك ابزار برای حل هر دو مساله استفاده می‌كنند.
همه این جنبه‌ها بر اهمیت كشف هر روشی برای محاسبه اعداد اول می‌افزاید.
در سال ۱۹۹۵زمانی كه پیتر شور از آزمایشگاههای بل اثبات كرد كه مجموعه- ای از آلگوریتمهای توانی برای فاكتور گیری وجود دارد، لرزه بر اندام بسیاری افتاد.
اما خوشبختانه برای استفاده از این آلگوریتم به كامپیوترهای كوانتومی نیاز است كه هنوز در مرحله تكمیل تئوریك قرار دارند.
اكنون روش تازه آگراوال و دوستانش دوباره سیستم آر اس آ را در معرض خطر قرار داده است. آگراوال اكنون این نكته را نشان داده كه می‌توان با كامپیوتر های معمولی، اعداد را از حیث اول بودن مورد آزمایش قرار داد.
سوالی كه اینك مطرح شده آن است كه آیا الگوریتم مشابهی كه به صورت توانی كار كند برای فاكتورگیری اعداد غیراول نیز موجود است؟ پاسخ اغلب متخصصان به این پرسش منفی است اما متاسفانه این متخصصان همین حرف را در مورد آلگوریتم توانی مربوط به اعداد اول نیز می‌زدند
در حال حاضر ریاضی دانان واقعا مطمئن نیستند كه كه آیا چنین آلگوریتمی یافت می‌شود یا نه.
اگر پاسخ مثبت باشد انگاه سیستم آر اس آ دیگر از امنیت برخوردار نیست.
یك عامل تخفیف‌دهنده نگرانیها آن است كه از سیستم آر اس آ برای انتقال همه محتوای پیامها استفاده نمی‌شود بلكه صرفا "كلید های رمز" را كه اندازه شان كوچك است با این سیستم انتقال می‌دهند.
برای انتقال بقیه پیام از روشهای رمزنگاری متعارف بهره گرفته می‌شود. به این ترتیب جاسوسان در صدد برخواهند آمد كه به كلید رمزها دست یابند.
به این ترتیب درسی كه از موفقیت گروه سه نفره هندی گرفته می‌شود آن است كه باید با احتیاط در ارسال پیامها عمل كرد. اگر اكتشافات مشابه آنچه گروه كانپور بدست اورده تكرار شود، انگاه دیگر نمی‌توان به ایمن بودن ارتباطاتی كه روی اینترنت برقرار می‌شود اطمینان داشت.
ماخذ :
كد - لینک:
ایستنا | آخرین اخبار و تحلیل های حوزه فناوری اطلاعات و ارتباطات (http://www.ictna.ir)
:104:
گردآونده:طه-Borna66