Algoritme RSA

Faktorisasi bilangan bulat besar masih open problem sampai saat ini. Belum ditemukan algoritme yang mangkus untuk mencari faktor bilangan bulat besar untuk komputer klasik. Dari masalah ini lahir algoritme RSA.

Lanjutkan membaca “Algoritme RSA”

Iklan

Metode Pollard p-1

Selain diturunkan untuk menguji bilangan prima (lihat: Uji Bilangan Prima Miller-Rabin), teorema kecil Fermat juga dapat diturunkan untuk mencari faktor bilangan bulat. Algoritme yang diturunkan dari teorema kecil Fermat untuk mencari faktor bilangan bulat salah satunya metode Pollard p – 1. Algoritme ini ditemukan oleh J. M. Pollard pada tahun 1974.

Lanjutkan membaca “Metode Pollard p-1”

Uji Bilangan Prima Miller-Rabin

Meskipun cukup akurat untuk menguji bilangan prima, ada bilangan komposit yang lulus jika diuji dengan teorema kecil Fermat. Bilangan ini disebut bilangan Carmichael. Salah satu contoh bilangan Carmichael adalah 561. Faktornya 3x11x17.

Agar diperoleh hasil yang lebih akurat, dapat digunakan uji bilangan prima Miller-Rabin. Uji bilangan prima Miller-Rabin merupakan algoritme uji bilangan komposit prima Monte Carlo (probabilistik).

Lanjutkan membaca “Uji Bilangan Prima Miller-Rabin”