ALGORITMA UJI KOMPOSIT BERDASARKAN TEOREMA KONGRUENSI FERMAT DAN TEOREMA STRONG PSEUDOPRIME
Oleh: BANGUN JATI KUSUMO G54101045
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
1
ALGORITMA UJI KOMPOSIT BERDASARKAN TEOREMA KONGRUENSI FERMAT DAN TEOREMA STRONG PSEUDOPRIME
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : BANGUN JATI KUSUMO G54101045
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
2
RINGKASAN BANGUN JATI KUSUMO. Algoritma Uji Komposit Berdasarkan Teorema Kongruensi Fermat dan Teorema Strong Pseudoprime. Dibimbing oleh SUGI GURITMAN dan SISWANDI. Dalam menentukan apakah suatu bilangan bulat positif ganjil m merupakan bilangan komposit atau bukan, diperlukan suatu uji. Uji tersebut dinamakan uji komposit. Uji Komposit I adalah uji yang didasarkan pada Teorema Kongruensi Fermat. Input dari uji ini adalah bilangan bulat m dan a sebagai basis. Jika uji berhasil maka m dapat dikatakan sebagai bilangan komposit. Jika tidak, maka m dikatakan bilangan diduga prima berbasis a, dimana a adalah anggota dari himpunan bilangan-bilangan bulat modulo m yang relatif prima dengan m. Uji Komposit II adalah uji yang didasarkan pada Teorema Strong Pseudoprime. Input dari uji ini adalah bilangan yang tidak dapat ditentukan kekompositannya menggunakan Uji Komposit II, yaitu bilangan diduga prima berbasis a. Jika uji berhasil maka m merupakan bilangan komposit dan disebut bilangan prima semu berbasis a. Jika tidak, maka m dikatakan bilangan diduga kuat prima berbasis a. Uji Carmichael adalah uji untuk menentukan apakah suatu bilangan merupakan bilangan Carmichael atau bukan. Input dari uji ini adalah m bilangan prima semu berbasis a. Jika uji berhasil maka bilangan tersebut merupakan bilangan Carmichael. Jika tidak, maka bilangan tersebut merupakan bilangan prima semu berbasis a. Uji komposit III adalah Uji Diduga Kuat Prima dengan basis a yang telah ditentukan, yaitu: 2, 3, 5, dan 7. Input dari Uji ini adalah bilangan diduga kuat prima berbasis a. Jika uji berhasil maka m dapat dikatakan sebagai bilangan komposit. Jika tidak, maka m disebut bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 yang merupakan hasil akhir dari tulisan ini. Bilangan komposit dan diduga kuat prima berbasis a disebut bilangan prima semu kuat berbasis a. Jadi bilangan komposit dari Uji Komposit III merupakan bilangan prima semu kuat berbasis a.
3
Judul Nama NRP
: Algoritma Uji Komposit Berdasarkan Teorema Kongruensi Fermat dan Teorema Strong Pseudoprime. : Bangun Jati Kusumo : G54101045
Menyetujui,
Pembimbing I
Pembimbing II
Dr. Sugi Guritman NIP. 131 999 582
Drs. Siswandi, M. Si NIP. 131 957 320
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Prof. Dr. Ir. Yonny Koesmaryono, MS. NIP. 131 473 999
Tanggal Lulus : …………………..
4
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 1 Juni 1982 sebagai anak pertama dari tiga bersaudara. Ayah bernama Nurhadi (almarhum) dan Ibu bernama Pudji Rahayu. Penulis menyelesaikan pendidikan Sekolah Dasar pada tahun 1994 di SD Negeri Mangunsari 1 Magelang, Sekolah Lanjutan Tingkat Pertama Negeri 7 Magelang tahun 1997, Sekolah Menengah Umum Negeri 1 Muntilan tahun 2000, dan masuk Institut Pertanian Bogor melalui jalur UMPTN pada tahun 2001. Penulis pernah menjadi anggota aktif dalam himpunan profesi Gugus Mahasiswa Matematika IPB sebagai ketua departemen humaniora pada tahun 2003.
5
PRAKATA Puji syukur penulis panjatkan kepada Allah SWT. yang selalu menjadi pusat tujuan hidup dan rasa syukur yang mendalam kepada Sang Guru Sejatiku, Muhammad SAW yang selalu ada memberikan pepadang, tuntunan, dan lindungan, sehingga penulis dapat menyelesaikan karya ilmiah ini. Keterbatasan dan ketidaksempurnaan membuat penulis membutuhkan bantuan, dukungan dan semangat dari orang-orang secara langsung ataupun tidak langsung berkontribusi besar dalam pembuatan karya ilmiah ini. Oleh karena itu penulis ingin mengucapkan rasa terima kasih yang sebesar-besarnya kepada ibu yang selalu ada memberikan kasih sayang, semangat dan doa. Almarhum Bapak Nurhadi atas petuah-petuah bijaknya waktu itu. Bapak Sugi Guritman dan Bapak Siswandi yang dengan sabar telah membimbing dan mengarahkan selama penulisan karya ilmiah ini. Dwicandra Ekastrya yang telah memberi masukan dan semangat. Wanda yang telah memberi dukungan dan doa. Seluruh Dosen Departemen Matematika atas segala ilmu yang telah diberikan tanpa lelah. Staf dan karyawan TU Matematika IPB: Mas Yono, Mas Deni, Ibu Susi, Ibu Ade, Mas Bono, Ibu Marisi, Pak Juanda dan Mbak Yanti yang senantiasa direpotkan. Matematika angkatan 38 atas persahabatannya yang semoga tidak akan berakhir. Serta seluruh pihak-pihak yang tidak dapat penulis sebutkan satu per satu. Semoga karya ilmiah ini dapat bermanfaat.
Bogor, Agustus 2006 Bangun Jati Kusumo
6
DAFTAR ISI Halaman DAFTAR BAGAN DAN GRAFIK ............................................................................... vii DAFTAR LAMPIRAN .................................................................................................. vii PENDAHULUAN ......................................................................................................... 1.1. Latar Belakang ............................................................................................... 1.2. Tujuan penulisan ............................................................................................
1 1 1
LANDASAN TEORI ..................................................................................................... 2.1 Keterbagian, ..................................................................................................... 2.2 Teorema Fermat dan Teorema Strong Pseudoprime ......................................
1 1 2
UJI KOMPOSIT I .......................................................................................................... 3.1 Penentuan bilangan bulat m ............................................................................. 3.2 Penentuan bilangan bulat a ............................................................................. 3.4 Bilangan diduga prima berbasis a ......................................................................
4 4 4 4
UJI KOMPOSIT II ......................................................................................................... 4.1 Menentukan bilangan bulat x ............................................................................. 4.3 Bilangan diduga kuat prima berbasis a .......................................................... 4.4 Bilangan prima semu berbasis a .....................................................................
5 5 5 6
UJI CARMICHAEL ...................................................................................................... 5.1 Definisi bilangan Carmichael .......................................................................... 5.2 Algoritma Uji Carmichael ...............................................................................
7 7 7
UJI DIDUGA KUAT PRIMA ....................................................................................... 6.1 Algoritma Uji Diduga Kuat Prima ..................................................................
8 8
UJI KOMPOSIT III ....................................................................................................... 9 7.1 Algoritma Uji Komposit III ............................................................................ 10 7.3 Bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 ......................................... 10 PENENTUAN BILANGAN .......................................................................................... 10 8.2 Bilangan prima semu kuat berbasis a .............................................................. 10 SIMPULAN DAN SARAN .............................................................................................. 9.1 Simpulan ............................................................................................................. 9.2 Saran ................................................................................................................... 9.3 DAFTAR PUSTAKA ....................................................................................................
12 12 13 13
LAMPIRAN ................................................................................................................... 14
7
DAFTAR BAGAN DAN GRAFIK Halaman Bagan 1 : Klasifikasi Uji Komposit I ............................................................................. Bagan 2 : Klasifikasi Uji Komposit II ............................................................................ Bagan 3 : Himpunan bilangan komposit, prima semu, dan diduga kuat berbasis a ....... Bagan 4 : Letak bilangan Carmichael ............................................................................ Bagan 5 : Penentuan bilangan menjadi lima macam ....................................................... Bagan 6 : Posisi bilangan-bilangan hasil Penentuan Bilangan ....................................... Bagan 7 : Semua uji yang telah dilakukan ..................................................................... Grafik 1 : Banyaknya bilangan komposit pada setiap selang satu juta ........................... Grafik 2 : Banyaknya bilangan prima semu berbasis a pada setiap selang satu juta ...... Grafik 3 : Banyaknya bilangan prima semu kuat berbasis a pada setiap selang satu juta Grafik 4 : Banyaknya bilangan Carmichael pada setiap selang satu juta ....................... Grafik 5 : Banyaknya bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 ........................ Grafik 6 : Persentase banyaknya bilangan ganjil antara 9-20000000 ............................
5 7 7 8 11 11 12 20 20 21 21 21 21
DAFTAR LAMPIRAN Halaman Lampiran A : Algoritma Kongruensi Bilangan Pangkat dan implementasinya ............. Lampiran B : Algoritma dengan bantuan perangkat lunak Matematica 5.1 .................... Lampiran C : Tabel dan grafik hasil uji komposit ........................................................... Lampiran D : Beberapa bilangan Carmichael dan prima semu kuat berbasis 2 ..............
8
15 17 20 22
BAB I PENDAHULUAN pertama kali oleh Korslet pada tahun 1899 namun Korslet tidak dapat memberikan contohnya. Hingga pada tahun 1910 Robert Daniel Carmichael pertama kali menemukan bilangan prima semu mutlak pertama dan terkecil yaitu 561 dan diberi nama bilangan Carmichael. Dalam sejarah perkembangan bilangan Carmichael, Paul Erdos pernah memberikan argumen bahwa seharusnya bilangan Carmichael memiliki tak hingga jumlahnya. Pada 1994, William Alford, Andrew Granville dan Carl Pomerance menunjukkan bahwa ada tak hingga bilangan Carmichael. Hingga saat ini sudah diketahui ada 585355 Bilangan Carmichael antara 1- 1017 . Bilangan
Latar Belakang Dalam menentukan apakah suatu bilangan bulat positif m merupakan bilangan komposit atau bukan, diperlukan suatu uji. Uji tersebut dinamakan uji komposit. Teorema Fermat dan Teorema Strong Pseudoprime [SPP] akan digunakan sebagai landasan teori pada beberapa uji komposit yang akan dilakukan. Bilangan bulat positif m dikatakan komposit jika memenuhi kontraposisi dari Teorema Fermat terhadap basis a, dimana a adalah anggota dari himpunan bilanganbilangan bulat modulo m yang relatif prima dengan m. Jika m tidak memenuhi kontraposisi Teorema Fermat maka m disebut bilangan diduga prima berbasis a. Kemudian bilangan yang telah diketahui diduga prima berbasis a dapat ditentukan kekompositannya menggunakan Teorema SPP. Jika m memenuhi kontraposisi Teorema SPP maka m adalah bilangan komposit. Jika tidak, maka m disebut bilangan diduga kuat prima berbasis a. Selanjutnya bilangan diduga kuat prima berbasis a akan ditentukan kekompositannya dengan cara mengganti basisnya dengan bilangan-bilangan yang telah ditentukan, yaitu 2, 3, 5, dan 7. Bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 adalah hasil akhir dari tulisan ini. Bilangan prima semu mutlak m adalah bilangan komposit yang tidak dapat ditentukan kekompositannya hanya menggunakan Teorema Fermat terhadap setiap basisnya yang relatif prima dengan m. Bilangan prima semu mutlak dibicarakan
Carmichael dapat juga digunakan dalam proses pembuatan data enkripsi untuk membangun sebuah kunci dan dapat digunakan pula pada aplikasi graf. [Wikipedia, 2006] 1.2 Tujuan Tujuan dari penulisan ini adalah: 1. Mengkaji beberapa teorema yang berkaitan dengan penentuan apakah bilangan bulat positf ganjil adalah komposit atau bukan. 2. Mempelajari algoritma-algoritma yang digunakan untuk menentukan bilangan komposit, bilangan prima semu berbasis a, bilangan prima semu kuat berbasis a, bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 serta bilangan Carmichael.
BAB II LANDASAN TEORI bulat x sedemikian sehingga b = ax dan ditulis a|b. Apabila b tidak terbagi oleh a, maka ditulis aFb. [Niven,1991]
Dalam tulisan ini secara khusus akan dibicarakan bilangan bulat. Himpunan bilangan bulat dinotasikan dengan Z. Berikut adalah aspek teoritis yang menjadi landasan teori bagi penulisan tugas akhir ini.
Definisi 1.2 (Bilangan Prima) Sebuah bilangan bulat p ( p ≥ 2 ) dikatakan sebagai bilangan prima jika p hanya terbagi oleh satu dan dirinya sendiri. Selainnya, disebut bilangan komposit. [Menezes,1997]
2.1 Keterbagian, Bilangan Prima, Modulo, Pembagi Bersama Terbesar, Relatif Prima, dan Kongruensi. Definisi 1.1 (Keterbagian) Bilangan bulat b dikatakan terbagi oleh bilangan bulat a (a ≠ 0) , jika ada bilangan
9
Definisi 1.3 (Himpunan Bilangan Bulat Modulo m) Himpunan bilangan bulat modulo m,
Definisi 1.7 (Kongruensi) Misalkan a, b dan m bilangan bulat, dengan m > 0 . Bilangan a dikatakan kongruen terhadap b modulo m, dinotasikan dengan a ≡ b(mod m) , jika m membagi (a − b) . Bilangan bulat m disebut modulus dari kongruensi. [Menezes,1997]
dinotasikan Z m , merupakan suatu himpunan dari bilangan-bilangan bulat {0,1,2,3,…,m-1}. [Menezes,1997] Operasi pada penjumlahan, pengurangan, dan perkalian bilangan bulat modulo m bersifat
Definisi 1.8 (Sistem Residu Lengkap Modulo m) Jika x ≡ y (mod m) , maka y dikatakan residu
tertutup dalam Z m . Contoh Untuk m = 3 . 1. Himpunan bulat modulo tiga adalah Z 3 = {0,1, 2} . 2. Operasi penjumlahan yang berlaku: 0 + 1 = 1, 1 + 2 = 0,
dari x modulo m. Himpunan x1 , x 2 , x3 , ..., x m disebut sistem residu lengkap modulo m jika untuk setiap bilangan bulat y ada satu dan hanya satu
xj
sedemikian sehingga
y ≡ x j (mod m) , dengan j = 1,2,3,…,m. [Niven,1991]
2 + 2 = 1. Operasi pengurangan yang berlaku: 2 −1 = 1,
Definisi 1.9 (Sistem Residu Tereduksi Modulo m) Suatu sistem residu tereduksi modulo m adalah himpunan dari bilangan-bilangan bulat T = { x1 , x2 ,..., xr } , dengan r ≤ m sedemikian sehingga berlaku: i. ( ∀xi ∈ T )(m, xi ) = 1 , ii. Jika i ≠ j maka xi T x j (mod m) , dan
1− 2 = 2. Operasi perkalian yang berlaku: 1.2 = 2, 2.2 = 1, 1.1 = 1. Definisi 1.4 (Pembagi Bersama) Suatu bilangan bulat c disebut pembagi bersama dari bilangan a dan bilangan b jika c|a dan c|b. [Niven,1991]
iii. Jika
x∈Z
dan
( x, m) = 1 , maka
(∃! xi ∈ T ) ∋ xi ≡ x(mod m) . [Niven,1991] 2.2 Teorema Fermat dan Teorema SPP
Definisi 1.5 (Pembagi Bersama Terbesar) Suatu bilangan bulat tak negatif d dikatakan pembagi bersama terbesar dari bilangan bulat a dan b, jika : 1. d adalah pembagi bersama dari a dan b, dan 2. Jika ∃c ∈ Z dimana c|a dan c|b, maka c|d. Biasanya pembagi bersama terbesar dari a dan b dinotasikan dengan d = (a, b) . [Menezes,1997]
Teorema 2.1 (Sistem Residu Tereduksi dan Lengkap Modulo m) Misalkan dan misalkan ( a , m) = 1 r1 , r2 , r3 , ..., rn adalah sistem residu lengkap
modulo m atau sistem residu tereduksi modulo m maka
ar1 , ar2 , ar3 , ..., arn
adalah juga
sistem residu lengkap atau sistem residu tereduksi modulo m. [Niven,1991]
Definisi 1.6 (Relatif Prima) Bilangan a dan b dikatakan relatif prima jika (a, b) = 1 dan bilangan-bilangan a1 , a2 ,..., an dikatakan relatif prima jika (a1 , a2 ,..., an ) = 1 .
Teorema 2.2 (Sifat Kongruensi) Misalkan a, b, c, d adalah bilangan bulat, maka: 1. Ketiga pernyataan berikut ekuivalen : i. a ≡ b(mod m) ,
dikatakan Bilangan-bilangan a1 , a2 ,..., an relatif prima berpasangan jika (ai , a j ) = 1
ii. b ≡ a(mod m) , dan iii. a − b ≡ 0(mod m) .
untuk setiap i = 1, 2,3..., n dan j = 1, 2,3..., n dengan i ≠ j . [Niven,1991]
10
2. 3. 4.
Jika a ≡ b(mod m) dan c ≡ d (mod m) maka ac ≡ bd (mod m) .
5.
Jika a ≡ b(mod m) dan d | m , d > 0 maka a ≡ b(mod d ) . Jika a ≡ b(mod m) maka ac ≡ bc (mod m) untuk setiap bilangan bulat positif c. [Niven,1991]
6.
Selanjutnya:
Jika a ≡ b(mod m) dan b ≡ c(mod m) maka a ≡ c(mod m) . Jika a ≡ b(mod m) dan c ≡ d (mod m) maka a + c(mod m) ≡ b + d (mod m) .
a
φ(m)
φ(m)
∏
φ(m)
( rj ) ≡
j =1
∏ rj (mod m ) . j =1
Sekarang ( r j ,m)=1. Dengan demikian dapat digunakan Teorema 2.3 bagian 2 untuk menghilangkan r j . Dari sini diperoleh bahwa a
φ(m)
≡ 1(mod m ) .
Dari Teorema 2.4 dapat diperoleh teorema berikut.
Teorema 2.3 (Kongruensi Pembagian) Misalkan a, x, y adalah bilangan-bilangan bulat, jika ax ≡ ay (mod m ) dan (a,m)=1 maka x ≡ y (mod m ) . [Niven,1991]
Teorema 2.5 (Kongruensi Fermat). Jika p merupakan bilangan prima maka ∀a ∈ Z yang memenuhi (a,p)=1, berlaku p−1 ≡ 1(mod p ) . a [Niven,1991] Bukti Teorema Fermat. Diketahui (a, p) = 1 , oleh karena itu menurut
Teorema 2.4 (Generalisasi Euler dari Teorema Fermat.) Jika (a,m)=1 maka aφ ( m ) ≡1(mod m ) ,
φ( p)
≡ 1(mod p ) . Teorema 2.4 didapat a Semua bilangan bulat 1,2,3,…,p-1 adalah relatif prima dengan p. Jadi kita mendapatkan bahwa φ ( p ) = p −1 .
dengan φ ( m ) adalah bilangan bulat positif kurang atau sama dengan m yang relatif prima dengan m. [Niven,1991]
Teorema 2.6 (Faktor Pembagi) Jika p|ab, dengan p adalah prima, maka atau Umumnya, jika p|a p|b. p | a , a , a ,..., a maka p membagi sedikitnya
Bukti.
Misalkan r1 , r2 , r3 , ..., rφ ( m ) adalah sistem residu tereduksi modulo m, maka dengan
1 2 3
n
Teorema 2.1, ar1 , ar2 , ar3 , ..., arφ ( m ) adalah juga sistem residu tereduksi modulo m.
satu faktor dari ai .
Dengan demikian korespondensi setiap ri
Teorema 2.7 (Teorema Strong Pseudoprime (SPP)) Jika p suatu bilangan prima, maka berlaku x 2 ≡ 1(mod p) ↔ x ≡ ±1(mod p ) , dengan x adalah bilangan bulat. [Niven,1991]
adalah satu dan hanya satu sedemikian Selanjutnya
yang
ri ≡ arj (mod m ) .
sehingga ri
arj
[Niven,1991]
yang
berbeda
akan
Bukti Teorema SPP. Bentuk kongruensi pangkat di atas dapat diekspresikan x 2 −1 ≡ 0(mod p ) . Bentuk tersebut setara dengan bentuk Dari bentuk ( x + 1)( x −1) ≡ 0(mod p) . terakhir dapat dikatakan bahwa p | ( x + 1)( x − 1) . Berdasarkan Teorema 2.6, p | ( x + 1)( x − 1) dapat ditulis
mendapatkan korespondensi berbeda dari arj . Ini
berarti
bahwa
ar1 , ar2 , ar3 , ..., arφ ( m )
hanya
bilangan merupakan
residu modulo m dari r1 , r2 , r3 , ..., rφ ( m ) . Dengan menggunakan Teorema 2.2 bagian 4, dapat diperoleh: φ(m)
φ(m)
sebagai p | ( x + 1) atau p | ( x − 1) , sama artinya dengan x ≡ 1(mod p ) atau
∏ ( arj ) ≡ ∏ ri (mod m ). j =1
i=1
11
Kontraposisi Teorema SPP digunakan sebagai landasan teori uji komposit pada pembahasan.
x ≡ −1(mod p ) . Sebaliknya, jika salah satu dari bentuk dua kongruensi terakhir benar, dengan menggunakan Teorema 2.2 bagian 4 maka didapat bahwa x 2 ≡ 1(mod p ) .
BAB III PEMBAHASAN Uji Komposit I Berdasarkan Teorema 2.5 (Kongruensi Fermat) diperoleh kontraposisinya, yaitu: Teorema 3.1 (Uji Komposit I): Jika ∃a ∈ Z memenuhi (a, m) = 1 dan m −1
berlaku a T1(modm) maka m adalah bilangan komposit. Teorema 3.1 akan digunakan sebagai alat untuk menguji kekompositan dari suatu bilangan bulat positif m. Berdasarkan Definisi 1.2 (bilangan prima) maka uji hanya akan dilakukan pada bilangan bulat positif lebih besar 2 ( m > 2) . Karena telah diketahui bahwa bilangan prima genap hanya satu yaitu 2 maka uji hanya akan dilakukan pada bilangan ganjil. Pelaksanaan Uji Komposit I ada beberapa tahap, yaitu: i. Menentukan bilangan bulat a yang diambil dari anggota bilangan-bilangan bulat modulo m, jadi a ∈ [0, m −1] . Selanjutnya a disebut basis dari m. ii. Bilangan bulat a harus relatif prima dengan m ( (a,m)=1). Jika a = 0 maka a dapat diabaikan karena 0 dipangkatkan berapapun akan menghasilkan 0, tidak menghasilkan kesimpulan. Jika a = 1 maka a juga dapat diabaikan karena 1 dipangkatkan berapapun akan tetap sama dengan 1. Jika a = m −1 maka a juga dapat diabaikan karena m −1 setara dengan -1 pada bilangan modulo m dan m −1 merupakan bilangan genap karena m adalah bilangan ganjil, sehingga -1 pangkat bilangan genap akan menjadi 1. Jadi, jika a = {0,1, m −1} maka kita tidak akan memperoleh hasil apapun pada Uji Komposit I ini. Jadi a = {0,1, m −1} tidak digunakan sebagai alat uji. Dengan demikian a ∈ [2, m − 2] .
komposit I dan m disebut bilangan diduga prima berbasis a. Untuk menentukan apakah a m−1 T 1(mod m) digunakan AKBP (lihat Lampiran A). Contoh 1. Misalkan m = 1763 , apakah m adalah bilangan komposit ? Cara penyelesaiannya adalah sebagai berikut: 1. Ambil a = 2 ∈ [2,1761] .
2.
(2,1763) = 1 .
1762 ditentukan 2 ≡ 742 mod 1763 , menggunakan AKBP. Jadi 1763 adalah bilangan komposit. Tidak selamanya Uji Komposit I ini berhasil.
3.
Contoh 2. Misalkan m = 1387 , apakah m adalah bilangan komposit ? Cara penyelesaiannya adalah sebagai berikut: 1. Ambil a = 2 ∈ [2,1385] .
2.
(2,1387) = 1 .
1386 ditentukan ≡ 1(mod 1387) , 2 menggunakan AKBP. Jadi 1387 merupakan bilangan diduga prima berbasis 2. Sejauh ini bilangan bulat ganjil m ≥ 2 telah dapat ditentukan menjadi dua macam yaitu bilangan komposit dan bilangan diduga prima berbasis a (lihat Bagan 1). Jika pada Uji Komposit I didapat hasil bahwa m merupakan bilangan diduga prima berbasis a maka ada dua cara yang dapat dilakukan selanjutnya untuk menentukan kekompositannya. Pertama, adalah dengan mengganti basisnya hingga didapat bahwa m adalah bilangan komposit, namun cara ini tidak efisien untuk bilangan m yang besar. Kedua, dengan melakukan uji komposit yang lain, yaitu Uji Komposit II.
3.
iii. Menguji apakah a m−1 T 1(mod m) . Jika uji berhasil maka m merupakan bilangan komposit. Jika tidak (berarti a m−1 ≡ 1(mod m) ), maka tidak dapat diambil kesimpulan apapun dari uji
12
Untuk menentukan apakah ada x yang memenuhi Teorema 3.2 digunakan AKBP (lihat Lampiran A). Ilustrasi : Langkah 1. Misalkan x12 = a m−1 ≡ 1(mod m) m−1 2
sehingga
m−1 2
dan x1 = a (mod m) dihitung x1 = a menggunakan AKBP. Ada 3 kemungkinan dari nilai x1 , yaitu: a. Jika x1 T ±1(mod m) maka ada nilai x yang memenuhi Teorema 3.2, yaitu m−1
b. Bagan 1. Klasifikasi uji komposit I.
Uji Komposit II
c.
Berdasarkan Teorema 2.7 (SPP) diperoleh kontraposisinya, yaitu: Kontraposisi Teorema 2.7: Jika ( x 2 ≡ 1(mod m) ∧ x T ±1(mod m) ) atau
( x 2 T 1(mod m) ⁄xª ±1(mod m) ), maka m adalah komposit.
x = a 2 . Jadi m adalah bilangan komposit. Jika x1 ≡ −1(mod m) , maka m adalah bilangan diduga kuat prima karena tidak ada x yang memenuhi Teorema 3.2. Pencarian nilai x dihentikan. Jika x1 ≡ 1(mod m) , maka kita belum mendapat kesimpulan apapun dan perhitungan dilanjutkan ke langkah 2.
Langkah 2. Dari langkah sebelumnya telah diketahui bahwa x1 ≡ 1(mod m) . Misalkan x1 = x2 2 ⇒ x2 = a
Untuk kepentingan Uji Komposit II maka kontraposisi Teorema 2.7 (SPP) hanya akan digunakan sebagian. Teorema 3.2 (Uji Komposit II). Jika x 2 ≡ 1(mod m) dan x T ±1(mod m) maka m adalah bilangan komposit.
Uji Komposit II merupakan kelanjutan dari Uji Komposit I, sehingga input dari uji ini adalah bilangan diduga prima berbasis a yang diperoleh dari Uji Komposit I. Jadi kita memiliki bilangan m sedemikian sehingga ada bilangan bulat a ∈ [2, m − 2] yang memenuhi (a, m) = 1 dan berlaku a m−1 ≡ 1(mod m) . Selanjutnya nilai x yang memenuhi Teorema 3.2 ditentukan dari a m−1 yang nilai pangkatnya dibagi 2 secara berulang hingga didapat x yang diinginkan atau hingga pangkatnya tidak dapat dibagi lagi ( x ∈ {a m−1 , a
m−1 2
,a
m−1 4
,..., a
m −1 n
} , dan
m −1 n
adalah bilangan ganjil). Jika tidak didapat x yang diinginkan maka m disebut bilangan diduga kuat prima berbasis a.
m−1 4
m−1 4
. Hitung nilai
x2 = a (mod m) dengan AKBP. kemungkinan dari nilai x2 , yaitu: a.
Ada
3
Jika x2 T ±1(mod m) maka ada nilai x yang memenuhi Teorema 3.2, yaitu m−1
b.
c.
x = a 4 . Jadi m adalah bilangan komposit. x2 ≡ −1(mod m) , maka m adalah bilangan diduga kuat prima karena tidak ada x yang memenuhi Teorema 3.2. Pencarian nilai x dihentikan. x2 ≡ 1(mod m) , maka kita belum mendapat kesimpulan apapun.
Langkah-langkah selanjutnya adalah sama seperti langkah kedua (dengan mengganti xi = x2 , i = 3, 4,5..., n ), jika selalu diperoleh hasil adalah bagian c. Langkah dihentikan ketika pangkat dari a adalah ganjil sehingga tidak dapat dibagi 2 lagi. Pada langkah tersebut hanya ada 2 kemungkinan. Langkah n. Dari langkah sebelumnya telah diketahui bahwa xn−1 ≡ 1(mod m) .
13
Misalkan xn−1 = xn 2 ⇒ xn = a m −1 n
m −1 n
,
dengan
adalah bilangan ganjil. Hitung nilai m −1
xn = a n (mod m) dengan AKBP. Ada dua kemungkinan dari nilai xn , yaitu: a. Jika xn T ±1(mod m) maka ada nilai x yang memenuhi Teorema 3.2, yaitu
Contoh 5. Misalkan m=341, apakah m adalah bilangan komposit ? 1. Uji Komposit I. Ambil a = 2 ∈ [2,339] ,
(2,341)=1. 2340 ≡ 1(mod 341) . 2. x1 = 2340 ≡ 1(mod 341) . 3. Misalkan
x1 = x2 2
maka
170
m−1 n
m adalah bilangan x=a . komposit. b. xn ≡ ±1(mod m) , maka m adalah bilangan diduga kuat prima karena tidak ada x yang memenuhi Teorema 3.2. Pencarian nilai x dihentikan. Untuk lebih jelasnya diberikan beberapa contoh kasus.
x2 = 2 ≡ 1(mod 341) . dilanjutkan. 4. Misalkan maka x2 = x3 2 85
x3 = 2 ≡ 32(mod 341) .
nilai
dari
Perhitungan nilai
Karena
ada
dari x
85
dengan x = 2 yang memenuhi Teorema 3.2. Jadi 341 adalah bilangan komposit. Contoh di atas membutuhkan beberapa kali perhitungan.
Contoh 3. Misalkan m=1387, apakah m adalah bilangan komposit ? 1. Uji Komposit I. Dari hasil pada Contoh 2, didapat bahwa 1387 adalah bilangan diduga prima berbasis 2. 2. Misalkan x12 = 21386 ≡ 1(mod1387) .
Contoh 6. Misalkan m = 2047 , apakah m adalah bilangan komposit ? 1. Uji Komposit I. Ambil a = 2 ∈ [2, 2045] ,
3. x1 = 2693 ≡ 512(mod1387) .
3. Misalkan
x1 T ±1(mod m) , maka ada x dengan 693
x = 2 yang memenuhi Teorema 3.2. Jadi m merupakan bilangan komposit. Contoh di atas hanya membutuhkan satu kali perhitungan.
Contoh 4. Misalkan m=1905, apakah m adalah bilangan komposit ? 1. Uji Komposit I. Ambil a = 2 ∈ [2,1903] ,
(2,1905)=1. 21904 ≡ 1(mod1905) . 2. x1 = 21904 ≡ 1(mod1905) . 3. Misalkan
x1 = x2 2
maka
nilai
dari
952
Perhitungan x2 = 2 ≡ 1(mod1905) . dilanjutkan. 4. Misalkan x2 = x3 2 maka nilai dari x3 = 2476 ≡ 1(mod1905) . Perhitungan dilanjutkan. 5. Misalkan x3 = x4 2 maka nilai dari x4 = 2238 ≡ 1144(mod1905) . Karena ada x dengan x = 2 238 yang memenuhi Teorema 3.2, maka 1905 adalah bilangan komposit. Contoh di atas membutuhkan beberapa kali perhitungan.
(2,2047)=1. 2 2046 ≡ 1(mod 2047) . 2. x1 = 22046 ≡ 1(mod 2047) . x1 = x2 2
maka
nilai
dari
1023
x2 = 2 ≡ 1(mod 2047) . Karena tidak ada x yang memenuhi Teorema 3.2 maka langkah dihentikan dan m adalah bilangan diduga kuat prima berbasis 2. Contoh di atas hanya membutuhkan satu kali perhitungan.
Uji Komposit II menghasilkan dua klasifikasi bilangan yaitu bilangan komposit dan bilangan diduga kuat prima berbasis a. Bilangan komposit dan bilangan diduga prima berbasis a disebut bilangan prima semu berbasis a. Karena input dari Uji Komposit II merupakan bilangan diduga prima berbasis a maka contohcontoh bilangan pada Uji Komposit II di atas yang merupakan bilangan komposit (341, 1905, 1387) adalah contoh bilangan prima semu. Sampai Uji Komposit II ini bilangan bulat ganjil telah dapat ditentukan menjadi tiga macam yaitu bilangan komposit, bilangan prima semu berbasis a dan bilangan diduga kuat prima berbasis a (bagan 2). Letak dari bilangan komposit, prima semu berbasis a dan diduga kuat prima berbasis a digambarkan pada bagan 3 di bawah. Bilangan diduga kuat prima berbasis a akan ditentukan kemudian menggunakan Uji Komposit III. Contoh bilangan-bilangan prima semu kuat dengan beberapa basis berbeda di bawah 1000:
14
1. 2. 3. 4. 5. 6. 7. 8.
121,703 adalah bilangan prima semu kuat berbasis 3. 341 adalah bilangan prima semu kuat berbasis 4. 781 adalah bilangan prima semu kuat berbasis 5. 481, 217 adalah bilangan prima semu kuat berbasis 6. 25, 325, 703 adalah bilangan prima semu kuat berbasis 7. 9, 65, 481, 511 adalah bilangan prima semu kuat berbasis 8. 91, 121, 671, 703 adalah bilangan prima semu kuat berbasis 9. 9, 91 adalah bilangan prima semu kuat berbasis 10.
Uji Carmichael Definisi Bilangan Carmichael: Misalkan m adalah komposit. Jika ∀a ∈ [2, m − 2] yang memenuhi (a,m)=1
berlaku a m−1 ≡ 1(mod m) , maka m adalah bilangan Carmichael. [Menezes,1997] Input dari Uji Carmichael adalah bilanganbilangan prima semu berbasis a yang ditentukan dari hasil uji komposit II. Berdasarkan Definisi Bilangan Carmichael akan dibuat algoritma uji Carmichael. Algoritma Uji Carmichael : Input : m (m adalah bilangan prima semu). Output : m adalah bilangan Carmichael atau bukan. 1. a = 2 . 2. Selama a < m −1 , lakukan: 1.1. Jika (a , m ) = 1 maka
a m−1 ≡ 1(mod m) , 1.2. Jika pernyataan di atas bernilai benar maka a = a + 1 , 1.3. Jika pernyataan di atas bernilai salah maka m adalah bilangan prima semu berbasis a saja. Berhenti. 3. Jika langkah kedua tidak berhenti hingga didapat a = m − 2 ≡ 1(mod m) maka m adalah bilangan Carmichael.
Bagan 2. Klasifikasi uji komposit II.
Jika m adalah bilangan Carmichael maka bilangan ini memiliki sifat yang unik karena meskipun merupakan bilangan komposit, namun benar-benar tidak dapat ditentukan hanya menggunakan Uji Komposit I pada semua basis yang relatif prima dengan m.
Contoh kecil bilangan Carmichael pertama : 561, 1105, 1729, 2465, 2821, 6601, 8911. 561 adalah bilangan Carmichael terkecil dan memiliki tiga faktor. Dan contoh bilangan Carmichael pertama dengan k=3,4,5,6,7,8,9 (k adalah banyak faktor dari bilangan Carmichael).
Bagan 3. A
= Himpunan bilangan diduga prima berbasis a, A-B = Himpunan bilangan diduga kuat prima berbasis a, A…B = Himpunan bilangan prima semu berbasis a, B = Bilangan komposit.
k 3. 4. 5. 6.
7. 8.
15
561 41041 825265 321197185
= 3 . 11 . 17 = 7 . 11 . 13 . 41 = 5 . 7 . 17 . 19 . 73 = 5 . 19 . 23 . 29 . 37 . 137 5394826801 = 7 . 13 . 17 . 23 . 31 . 67 . 73 232250619601 = 7 . 11 . 13 . 17 . 31 . 37 . 73 . 163
9.
9746347772161 = 7 . 11 . 13 . 17 . 19 . 31 . 37 . 41 . 641 [Wikipedia, 2006]
Bagan 4. Letak bilangan Carmichael. A = Himpunan bilangan diduga prima berbasis a, A-B = Himpunan bilangan diduga kuat prima berbasis a, A…B = Himpunan bilangan prima semu berbasis a, B = Bilangan komposit, dan C = Bilangan Carmichael. Bilangan Carmichael mengambil tempat pada bagian bilangan prima semu berbasis a. Disertakan hasil Uji Carmichael (pada Lampiran D) untuk bilangan bulat antara satu hingga dua puluh juta.
j dengan j a d ,a 2 d ,a 4 d ,...,a 2 d (mod m ) , adalah bilangan bulat. d Dimulai dari a dan menggunakan Teorema 2.2 (Sifat Kongruensi) bagian 4: Jika a ≡ b (mod m) maka a 2 ≡ b 2 (mod m). Kita dapat mengkonstruksi algoritma diduga kuat prima.
Algoritma Diduga Kuat Prima: Input : Bilangan bulat dan m≥3 a ∈ [2, m − 2] . Output : m adalah bilangan komposit atau diduga kuat prima berbasis a. 1. Cari nilai j dan d dengan d adalah bilangan ganjil, sedemikian sehingga memiliki j bentuk m − 1 = 2 d . 2. Cari nilai residu dari a d (mod m ) dengan
3.
nilai dari a 2 d (mod m ) menggunakan AKBP. Jika a 2 d ≡1(mod m ) maka m adalah
Uji Diduga Kuat Prima Uji ini dibangun berdasarkan Teorema 3.1 dan Teorema 3.2. Pada prinsipnya uji ini hampir sama dengan Uji Komposit II hanya berbeda pada teknik penentuan x yang memenuhi Teorema 3.2. Pada uji ini digunakan teknik terbalik yang dimulai dari a d , dengan d adalah bilangan ganjil. Agar lebih jelas, perhatikan ilustrasi berikut: x ditentukan dari a m−1 (modm) hingga
bilangan komposit, berhenti. Jika a 2 d ≡−1(mod m ) maka
4.
a
a
m −1 2
m −1 4
…
(modm) (modm)
a2
j−1
d
(modm)
a2
j−2
d
(modm)
5.
8d
16 d
2 j−1 d
. a 2d dengan a , a , a , ..., a Jika langkah di atas telah dilakukan dan tidak mendapatkan hasil maka m adalah bilangan komposit. [Niven,1991]
Ilustrasi algoritma diduga kuat prima: Langkah 1. 1.1 Jika pada perhitungan awal didapat a d ≡ ±1(mod m) maka m adalah bilangan
diduga kuat prima berbasis a, berhenti. Sebab tidak ada nilai x dimana 2jd d 2d 4d yang x ∈ {a , a , a , ..., a } memenuhi Teorema 3.2. Ilustrasi Langkah 1.1: d a ≡ ±1(mod m )
…
m −1 n
a d (modm) a (modm) Jadi dengan teknik terbalik, x ditentukan dari bilangan-bilangan:
m adalah bilangan diduga kuat prima berbasis a. Berhenti. Ulangi langkah tiga dengan mengganti nilai 4d
m −1
a n (modm) dengan m −1 dibagi 2 secara berulang hingga tidak dapat dibagi lagi dan m −1 d= dengan d adalah bilangan ganjil. n j a m−1 (modm) a 2 d (modm)
AKBP. Jika a d ≡±1(mod m ) maka m adalah bilangan diduga kuat prima berbasis a, berhenti. Kuadratkan a d menjadi a 2d , cari reduksi
akan
a
16
2d
≡ 1(mod m )
… 2jd a ≡ 1(mod m ) m−1 ≡ 1(mod m ) . a 1.2 Jika langkah 1.1 tidak berhasil maka lanjutkan ke langkah 2.
Langkah 2.
j −1 d , lakukan: Selama x ≤ a 2 Dengan asumsi bahwa perhitungan sebelumnya didapat
a2
(1 ≤ i ≤ j ) , maka hitung a
j−1
d
T ±1(mod m) ,
2i d
(mod m ) .
i
2d 2.1 Jika didapat a ≡ 1(mod m ) maka m adalah bilangan komposit, berhenti. Ilustrasi langkah 2.1: d a ≡ ±1(mod m ) … 2i−1 d T≤ 1(mod m ) a
a a
2i d 2
i +1
m−1 ≡ 1(mod m ) . a Artinya tidak ada x sedemikian sehingga 2 x ≡ 1(mod p ) ∧ x T ±1(mod p ) . 2.3 Jika langkah 2.1 dan 2.2 tidak berhasil maka i = i +1 . Langkah-langkah selanjutnya mengikuti langkah 2 jika selalu didapatkan hasil 2.3.
Langkah n. Jika
a
2jd
2.
≡ 1(mod m )
2i d 2.2 Jika didapat a ≡ −1(mod m ) maka m adalah bilangan diduga kuat prima berbasis a, berhenti. Ilustrasi 2.2: d a ≡ ±1(mod m ) … 2i−1 d T≤ 1(mod m ) a
2i d
2 a …
a
i +1
2jd
tidak
2 j−1 d Teorema 3.2 ada x= a sedemikian sehingga x memenuhi 2 x ≡ 1(mod p ) ∧ x T ±1(mod p ) . Jadi m dapat dikatakan bilangan komposit 2j d Jika a T 1(mod m ) setara dengan m−1 T 1(mod m ) dan menurut Teorema a 3.1 maka dapat dikatakan bahwa m adalah bilangan komposit.
≡ 1(mod m ) .
2i−1 d Artinya ada x dengan x = a yang memenuhi Teorema 3.2. Jadi m adalah bilangan komposit.
a
2 j−1 d
2j d dari a dapat ditunjukkan bahwa m adalah bilangan komposit. 2jd 1. Jika a ≡ 1(mod m ) maka menurut
≡ 1(mod m )
m−1
a
2 d mendapat hasil ( a T≤1(mod m)), maka m adalah bilangan komposit. Karena apapun hasil
… a
perhitungan j−1
≡ 1(mod m ) , (1 ≤ i ≤ j). d
hingga
≡ −1(mod m ) , (1 ≤ i ≤ j). d
≡ 1(mod m )
≡ 1(mod m )
Uji Komposit III Uji komposit III adalah Uji Diduga Kuat Prima dengan menggunakan beberapa basis yang berbeda. Dalam tulisan ini akan digunakan empat bilangan pertama yang telah kita ketahui prima,yaitu 2, 3, 5, dan 7. Karena telah diketahui bahwa keempat bilangan tersebut adalah prima dan bilangan bulat selain bilangan prima di atas yang kurang dari tujuh ( m < 7 ) adalah komposit maka Uji Komposit III ini akan mengambil input m > 7 . Pertama karena telah diketahui bahwa keempat bilangan tersebut adalah prima maka keempat bilangan tersebut hanya dapat dibagi oleh dirinya dan 1. Jadi untuk mengetahui apakah m > 7 relatif prima dengan setiap anggota dari himpunan A={2,3,5,7} atau tidak, adalah cukup dengan mencari adakah ai ∈ A, dimana ( 1 ≤ i ≤ 4 ) yang membagi m. Jika ada maka m tidak relatif prima dengan ai , yang artinya ( ai ,m)= ai . Jika ( ai ,m)= ai maka ai |m. Artinya
17
m adalah komposit karena dapat dibagi oleh ai dimana ai ≠ 1 dan ai ≠ m ( m > 7 ). Jika m relatif prima dengan setiap anggota A maka langkah selanjutnya adalah melakukan algoritma diduga kuat prima dengan setiap anggota A sebagai basisnya. Algoritma Uji Komposit III: Input : m > 7 , dengan m adalah bilangan bulat ganjil. Output : m adalah bilangan diduga kuat prima berbasis 2, 3, 5 dan 7 atau m adalah bilangan komposit.
1. 2. 3.
j Bentuk, sedemikian m −1 = 2 d sehingga d adalah bilangan ganjil. i=1 Selama i ≤ 4 , ikuti langkah berikut: 3.1 ai ∈ A = {2,3,5, 7} .
j 3.2 Hitung nilai y = ai (mod m) dengan AKBP. 3.3 Jika y ≠ 1 dan y ≠ m −1 maka ikuti langkah berikut: j =1. Selama j ≤ d −1 dan y ≠ m −1 lakukan langkah berikut: Hitung y ← y 2 (mod m) . Jika y = 1 maka m adalah bilangan komposit, berhenti. j = j +1 . Jika y≠m-1 maka m adalah bilangan komposit, berhenti. 3.4 i = i + 1 4. Jika langkah 3 tidak berhasil maka m adalah bilangan diduga kuat prima berbasis 2, 3, 5 dan7. Hasil dari Uji Komposit III ini adalah bilangan komposit atau bilangan diduga kuat prima berbasis 2, 3, 5 dan 7 yang merupakan hasil akhir dari tulisan ini. Uji ini digunakan untuk membantu penentuan bilangan bulat.
menggunakan Teorema 3.2 akan dilanjutkan Uji Carmichael karena input dari Uji Carmichael adalah bilangan-bilangan prima semu. Jika Uji Carmichael menentukan bahwa bilangan m adalah bilangan komposit maka m adalah hanya bilangan prima semu berbasis a dan jika uji berhasil maka kita mendapatkan bahwa m adalah bilangan Carmichael. Pada penentuan yang menghasilkan bilangan diduga kuat prima berbasis a akan dilanjutkan dengan Uji Komposit III yang merupakan bahasan selanjutnya tulisan ini. Jika menggunakan Uji Komposit III didapat hasil bahwa suatu bilangan adalah bilangan komposit maka bilangan tersebut disebut bilangan prima semu kuat berbasis a. Penentuan Bilangan digunakan untuk menentukan suatu bilangan ganjil menjadi lima macam, yaitu: bilangan komposit, bilangan prima semu, bilangan prima semu kuat, bilangan Carmichael dan bilangan diduga kuat prima berbasis a. Jika Penentuan Bilangan menentukan bahwa suatu bilangan bulat m adalah bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 maka kita belum dapat menentukan bahwa m adalah benar-benar prima (lihat bagan 5). Berdasarkan [Niven,1991] telah diuji bahwa bilangan-bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 dapat dinyatakan prima jika m≠3.215.031.751 dan m ≤ 25.000.000.000. Dengan bantuan perangkat lunak Matematica 5.1 hasil dari Niven dapat dilanjutkan untuk bilangan-bilangan yang ditentukan diduga kuat prima berbasis 2, 3, 5, dan 7. Hasil uji adalah hingga bilangan 25.006.229.057 tidak ditemukan bilangan prima semu kuat berbasis 2, 3, 5, dan 7, selain m = 3.215.031.751. Dengan demikian selama m ≤ 25.006.229.057 dan m ≠ 3.215.031.751 maka bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 dapat dinyatakan prima.
Penentuan Bilangan Bulat Penentuan bilangan bulat dilakukan berdasarkan algoritma diduga kuat prima. Bilangan yang diketahui bilangan komposit menggunakan Teorema 3.1 adalah bilangan komposit biasa. Bilangan-bilangan yang diketahui komposit menggunakan Teorema 3.2 disebut bilangan prima semu, oleh karena jika ada suatu bilangan bulat 2 x ∋ x ≡ 1 mod p ∧ x T ±1 mod p maka a m−1 ≡ 1(mod m) . Dari algoritma diduga prima yang menghasilkan komposit
18
Bagan 5. Penentuan bilangan menjadi lima macam.
Bagan 6. Posisi bilangan-bilangan hasil Penentuan Bilangan : A = Himpunan bilangan diduga prima berbasis a, A-B = Himpunan bilangan diduga kuat prima berbasis A={2,3,5,7}, A…B = Himpunan bilangan prima semu berbasis a, B = Bilangan komposit, C = Bilangan Carmichael, D = Bilangan prima semu kuat berbasis a .
19
Bagan 7. Semua uji yang telah dilakukan.
BAB IV SIMPULAN DAN SARAN 8.1 Simpulan Pada uji prima kali ini didapat beberapa hasil sebagai berikut: 1. Teorema 2.5 (Kongruensi Fermat) menjadi landasan teori pada Uji Komposit I, Uji Komposit III, Penentuan Bilangan dan Uji Carmichael. Di lain pihak Teorema 2.7 (SPP) menjadi landasan teori pada Uji Komposit II, Uji Komposit III dan Penentuan Bilangan. 2. Algoritma penentuan bilangan dibantu dengan AKBP, Uji Komposit III dan Uji Carmichael adalah algoritma yang menentukan bilangan bulat positif ganjil menjadi lima macam, yaitu : bilangan komposit, bilangan prima semu berbasis a, bilangan Carmichael, bilangan prima semu kuat berbasis a dan bilangan diduga kuat prima berbasis 2, 3, 5, dan 7. 3. Karena pada uji komposit kali ini menggunakan perhitungan bilangan berpangkat maka uji komposit kali ini
hanya terbatas pada bilangan-bilangan yang memiliki digit yang kecil. Semakin besar nilai bilangan bulat ganjil yang akan diuji maka akan semakin panjang perhitungan yang harus dilakukan sehingga semakin lama waktu yang dibutuhkan untuk mendapatkan hasil dari perhitungan. 4. Hasil akhir dari tulisan ini adalah bilangan diduga kuat prima berbasis 2, 3, 5 dan, 7. 5. Bilangan Carmichael merupakan bilangan komposit yang dihasilkan dari Uji Komposit II dan memenuhi Uji Carmichael. Meskipun merupakan bilangan komposit, bilangan Carmichael tidak dapat ditentukan kekompositannya hanya menggunakan Uji Komposit I pada setiap basis yang relatif prima dengan bilangan tersebut. Bilangan Carmichael memiliki letak tersendiri (lihat bagan 6), bilangan Carmichael merupakan
20
Selesai
bagian dari bilangan prima semu berbasis a, namun bilangan ini bukan merupakan prima semu kuat berbasis a. Pada penentuan bilangan Carmichael benarbenar akan membuat perhitungan semakin lebih besar sehingga akan memakan waktu semakin lama karena kita harus menghitung setiap basis yang relatif prima dengan m terhadap Teorema 3.1. Semakin besar bilangan yang diuji semakin lama waktu perhitungan. 6. Pada tulisan ini suatu bilangan bulat dapat diuji apakah merupakan bilangan komposit atau bukan komposit (diduga prima berbasis 2, 3, 5, dan 7). Untuk bilangan bulat yang bukan komposit belum dapat dikatakan sebagai bilangan prima. Jadi pada tulisan ini, menentukan apakah suatu bilangan adalah bilangan komposit lebih mudah daripada menentukan apakah suatu bilangan adalah bilangan prima.
7. Hingga bilangan 20000000, banyaknya bilangan komposit memiliki kecenderungan meningkat pada setiap selang 1000000. Sedangkan banyaknya bilangan prima semu berbasis a, prima semu kuat berbasis a, Carmichael, dan bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 memiliki kecenderungan menurun pada setiap selang yang sama (lihat Lampiran C). 8.2 Saran Tema dalam karya ilmiah ini dapat diteruskan bagi yang berminat, salah satunya adalah menentukan kekompositan bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 menggunakan faktorisasi prima.
DAFTAR PUSTAKA Niven, I. Zuckerman, H. S. dan Montgomery, L. H. 1991. An Introduction to The Theory of Numbers. John Wiley & Sons. Inc: New York. Menezes, A. J. Oorschot, P. C. V. dan S. Vanstone. 1997. Handbook of Applied Cryptography. CRC Press, Inc: New York. Wikipedia. 2006. Carmichael Number. In Wikipedia, The Free Encyclopedia. The Wikipedia. http://en.wikipedia.org/wiki/Carmichael _number. Buchmann, J. Muller, V. 1992. Primality Testing. Germany. Elledge, S. Glenn, H. 2005. An Application of Graph Pebbling to Zero-Sum Sequences in Abelian Groups. Department of Mathematics and Statistics, Arizona State University: Arizona. Higgins, B. C. 2006. The Rabin-Miller Probabilistic Primality Test: Some Result on The Number of No-Witnesses to compositness. Penn State Erie-The Behrend College. Hardy, G. H. Wright, E. M. 1997. An Intoduction to The Theory of Numbers, Oxford University Press.
21
LAMPIRAN
22
Lampiran A. Algoritma Kongruensi Bilangan Pangkat dan Implementasinya. Kongruensi bilangan pangkat.
Bilangan berpangkat (a k ) cenderung memiliki nilai yang besar untuk dihitung atau diketahui nilai bilangan pangkat satunya sebelum direduksi dengan m sebagai modulo bilangan pembaginya, a k (mod m) . Dengan demikian untuk memudahkannya k dibagi dua secara berulang hingga didapat bahwa nilai k sama dengan satu, dengan nilai a dikuadratkan secara bersamaan. Lalu bilangan hasil pembagian yang memiliki pangkat lebih kecil dapat direduksi oleh modulo bilangan pembaginya (m) dengan lebih mudah. Ilustrasi. Mencari nilai: 999179 mod1763
999179 mod1763 89 ≡ 9992 (999) mod1763
(
)
44
( ) (9992 )(999) mod1763 22 ≡ (9998 ) (9992 )(999) mod1763 11 ≡ (99916 ) (9992 )(999) mod1763 5 ≡ (99932 ) (99916 )(9992 )(999) mod1763 2 ≡ (99964 ) (99932 )(99916 )(9992 )(999) mod1763 ≡ (999128 ) (99932 )(99916 )(9992 )(999) mod1763 ≡ 9994
Lalu nilai diatas direduksi dengan modulo bilangan pembaginya. 9992 ≡ 143( mod1763)
( ) (9994 ) ≡ 1432 ≡ 1056(mod1763) (9998 ) ≡ 10562 ≡ 920(mod1763) (99916 ) ≡ 9202 ≡ 160(mod1763) (99932 ) ≡ 1602 ≡ 918(mod1763) (99964 ) ≡ 9182 ≡ 10(mod1763) (999128 ) ≡ 102 ≡ 100(mod1763)
lalu substitusi bilangan pangkat yang besar dengan bilangan hasil reduksi modulo di atas.
(
≡ 999128
) (99932 )(99916 )(9992 )(999) mod1763
≡ 100 918 160 143 999 (mod 1763). ≡ 1219 (mod 1763). Dengan cara yang hampir sama dapat dibangun sebuah algoritma untuk menyelesaikan masalah di atas, yaitu algoritma kongruensi bilangan pangkat.
23
AKBP: Input
k : a (mod m )
k Output : x (residu dari a (mod m ) ) 1. Bentuk x=1. 2. Selama k>0, ulangi langkah-langkah berikut: k a. e = k − 2[ ] . (nilai e = 0 atau e = 1 tergantung dari nilai k apakah ganjil atau genap). 2 b. Jika e=1 maka gantikan nilai x dengan ax. Dan reduksi nilai tersebut dengan modulo m. Jika e=0 maka tidak dilakukan apapun ( x = x ). c. Gantikan nilai a dengan a 2 . Dan reduksi nilai tersebut dengan modulo m. k −e d. Gantikan nilai k dengan . 2 3. Jika langkah satu dan dua telah selesai maka dapat kita lihat bahwa x≡a k mod m .
[Niven,1991]
Ilustrasi: Input: 35 (mod 5) , a=3, k=5, m=5. k= a. b. c. 5>0 x=1 a=3 5>0 e=5-2.[5/2]=1 x=3 a=4 2>0 e=2-2.[2/2]=0 x=3 a=1 1>0 e=2-2.[1/2]=1 x=3 a=1 berhenti ku0 Jadi x=3 sehingga 35 ≡ 3(mod 5) .
d. k=5 k=2 k=1 k=0
Implementasi AKBP dengan bantuan perangkat lunak Matematica 5.1. Algoritma kongruensi bilangan pangkat. Input : a k (mod m) .
: y sebagai hasil reduksi a k (mod m) .
Output
AKBP[aa_Integer, kk_Integer, mm_Integer]:= Module[{x=1, a=aa, k = kk, m=mm},
While[k>0, e=k-2 Floor[
k ]; 2
If[e = = 1, x = a x; x = mod[x,m] ]; a= a 2 ; a=Mod[a,m]; k=
k −e 2
]; x ] Contoh: Input : AKBP[234,12345,12346] Output : 234
Input : AKBP[2,560,561] Output : 1
24
Lampiran B. Algoritma dengan bantuan perangkat lunak Matematica 5.1.
1.
Algoritma Uji Carmichael. Input : m adalah bilangan prima semu berbasis a. Output : menentukan apakah m merupakan bilangan Carmichael (Uji Carmichael=3) atau bukan(Uji Carmichael=5). UjiCarmichael[nn_Integer]:= Module[{i=2, n=nn, c, xx}, While[i
2.
Contoh : Input Output
: UjiCarmichael[341] : 5 ( 341 bukan bilangan Carmichael).
Input Output
: UjiCarmichael[561] : 3 (561 adalah bilangan Carmichael).
Algoritma Uji Komposit III. 2.1 Algoritma uji relatif prima bilangan bulat m dengan setiap anggota dari A. Input : m adalah bilangan bulat ganjil. Output : m relatif prima (RelatifP=1) atau tidak relatif prima dengan setiap anggota dari himpunan A(RelatifP=0). ClearAll[] RelatifP[m_Integer]:= If[IntegerQ[
m m m m ] || IntegerQ[ ] || IntegerQ[ ] || IntegerQ[ ], 0,1] 2 3 5 7
Contoh: Input : RelatifP[561] Output : 0 (561 tidak relatif prima dengan salah satu anggota A, yaitu 3).
Input : RelatifP[1237] Output : 1 (1237 relatif prima dengan setiap anggota dari A).
2.2 Algoritma Uji Komposit III. Input : m adalah bilangan bulat ganjil. Output : m adalah komposit (DidugaKP=4) atau diduga kuat berbasis A (DidugaKP=2). Selama m ≠ 3.215.031.751 dan m ≤ 25.006.229.057maka m dapat dinyatakan prima. DidugaKP[m_Integer]:= Module[{s=0, x, r=m-1, a, j, v, A={2,3,5,7}, i, y}, If[RelatifP[m] = = 0, x=4,
While[EvenQ[r],
r ;s++]; 2
For[i=1, i≤4,
25
a=A[[i]]; y=AKBP[a,r,m]; If[ y≠1 && y≠m-1, j=1; While[j≤s-1&&y≠m-1, y=AKBP[y,2,m]; If[y= =1, x=4; Goto[selesai]; ]; j++; ]; If[y≠m-1, x=4; Goto[selesai]; ];
]; i++]; x=2; Label[selesai];
]; x ] Contoh : Input : DidugaKP[234567]. Output : 4(m adalah komposit). Input : DidugaKP[3.215.031.751] Output : 2 (m adalah diduga kuat prima, dan telah diuji prima bahwa m adalah komposit. Jadi m adalah prima semu kuat berbasis 2, 3, 5 dan 7).
3.
Algoritma Penentuan Bilangan. Terdiri dari dua fungsi a. Algoritma Penentuan Bilangan: Input : m bilangan bulat yang akan diuji dan a sebagai basis dari m. Output : menentukan m menjadi lima macam, yaitu : m=1(Bilangan Komposit), m=2(Bilangan Prima), m=3(Bilangan Carmichael), m=4(Bilangan Prima Semu Kuat), m=5(Bilangan Prima Semu). Penentuan[mm_Integer, aa_Integer]:= Module[{m=mm, a=aa, j=0, y=m-1, d, x},
While[EvenQ[y], y=
y ;j++]; 2
d =y ; If[AKBP[a,d,m] = =1 || AKBP[a,d,m] = = -1, x=DidugaKP[m], While[d<m, If[d==m-1, If[AKBP[a,d,m]≠1, x=1; Break[], x=UjiCarmichael[m];Break[] ], d=2 d; Switch[AKBP[a,d,m], 1, x=UjiCarmichael[m]; Break[],
26
m-1, x=DidugaKP[m];Break[] ]
] ] ]; X ] Contoh: Input : Seleksi[2047] Output : 4.
Input : Seleksi[561] Output : 3.
b.
Algoritma bantuan untuk algoritma penentuan bilangan. Input : m bilangan bulat yang akan diuji dan a sebagai basis dari m. Output : menentukan m menjadi lima macam, yaitu : bilangan komposit, bilangan prima ( m ≠ 3.215.031.751 dan m ≤ 25.006.229.057 ), bilangan prima semu berbasis a, bilangan prima semu kuat berbasis a dan bilangan Carmichael. Fseleksi[mm_Integer, aa_Integer]:=Module[{m=mm,a=aa}, x=If [GCD[a,m] = = 1,Penentuan[m,a],x=6]; Switch[x, 1,Print[m];Print["adalah bilangan komposit"], 2,Print[m];Print["adalah bilangan diduga kuat prima berbasis 2, 3, 5 dan 7"], 3,Print[m];Print["adalah bilangan Carmichael"], 4,Print[m];Print["adalah bilangan prima semu kuat berbasis a"], 5,Print[m];Print["adalah bilangan prima semu berbasis a"], 6,Print[m];Print["a dan m tidak relatif prima"] ] ] Contoh: Input :Fseleksi[41041,2] Output :41041 Bilangan Carmichael.
Input :Fseleksi[703,9] Output :703 adalah bilangan prima semu kuat berbasis a"],. Input :Fseleksi[341,2] Output :341 adalah bilangan prima semu berbasis a. Input :Fseleksi[99,2] Output :99 adalah bilangan komposit. Input :Fseleksi[25005457493,2] Output : 25005457493 adalah bilangan diduga kuat prima berbasis 2, 3, 5 dan, 7.
27
Lampiran C. Tabel dan grafik banyaknya bilangan-bilangan komposit, prima semu berbasis a, prima semu kuat berbasis a, Carmichael dan diduga kuat prima berbasis 2, 3, 5, dan 7. Selang
Bilangan bulat ganjil
Banyaknya bilangan-bilangan bulat yang Diduga kuat prima Prima semu Prima semu Carmichael berbasis 2, 3, 5, dan 7 kuat berbasis a berbasis a 421257 161 46 38 78494 429456 71 27 11 70435 432033 58 18 8 67883 433620 34 11 5 66330 434577 42 10 4 65367 435615 30 14 5 64336 436155 30 9 7 63799 436837 23 8 3 63129 437251 23 7 7 62712 437870 22 12 6 62090 438020 28 8 6 61938 438434 13 6 4 61543 438781 21 2 4 61192 439146 17 9 3 60825 439349 16 5 3 60627 439543 16 12 3 60426 439790 15 9 2 60184 439924 11 7 5 60053 440292 15 7 3 59683 440427 10 4 2 59557 8728377 656 231 129 1270603 9999996 87.283 % 0.006 % 0.002 % 0.001 % 12.603 %
Komposit 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
9 1000001 2000001 3000001 4000001 5000001 6000001 7000001 8000001 9000001 10000001 11000001 12000001 13000001 14000001 15000001 16000001 17000001 18000001 19000001
1000000 2000000 3000000 4000000 5000000 6000000 7000000 8000000 9000000 10000000 11000000 12000000 13000000 14000000 15000000 16000000 17000000 18000000 19000000 20000000 Jumlah Jumlah total Persentase
-
440000
430000
420000
410000
1
2 3
4 5
6
7 8
9 10 11 12 13 14 15 16 17 18 19 20
Grafik 1. Banyaknya bilangan komposit pada setiap selang satu juta.
28
(Selang ke-)
150 125 100 75 50 25 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(Selang ke-)
Grafik 2. Banyaknya bilangan prima semu berbasis a pada setiap selang satu juta.
40
30
20
10
(Selang ke-) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Grafik 3. Banyaknya bilangan prima semu kuat berbasis a pada setiap selang satu juta.
35 30 25 20 15 10 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(Selang ke-)
Grafik 4. Banyaknya bilangan Carmichael pada setiap selang satu juta.
75000 70000 65000 60000 55000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(Selang ke-)
Grafik 5. Banyaknya bilangan diduga kuat prima berbasis 2, 3, 5, dan 7 pada setiap selang satu juta.
29
1 2 3 4 5
Grafik 6. Persentase banyaknya bilangan ganjil antara 9-20000000, yang berupa : 1. Bilangan komposit, 2. Bilangan prima semu berbasis a, 3. Bilangan prima semu kuat berbasis a, 4. Bilangan Carmichael, dan 5. Bilangandiduga kuat prima berbasis 2, 3, 5, dan 7.
30
Lampiran D. Beberapa bilangan Carmichael dan prima semu kuat berbasis 2.
Bilangan prima semu kuat berbasis 2. 2047 1016801 3277 1023121 4033 1082401 4681 1145257 8321 1194649 15841 1207361 29341 1251949 42799 1252697 49141 1302451 52633 1325843 65281 1357441 74665 1373653 80581 1397419 85489 1441091 88357 1493857 90751 1507963 104653 1509709 130561 1530787 196093 1678541 220729 1730977 233017 1811573 252601 1876393 253241 1907851 256999 1909001 271951 1969417 280601 1987021 314821 2004403 2081713 357761 2181961 390937 2205967 458989 2264369 476971 2269093 486737 2284453 489997 2304167 514447 2387797 580337 2419385 635401 2510569 647089 2746477 741751 2748023 800605 2757241 818201 2811271 838861 2909197 873181 2953711 877099 2976487 916327 3090091 976873 3116107 983401 3125281 1004653
3375041 3400013 3429037 3539101 3567481 3581761 3605429 3898129 4181921 4188889 4335241 4360621 4469471 4502485 4513841 4682833 4835209 4863127 5016191 5044033 5049001 5173169 5173601 5256091 5310721 5444489 5489641 5590621 5599765 5672041 5681809 5919187 6140161 6226193 6233977 6334351 6368689 6386993 6787327 6836233 6952037 7177105 7306261 7306561 7462001 7674967 7759937
31
7820201 7883731 8036033 8095447 8384513 8388607 8534233 8725753 8727391 9006401 9056501 9069229 9073513 9371251 9564169 9567673 9588151 9729301 9774181 9863461 9995671 10323769 10386241 10425511 10610063 10655905 10712857 10763653 10974881 11081459 11335501 11473885 11541307 11585293 11777599 12263131 12327121 13057787 13216141 13338371 13421773 13446253 13500313 13635289 13694761 13747361 14179537
14324473 14709241 14794081 14865121 15101893 15139199 15188557 15220951 15247621 15479777 15510041 15603391 15698431 15802681 15976747 15978007 16070429 16132321 16324001 16360381 16705021 16773121 16822081 16853077 16879501 17116837 17134043 17208601 17327773 17375249 17509501 17585969 18073817 18366937 18443701 18454921 18535177 18653353 18740971 19328653 19404139 19471033 19607561 20261251
Bilangan Carmichael. 561 1105 1729 2465 2821 6601 8911 10585 41041 46657 62745 63973 75361 101101 115921 126217 162401 172081 188461 278545 294409 334153 340561 399001 410041 449065
488881 512461 530881 552721 656601 658801 670033 748657 825265 838201 852841 997633 1024651 1033669 1050985 1082809 1152271 1193221 1461241 1569457 1615681 1773289 1857241 2100901 2113921 2433601
2455921 2508013 2531845 2628073 2704801 3057601 3146221 3224065 3664585 3828001 4463641 4767841 4903921 4909177 5031181 5148001 5481451 5632705 5968873 6049681 6054985 6189121 6313681 6733693 6840001 6868261
32
7207201 7519441 7995169 8134561 8341201 8355841 8719309 8719921 8830801 8927101 9439201 9494101 9582145 9585541 9613297 9890881 10024561 10267951 10402561 10606681 10837321 10877581 11119105 11205601 11921001 11972017
12261061 12262321 12490201 12945745 13187665 13696033 13992265 14469841 14676481 14913991 15403285 15829633 15888313 16046641 16778881 17098369 17236801 17316001 17586361 17812081 18162001 18307381 18900973 19384289 19683001 20964961
