در سال ‪ ۱۹۸۳‬روشي كشف شد كه بسيار نزديك به روشهاي تواني بود. اين روش كه به وسيله سه رياضي دان به نامهاي لئونارد آدلمن از دانشگاه كاليفرنياي جنوبي، كارل پومرانس از آزمايشگاهاي بل در موري هيل نيو جرسي، و رابرت روملي از دانشگاه جورجيا كشف شد به نام خود آنان به روش آپي آر ‪ 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.irna.ir/fa/news/view/menu-279/8405190499170629.htm

ماشين رياضي جديدي براي رام كردن اعداد اول (‪(۱

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

طي قرنهاي متمادي رياضي دانان در شرق و غرب عالم به جستجوي راههايي براي دستيابي به اعداد اول برخاسته‌اند و با اين همه بهترين روشهايي كه تا بحال در اين زمينه ابداع شده چنان كند است كه حتي پر سرعت‌ترين كامپيوتر هاي كنوني نيز نمي‌توانند كمك چنداني در شكار اين اعداد شگفت انگيز كنند.

اعداد اول بر طبق تعريف اعدادي هستند كه تنها به ‪ ۱‬و بر خودشان تقسيم پذيرند. به عنوان نمونه اعداد ‪ ۲،۳،۵،۷،۱۱،۱۳،۱۷،۱۹‬اعداد اول كمتر از ‪۲۰‬ در سلسله اعداد طبيعي هستند. اما هرچه در اين سلسله پيش تر برويم اعداد اول ناياب تر مي‌شوند.

بطوريكه اگر چندين ميليون بار به سرعت كامپيوتر هاي كنوني افزوده شود، تنها چند رقم به شماره ارقام بزرگترين عدد اولي كه تا به حال شناخته شده افزوده مي‌گردد.

رياضي دانان در آرزوي دست يافته به روشي هستند كه با استفاده از آن بتوانند با سرعت به يافتن اعداد اول توفيق يابند و يا اگر با عددي هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند كه آيا عدد اول است ؟ - اما يافتن چنين روشي به فسفر مغز نياز دارد و نه سرعت كامپيوتر. -
اما يك گروه از رياضي دانان هندي مدعي شده‌اند كه در آستانه دستيابي به همان آزموني هستند كه رياضي دانان قرنها مشتاقانه در آرزويش بوده اند.

مانيندرا اگراوال ‪ ,Manindra Agrawal‬و دانشجويانش نيراج كايال ‪Neeraj‬ ‪ Kayal‬و نيتين سكسنا ‪ Nitin Saxena‬در موسسه تكنولوژي كانپور مدعي شده‌اند كه در آستانه تكميل آزموني هستند كه اول بودن يا نبودن هر عدد طبيعي را با سرعت مشخص مي‌كند. اين آزمون در صورتي كه تكميل شود مي‌تواند تبعات و نتايج بسيار گسترده‌اي براي جهان كنوني به بار آورد.

درحال حاضر بسياري از معاملات تجاري و نقل و انتقالات مالي و نيز مبادله اطلاعات محرمانه از طريق شبكه هاي مخابراتي مانند اينترنت و با بهره گيري از رمز كردن پيامها به انجام مي‌رسد.

اعداد اول در تنظيم اين قبيل رمزها نقشي اساسي بر عهده دارند و از همين رو دستيابي به اعداد اول جديد كه ديگران از آن بي‌خبر باشند براي سازندگان اين رمزها و نيز مشتريان آنان از اهميت زياد برخوردار است.

اما اگر روش اين محققان هندي تكميل شود در آن صورت امنيت اين قبيل نقل و انتقالات در معرض خطر جدي قرار خواهد گرفت.

سابقه قرار گرفتن رياضي دانان تحت جاذبه اعداد اول به قرنها پيش باز مي گردد. در سال ‪ ۱۸۰۱‬كارل گائوس از بزرگترين رياضي دانان اعلام كرد كه مساله تشخيص اعداد اول از اعداد غير اول يكي از مهمترين مسائل حساب به شمار مي‌آيد.

اعداد اول به يك معنا همان نقشي را در سلسله اعداد بازي مي‌كنند كه اتمها در ساختار بناي كيهان دارند- اين اعداد سنگ بناي ناپيداي ديگر اعداد محسوب مي‌شوند.

يكي از عادي‌ترين راههاي شناسايي اعداد اول تقسيم آن به ديگر اعداد است.

از طرف ديگر با اندكي تامل روشن مي‌شود كه اعداد زوج عدد اول نيستند زيرا همگي بر ‪ ۲‬قابل قسمتند.

اعدادي كه بتوان جذر آنها را به دست آورد نيز اول نيستند. اما اين روشها براي شناسايي اعداد اول بزرگ به كلي بي‌فايده‌اند. به عنوان مثال اگر عدد اولي داراي ‪ ۱۰۰‬رقم باشد در آن صورت كل عمر باقيمانده از كيهان بر اساس نظريه هاي جديد كيهانشناسي نيز براي مشخص كردن اول بودن يا نبودن اين عدد با اين شيوه هاي متعارف كفايت نمي‌كند.

بنابراين رياضي دانان به سراغ روشهاي ديگر رفته‌اند. مهمترين سوال در مورد همه اين روشها آن است كه با چه سرعتي مي‌توانند يك عدد اول را مشخص كنند و با ازدياد ارقام عدد اول زمان لازم براي محاسبه چه اندازه طولاني تر مي شود. اگر به عنوان مثال زمان محاسبه به توان ثابتي از شمار ارقام عدد ازدياد يابد در آن صورت اين روش روش قابل قبولي به شمار آورده مي‌شود .

به اين نوع روشها كه زمان به صورت تواني در آنها افزوده مي‌شود "روشهاي تواني" مي‌گويند. روشهاي ديگر كه زمان در آنها با سرعت بيشتري افزايش مي‌يابد روشهاي غيرتواني نام دارند.

به عنوان مثال روش تقسيم معمولي يك روش غيرتواني براي يافتن اعداد اول است. در اين روش زمان لازم براي تعيين اول بودن يك عدد با ‪ d‬رقم، برابر با ‪ /۱۰d/2‬اين نوع روشها بسيار نامناسبند.

در سال ‪ ۱۹۵۶‬منطق‌دان برجسته آلماني كورت گودل اين پرسش را مطرح ساخت كه آيا مي‌توان اين نوع روشهاي تقسيم را بهبود بخشيد. تلاش خود او نهايتا به كشف شماري از روشهاي عملي براي يافتن اعدادي به بزرگي ‪ ۱۰۰‬رقم يا بيشتر منجر شد. همه اين روشها احتمالاتي هستند و بنابراين در مواردي پاسخ غلط به دست مي‌دهند هرچند كه اين موارد بسيار نادرند.

ادامه دارد...

منبع:

http://www.irna.ir/fa/news/view/menu-279/8405194318165146.htm