Analisis Komparatif Performa dan Robustness Algoritma Probabilistik (Fermat, Miller–Rabin, dan Baillie–PSW) terhadap Bilangan Acak dan Carmichael dalam Konteks Kriptografi

Bilangan prima, Miller-Rabin, kriptografi, algoritma probabilistik

Abstract

Pembangkitan bilangan prima besar merupakan komponen penting dalam keamanan skema kriptografi kunci publik, karena validitas bilangan prima berpengaruh langsung terhadap keandalan sistem. Penelitian ini bertujuan membandingkan performa dan ketahanan tiga algoritma uji keprimaan, yaitu Fermat, Miller–Rabin, dan Baillie–PSW (BPSW). Evaluasi dilakukan melalui eksperimen komputasi dengan dua skenario input, yaitu bilangan acak sebagai representasi kondisi umum dan bilangan Carmichael sebagai representasi input adversarial, dengan variasi panjang bit hingga 2048-bit. Hasil eksperimen menunjukkan bahwa algoritma Fermat menghasilkan false positive pada input tertentu, sehingga kurang sesuai untuk kebutuhan kriptografi yang menuntut akurasi tinggi. Miller–Rabin menunjukkan reliabilitas yang baik, tetapi cenderung memiliki waktu eksekusi dan variasi kinerja yang lebih besar pada beberapa skenario pengujian. Sementara itu, BPSW menunjukkan keseimbangan yang lebih baik antara akurasi, efisiensi waktu, dan stabilitas kinerja pada ruang uji yang digunakan. Dengan demikian, BPSW dapat dipertimbangkan sebagai salah satu pendekatan penapisan prima yang efektif untuk mendukung implementasi kriptografi berbasis bilangan prima besar.