در سال ۱۹۸۳روشي كشف شد كه بسيار نزديك به روشهاي تواني بود. اين روش كه به وسيله سه رياضي دان به نامهاي لئونارد آدلمن از دانشگاه كاليفرنياي جنوبي، كارل پومرانس از آزمايشگاهاي بل در موري هيل نيو جرسي، و رابرت روملي از دانشگاه جورجيا كشف شد به نام خود آنان به روش آپي آر 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بايد يك مقسوم عليه يا بخشياب بسيار بزرگ باشد.
ادامه دارد...