METODE SOLOVAY-STRASSEN UNTUK PENGUJIAN BILANGAN PRIMA

Abstract

Bilangan prima merupakan bilangan bulat positif yang lebih besar dari satu dan hanya habis dibagi oleh satu dan dirinya sendiri, sedangkan bilangan bulat positif selain prima disebut bilangan komposit atau bilangan yang terdiri dari minimal dua faktor prima. Untuk mencari faktor prima dapat menggunakan uji probabilistik. Uji probabilistik merupakan uji yang menggunakan konsep acak. Salah satu uji probabilistik yaitu metode Solovay-Strassen. Pengujian pada metode Solovay-Strassen diuji berdasarkan Euler pseudoprima. Langkah pertama pengujian bilangan prima pada metode Solovay-Strassen yaitu menentukan bilangan yang diuji yaitu n, n yang dimaksud adalah bilangan bulat positif ganjil. Kemudian menentukan basis b yang dipilih secara acak, basis b yang dimaksud adalah sebarang bilangan bulat positif yang berada pada interval 0<b<n. Kemudian dilanjutkan dengan mencari d=gcd(b,n) dengan menggunakan algoritma Euclid. Jika didapat bahwa d>1, maka n dikatakan komposit. Namun jika didapat bahwa d=1, maka n diuji dengan menggunakan Euler pseudoprima. Jika n lulus uji Euler pseudoprima untuk basis b, maka n disebut Euler pseudoprima untuk basis b. Dengan demikian n dapat dikatakan bilangan prima. Jika n tidak lulus uji persamaan Euler pseudoprima, maka n disebut sebagai komposit.
Kata Kunci : Solovay-Strassen, Simbol Jacobi, Simbol Legendre.