ماشین‌حساب آزمون اول بودن میلر-رابین

درباره این ابزار

آزمون میلر-رابین اول بودن را چنین بررسی می‌کند: n − 1 را به‌صورت 2ˢ·d با d فرد می‌نویسد و سپس می‌سنجد که آیا پایهٔ شاهد a در aᵈ ≡ 1 (mod n) یا در a^(2ʳ·d) ≡ −1 (mod n) برای یک r < s صدق می‌کند. یک شاهد به‌تنهایی فقط نتیجه‌ای احتمالاتی می‌دهد، اما آزمودن با مجموعه‌ای کوچک و اثبات‌شده از پایه‌های شاهد ثابت (مثلاً 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) آزمون را برای هر عدد صحیح کوچک‌تر از حدود ۳٫۱۸ × 10²³ قطعی می‌کند — بسیار بیشتر از آنچه بیشتر کاربردها نیاز دارند.

رمزنگاران و توسعه‌دهندگان نرم‌افزار دقیقاً از همین نوع آزمون هنگام تولید نامزدهای اول بزرگ برای کلیدهای RSA یا دیفی-هلمن استفاده می‌کنند، و دانشجویان علوم کامپیوتر با آن روی اعداد واقعی می‌بینند که چرا میلر-رابین برای بررسی اول بودن یک عدد صحیح بزرگ بسیار بهتر از تقسیم آزمایشی مقیاس‌پذیر است.