UJI PRIMALITAS Sangadji*
ABSTRAK UJI PRIMALITAS . Makalah ini membahas dan membuktikan tiga teorema untuk testing primalitas, yaitu teorema Lucas, teorema Lucas yang disempurnakan dan teorema Pocklington. Di samping itu, makalah ini juga membahas satu contoh aplikasi untuk disesuaikan oleh tiga teorema tersebut, sehingga dapat menunjukkan efisiensi relatif dari ketiga teorema.
ABSTRACT PRIMALITY TESTING. This paper discusses and proves three theorems for primality testing, i.e. Lucas’ theorem, improved Lucas’ theorem, and Pocklington’s theorem. Besides, this paper also discusses one example to be solved by the tree theorems, and thereby showing the relative efficiencies of the three theorems.
PENDAHULUAN Bilangan bulat positif n > 1 disebut komposit bila terdapat faktorisasi n = ab dengan a dan b bilangan bulat positif dengan a < n & b < n. Bila tidak demikian bilangan n tersebut disebut prima. Sesuai dengan namanya, bilangan-bilangan prima berperan sangat penting dan fundamental dalam Teori Bilangan. Perlu diketahui bahwa terdapat tak berhingga banyak bilangan-bilangan prima. Bukti dari pernyataan atau teorema ini dapat diperoleh dalam buku-buku teks Teori Bilangan. Dalam Teorema Fundamental Aritmetik a dinyatakan bahwa setiap bilangan alam yang lebih besar dari 1 adalah produk dari bilangan-bilangan prima dengan penyajian atau penulisan yang tunggal, terlepas dari urutan faktor-faktornya. Di sini kita tidak membuktikan Teorema Fundamental Aritmetika tersebut. Bukti dari teorema ini juga dapat diperoleh dalam buku-buku teks Teori Bilangan. Uji primalitas adalah suatu ujian untuk menentukan apakah sebarang bilangan alam yang lebih besar dari satu yang diberikan adalah bilangan prima atau bukan. Uji primalitas adalah salah satu masalah yang sangat penting dalam konsep bilangan. *
Pusat Pengembangan Teknologi Informasi dan Komputasi - BATAN
Metode klasik yang cukup dikenal adalah Eratosthenes yang dikenal dengan nama Sieve of Eratosthenes. Metode tersebut berdasar pada ujian apakah ada bilangan bulat mulai 2 sampai dengan [ n ] yang merupakan faktor dari n, di mana [ n ] adalah bilangan bulat terbesar yang lebih kecil atau sama dengan n . Bila bilangan tersebut dapat ditemukan, maka n adalah bilangan komposit atau bukan prima. Bila tidak demikian maka bilangan tersebut adalah bilangan prima. Kelemahan dari metoda tersebut adalah bahwa, meskipun dilakukan oleh komputer yang canggih, metode tersebut tidak praktis dan banyak memerlukan waktu. Bukti dari metode Eratosthenes dapat diperoleh dalam sebagian besar buku-buku teks tentang Teori Bilangan. Dalam makalah ini dibahas tiga teorema untuk uji primalitas, yaitu teorema Lucas, teorema Lucas yang disempurnakan dan teorema Pocklington. Sebagai pelengkap dibahas juga satu contoh aplikasi dari tiga teorema tersebut.
UJI PRIMALITAS Sebelum kita membahas dan membuktikan tiga teorema di muka, terlebih dulu kita perkenalkan beberapa definisi dan terminologi yang diperlukan. Bilangan bulat x congruent dengan bilangan bula t y modulo n dengan n bilangan bulat positif, ditulis x ≡ y (mod n) , bila x-y pembagi dari n, ditulis
x − y | n. Bila bilangan-bilangan bulat x dan y yang keduanya bukan bilangan nol mempunyai sifat bahwa gcd( x, y ) = 1 , maka x dan y disebut prima relatif. Untuk setiap bilangan bulat positif n, fungsi ϕ(n ) menyatakan banyaknya bilangan alam yang lebih kecil atau sama dengan n yang prima relatif terhadap n. Fungsiϕ(n ) ini disebut fungsi phi Euler. Jelas bahwa untuk bilangan prima p, maka
ϕ( p ) = p − 1. Misalkan n bilangan bulat dengan n > 1 . Misalkan juga bilangan bulat a dan n keduanya prima relatif. Yang dimaksud dengan order dari a modulo n adalah bilangan alam terkecil k sedemikian sehingga a k ≡ 1(mod n ). Di bawah ini berturut-turut dibahas dan dibuktikan tiga teorema, yaitu teorema Lucas, teorema Lucas yang disempurnakan dan teorema Pocklington.
TEOREMA 1 (LUCAS) Bila terdapat bilangan bulat a sedemikian sehingga a n −1 ≡ 1 (mod n) dan
a ( n −1) / p ≠ 1 (mod n) untuk semua bilangan prima p yang membagi n − 1, maka n adalah bilangan prima.
BUKTI Misalkan a punya order k modulo n. Berdasarkan Teorema 8.1 pada Daftar Pustaka 1, kondisi a n −1 ≡ 1 (mod n) menghasilkan k | n − 1 . Sehingga terdapat bilangan bulat j sedemikian sehingga n − 1 = k j . Bila j > 1 maka j akan mempunyai pembagi prima q. Jadi terdapat bilangan bulat h yang memenuhi j = q h. Sebagai hasil diperoleh
( )
a ( n −1) / q = a k
≡ 1h = 1(mod n) yang kontradiksi dengan hipotesis di atas. Jadi diperoleh j = 1 karena j adalah bilangan bulat positif. Mengingat order dari a tidak melampaui ϕ(n ), maka n − 1 = k ≤ ϕ(n ) ≤ n − 1 yang berakibat ϕ( n) = n − 1. Dari hasil terakhir ini dapat disimpulkan bahwa n − 1 adalah bilangan prima. h
TEOREMA 2 (PENYEMPURNAAN DARI TEOREMA 1) Bila untuk setiap bilangan prima p i yang membagi n − 1 terdapat bilangan bulat a i sedemikian sehingga a in −1 ≡ 1 (mod n) tetapi a adalah bilangan prima.
( n −1) / pi
≠ 1 (mod n), maka n
BUKTI Misalkan bahwa n − 1 = p1k1 p 2k2 L prk r , di mana para p i adalah bilanganbilangan prima yang berlainan. Misalkan juga hi adalah order dari a i modulo n.
Menggunakan fakta bahwa hi | n − 1 dan diperoleh hasil bahwa p
ki i
hi tidak membagi
( n − 1) / p i dapat
| hi . Sehingga untuk setiap i diperoleh hi | ϕ( n) dan
didapat p iki | ϕ( n). Jadi n − 1 | ϕ( n) dengan n bilangan prima.
TEOREMA 3 (POCKLINGTON)
m = p1k1 p 2k2 L psk s , m ≥ n dan gcd( m, j ) = 1. Bila untuk setiap bilangan prima p i ,1 ≤ i ≤ s terdapat bilangan bulat Misalkan
n − 1 = mj,
di
mana
a i dengan a in −1 ≡ 1 (mod n) dan gcd( ai( n −1 ) / p i − 1, n) = 1, maka n adalah bilangan prima. BUKTI Misalkan p sebarang pembagi prima dari n. Misalkan juga hi adalah order dari
ai modulo p. Maka diperoleh hi | p − 1. Mengingat bahwa a in −1 ≡ 1(mod p ) diperoleh
(
)
juga hi | n − 1. Dari hipotesis gcd ai( n −1) / pi − 1, n = 1 yang berakibat bahwa
a
( n −1) / p i i
≠ 1(mod p ), menghasilkan fakta bahwa tidaklah benar hi | ( n − 1) / p i . Jadi
dapat disimpulkan bahwa p ik i | hi sehingga diperoleh p ik i | p − 1. Karena ini berlaku untuk setiap i maka m | p − 1. Mengingat bahwa setiap pembagi prima dari n harus lebih besar dari m ≥ n maka timbul suatu kontradiksi, sehingga n adalah bilangan prima.
CONTOH PENGGUNAAN Di bawah ini diberikan contoh penggunaan dari uji primalitas, berturut-turut sebagai aplikasi dari Teorema 1, Teorema 2 dan Teorema 3 di atas. Contoh 1 Menggunakan uji primalitas dari Teorema 1, akan diselidiki apakah 997 prima atau komposit.
Solusi Dengan
7
996
mengambil
n = 997
dan
basis
a = 7, maka
didapat
≡ 1(mod 997). Karena n − 1 = 996 = 2 ⋅ 3 ⋅ 83, kita lakukan komputasi berikut 2
7 996 / 2 = 7 498 ≡ −1 (mod 997), 7 996 / 3 = 7 332 ≡ 304 (mod 997), 7 996 / 83 = 712 ≡ 9 (mod 997 ). Menggunakan Teorema 1 di atas, dapat disimpulkan bahwa 997 adalah bilangan prima. Contoh 2 Untuk membandingkan dua uji primalitas dari dua teorema di atas, akan diselidiki juga apakah 997 prima atau komposit menggunakan Teorema 2.
Solusi Ambil n = 997. Mengingat pembagi-pembagi prima dari n − 1 = 996 adalah 2, 3 dan 83, maka dengan basis-basis 3, 5 dan 7 diperoleh
3996 / 83 = 312 ≡ 40 (mod 997), 3996 / 2 = 5 498 ≡ −1 (mod 997), 7 996 / 3 = 7 332 ≡ 304 (mod 997). Menggunakan Teorema 2 di atas, juga dapat disimpulkan bahwa 997 adalah bilangan prima.
Contoh 3 Menggunakan uji primalitas dari Teorema 3, akan diselidiki juga apakah 997 prima atau komposit. Solusi Mengingat
n − 1 = 996 = 12 ⋅ 83, di mana 83 > 997, maka diperlukan
pemilihan basis yang sesuai untuk 83, misalkan 2. Mengingat 2 996 ≡ 1(mod 997) dan
gcd( 2 996 / 83 − 1, 997) = gcd( 4095, 997 ) = 1, dengan Teorema 3 di atas dapat disimpulkan bahwa 997 juga prima.
KESIMPULAN Dari tiga uji primalitas di atas yang dinyatakan oleh Teorema 1, Teorema 2 dan Teorema 3, maka dapat disimpulkan bahwa ketiganya lebih baik dari metode Sieve of Eratosthenes. Uji primalitas dari Teorema 2 lebih baik dari uji primalitas dari Teorema 1, sedangkan uji primalitas dari Teorema 3 lebih baik dari dua uji primalitas dari dua teorema sebelumnya.
DAFTAR PUSTAKA 1. BURTON, DAVID M., Elementary Number Theory, Fifth Edition, McGraw-Hill Higher Education, McGraw-Hill Company, New York (2002) 2. FLATH, DANIEL E., Introduction to Number Theory, John Wiley & Sons Inc., New York (1989) 3. NIVEN, I., ZUCKERMAN, H., and MONTGOMERY, H., An Introduction to the Theory of Numbers, Fifth Edition, John Wiley & Sons Inc., New York (1991)
HOME
KOMPUTASI DALAM SAINS DAN TEKNOLOGI NUKLIR XIII
