Bilangan prima adalah unsur penyusun bilangan bulat: setiap bilangan bulat di atas 1 adalah bilangan prima atau hasil kali unik bilangan prima. Kalkulator ini menguji primalitas, memfaktorkan bilangan, dan mencantumkan bilangan prima dalam suatu rentang — dan ia melakukannya bahkan untuk bilangan yang terlalu besar untuk spreadsheet, menggunakan uji Miller-Rabin yang sama yang mendasari kriptografi modern.
Apa yang membuat suatu bilangan menjadi prima
Bilangan prima mempunyai tepat dua pembagi positif: 1 dan dirinya sendiri. Definisi tersebut mengesampingkan 1 (yang hanya memiliki satu pembagi) dan 0 (yang habis dibagi semua), sehingga bilangan prima terkecil adalah 2 — dan merupakan satu-satunya bilangan prima genap, karena setiap bilangan genap lainnya habis dibagi 2.
Untuk memeriksa suatu bilangan dengan tangan, Anda hanya perlu menguji pembagi hingga akar kuadratnya. Jika tidak ada bilangan bulat dari 2 sampai √n yang membagi n, maka n bilangan prima. Itu sebabnya 97 hanya membutuhkan empat divisi percobaan (2, 3, 5, 7) daripada sembilan puluh lima.
Faktorisasi dan saringan
Teorema dasar aritmatika menjamin bahwa setiap bilangan bulat di atas 1 difaktorkan menjadi bilangan prima dengan tepat satu cara. Faktorisasi prima menggerakkan segalanya mulai dari mereduksi pecahan hingga menemukan kelipatan persekutuan terkecil. Alat ini menggunakan pembagian percobaan untuk mengupas faktor prima terkecil secara berulang-ulang hingga hanya tersisa 1.
Untuk mencari semua bilangan prima dalam suatu rentang, metode klasik tercepat adalah saringan Eratosthenes: sebutkan bilangan-bilangannya, lalu coret kelipatan 2, lalu 3, lalu 5, dan seterusnya. Apapun yang bertahan adalah yang utama. Saringan tersegmentasi menerapkan ide yang sama hanya pada jendela yang Anda minta, sehingga membuatnya tetap cepat bahkan pada jutaan angka.
Angka besar dan kriptografi
Percobaan pembagian tidak ada harapan lagi jika angkanya menjadi besar — menguji angka 60 digit akan memakan waktu lebih lama daripada usia alam semesta. Sebaliknya, kalkulator ini beralih ke uji Miller-Rabin, yang menggunakan eksponensial modular untuk menentukan primalitas dalam sepersekian detik. Dengan kumpulan basis saksi yang tetap, pengujian ini terbukti tepat untuk setiap angka di bawah 3,3 × 10²⁴.
Hal ini penting karena bilangan prima yang besar adalah dasar dari kriptografi kunci publik. Enkripsi RSA mengalikan dua bilangan prima yang sangat besar untuk membentuk kunci publik; keamanannya terletak pada fakta bahwa mengembalikan produk ke bilangan prima sangatlah sulit, meskipun menguji kandidat untuk primalitas itu mudah. Asimetri antara pengujian primalitas cepat dan pemfaktoran lambat adalah hal yang membuat lalu lintas terenkripsi tetap aman.