MENGIDENTIFIKASI BILANGAN PRIMA-SEMU (PESUDOPRIME) DALAM PENGUJIAN PRIMALITAS MENURUT TEOREMA KECIL FERMAT MENGGUNAKAN MATHEMATICA

Abstract

Primalitas is a test process to test whether an integer n is a prime number or a composite. Some test primalitas like Fermat's test, Miller-Rabin, and Lucas-Lehmer test for primalitas which is a probabilistic relative outcomes more accurately and quickly than deterministic tests, could give a false prime number/pseudo, known with a pseudoprime. For melaksanakanpengujian, the researchers formulate Fermat's Little Theorem then algorithm the algorithm coded in Mathematica (version 8.0). Application of algorithm of Fermat's Little Theorem and Euler's Theorem leads to the concept of prima pseudo (pseudoprime). By using the software Mathematica 8.0, found large number of primes ≤ 10,000 is 1229. Then by dividing n (psp) at 1229. the percentage of pseudo-prime on each base of gathered. On the primes ≤ 10,000, 2 ≤ a ≤ 20, base 8 generate the highest amount of pseudoprime, namely achieving 5.70%, while the number of lowest pseudoprime (1.22%) generated by the base 7. Though prima pseudo-not too much, but it's not quite rare to be ignored, given the prima-pseudo is one of Fermat's Little Theorem implications.

Abstrak

Uji primalitas adalah proses untuk menguji apakah bilangan bulat n merupakan bilangan prima atau komposit. Beberapa uji primalitas seperti tes Fermat, Miller-Rabin, dan Lucas-Lehmer yang merupakan uji primalitas probabilistik memberikan hasil yang relatif lebih tepat dan cepat daripada uji deterministik, berpeluang memberikan bilangan prima palsu/semu, dikenal dengan pseudoprime. Untuk melaksanakanpengujian, peneliti merumuskan algoritma Teorema Kecil Fermat lalu algoritma dikodekan dalam Mathematica (versi 8.0). Penerapan algoritma Teorema Little Fermat dan Teorema Euler tersebut mengarah pada konsep prima semu (pseudoprime). Dengan menggunakan perangkat lunak Mathematica 8.0, ditemukan banyaknya bilangan prima ≤10.000 adalah 1229. Kemudian dengan membagi n (psp) pada 1229, persentase pseudo-prime pada setiap basis dikumpulkan. Pada bilangan prima ≤10.000, 2≤a≤20, basis 8 menghasilkan jumlah pseudoprime tertinggi, yaitu mencapai 5,70%, sedangkan jumlah pseudoprime terendah (1,22%) dihasilkan oleh basis 7. Meski prima-semu tidak terlalu banyak, tapi tidak cukup langka untuk diabaikan, mengingat prima-semu merupakan salah satu implikasi Teorema Kecil Fermat.

Kata kunci: Uji primalitas, Fermat, Pseudoprime, Mathematica, Bilangan Prima