Util Monster
Gratis
Uji Keprimaan · Faktorisasi · Pembuatan Bilangan Prima
Bilangan prima adalah bilangan asli lebih besar dari 1 yang tidak memiliki pembagi positif selain 1 dan dirinya sendiri. Contoh: 2, 3, 5, 7, 11, 13... Semua bilangan prima kecuali 2 adalah ganjil. Bilangan prima adalah "atom dari angka."
Algoritma kuno yang dikembangkan oleh matematikawan Yunani Eratosthenes sekitar 240 SM. Algoritma ini secara efisien menemukan semua bilangan prima hingga n dengan menandai kelipatan dari setiap bilangan prima secara berulang sebagai komposit.
Bilangan prima kembar adalah pasangan bilangan prima yang selisihnya 2: (3,5), (5,7), (11,13), (17,19)... Apakah ada tak terhingga banyaknya bilangan prima kembar masih menjadi masalah yang belum terpecahkan.
• Enkripsi RSA: Keamanan berbasis pada sulitnya memfaktorkan bilangan besar • Fungsi hash: Tabel hash berukuran prima mengurangi tabrakan • Pembuatan bilangan acak: Bilangan prima dalam algoritma PRNG • Alam: Siklus hidup jangkrik menggunakan bilangan prima
Bilangan prima adalah bilangan asli lebih besar dari 1 yang tidak memiliki pembagi selain 1 dan dirinya sendiri. Bilangan prima terkecil adalah 2, satu-satunya bilangan prima genap. Urutan: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Matematikawan Yunani kuno Euclid membuktikan sekitar 300 SM bahwa bilangan prima jumlahnya tak terhingga. Bilangan prima disebut "atom dari angka" karena setiap bilangan bulat > 1 dapat difaktorkan secara unik menjadi bilangan prima (Teorema Dasar Aritmetika). Contoh: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
Metode paling sederhana menguji keterbagian dengan semua angka dari 2 hingga n-1, tetapi ini tidak efisien. Peningkatannya adalah hanya menguji 2 hingga √n, karena jika n = a × b, maka a ≤ √n atau b ≤ √n. Untuk 101: √101 ≈ 10.05, jadi cukup uji 2, 3, 5, 7. Uji probabilistik Miller-Rabin menangani bilangan sangat besar secara efisien. AKS (2002) adalah algoritma deterministik waktu-polynomial pertama. Kriptografi modern menggunakan ratusan digit, sehingga membutuhkan pengujian yang efisien.
Dikembangkan oleh matematikawan Yunani Eratosthenes sekitar 240 SM. Proses: ① Daftarkan angka 2 sampai n. ② Tandai 2 sebagai bilangan prima, hapus kelipatannya (4,6,8,10...). ③ Angka tak bertanda berikutnya 3 adalah prima, hapus kelipatannya. ④ Lanjutkan dengan 5, 7, dan seterusnya hingga √n. ⑤ Angka yang tersisa adalah bilangan prima. Untuk n=30: bilangan prima adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Kompleksitas waktu: O(n log log n). Dapat menemukan semua bilangan prima di bawah 1 juta dalam hitungan detik.
Faktorisasi bilangan prima menyatakan sebuah bilangan sebagai hasil kali bilangan prima. Menurut Teorema Dasar, setiap bilangan bulat > 1 memiliki faktorisasi yang unik. Metode: ① Mulai dengan bilangan prima terkecil 2. ② Bagi berulang kali dengan 2 hingga tidak bisa lagi dibagi. ③ Coba bilangan prima berikutnya 3, 5, 7... ④ Lanjutkan sampai hasil bagi menjadi 1. Contoh 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Hasil: 360 = 2³×3²×5. Penerapan: perhitungan FPB/KPK, penyederhanaan pecahan, keamanan RSA.
Bilangan prima kembar berbeda 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Dugaan Bilangan Prima Kembar menyatakan bahwa jumlahnya tak terhingga tetapi masih belum terbukti. Pada 2013, Yitang Zhang membuktikan bahwa ada tak terhingga banyaknya pasangan bilangan prima yang berbeda ≤70 juta, lalu diturunkan menjadi 246. Dugaan Goldbach (1742): setiap bilangan genap > 2 adalah jumlah dari dua bilangan prima. Contoh: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Telah diverifikasi hingga 4×10¹⁸ tetapi masih belum terbukti.
Enkripsi RSA, inti keamanan internet, bergantung pada perkalian yang mudah tetapi faktorisasi bilangan prima besar yang sulit. Pembuatan kunci: ① Pilih bilangan prima besar p, q (masing-masing 1024+ bit). ② Hitung n = p×q (publik). ③ Hitung φ(n) = (p-1)(q-1). ④ Pilih eksponen publik e yang koprima terhadap φ(n) (biasanya 65537). ⑤ Hitung eksponen privat d sehingga e×d ≡ 1 (mod φ(n)). Kunci publik: (n,e), kunci privat: (n,d). Enkripsi: C = M^e mod n, Dekripsi: M = C^d mod n. Memfaktorkan n untuk menemukan p,q akan merusak enkripsi, tetapi memfaktorkan bilangan ratusan digit membutuhkan jutaan tahun. Penerapan lain: ukuran tabel hash prima mengurangi tabrakan, siklus 13/17 tahun jangkrik menghindari tumpang tindih dengan predator, ritme prima dalam musik.