قضیه کوچک فرما: اگر p عددی اول و b عدد دلخواهی باشد که p و b نسبت به هم اول باشند، آن گاه باقیمانده تقسیم بر p و باقیمانده تقسیم b بر p همیشه برابرند.

بنابراین برای اینکه بدانیم عددی مثل a اول است یا نه کافیست عدد دلخواهی مثل b که نسبت به a اول باشد انتخاب کنیم و باقیمانده تقسیم بر a را بیابیم اگر این باقیمانده برابر b نباشد عدد ما اول نیست.

تنها مشکلی که وجود دارد این است که از آنجا که عکس قضیه فرما لزوما درست نیست - یعنی ممکن است بعضی از اعداد مرکب هم این خاصیت را داشته باشند - اگر باقیمانده b باشد نمی توان در مورد اول بودن یا نبودن a اظهارنظری کرد. این مشکل هم ۳۰۰ سال بعد در تابستان ۲۰۰۲ بوسیله سه ریاضیدان هندی به نام‌های Agrawal، Kayal و Saxena حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقم اظهارنظر کنیم.

 



بعد از ۲۰۰۰ سال مساله آزمایش اول بودن اعداد پاسخ خوبی پیدا کرد اما مساله دوقلو یعنی یافتن عوامل اول همچنان مقاومت می کند و کسی نمی داند آیا این مساله راه حل ساده تری دارد یا نه؟

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