PERANCANGAN PERANGKAT AJAR DENGAN PERMAINAN MENGENAI CHINESE REMAINDER THEOREM

PERANCANGAN PERANGKAT AJAR DENGAN PERMAINAN MENGENAI CHINESE REMAINDER THEOREM

SKRIPSI

Oleh:

ERWIN NIM. 1144028

PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER STMIK TIME MEDAN 2015

ABSTRAK

Chinese Remainder Theorem (CRT) yang dikemukakan oleh seorang ahli matematika Tiongkok yang bernama Sun Tze merupakan salah satu teori yang dapat diterapkan untuk mencari nilai invers dari sebuah sistem kongruen linier. CRT ini memanfaatkan algoritma Extended Euclidean dalam proses penyelesaiannya. Perangkat lunak pemahaman dan permainan Chinese Remainder Theorem ini membahas mengenai proses kerja dari CRT secara terperinci. Proses kerja yang dibahas mencakup pembahasan mengenai proses kerja Chinese Remainder Theorem dan algoritma Extended Euclidean. Perangkat lunak ini menampilkan tahapan-tahapan proses perhitungan dari CRT secara tahap demi tahap. Perangkat lunak juga menyediakan interface untuk membahas proses kerja dari algoritma Extended Euclidean dan interface permainan untuk bermain Chinese Remainder Theorem. Kata kunci: Chinese Remainder Theorem, algoritma Extended Euclidean, permainan, pemahaman

i

ABSTRACT

Chinese Remainder Theorem (CRT) is proposed by mathematician from China, named Sun Tze which is one of the theory that could be used to find invers modular of linear congruent system. CRT uses Extended Euclidean algorithm in the computation process. This application could show the detail computation of CRT. The process includes the process of Chinese Remainder Theorem and Extended Euclidean algorithm. This application could show the detail computation process of CRT. The software provides interface for showing the detail computation process of Extended Euclidean algorithm and interface for playing Chinese Remainder Theorem. Keywords: Chinese Remainder Theorem, Extended Euclidean algorithm, games, learning

ii

KATA PENGANTAR

Puji syukur kepada Tuhan Yang Maha Esa yang telah memberikan kesehatan kepada penulis dan berkat kebajikan yang telah diperbuat selama ini sehingga penulis dapat menyelesaikan skripsi yang merupakan salah satu pemenuhan kurikulum program studi Teknik Informatika pada STMIK TIME Medan. Adapun judul dari skripsi ini adalah “Perancangan Perangkat Ajar dengan Permainan Mengenai Chinese Remainder Theorem”. Dalam penyusunan skripsi ini, penulis banyak menerima bantuan, baik bimbingan maupun petunjuk serta saran nasehat dari berbagai pihak. Melalui kesempatan ini, penulis ingin menyampaikan rasa terima kasih yang sebesar – besarnya kepada : 1.

Ibu Yoshida Sary, SE, M.Kom, selaku Dosen Pembimbing I yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.

2.

Ibu Ester Hervina, S.Sos, M.Si, selaku Dosen Pembimbing II yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.

3.

Bapak Simon Kanggali, selaku Ketua Yayasan STMIK TIME Medan.

4.

Bapak Prof. Chainur Arrasyid,SH , selaku Ketua BPH STMIK TIME Medan.

5.

Bapak Prof. Harlem Marpaung, Ph.D, selaku Ketua STMIK TIME Medan.

6.

Bapak Jackri Hendrik, ST, M.Kom, selaku Puket I STMIK TIME Medan.

7.

Bapak Hendri, M.Kom, selaku Ketua Program Studi Teknik Informatika STMIK TIME Medan.

8.

Seluruh Dosen STMIK TIME Medan, yang telah banyak memberikan ilmu pengetahuan kepada penulis selama perkuliahan.

iii

Meskipun telah disusun, penulis menyadari bahwa isi dan teknik penulisan skripsi ini masih memerlukan perbaikan untuk menyempurnakannya baik dari segi tata bahasa manapun materi yang terkandung didalamnya. Oleh karena itu, setiap kritik dan saran akan diterima dengan senang hati agar dapat dijadikan bahan perbaikan untuk penulisan selanjutnya.

Medan, 04 Mei 2015 Penulis

Erwin

iv

DAFTAR ISI

ABSTRAK ..............................................................................................................

i

ABSTRACT .............................................................................................................. ii KATA PENGANTAR ............................................................................................. iii DAFTAR ISI ............................................................................................................ v DAFTAR TABEL ................................................................................................... vii DAFTAR GAMBAR ............................................................................................... viii DAFTAR LAMPIRAN ........................................................................................... x BAB I

PENDAHULUAN ............................................................................ 01 1.1. Latar Belakang Masalah ............................................................. 01 1.2. Identifikasi Masalah ................................................................... 02 1.3. Batasan Masalah ........................................................................ 02 1.4. Tujuan dan Manfaat Penulisan ................................................... 03 1.5. Sistematika Penulisan ................................................................ 04

BAB II

LANDASAN TEORI ....................................................................... 05 2.1. Pengenalan Sistem Bilangan ...................................................... 05 2.2. Bilangan Bulat ........................................................................... 09 2.2.1. Pembagian Bilangan Bulat .............................................. 10 2.2.2. Faktorisasi Pembagi Terbesar ......................................... 12 2.2.3. Algoritma Euclidean ....................................................... 13 2.3. Bilangan Prima .......................................................................... 14 2.3.1. Teorema Fermat .............................................................. 16 2.3.2. Metode Tes Prima ........................................................... 17 2.3.3. Prima Relatif ................................................................... 19 2.4. Bilangan Besar ........................................................................... 19 2.4.1. Penamaan Bilangan Besar ............................................... 19 2.4.2. Penulisan Bilangan Besar ................................................ 21 2.4.3. Penerapan Bilangan Besar ............................................... 22 2.5. Aritmatika Modulo .................................................................... 22 2.5.1. Kongruen dalam Modulo ................................................ 23

v

2.5.2. Invers Modulo .................................................................. 24 2.5.3. Kekongruenan Linier ....................................................... 25 2.6. Chinese Remainder Theorem .................................................... 27 2.6.1. Cara Kerja Chinese Remainder Theorem ........................ 27 2.6.2. Penerapan Chinese Remainder Theorem ........................ 33 BAB III

METODE PENELITIAN ............................................................... 36 3.1. Tempat dan Jadwal Penelitian ................................................... 36 3.2. Kerangka Kerja .......................................................................... 36 3.3. Pengumpulan Data .................................................................... 37 3.4. Analisa Sistem ........................................................................... 38 3.5. Perancangan Sistem ................................................................... 38 3.6. Pembangunan Sistem ................................................................ 39 3.7. Uji Coba Sistem ......................................................................... 39

BAB IV

ANALISA DAN PERANCANGAN ................................................ 40 4.1. Analisa ....................................................................................... 40 4.1.1. Proses Kerja Perangkat Lunak ......................................... 42 4.2. Perancangan ............................................................................... 43 4.2.1. Form Awal ....................................................................... 44 4.2.2. Form Pemahaman ............................................................ 46 4.2.3. Form Input ....................................................................... 46 4.2.4. Form proses ..................................................................... 48 4.2.5. Form Extended Euclidean................................................ 49 4.2.6. Form Pilih Pemain ........................................................... 50 4.2.7. Form Cerita ...................................................................... 51 4.2.8. Form Bermain .................................................................. 51 4.2.9. Form High Score.............................................................. 53 4.2.10. Form About .................................................................... 53 4.3. Perancangan Database ............................................................... 55

BAB V

HASIL DAN PEMBAHASAN ....................................................... 56 5.1. Hasil ............................................................................................ 56 5.2. Algoritma .................................................................................... 70 5.2.1. Algoritma Chinese Remainder ......................................... 70

vi

5.2.2. Algoritma Extended Euclidean ........................................ 74 BAB V1

KESIMPULAN DAN SARAN ....................................................... 75 6.1. Kesimpulan ................................................................................. 75 6.2. Saran ........................................................................................... 76

DAFTAR PUSTAKA LAMPIRAN

vii

DAFTAR GAMBAR

Gambar 2.1.

Sistem Bilangan ................................................................................. 6

Gambar 3.1.

Kerangka kerja ................................................................................... 37

Gambar 4.1.

Diagram Kerja Sistem dari Perangkat Lunak .................................... 40

Gambar 4.2.

Proses Kerja dari Chinese Remainder Theorem ................................ 41

Gambar 4.3.

Rancangan Form Awal ...................................................................... 45

Gambar 4.4

Rancangan Form Pemahaman............................................................ 46

Gambar 4.5.

Rancangan Form Input ...................................................................... 47

Gambar 4.6.

Rancangan Form Proses .................................................................... 48

Gambar 4.7.

Rancangan Form Extended Euclidean ............................................... 49

Gambar 4.8.

Rancangan Form Pilih Pemain .......................................................... 50

Gambar 4.9.

Rancangan Form Cerita ..................................................................... 51

Gambar 4.10. Rancangan Form Bermain ................................................................. 52 Gambar 4.11. Rancangan Form High Score ............................................................. 53 Gambar 4.12. Rancangan Form About ..................................................................... 54 Gambar 4.13. Relationship Tabel Pada Database .................................................... 55 Gambar 5.1.

Tampilan Form Awal ......................................................................... 56

Gambar 5.2.

Tampilan Form Pemahaman ............................................................. 57

Gambar 5.3.

Tampilan Form Input ......................................................................... 58

Gambar 5.4.

Tampilan Form Input Setelah Pengisian Data ................................... 59

Gambar 5.5.

Tampilan Form Proses Langkah 1 ..................................................... 60

Gambar 5.6.

Tampilan Form Proses Langkah 2 ..................................................... 60

Gambar 5.7.

Tampilan Form Proses Langkah 3 ..................................................... 61

Gambar 5.8.

Tampilan Form Proses Langkah 4 ..................................................... 61

Gambar 5.9.

Tampilan Form Proses Langkah Terakhir ......................................... 62

Gambar 5.10. Tampilan Form Proses Perhitungan Invers Modular ......................... 62 Gambar 5.11. Tampilan Form Pesan Pemberitahuan ............................................... 63 Gambar 5.12. Tampilan Form Pilih Pemain ............................................................. 63 Gambar 5.13. Tampilan Form Nama Pemain ........................................................... 64

viii

Gambar 5.14. Tampilan Form Cerita Halaman 1 ..................................................... 64 Gambar 5.15. Tampilan Form Cerita Halaman 2 ..................................................... 65 Gambar 5.16. Tampilan Form Cerita Halaman 3 ..................................................... 65 Gambar 5.17. Tampilan Form Cerita Halaman 4 ..................................................... 66 Gambar 5.18. Tampilan Form Permainan ................................................................ 66 Gambar 5.19. Tampilan Form Detail Permainan...................................................... 67 Gambar 5.20. Tampilan Pesan Pemberitahuan untuk Jawaban Benar...................... 68 Gambar 5.21. Tampilan Pesan Pemberitahuan untuk Jawaban Salah ...................... 68 Gambar 5.22. Tampilan Pesan Pemberitahuan Setelah Selesai Menjawab Semua Langkah.............................................................................................. 68 Gambar 5.23. Tampilan High Score ......................................................................... 69 Gambar 5.24. Tampilan About .................................................................................. 69

ix

DAFTAR TABEL

Tabel 2.1

Perbandingan Penamaan Bilangan dalam Sistem Amerika dan Inggris ................................................................................................... 20

Tabel 3.1

Jadwal Penelititan ................................................................................. 36

Tabel 4.1

Tabel HighScore ................................................................................... 55

Tabel 4.2

Tabel UserList ....................................................................................... 55

x

DAFTAR LAMPIRAN

CD program Surat keputusan dosen pembimbing skripsi Daftar riwayat hidup mahasiswa Listing program

xi

BAB I PENDAHULUAN

1.1.

Latar Belakang Masalah Chinese Remainder Theorem adalah sebuah hasil mengenai kongruen

dalam teori bilangan dan pengembangannya pada aljabar abstrak. Teorema ini pertama kali diperkenalkan oleh seorang ahli matematika China yang bernama Sun Tze pada abad pertama. Bentuk asli dari teorema ini terdapat pada buku abad5 yang berjudul Sunzi’s Mathematical Classic yang ditulis oleh seorang ahli matematika China bernama Sun Tze. Teorema ini diselesaikan oleh Qin Jiu shao pada tahun 1247 dengan menggunakan sebuah aturan yang disebut Da yan shu Penjabaran solusi dari teorema ini terdapat pada buku Mathematical Treatise in Nine Sections. Chinese Remainder Theorem dapat diilustrasikan sebagai berikut, Alkisah seorang Nenek pergi ke pasar dengan membawa keranjang berisi telur.Di pasar keranjang tersebut ditaruh di gerobak, tanpa sengaja seorang pemuda berkuda menabrak nenek tersebut sehingga pecah semua telur yang berada didalam keranjang. Pemuda tersebut berniat menganti kerugian dan bertanya kepada si nenek berapa jumlah telur di keranjang. Akan tetapi si Nenek tidak ingat berapa jumlah telur di keranjang. Si Nenek hanya ingat jika jumlah telur tersebut dibagi 3 maka sisanya 2 telur. Jika dibagi 5 maka sisanya 3 telur dan jika dibagi 7 maka sisanya 2 telur. Pertanyaanya berapa jumlah telur yang dimilik sang nenek. Menurut Sun Tzu untuk variabel a < p dan b < q, dimana p dan q adalah bilangan

1

2

prima, maka terdapat sebuah hasil unik, x, dimana x lebih kecil dari pq, sedemikian sehingga x ≡ a (mod p) dan x ≡ b (mod q). Permainan ini sulit untuk diselesaikan secara manual. Oleh karena itu, penulis mencoba untuk mencari solusi dari permainan ini dengan cara merancang sebuah perangkat lunak yang mampu untuk menyelesaikan permainan tersebut, sekaligus menyediakan interface untuk menyelesaikan permainan tersebut secara manual. Maka penulis mengambil skripsi yang berjudul “Perancangan Perangkat Ajar dengan Permainan Mengenai Chinese Remainder Theorem”.

1.2.

Identifikasi Masalah Berdasarkan latar belakang pemilihan judul di atas, maka yang menjadi

permasalahan adalah : 1. Menampilkan proses penyelesaian dari Chinese Remainder Theorem. 2. Menyediakan

sebuah

interface

yang

memungkinkan

user

untuk

menyelesaikannya secara manual.

1.3.

Batasan Masalah Karena keterbatasan waktu dan pengetahuan penulis, maka ruang lingkup

permasalahan dalam merancang perangkat lunak ini antara lain : 1. Jumlah persamaan modulo yang di-input minimal 2 buah dan maksimal 10 buah, yang berarti bahwa terdapat minimal 2 kali pembagian dan maksimal 10 kali pembagian. 2. Jumlah orang dapat ditentukan dengan batasan antara 2 sampai 99.

3

3. Perangkat lunak akan menampilkan prosedur kerja dari Chinese Remainders Theorem secara tahap demi tahap. 4. Perangkat lunak juga menyediakan daftar 10 nilai tertinggi yang disimpan ke dalam sebuah database yang dibuat dengan aplikasi Microsoft Access 2010. 5. Perangkat lunak dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic.NET 2010. 1.4.

Tujuan dan Manfaat Penulisan Tujuan penyusunan skripsi ini adalah :

1. Membahas proses kerja dari Chinese Remainders Theorem dalam mencari nilai invers modular. 2. Merancang suatu perangkat lunak yang mampu untuk membantu pemahaman terhadap Chinese Remainders Theorem dengan menjelaskan tahapan–tahapan penyelesaiannya. 3. Menyediakan interface untuk bermain Chinese Remainder Theorem secara manual. Manfaat dari penyusunan skripsi ini yaitu : 1. Perangkat lunak hasil rancangan dapat digunakan sebagai fasilitas pendukung dalam proses belajar-mengajar. 2. Perangkat lunak dapat dijadikan sebagai sarana permainan yang sangat menarik dan menghibur. 3. Perangkat lunak dapat dijadikan dasar untuk mengembangkan perangkat lunak permainan berbasis matematika lainnya.

4

1.5.

Sistematika Penulisan Agar pembahasan lebih sistematika maka tulisan ini dibuat dalam enam

bab, yaitu : BAB I

PENDAHULUAN Berisi latar belakang pemilihan judul, identifikasi masalah, tujuan dan manfaat, batasan masalah dan sistematika penulisan.

BAB II

LANDASAN TEORI Berisi tentang penjelasan singkat mengenai topik yang dibahas.

BAB III

METODE PENELITIAN Berisi tentang tempat dan jadwal penelitian, kerangka kerja, metode pengumpulan data, analisa sistem, perancangan sistem, pembangunan sistem, uji coba sistem dan implementasi sistem.

BAB IV

ANALISA DAN PERANCANGAN Berisi tentang pembahasan mengenai proses kerja dan perancangan tampilan antarmuka.

BAB V

ALGORITMA DAN IMPLEMENTASI Berisi tentang algoritma dan implementasi dari perangkat lunak.

BAB VI

KESIMPULAN DAN SARAN Berisi tentang kesimpulan dan saran-saran yang diambil penulis setelah menyelesaikan skripsi.

BAB II LANDASAN TEORI

2.1.

Pengenalan Sistem Bilangan Di dalam sistem bilangan, yang paling sederhana adalah bilangan asli yaitu

1, 2, 3, 4, 5, …. Jika menggabungkan bentuk negatif bilangannya dan nol, maka akan diperoleh bilangan bulat yaitu …, -2, -1, 0, 1, 2, …. Untuk keperluan tertentu seperti pengukuran panjang, berat atau tegangan listrik, bilangan-bilangan bulat tidak memadai. Bilangan ini tidak mampu untuk memberikan ketelitian yang cukup. Oleh karena itu diperlukan untuk mempertimbangkan hasil bagi (rasio) dari bilangan-bilangan bulat seperti ¾, ½, dan sebagainya. Bilangan-bilangan yang dapat dituliskan dalam bentuk m/n dimana m dan n adalah bilangan-bilangan bulat dengan n ≠ 0, disebut bilangan rasional. Bilangan-bilangan rasional tidak berfungsi untuk mengukur semua panjang. Fakta yang mengejutkan ini ditemukan oleh orang Yunani kuno beberapa abad sebelum Masehi. Mereka memperlihatkan bahwa meskipun √2 merupakan panjang sisi miring sebuah segitiga siku-siku dengan sisi-sisi 1, bilangan ini tidak dapat dituliskan sebagai suatu hasil bagi dari dua bilangan bulat. Jadi √2 adalah suatu bilangan tak rasional. Demikian juga bentuk-bentuk akar lainnya. Sekumpulan bilangan rasional dan tak rasional yang dapat mengukur panjang, bersama-sama dengan bentuk negatif bilangannya dan nol dinamakan bilangan riil. Bilangan-bilangan riil dapat dipandang sebagai pengenal (label) untuk titik-titik sepanjang sebuah garis mendatar. Di sana bilangan-bilangan ini

5

6

mengukur jarak ke kanan atau ke kiri (jarak berarah) dari suatu titik tetap yang disebut titik asal dan diberi label 0. Walaupun tidak mungkin memperlihatkan semua label itu tiap titik memang mempunyai sebuah label tunggal bilangan riil. Bilangan ini disebut koordinat titik tersebut. Dan garis koordinat yang dihasilkan diacu sebagai garis riil.

Bilangan Kompleks

Bilangan Riil

Bilangan Khayal

Bilangan Irrasional

Bilangan Rasional

Bilangan Bulat

Bilangan Bulat (-)

Bilangan Pecahan

Bilangan Cacah

Bilangan Prima

Tak Murni

Murni

Bilangan Bulat (+)

Nol

(+)

Bilangan NonPrima

Gambar 2.1 Sistem Bilangan Sumber : Besari, 2010: 5

(-)

(+)

(-)

7

Sistem bilangan masih dapat diperluas lebih jauh lagi ke bilangan yang disebut bilangan kompleks. Bilangan-bilangan ini berbentuk a + b√-1, dimana a dan b adalah bilangan-bilangan riil. Dalam matematika, bilangan kompleks adalah bilangan yang berbentuk

dimana a dan b adalah bilangan riil, dan i adalah bilangan imajiner tertentu yang mempunyai sifat i

2

= −1. Bilangan riil a disebut juga bagian riil dari bilangan

kompleks, dan bilangan real b disebut bagian imajiner. Jika pada suatu bilangan kompleks, nilai b adalah 0, maka bilangan kompleks tersebut menjadi sama dengan bilangan real a. Bilangan kompleks dapat ditambah, dikurang, dikali, dan dibagi seperti bilangan riil; namun bilangan kompleks juga mempunyai sifat-sifat tambahan yang menarik. Misalnya, setiap persamaan aljabar polinomial mempunyai solusi bilangan kompleks, tidak seperti bilangan riil yang hanya memiliki sebagian. Bilangan riil atau bilangan real dalam matematika menyatakan bilangan yang bisa dituliskan dalam bentuk desimal, seperti 2,4871773339… atau 3,25678. Bilangan riil meliputi bilangan rasional, seperti 42 dan −23/129, dan bilangan irasional, seperti π dan

. Bilangan rasional direpresentasikan dalam

bentuk desimal berakhir, sedangkan bilangan irasional memiliki representasi desimal tidak berakhir namun berulang. Bilangan riil juga dapat direpresentasikan sebagai salah satu titik dalam garis bilangan. Bilangan imajiner (imaginary number) adalah bilangan yang mempunyai sifat i

2

= −1. Bilangan ini biasanya merupakan bagian dari bilangan kompleks.

Selain bagian dari bilangan kompleks, bilangan imajiner merupakan bagian

8

bilangan riil. Secara definisi, (bagian) bilangan imajiner ini diperoleh dari penyelesaian persamaan kuadratik:

atau secara ekuivalen

atau juga sering dituliskan sebagai . Bilangan rasional adalah bilangan yang dapat dinyatakan sebagai a/b dimana a, b bilangan bulat dan b tidak sama dengan 0. dimana batasan dari bilangan rasional adalah mulai dari selanga (-∞, ∞). Bilangan bisa dikatakan dapat dibagi menjadi 2 sekup besar yaitu bilangan rasional dan bilangan irasional. Bila dikatakan bilangan rasional berarti di dalamnya sudah mencakup bilangan-bilangan lain seperti: bilangan bulat, bilangan asli, bilangan cacah, bilangan prima dan bilangan-bilangan lain yang menjadi subset dari bilangan rasional. Dalam matematika, bilangan irasional adalah bilangan riil yang tidak bisa dibagi (hasil baginya tidak pernah berhenti). Dalam hal ini, bilangan irasional tidak bisa dinyatakan sebagai a/b, dengan a dan b sebagai bilangan bulat dan b tidak sama dengan nol. Jadi bilangan irasional bukan merupakan bilangan rasional. Contoh yang paling populer dari bilangan irasional ini adalah bilangan π, , dan bilangan e. Bilangan bulat terdiri dari bilangan cacah (0, 1, 2, 3, ...) dan negatifnya (-1, -2, -3, ...; -0 adalah sama dengan 0 sehingga tidak lagi dimasukkan secara terpisah). Bilangan bulat dapat dituliskan tanpa komponen desimal atau pecahan.

9

Pecahan terdiri dari pembilang dan penyebut. Hakikat transaksi dalam bilangan pecahan adalah bagaimana cara menyederhanakan pembilang dan penyebut. Penyederhanaan pembilang dan penyebut akan memudahkan dalam operasi aritmetika sehingga tidak menghasilkan angka yang terlalu besar tetapi tetap mempunyai nilai yang sama. Contohnya: bila dibandingkan antara 50/100 dan ½ maka lebih mudah dan sederhana melihat angka ½. Jika 50/100 terlihat sebagai ”angka raksasa” yang kelihatannya lebih kompleks dibandingkan ½, padahal sebenarnya kedua angka ini tetap memiliki nilai yang sama. Pada operasi penjumlahan dan pengurangan pada pecahan selain disederhanakan juga penyebutnya harus disamakan dengan bilangan yang sama, sedangkan pada operasi perkalian caranya adalah pembilang dikali pembilang, penyebut dikali penyebut. dan dalam operasi pembagian, pecahan yang di kanan dibalikkan, setelah dibalikkan, tanda : diubah menjadi tanda kali (X), seperti 3/4 : 5/6 = 3/4 X 6/5 = 18/20 = 9/10. Bilangan cacah adalah himpunan bilangan bulat yang tidak negatif, yaitu {0, 1, 2, 3 ...}. Dengan kata lain himpunan bilangan asli ditambah 0. Bilangan cacah selalu tidak bertanda negatif.

2.2.

Bilangan Bulat Menurut Munir (2014: 183), “bilangan bulat adalah bilangan yang tidak

mempunyai pecahan desimal, misalnya 8, 21, 8675, - 34, 0 dan sebagainya. Lawan dari bilangan bulat adalah bilangan riil yang mempunyai titik desimal, seperti 8.0, 34.25, dan sebagainya”.

10

2.2.1. Pembagian Bilangan Bulat Sifat pembagian pada bilangan bulat melahirkan konsep-konsep seperti bilangan prima, dan aritmetika modulo. Salah satu algoritma penting yang berhubungan dengan sifat pembagian ini adalah algoritma Euclidean. Baik bilangan prima, aritmetika modulo dan algoritma Euclidean memainkan peranan yang penting dalam bidang kriptografi, yaitu ilmu yang mempelajari kerahasiaan pesan. Menurut Munir (2014: 183), definisi pembagian pada bilangan bulat dapat dijabarkan sebagai berikut : Misalkan a dan b adalah dua buah bilangan bulat dengan syarat b ≠ 0, maka dapat dinyatakan bahwa a habis dibagi b jika terdapat bilangan bulat c sedemikian sehingga a = bc. Definisi di atas dapat dinyatakan dalam bentuk notasi berikut : Notasi : a | b jika a = bc, c ∈ Z; Z adalah bilangan bulat. Dengan perkataan lain, jika a dibagi dengan b, maka hasil pembagiannya berupa bilangan bulat. Kadang-kadang pernyataan “a habis dibagi b” dapat ditulis juga sebagai “a kelipatan b”. Contoh 12| 4. Secara umum, jika hasil pembagian bilangan bulat dinyatakan sebagai bilangan bulat juga, maka sembarang bilangan bulat bila dibagi dengan suatu bilangan bulat positif, akan selalu terdapat hasil bagi dan sisa pembagian. Misalnya 13 / 4 memberikan hasil bagi 3 dan sisa 1. Kasus khusus, jika a habis dibagi b, maka sisa pembagian adalah 0, misalnya 12 / 4 memberikan hasil bagi 3 dan sisa 0. Perhatikan juga bahwa sisa hasil pembagian selalu lebih besar atau sama dengan nol tetapi lebih kecil dari pembagi. Sifat ini dapat dituangkan dalam teorema berikut :

11

Teorema 2.1 : Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder), sedemikian sehingga : m = nq + r dengan 0 ≤ r < n. Teorema ini sering disebut juga teorema Euclidean, yang diambil dari nama ilmuwan Yunani yang bernama Euclid. Bilangan n disebut pembagi (divisor), m disebut yang dibagi (dividend), q disebut hasil bagi (quotient) dan r disebut sisa (remainder). Notasi yang digunakan untuk mengekspresikan hasil bagi dan sisa adalah dengan menggunakan operator mod dan div seperti berikut : q = m div n r = m mod r Contoh : − 1987 jika dibagi dengan 97 akan memberikan hasil bagi 20 dan sisa 47. Maka, dapat dituliskan bahwa : 1987 = 97 . 20 + 47 Atau diekspresikan sebagai 1987 div 97 = 20 dan 1987 mod 97 = 47. − Begitu juga, jika – 22 dibagi dengan 3 dapat dituliskan sebagai : – 22 = 3(– 8) + 2 Atau diekspresikan sebagai – 22 div 3 = – 8 dan – 22 mod 3 = 2. Satu hal yang perlu diperhatikan yaitu bahwa sisa pembagian tidak boleh negatif, jadi tidak boleh ditulis : – 22 = 3(– 7) – 1 Karena r = – 1 tidak memenuhi syarat 0 ≤ r < n.

12

Contoh lainnya, jika 24 dibagi dengan 3, maka dapat dituliskan : 24 = 3 . 8 + 0 Karena r = 0 memenuhi syarat 0 ≤ r < n. (Munir, 2014: )

2.2.2. Faktorisasi Pembagi Terbesar Menurut Munir (2014: 185), Dua buah bilangan bulat dapat memiliki faktor pembagi yang sama. Faktor pembagi bersama yang terpenting adalah faktorisasi pembagi terbesar (greatest common divisor atau GCD). Contoh : 45 memiliki faktor pembagi 1, 3, 5, 9, 15 dan 45 sendiri. 36 memiliki faktor pembagi 1, 2, 3, 4, 9, 12, 18 dan 36 sendiri. Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9. Yang terbesar adalah 9 sehingga GCD(45, 36) = 9. Definisi formal dari GCD ini dapat dinyatakan sebagai berikut : Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini, dapat dinyatakan bahwa GCD(a, b) = d. Sifat-sifat dari pembagi bersama terbesar dapat dilihat pada teorema 2.2 berikut : Teorema 2.2 : Misalkan a, b dan c adalah bilangan bulat : a. Jika c adalah GCD dari a dan b, maka c | (a + b). b. Jika c adalah GCD dari a dan b, maka c | (a – b). c. Jika c | a, maka c | ab.

13

Dari teorema 2.1 di atas, jika ingin ditunjukkan bahwa GCD dari dua buah bilangan bulat sama dengan GCD dari salah satu bilangan bulat tersebut dengan sisa hasil pembagiannya. Hal ini dapat dinyatakan pada Teorema 2.3 berikut : Teorema 2.3 : Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n > 0 sedemikian sehingga : m = nq + r, 0 ≤ r < n. maka GCD(m, n) = GCD(n, r).

2.2.3. Algoritma Euclidean Menurut Munir (2014: 187), “Algoritma Euclidean merupakan salah satu metode yang efisien untuk menemukan GCD”. Algoritma Euclidean sudah dikenal sejak berabad-abad yang lampau. Euclid, penemu Algoritma Euclidean, adalah seorang ahli matematika Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element. Algoritma Euclidean didasarkan pada Teorema 2.3 secara berturut-turut sampai ditemukan sisa pembagian bernilai nol. Secara formal, Algoritma Euclidean ini dapat dirumuskan sebagai berikut : Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n. Misalkan r0 = m dan r1 = n. Lakukan secara berturut-turut pembagian untuk memperoleh : r0 = r1q1 + r2

0 ≤ r2 ≤ r1,

r1 = r2q2 + r3

0 ≤ r3 ≤ r2,

… rn – 2 = rn – 1qn – 1 + rn rn – 1 = rnqn + 0

0 ≤ rn ≤ rn – 1,

14

Menurut Teorema 2.3 : GCD(m, n) = GCD(r0, r1) = GCD(r1, r2) = … = GCD(rn – 2, rn – 1) = GCD(rn – 1, rn) = GCD(rn, 0) = rn Berarti, GCD dari m dan n adalah sisa terakhir yang tidak nol dari deretan pembagian tersebut. Jika diberikan dua buah bilangan bulat tak-negatif m dan n (m ≥ n), maka Algoritma Euclidean berikut dapat mencari pembagi bersama terbesar dari kedua bilangan tersebut, yaitu bilangan bulat positif terbesar yang habis membagi m dan n. Algoritma Euclidean : 1. Jika n = 0, maka : GCD(m, n)=m; stop. tetapi jika n ≠ 0, lanjutkan ke langkah 2. 2. Bagilah m dengan n dan misalkan r adalah sisanya. 3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1. Catatan : jika m ≤ n, maka pertukarkan terlebih dahulu nilai m dan n.

2.3.

Bilangan Prima Bilangan bulat positif yang mempunyai aplikasi penting dalam ilmu

komputer dan matematika diskrit adalah bilangan prima. Bilangan prima adalah

15

bilangan bulat positif yang lebih besar dari 1, yang hanya habis dibagi oleh 1 dan dirinya sendiri. Menurut Munir (2014: 200), bilangan prima dapat didefinisikan sebagai berikut : ”Bilangan bulat positif p, dengan p > 1 disebut bilangan prima jika pembaginya hanya 1 dan p”. Contoh : 2, 3, 5, 7, 11, 13, … Seluruh bilangan prima adalah bilangan ganjil, kecuali 2 yang merupakan bilangan genap. Bilangan selain prima disebut bilangan komposit (composite). Misalnya 20 adalah bilangan komposit karena 20 dapat dibagi oleh 2, 4, 5 dan 10, selain 1 dan 20 sendiri. Teorema penting yang menyangkut bilangan prima dinyatakan oleh teorema yang terkenal dalam teori bilangan, yaitu teorema fundamental aritmetik, yang bunyinya adalah sebagai berikut : Teorema 2.4 : Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Teorema di atas menyatakan bahwa baik bilangan prima maupun bilangan komposit, keduanya dapat dinyatakan sebagai perkalian dari satu atau lebih faktor prima. Misalnya : − 9 = 3 x 3. − 100 = 2 x 2 x 5 x 5. Masalah lain yang juga penting adalah menguji apakah sebuah bilangan merupakan prima atau bukan. Sembarang bilangan bulat positif habis dibagi oleh faktor-faktor primanya. Faktor prima dari sebuah bilangan selalu lebih kecil atau

16

sama dengan akar kuadrat dari bilangan tersebut. Hal ini mudah ditunjukkan sebagai berikut : Misalkan a adalah faktor prima dari n, dengan 1 < a < n, maka a habis membagi n dengan hasil bagi b sedemikian sehingga n = ab. Nilai a dan b haruslah ≤ n, agar : ab > √n . √n = n Dengan perkataan lain, faktor prima dari n selalu lebih kecil atau sama dengan √n. Hal ini dinyatakan dengan teorema berikut : Teorema 2.5 : Jika n adalah bilangan komposit, maka n mempunyai faktor prima yang lebih kecil atau sama dengan √n. Untuk menguji apakah n merupakan bilangan prima atau komposit, cukup membagi n dengan sejumlah bilangan prima, mulai dari 2, 3, …, bilangan ≤ √n. Jika n habis dibagi dengan salah satu dari bilangan prima tersebut, maka n adalah bilangan komposit, tetapi jika n tidak habis dibagi oleh semua bilangan prima tersebut, maka n adalah bilangan prima.

2.3.1. Teorema Fermat Menurut Munir (2014: 202), Menguji keprimaan suatu bilangan bulat n dengan cara membaginya dengan sejumlah bilangan prima yang ≤ √n tentu tidak efisien untuk n yang besar, karena harus ditentukan terlebih dahulu semua bilangan prima yang lebih kecil dari √n. Metode lainnya yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat dikenal dengan nama Teorema Fermat (kadang-kadang dinamakan juga Fermat’s Little Theorem).

17

Teorema ini diperkenalkan oleh Pierre de Fermat, seorang ahli matematika berkebangsaan Prancis pada tahun 1640. Teorema ini dapat dinyatakan sebagai berikut : Jika p adalah bilangan prima dan a bukan kelipatan dari p, maka dapat dinyatakan bahwa : ap – 1 ≡ 1 (mod p)

2.3.2. Metode Tes Prima Menurut Schneier (2007: 259-260), metode-metode yang dapat digunakan untuk tes peluang prima antara lain: 1. Solovay-Strassen Robert Solovay dan Volker Strassen merancang suatu algoritma untuk mengetes bilangan prima. Algoritma ini menggunakan simbol Jacobi untuk melakukan pengetesan seperti berikut : a. Pilih suatu bilangan acak a, yang lebih kecil dari p. b. Jika gcd(a,p) ≠ 1 maka p gagal tes dan nilainya dibalik. c. Hitung j = a(p-1)/2 mod p. d. Hitung simbol Jacobi J(a,p). e. Jika j ≠ J(a,p) maka p pasti bukan bilangan prima. f. Jika j = J(a,p) maka p bukan bilangan prima memiliki persentase kemungkinan tidak lebih dari 50 %. 2. Lehmann Tes sederhana lainnya juga dirancang secara terpisah dan independen oleh Lehmann. Algoritma pengetesannya adalah sebagai berikut :

18

a. Pilih suatu bilangan acak a, yang lebih kecil dari p. b. Hitung a(p-1)/2 mod p. c. Jika a(p-1)/2 mod p ≡ 1 atau -1 (mod p) maka p pasti bukan bilangan prima. d. Jika a(p-1)/2 mod p ≡ 1 atau -1 (mod p) maka kemungkinan p bukan bilangan prima tidak lebih dari 50 %. 3. Rabin-Miller Algoritma sederhana yang digunakan oleh semua orang dirancang oleh Michael Rabin dengan berdasarkan beberapa ide dari Gary Miller. Algoritma pengetesan ini adalah seperti berikut : a. Pilih bilangan acak p untuk dites. b. Hitung b, dimana b adalah banyaknya (p – 1) dibagi 2 (yaitu, b adalah pangkat terbesar dari 2, sedemikian sehingga 2b merupakan faktor dari p – 1). c. Kemudian hitung m, sedemikian sehingga p = 1 + 2b.m d. Pilih bilangan acak a sedemikian sehingga a lebih kecil daripada p. e. Set j = 0 dan set z = am mod p. f. Jika z = 1 atau jika z = p – 1, maka p lolos tes dan mungkin bilangan prima. g. Jika j > 0 dan z = 1, maka p bukan bilangan prima. h. Set j = j + 1. Bila j < b dan z ≠ p – 1, set z = z2 mod p dan kembali ke tahap d. Jika z = p – 1, maka p lolos tes dan mungkin prima. i. Jika j = b dan z ≠ p – 1, maka p bukan bilangan prima.

19

2.3.3. Prima Relatif Menurut Munir (2014: 190)Dua buah bilangan dikatakan relatif prima jika mereka tidak memiliki faktor prima yang sama kecuali 1. Dengan perkataan lain, jika GCD dari a dan n adalah sama dengan satu, maka a dan n adalah relatif prima. Bentuk ini dapat ditulis sebagai GCD(a, n) = 1.

2.4.

Bilangan Besar Rubrik Bahasa,( 27 Februari 2009 ) Bilangan besar adalah bilangan yang

lebih besar daripada bilangan yang digunakan dalam kehidupan sehari-hari, seperti dalam perhitungan sederhana atau dalam transaksi moneter. Bentuk yang digunakan dalam kehidupan sehari-hari umumnya berupa bilangan besar integer positif ataupun bilangan besar real. Googol adalah sebuah bilangan 1 yang diikuti oleh 100 buah bilangan nol dibelakangnya. Bilangan ini dapat dituliskan dengan menggunakan eksponen yaitu 10100. Bilangan yang lebih besar daripada bilangan googol adalah googolplex yaitu 10 pangkat bilangan googol atau 10^(10100), yaitu bilangan 1 yang diikuti oleh bilangan nol sebanyak bilangan googol.

2.4.1. Penamaan Bilangan Besar Daryl Haviz(10 Maret 2011) Penamaan bilangan dapat menggunakan dua buah sistem yaitu sistem Amerika dan sistem Inggris seperti dijabarkan pada tabel berikut ini :

20

Tabel 2.1 Perbandingan Penamaan Bilangan dalam Sistem Amerika dan Inggris 10n

Sistem Amerika

Sistem Inggris

6

million

million

9

billion

milliard

12

trillion

billion

15

quadrillion

billiard

18

quintillion

trillion

21

sextillion

trilliard

24

septillion

quadrillion

27

octillion

quadrilliard

30

nonillion

quintillion

33

decillion

quintilliard

36

undecillion

sextillion

39

duodecillion

sextilliard

42

tredecillion

septillion

45

quattuordecillion

septilliard

48

quindecillion

octillion

51

sexdecillion

octilliard

54

septendecillion

nonillion

57

octodecillion

nonilliard

21

60

novemdecillion

decillion

63

vigintillion

decilliard

66

unvigintillion

undecillion

69

duovigintillion

undecilliard

72

trevigintillion

duodecillion

75

quattuorvigintillion

duodecilliard

78

quinvigintillion

tredecillion

81

sexvigintillion

tredecilliard

84

septenvigintillion

quattuordecillion

87

octovigintillion

quattuordecilliard

90

novemvigintillion

quindecillion

93

trigintillion

quindecilliard

96

untrigintillion

sexdecillion

99

duotrigintillion

sexdecilliard

2.4.2. Penulisan Bilangan Besar Rubrik Bahasa,( 27 Februari 2009 )

Bilangan sangat besar umumnya

dituliskan dengan menggunakan scientific notation. Scientific notation diciptakan untuk mengatasi nilai-nilai yang muncul dalam ilmu sains yang memiliki range sangat luas. Sebagai contoh, 1.0 x 109 yang berarti one billion, yaitu sebuah bilangan 1 yang diikuti oleh sembilan buah bilangan 0 seperti berikut 1 000 000 000, dan 1.0 × 10−9 berarti one billionth, atau 0.000 000 001.

22

2.4.3. Penerapan Bilangan Besar Bilangan sangat besar sering ditemukan dalam bidang ilmu seperti matematika, kosmologi dan kriptografi. Kadang-kadang orang menyebut bilangan ini sebagai bilangan yang “sangat besar secara astronomi”. Namun sebenarnya sangat mudah untuk mendefinisikan secara matematis bilangan yang lebih besar daripada bilangan yang digunakan dalam astronomi. Beberapa contoh penerapan bilangan besar yang sering ditemukan adalah sebagai berikut : 1. Jumlah perokok di Amerika Serikat dalam setahun yaitu sekitar 1012 (disebut one trillion). 2. Jumlah bit dalam sebuah hard disk komputer yang paling besar yang dapat ditemukan sekarang adalah sekitar 2 TeraByte lebih. 3. Jumlah sel dalam tubuh manusia, yang berjumlah lebih besar daripada 1014. 4. Jumlah koneksi neuron dalam otak manusia, berjumlah maksimal 1014. 5. Bilangan Avogadro seperti jumlah atom dalam 12 gram Carbon-12 (C12) yaitu sekitar 6,022 x 1023.

2.5.

Arimatika Modulo Aritmatika modulo (modular arithmetic) memainkan peranan yang

penting dalam komputasi integer, khususnya pada aplikasi kriptografi. Operator yang digunakan pada aritmetika modulo adalah mod. Operator mod memberikan sisa pembagian. Misalnya 23 dibagi 5 memberikan hasil = 4 dan sisa = 3, sehingga ditulis 23 mod 5 = 3.

23

Menurut Munir(2014: 191), definisi dari operator mod dapat dinyatakan sebagai berikut : ”Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi a mod m memberikan sisa jika a dibagi dengan m. Dengan kata lain, a mod m = r sedemikian sehingga a = mq + r, dengan 0 ≤ r < m”. Bilangan m disebut modulus atau modulo dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}. Jika a mod m = 0, maka dikatakan bahwa a adalah kelipatan dari m, yaitu a habis dibagi dengan m. Misalnya 27 mod 3 = 0, berarti 27 adalah kelipatan 3.

2.5.1. Kongruen dalam Modulo Menurut Munir (2014: 192)Kadang-kadang dua buah bilangan bulat, a dan b, mempunyai sisa yang sama jika dibagi dengan bilangan bulat positif m. Hal itu dapat dikatakan bahwa a dan b kongruen dalam modulo m dan dilambangkan sebagai : a ≡ b (mod m) Jika a tidak kongruen dengan b dalam modulus m maka ditulis : a ≡ b (mod m) Definisi formal dari kekongruenan dinyatakan sebagai berikut : Misalkan a dan b adalah bilangan bulat dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b. Kekongruenan a ≡ b (mod m) dapat pula dituliskan dalam hubungan : a = b + km yang dalam hal ini sembarang k adalah bilangan bulat.

24

Berdasarkan definisi aritmetika modulo, maka dapat dituliskan a mod m = r sebagai : a ≡ r (mod m) Sifat-sifat pengerjaan hitung pada aritmetika modulo khususnya terhadap operasi perkalian dan penjumlahan dapat dinyatakan dalam Teorema 2.6 berikut : Teorema 2.6 : Misalkan m adalah bilangan bulat positif : 1. Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat maka : i.

(a + c) ≡ (b + c) (mod m)

ii.

ac ≡ bc (mod m)

iii.

ap ≡ bp (mod m), untuk suatu bilangan bulat positif p.

2. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka : i.

(a + c) ≡ ( b + d) (mod m)

ii.

ac ≡ bd (mod m)

2.5.2. Invers Modulo Menurut Munir (2014: 194)Di dalam aritmetika bilangan riil, invers dari perkalian adalah pembagian. Misalnya invers dari 4 adalah ¼, karena 4 x ¼ = 1. Di dalam aritmetika modulo, masalah menghitung invers modulo lebih rumit. Jika a dan m relatif prima dan m > 1, maka dapat ditemukan invers dari a modulo m. Invers dari a modulo m adalah bilangan bulat a-1 sedemikian sehingga: a . a-1 ≡ 1 (mod m) Pembuktian invers modulo ini sangat mudah seperti terlihat pada penjabaran berikut ini : GCD(a, m) = 1.

25

pa + qm = 1, yang mengimplikasikan bahwa pa + qm ≡ 1 (mod m). Karena qm ≡ 1 (mod m), maka : pa ≡ 1 (mod m) Kekongruenan ini berarti bahwa p adalah invers dari a modulo m. Metode yang sering digunakan untuk mencari invers modulo adalah algoritma Euclidean yang diperluas (extended Euclidean algorithm). Langkahlangkah dari algoritma ini dalam mencari nilai x yang memenuhi persamaan a-1 ≡ x (mod n) adalah seperti berikut : 1. Bentuk Array A[3x2] dimana A[1,1] = n dan A[1,2] = a 2. Isikan A[2,1] .. A[3,2] dengan matriks Identitas. 3. Hitung bilangan bulat m dengan kondisi m * A[1,2] ≤ A[1,1]; usahakan m maksimum. 4. Hitung Xt = A[1,1] - m * A[1,2]. 5. Ubah nilai A[1,1] = A[1,2] dan A[1,2] = Xt. 6. Lakukan langkah 4 dan 5 untuk baris kedua dan ketiga dari array A. 7. Ulang langkah 3 sampai 5 hingga elemen terakhir dari baris 1 = 0. 8. Jika A[3,1] ≥ 0 maka x = A[3,1] sebaliknya x = A[3,1] + n.

2.5.3. Kekongruenan Lanjar Menurut Munir (2014: 197)Kekongruenan lanjar adalah kongruen yang berbentuk : ax ≡ b (mod m) dengan m adalah bilangan bulat positif, a dan b adalah sembarang bilangan bulat, dan x adalah peubah. Bentuk kongruen linier berarti menentukan nilai-nilai x yang

26

memenuhi kekongruenan tersebut. Metode yang sederhana untuk mencari nilainilai x tersebut adalah sebagai berikut : ax = b + km yang dapat disusun menjadi : x = (b + km) / a dengan k adalah sembarang bilangan bulat. Cobalah nilai-nilai k = 0, 1, 2, … dan k = -1, -2, … ke dalam persamaan yang terakhir untuk menghasilkan x sebagai bilangan bulat. Metode lain untuk mencari solusi kekongruenan linier adalah dengan menggunakan invers modulo. Caranya serupa dengan pencarian solusi pada persamaan linier biasa, seperti pada : 4x = 12 Untuk mencari solusi persamaan di atas, kalikan kedua ruas dengan invers perkalian dari 4, yaitu ¼, ¼ . 4x = ¼ . 12 x=3 Terapkan metode seperti ini pada kekongruenan linier pada : 4x ≡ 3 (mod 9) Kalikan kedua ruas dengan invers dari 4 (mod 9), yang dapat dicari dengan menggunakan algoritma Extended Euclidean, dan hasil yang diperoleh adalah – 2. – 2 . 4x ≡ – 2 . 3 (mod 9) – 8x ≡ – 6 (mod 9) Karena – 8 ≡ 1 (mod 9), maka : x ≡ – 6 (mod 9)

27

2.6.

Chinese Remainder Theorem Menurut Munir (2014: 199), Pada abad pertama, seorang ahli matematika

Tiongkok yang bernama Sun Tze mengajukan pertanyaan sebagai berikut : “Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7”. Pertanyaan Sun Tze dapat dirumuskan ke dalam sistem kongruen linier : x ≡ 3 (mod 5) x ≡ 5 (mod 7) x ≡ 7 (mod 11) Teorema Chinese Remainder berikut akan digunakan untuk menemukan solusi sistem kongruen linier seperti di atas : Teorema 2.7 : Misalkan m1, m2, …, mn adalah bilangan bulat positif sedemikian sehingga GCD(mi, mj) = 1 untuk i ≠ j. Maka sistem kongruen linier : x ≡ ak (mod mk) mempunyai sebuah solusi unik dalam modulo m = m1 . m2 . … . mn.

2.6.1. Cara Kerja Chinese Remainder Theorem hendry_dext,(8 mei 2010)Proses penyelesaian sebuah sistem kongruen linier dengan menggunakan Chinese Remainder Theorem dapat dibagi menjadi beberapa 2 tahapan, yaitu : 1. Proses pencarian nilai invers modulo dengan menggunakan algoritma Extended Euclidean. 2. Proses pencarian hasil dari sistem kongruen linier dengan menggunakan bantuan hasil nilai invers modulo yang diperoleh.

28

Selain itu Chinese Remainder Theorem juga menggunakan teknik matematika dasar yang digunakan untuk menyelesaikan sistem persamaan linier, yaitu sistem substitusi persamaan. Secara garis besar, cara kerja dari Chinese Remainder Theorem ini adalah sebagai berikut : 1. Ubahlah kongruen linier pertama x ≡ b1 (mod m1) ke dalam hubungan x = b1 + m1.k1. 2. Substitusikan bentuk hubungan kongruen linier pertama tersebut ke dalam kongruen linier kedua, yang dapat dijabarkan seperti berikut : x

≡ b2 (mod m2)

b1 + m1.k1

≡ b2 (mod m2)

m1.k1

≡ (b2 – b1) (mod m2)

Jika bentuk (b2 – b1) (mod m2) yang dihasilkan tidak valid, maka ubahlah ke bentuk valid. Bentuk valid dari kongruen linier harus memenuhi persyaratan bahwa nilai sisa modulo harus lebih kecil daripada nilai bilangan modulo. Dalam hal ini, nilai (b2 – b1) harus lebih kecil daripada nilai m2. Jika tidak valid, maka nilai (b2 – b1) harus di-modulo nilai m2. Hasil modulo menggantikan nilai (b2 – b1) tersebut. Sehingga, proses dapat dilanjutkan seperti berikut : Jika (b2 – b1) < m2 maka h = (b2 – b1) Jika tidak, h = (b2 – b1) mod m2 m1.k1

≡ h (mod m2)

29

≡ h (mod m2) . m1-1 (mod m2)

k1

Bagian bercetak tebal tersebut dapat dicari dengan menggunakan algoritma Extended Euclidean. Misalkan m1-1 (mod m2) = z, maka : ≡ h . z (mod m2)

k1

Sama seperti proses di atas, jika bentuk h . z (mod m2) yang dihasilkan tidak valid, maka ubahlah ke bentuk valid. Sehingga, proses dapat dilanjutkan seperti berikut : Jika h . z < m2 maka g=h.z Jika tidak, g = h . z mod m2 k1

≡ g (mod m2) ; atau :

k1

= g + m2.k2

3. Substitusikan hasil yang didapat ke dalam bentuk hubungan kongruen linier pertama, seperti dijabarkan berikut ini : x = b1 + m1.k1 x = b1 + m1.(g + m2.k2) x = b1 + m1.g + m1.m2.k2 x = (b1 + m1.g) + (m1.m2).k2 4. Ulangi langkah (2) dan (3) di atas untuk semua kongruen linier lainnya hingga kongruen linier terakhir (misalkan = n), didapatkan : x = (bn – 1 + mn – 1.g) + (mn – 1.mn).kn 5. Hasil yang memenuhi sistem kongruen linier adalah sebesar (bn – 1 + mn – 1.g). Agar dapat lebih memahaminya, diberikan sebuah contoh sederhana berikut :

30

Soal : X ≡ 37 (mod 83) X ≡ 73 (mod 6007) X ≡ 73 (mod 18307) X ≡ 2251 (mod 75781) X ≡ 7193 (mod 7817)

Penyelesaian : Persamaan 1 : X ≡ 37 (mod 83) Berarti x = 37 + 83k1 untuk beberapa nilai k1

Substitusikan ke dalam kongruen 2 menjadi : X

≡ 73 (mod 6007)

37 + 83k1

≡ 73 (mod 6007)

83k1

≡ 36 (mod 6007)

k1

≡ 36 (mod 6007) . 83-1 (mod 6007)

k1

≡ 36 (mod 6007) . 579

k1

≡ 20844 (mod 6007){bentuk tidak valid}

k1

≡ 2823 (mod 6007) {bentuk valid}

atau : k1 = 2823 + 6007k2 untuk beberapa nilai k2

Jadi, didapatkan : X = 37 + 83k1

31

= 37 + 83(2823 + 6007k2) = 37 + 234309 + 498581k2 X = 234346 + 498581k2; yang memenuhi 2 kongruen pertama

Substitusikan ke dalam kongruen 3 menjadi : X

≡ 73 (mod 18307)

234346 + 498581k2

≡ 73 (mod 18307)

498581k2

≡ -234273 (mod 18307) {bentuk tidak valid}

498581k2

≡ 3718 (mod 18307) {bentuk valid}

k2

≡ 3718 (mod 18307) . 498581-1 (mod 18307)

k2

≡ 3718 (mod 18307) . 2427

k2

≡ 9023586 (mod 18307){bentuk tidak valid}

k2

≡ 16542 (mod 18307) {bentuk valid}

atau : k2 = 16542 + 18307k3 untuk beberapa nilai k3

Jadi, didapatkan : X = 234346 + 498581k2 = 234346 + 498581(16542 + 18307k3) = 234346 + 8247526902 + 9127522367k3 X = 8247761248 + 9127522367k3; yang memenuhi 3 kongruen pertama

Substitusikan ke dalam kongruen 4 menjadi : X

≡ 2251 (mod 75781)

32

8247761248 + 9127522367k3

≡ 2251 (mod 75781)

9127522367k3

≡ -8247758997 (mod 75781) {bentuk tidak valid}

9127522367k3

≡ 17700 (mod 75781) {bentuk valid}

k3 ≡ 17700 (mod 75781) . 9127522367-1 (mod 75781) k3 ≡ 17700 (mod 75781) . 46395 k3 ≡ 821191500 (mod 75781){bentuk tidak valid} k3 ≡ 28584 (mod 75781) {bentuk valid} atau : k3 = 28584 + 75781k4 untuk beberapa nilai k4

Jadi, didapatkan : X = 8247761248 + 9127522367k3 = 8247761248 + 9127522367(28584 + 75781k4) = 8247761248 + 260901099338328 + 691692772493627k4 X = 260909347099576 + 691692772493627k4; yang memenuhi 4 kongruen pertama

Substitusikan ke dalam kongruen 5 menjadi : X

≡ 7193 (mod 7817)

260909347099576 + 691692772493627k4

≡ 7193 (mod 7817)

691692772493627k4 ≡ -260909347092383 (mod 7817) {bentuk tidak valid} 691692772493627k4 ≡ 6043 (mod 7817) {bentuk valid} k4 ≡ 6043 (mod 7817) . 691692772493627-1 (mod 7817) k4 ≡ 6043 (mod 7817) . 1337

33

k4 ≡ 8079491 (mod 7817){bentuk tidak valid} k4 ≡ 4530 (mod 7817) {bentuk valid} atau : k4 = 4530 + 7817k5 untuk beberapa nilai k5

Jadi, didapatkan : X = 260909347099576 + 691692772493627k4 = 260909347099576 + 691692772493627(4530 + 7817k5) = 260909347099576 + 3133368259396130310 + 5406962402582682259k5 X = 3133629168743229886 + 5406962402582682259k5; yang memenuhi 5 kongruen pertama

Dari hasil perhitungan diatas didapatkan solusinya adalah : X = 3133629168743229886

2.6.2. Penerapan Chinese Remainder Theorem Yuri Andri Gani,(2009)Chinese Remainder Theorem dapat diterapkan dalam berbagai metode dalam kriptografi. Beberapa penerapan tersebut dapat dirincikan sebagai berikut : 1. Aplikasi dari Chinese Remainder Theorem dalam enkripsi multiple-key pada sistem basis data. Dalam sebuah lingkungan basis data, data digunakan oleh beberapa pemakai (user). Penggunaan data oleh beberapa user ini memiliki beberapa masalah antara lain masalah sekuritas data, masalah penjaminan integritas data, dan

34

sebagainya dalam program aplikasi. Setiap user diberikan hak akses tertentu pada setiap sub bagian data dalam basis data, maka setiap user perlu untuk memasukkan password yang akan membuka data yang terenkripsi agar dapat dibaca. Karena setiap user memiliki identitas unik tersendiri maka password yang digunakan untuk mengakses basis data juga berbeda-beda. Cooper, Hyslop dan Patterson memberikan sebuah algoritma enkripsi yang akan melakukan proses enkripsi tunggal dari setiap record dalam basis data, dan selama dekripsi, hanya akan memunculkan field yang boleh diakses oleh user tersebut. 2. Penggunaan Chinese Remainder Theorem dalam algoritma kriptografi kunci publik. Motivasi penggunaan Chinese Remainder Theorem untuk algoritma sekuriti data tidak lepas dari berkembangkan komunikasi via internet yang sangat bertumpu pada akselerasi dan sekuriti datanya. Contohnya yaitu pada algoritma RSA. Kelebihan Chinese Remainder Theorem adalah sebagai berikut : a. Mempercepat untuk operasi kunci pribadi (dekripsi, generasi tandatangan). b. Dua n/2-bit eksponensial mod P dan mod Q. sebagai ganti satu n-bit eksponensial mod N ( N=P*Q). c. Split n-bit multiplier hardware ke dalam dua n/2-bit pengali, melaksanakan n/2-bit eksponensial paralel. d. Kombinasi hasil menurut Chinese Remainder Theorem. e. Chinese Remainder Theorem meningkatkan dekripsi melewati suatu faktor yang berkisar antara 3-3,5.

35

Kalkulasi penting di dalam rencana enkripsi RSA adalah eksponensial modular M= Ed (mod n). Ini dilakukan setiap kali bagian dari pesan dilakukan enkripsi/dekripsi. Variabel d dan n adalah bilangan bulat sangat besar. Oleh karena itu, operasi ini sangat computationally intensive. Maka, harus ditemukan alternatif metode biner untuk eksponensial modular. Keuntungan dasar dengan menggunakan Chinese Remainder Theorem adalah memungkinkan untuk membagi modulo eksponensial yang besar ke dalam dua eksponensial yang jauh lebih kecil, satu di atas p dan satu di atas q. Dua modulo ini adalah faktor utama n yang dikenali. Selain itu juga dapat mengurangi masalah ukuran dengan penggunaan teorema Fermat's yang lebih kecil. Metode ini pertama diusulkan oleh Quisquater dan Couvreur.

BAB III METODE PENELITIAN

3.1.

Tempat dan Jadwal Penelitian Penelitian ini dimulai dari Nopember 2014 dan akan berlangsung sekitar 6

bulan. Penelitian dilakukan di perpustakaan STMIK-TIME Jl.merbabu No 32AABB medan 20212 Lantai 4 dan di rumah, untuk melakukan pengujian permainan. Penelitian ini ditujukan untuk mengumpulkan data yang diperlukan dalam proses perancangan dan pembuatan sistem. Berikut ini dijabarkan jadwal penelitian yang dapat dilihat pada Tabel 3.1. Tabel 3.1 Jadwal Penelitian

Waktu Kegiatan

1

Nopember

Desember

Januari

Februari

Maret

April

2014

2014

2015

2015

2015

2015

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

1

2

3

4

Pengumpulan Data Analisa Sistem Perancangan Sistem Pembangunan Sistem Uji Coba Sistem Implementasi Sistem Penulisan Lap. Skripsi

3.2.

Kerangka Kerja Tahapan dan langkah-langkah pengembangan perangkat lunak ini dapat

digambarkan dalam bentuk diagram alir seperti diperlihatkan pada gambar 3.1.

36

37

Pengumpulan data

Analisa Sistem

Perancangan Sistem

Pembangunan Sistem

Uji Coba Sistem

Gambar 3.1 Kerangka Kerja

3.3.

Pengumpulan Data Di tahap pertama, penulis mengumpulkan bahan-bahan yang diperlukan

dalam penyusunan skripsi. Bahan tersebut dikumpulkan dari buku dan sumbersumber lainnya di internet. Proses dimulai dengan mengumpulkan data-data yang diperlukan dalam penelitian. Adapun metode pengumpulan data dalam penelitian dilakukan melalui: 1. Penelitian Kepustakaan (library research), dimana penulis mengumpulkan data-data melalui berbagai referensi seperti internet dan buku-buku yang relevan yang berhubungan dengan topik yang dibahas.

38

2. Observasi, yaitu penulis akan mengamati dan mempelajari contoh pencarian solusi dari Chinese Remainder Theorem (CRT) yang diperoleh dari internet. 3. Wawancara, yaitu penulis akan bertanya kepada teman-teman dan kakak kelas yang menguasai topik mengenai proses perhitungan dari Chinese Remainder Theorem (CRT).

3.4.

Analisa Sistem Tahap berikutnya ialah menganalisis kebutuhan-kebutuhan sistem. Sekali

lagi, perangkat dan teknik-teknik tertentu akan membantu penganalisis menentukan kebutuhan. Perangkat yang dimaksud ialah penggunaan diagram alir data untuk menyusun daftar input, proses dan output fungsi bisnis dalam bentuk grafik terstruktur. Pada tahap ini penulis akan menganalisis permasalahan lebih mendalam mengenai masalah yang muncul pada sistem berjalan, sehingga dapat dirancang sebuah sistem baru untuk menyelesaikan permasalahan tersebut.

3.5.

Perancangan Sistem Dalam tahap desain dari siklus hidup pengembangan sistem, penganalisis

sistem menggunakan informasi-informasi yang terkumpul sebelumnya untuk mencapai desain sistem informasi yang logik. Penganalisis merancang prosedur data-entry sedemikian rupa sehingga data yang dimasukkan ke dalam sistem informasi benar-benar akurat. Selain itu, penganalisis menggunakan teknik-teknik bentuk dan perancangan layar tertentu untuk menjamin keefektifan input sistem informasi.

39

3.6.

Pembangunan Sistem Dalam tahap keempat dari siklus hidup pengembangan sistem, pemrogram

akan mengembangkan suatu perangkat lunak awal yang diperlukan. Teknik terstruktur yang digunakan untuk merancang dan mendokumentasikan perangkat lunak meliputi adalah flowchart. Penganalisis sistem menggunakan perangkat ini untuk menjabarkan apa yang perlu diprogram. Proses dilanjutkan dengan melakukan coding terhadap perangkat lunak. Perangkat lunak ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan perincian sebagai berikut : 1. Data ditampilkan dengan menggunakan label dan textbox. 2. Proses perhitungan waktu akan diatur dengan menggunakan timer.

3.7.

Uji Coba Sistem Setiap aplikasi perangkat lunak yang telah dibangun harus dilakukan uji

coba terlebih dahulu sebelum digunakan, untuk mengetahui apakah aplikasi perangkat lunak yang dibangun sudah sesuai dengan yang diharapkan dan bekerja dengan baik atau masih terdapat kesalahan (error). Setiap kesalahan (error) yang terjadi akan diperbaiki kembali.

BAB IV ANALISA DAN PERANCANGAN

4.1.

Analisa Secara garis besar, prosedur kerja dari perangkat lunak ini dapat dilihat

pada gambar berikut ini :

Gambar 4.1. Diagram Kerja Sistem dari Perangkat Lunak Perangkat lunak permainan Chinese Remainder Theorem ini mampu menjelaskan proses kerja dari Chinese Remainder Theorem. Selain itu, perangkat lunak ini juga mampu untuk menyediakan interface untuk bermain Chinese Remainder Theorem. Proses kerja dari perangkat lunak dimulai dari penginputan data awal yang diperlukan. Chinese Remainder Theorem memerlukan input data

40

41

berupa sebuah sistem kongruen linier. Setelah proses peng-input-an data, maka proses dilanjutkan dengan proses perhitungan nilai output. Secara mendetail, proses kerja dari Chinese Remainder Theorem dapat dilihat pada gambar berikut ini :

Gambar 4.2. Proses Kerja dari Chinese Remainder Theorem

42

Chinese Remainder Theorem dapat digunakan untuk mencari nilai invers modular dari sebuah sistem kongruen linier, yang terdiri dari beberapa buah persamaan modular. Chinese Remainder Theorem juga memerlukan bantuan Extended Euclidean Algorithm untuk menghitung nilai invers dari sebuah persamaan modular. Nilai ini yang akan disubstitusikan ke dalam sistem kongruen linier untuk mencari nilai invers modular dari sistem kongruen linier tersebut.

4.1.1. Proses Kerja Perangkat Lunak Perangkat lunak pemahaman Chinese Remainder Theorem untuk mencari nilai invers modular ini mampu menjelaskan proses pencarian nilai invers modular dari sebuah sistem kongruen linier secara tahap demi tahap. Secara garis besar, proses kerja dari perangkat lunak ini dapat dibagi menjadi 2 bagian, yaitu : 1. Pemahaman. Proses pemahaman Chinese Remainder Theorem ini memiliki input data dengan persyaratan sebagai berikut : a. Jumlah persamaan yang di-input dibatasi minimal 2 buah dan maksimal 10 buah. Pembatasan minimal ini dikarenakan sebuah sistem kongruen linier minimal harus memiliki 2 buah persamaan. Sedangkan pembatasan maksimal ini diberikan agar perangkat lunak tidak memakan waktu terlalu lama dalam mencari solusinya. b. Nilai-nilai konstanta dalam sistem kongruen linier mencakup nilai sisa modulo dan nilai bilangan modulo. Kedua nilai tersebut bertipe data bilangan integer positif dan memiliki persyaratan sebagai berikut : 1) Bilangan modulo harus berupa bilangan prima.

43

2) Bilangan sisa modulo harus lebih kecil daripada bilangan modulo. c. Kedua nilai konstanta dalam sistem kongruen linier tersebut dapat di-input secara manual ataupun dihasilkan secara acak oleh komputer dengan berdasarkan pada persyaratan di atas. Sedangkan, output dari proses pemahaman Chinese Remainder Theorem ini berupa proses pencarian nilai invers modulo dari sebuah sistem kongruen linier secara tahap demi tahap.

2. Permainan. Permainan ini memiliki input data dengan persyaratan sebagai berikut : a. Jumlah persamaan modulo yang di-input minimal 2 buah dan maksimal 6 buah, yang berarti bahwa terdapat minimal 2 kali pembagian dan maksimal 6 kali pembagian. b. Jumlah orang dapat ditentukan dengan batasan antara 2 sampai 99. c. Perangkat lunak juga menyediakan daftar 10 nilai tertinggi yang disimpan ke dalam sebuah database yang dibuat dengan aplikasi Microsoft Access 2010. Sedangkan, output dari permainan ini berupa total nilai yang diperoleh pemain.

4.2.

Perancangan Perangkat lunak ini dirancang dengan menggunakan bahasa pemrograman

Microsoft Visual Basic.NET 2010. Perangkat lunak ini dirancang dengan menggunakan beberapa objek dasar seperti :

44

1. Label yang digunakan untuk menampilkan keterangan. 2. Link Label dapat digunakan sebagai link. 3. Textbox yang digunakan sebagai tempat penginputan data. 4. Richtextbox yang digunakan sebagai tempat untuk menampilkan hasil proses perhitungan. 5. Save file dialog yang digunakan untuk menampilkan dialog save. Rancangan tampilan dari perangkat lunak ini dapat dirincikan sebagai berikut : 1. Form “Awal” 2. Form “Pemahaman” 3. Form “Input” 4. Form “Proses” 5. Form “Extended Euclidean” 6. Form “Pilih Pemain” 7. Form “Cerita” 8. Form “Bermain” 9. Form “High Score” 10. Form “About”

4.2.1. Form Awal Form ini merupakan form pembuka (awal) dari perangkat lunak yang berfungsi sebagai penghubung (link) ke form-form lainnya. Rancangan tampilan dari form “Awal” ini dapat dilihat pada gambar berikut ini :

45

Gambar 4.3. Rancangan Form Awal Keterangan : 1 : Title bar yang berisi tulisan “Pembelajaran Chinese Remainder Theorem”. 2 : Tombol “X” berfungsi untuk menutup perangkat lunak. 3 : Link label “Pemahaman” yang berfungsi untuk menampilkan form “Input”. 4 : Link label “Permainan” yang berfungsi untuk menampilkan form “Bermain”. 5 : Link label “High Score” yang berfungsi untuk menampilkan form “High Score”. 6 : Link label “Mengenai Pembuat” yang berfungsi untuk menampilkan form “Mengenai Pembuat”. 7 : Link label “Nama Pemain” yang berfungsi untuk menampilkan form “Pilih Pemain”.

46

4.2.2. Form pemahaman Form ini berfungsi sebagai tempat pemberian penjelasan tentang Chinese Remainder Theorem dan fungsi dari Chinese Remainder Theorem difungsikan untuk di bagian mana . Rancangan tampilan dari form “pemahaman “ ini dapat dilihat pada gambar berikut.

1

NEXT 2 Gambar 4.4. Rancanggan Form Pemahaman Keterangan : 1 : listview berisikan penjelasan dan fungsi “Chinese Remainder Theorem”. 2 : Tombol “NEXT “ untuk ke Form “Input”

4.2.3. Form Input Form ini berfungsi sebagai tempat penginputan sistem kongruen linier yang akan dihitung nilai invers modularnya dengan menggunakan Chinese Remainder Theorem. Rancangan tampilan dari form “Input” ini dapat dilihat pada gambar berikut:

47

Gambar 4.5. Rancangan Form Input Keterangan : 1 : Title bar yang berisi tulisan “Pembelajaran Chinese Remainder Theorem”. 2 : Tombol “X”, berfungsi untuk menutup form “Input” dan kembali ke form “Awal”. 3 : Textbox “Jumlah Persamaan” yang berfungsi penginputan jumlah persamaan. 4 : Tombol “Ambil Nilai Acak”, yang berfungsi untuk menghasilkan nilai-nilai konstanta dalam sistem kongruen linier secara acak. 5 : Tombol "Validasi Nilai” yang berfungsi untuk mengecek nilai-nilai konstanta dalam sistem kongruen linier apakah valid atau tidak. 6 : Tabel ”Sistem Kongruen Linier”, yang berfungsi sebagai tempat penginputan sistem kongruen linier yang akan dicari penyelesaiannya. 7 : Tombol “Next >>”, yang berfungsi untuk menampilkan form “Proses”.

48

4.2.4. Form Proses Form ini berfungsi untuk menampilkan proses perhitungan dari Chinese Remainder Theorem secara tahap demi tahap. Rancangan tampilan dari form “Proses” dapat dilihat pada gambar berikut ini :

Gambar 4.6. Rancangan Form Proses Keterangan : 1 : Title bar yang berisi tulisan “Pembelajaran Chinese Remainder Theorem”. 2 : Tombol “X”, berfungsi untuk menutup form “Proses” dan kembali ke form “Awal”. 3 : Label “Keterangan” yang berfungsi untuk menampilkan keterangan mengenai langkah penyelesaian yang sedang ditampilkan. 4 : Textbox “Hasil Perhitungan” yang berfungsi untuk menampilkan tahapantahapan hasil perhitungan.

49

5 : Tombol “Home” yang berfungsi untuk menutup form “Proses” dan kembali ke form “Awal”. 6 : Tombol “Back >>”, yang berfungsi untuk menampilkan langkah sebelumnya. 7 : Tombol “Next >>”, yang berfungsi untuk menampilkan langkah selanjutnya.

4.2.5. Form Extended Euclidean Form ini berfungsi untuk menampilkan detail perhitungan dari algoritma Extended Euclidean yang digunakan untuk menghitung nilai invers modular. Rancangan tampilan dari form Extended Euclidean ini dapat dilihat pada gambar berikut:

Gambar 4.7. Rancangan Form Extended Euclidean Keterangan : 1 : listview “Perhitungan” berfungsi untuk menampilkan tabel perhitungan Extended Euclidean. 2 : tombol “Proses” yang berfungsi untuk menampilkan detail perhitungan secara langkah demi langkah. 3 : tombol “Skip” yang berfungsi untuk menampilkan hasil diperoleh.

50

4.2.6. Form Pilih Pemain Form ini berfungsi sebagai tempat pemilihan nama pemain yang akan bermain kuis. Nama pemain ini akan diperlukan pada saat penyimpanan daftar nilai tertinggi yang diperoleh pemain ke dalam database. Selain itu, pada form ini juga disediakan fasilitas untuk menambah nama pemain baru. Rancangan tampilan dari form Pilih Pemain ini dapat dilihat pada gambar berikut:

Gambar 4.8. Rancangan Form Pilih Pemain Keterangan : 1 : listbox “Nama Pemain” berfungsi untuk menampilkan daftar nama pemain yang tersimpan dalam database. 2 : tombol “Tambah” yang berfungsi untuk menambah nama pemain baru. 3 : tombol “Pilih” yang berfungsi untuk menyimpan nama pemain yang dipilih ke dalam memori sementara, sehingga dapat digunakan pada form “Kuis”. 4 : tombol “Hapus” yang berfungsi untuk menghapus nama pemain yang dipilih. 5 : tombol “Batal” yang berfungsi untuk menutup form dan kembali ke form Main.

51

4.2.7. Form Cerita Form “Cerita”, berfungsi untuk menampilkan informasi mengenai cerita yang melatarbelakangi permainan ini. Rancangan tampilan dari form “Cerita” ini dapat dilihat pada gambar 4.9 berikut ini:

Gambar 4.9. Rancangan Form Cerita Keterangan : 1 : Daerah tampilan keterangan mengenai cerita permainan. 2 : Tombol “Kembali” untuk menampilkan halaman teori sebelumnya. 3 : Tombol “Lanjut” untuk menampilkan halaman teori selanjutnya. 4 : Tombol “Keluar” untuk menutup form.

4.2.8. Form Bermain Form ini berfungsi untuk bermain Chinese Remainder Theorem. Rancangan tampilan dari form “Bermain” dapat dilihat pada gambar berikut :

52

Gambar 4.10. Rancangan Form Bermain Keterangan : 1 : Daerah tampilan nilai yang diperoleh pemain. 2 : Daerah tampilan level permainan sekarang. 3 : Daerah tampilan waktu yang tersisa untuk bermain. 4 : Daerah tampilan soal dan pilihan jawaban. 5 : Tombol “Pass”, yang berfungsi untuk melanjutkan ke soal berikutnya dan nilai pemain akan dikurangi sebesar 10. 6 : Tombol “Lanjut”, yang berfungsi untuk mengecek jawaban yang dipilih oleh pemain. Jika jawaban benar, maka nilai pemain akan ditambah sebesar 20 dan akan dilanjutkan ke soal berikutnya. Jika jawaban salah, maka nilai pemain akan ditambah sebesar 5 dan akan ditampilkan pesan kesalahan. 7 : Tombol “Keluar”, berfungsi untuk menutup form “Bermain” dan kembali ke “Awal”.

53

4.2.9. Form High Score Form “High Score” berfungsi untuk menampilkan sepuluh nilai tertinggi yang diperoleh pemain. Rancangan tampilan dari form “High Score” ini dapat dilihat pada gambar 4.11 berikut ini:

Gambar 4.11. Rancangan Form High Score Keterangan : 1 : Daerah tampilan 10 nilai tertinggi yang diperoleh user. 2 : Tombol “Hapus” untuk menghapus daftar nilai tertinggi. 3 : Tombol “Keluar” yang berfungsi untuk menutup form “High Score” dan kembali ke form “Awal” 4.2.10. Form About Form “About” berfungsi untuk menampilkan informasi mengenai perangkat lunak. Rancangan tampilan dari form “About” ini dapat dilihat pada gambar 4.12 berikut ini:

54

Gambar 4.12. Rancangan Form About Keterangan : 1 : Daerah tampilan informasi mengenai perangkat lunak. 2 : Tombol “Kembali” untuk menampilkan halaman teori sebelumnya. 3 : Tombol “Lanjut” untuk menampilkan halaman teori selanjutnya. 4 : Tombol “Keluar” untuk menutup form.

4.3.

Perancangan Database Perancangan database dilakukan dengan menggunakan Microsoft Access

2010. Desain database dimaksudkan untuk mendefinisikan isi atau struktur tabel. Entitas yang digunakan dalam perancangan database adalah sebagai berikut. 1. HighScore, berisi tentang daftar sepuluh nilai tertinggi. Rancangan tabel HighScore dapat dilihat pada tabel 4.1 berikut:

55

Tabel 4.1. Tabel HighScore Nama Input

Tipe Data

Panjang Maksimum

Text

30

Number

Integer

Tingkat

Text

6

Waktu

Date/Time

-

Lama

Number

Integer

NamaUser Nilai

2. UserList, berisi tentang daftar nama user. Rancangan tabel UserList dapat dilihat pada tabel 4.2 berikut: Tabel 4.2. Tabel UserList Nama Input NamaUser

Tipe Data

Panjang Maksimum

Text

30

Berdasarkan entitas yang diperoleh di atas, maka dapat dibuat hubungan antarentitasnya seperti ditunjukkan pada gambar 4.13 berikut ini:

Gambar 4.13. Relationship Tabel Pada Database

BAB V HASIL DAN PEMBAHASAN

5.1.

Hasil Tampilan output dari perangkat lunak ini adalah sebagai berikut :

1. Tampilan form “Main”, merupakan form pertama yang muncul pada saat menjalankan perangkat lunak. Tampilan form ini dapat dilihat pada gambar berikut:

Gambar 5.1. Tampilan Form Awal Pada form ini terdapat tiga buah link utama yang dapat digunakan, yaitu: a. Link Pemahaman, yang dapat digunakan untuk menampilkan rincian proses kerja dari Chinese Remainder Theorem.

56

57

b. Link Permainan, yang dapat digunakan untuk menampilkan interface untuk bermain Chinese Remainder Theorem. c. Link High Score, yang dapat digunakan untuk menampilkan daftar nilai tertinggi yang diperoleh pemain. Selain link diatas, juga terdapat dua buah link lainnya, yaitu: a. Link Nama Pemain, yang digunakan untuk melakukan pemilihan nama pemain. b. Link About, yang digunakan untuk menampilkan data pribadi dari pembuat perangkat lunak.

2. Tampilan form “Pemahaman”, merupakan form yang berfungsi untuk menampilkan detail rincian perhitungan dari soal Chinese Remainder yang dimasukkan. Untuk menampilkan form ini, maka dapat mengklik link ‘Pemahaman’ sehingga sistem akan menampilkan form “Input” berikut.

Gambar 5.2. Tampilan Form Pemahaman

58

Gambar 5.3. Tampilan Form Input Input jumlah persamaan dan detail nilai dari persamaan tersebut. Apabila pemakai ingin menghasilkannya secara acak, maka dapat mengklik tombol “Ambil Nilai Acak”. Apabila pengisian nilai dilakukan secara manual, maka pemakai dapat mengecek nilai tersebut dengan mengklik tombol “Validasi Nilai”. Tampilan form Input setelah pengisian data dapat dilihat pada gambar berikut:

59

Gambar 5.4. Tampilan Form Input Setelah Pengisian Data

Setelah pemakai mengisi semua nilai yang diperlukan, maka pemakai dapat mengklik tombol “Next”. Sistem akan menghitung dan mencari solusi dari persamaan Chinese Remainder Theorem yang dimasukkan. Setelah itu, sistem akan menampilkan form Pemahaman, seperti terlihat pada gambar berikut ini.

60

Gambar 5.5. Tampilan Form Proses Langkah 1 Pemakai dapat mengklik tombol “Next” untuk melanjutkan ke langkah berikutnya, seperti terlihat pada gambar berikut.

Gambar 5.6 Tampilan Form Proses Langkah 2

61

Pemakai dapat mengklik tombol “Next” untuk melanjutkan ke langkah berikutnya, seperti terlihat pada gambar berikut.

Gambar 5.7. Tampilan Form Proses Langkah 3 Pemakai dapat mengklik tombol “Next” untuk melanjutkan ke langkah berikutnya, seperti terlihat pada gambar berikut.

Gambar 5.8. Tampilan Form Proses Langkah 4

62

Apabila solusi belum diperoleh, maka pemakai dapat mengklik tombol “Next” untuk melanjutkan ke langkah berikutnya, seperti terlihat pada gambar berikut.

Gambar 5.9. Tampilan Form Proses Langkah Terakhir Untuk kembali ke form Awal, maka pemakai dapat mengklik tombol “Home” sehingga sistem akan menutup form Pemahaman dan kembali ke form Awal. Sementara itu, apabila pemakai ingin menampilkan detail perhitungan dari proses perhitungan invers modular, maka dapat mengklik tombol Invers Modular sehingga sistem akan menampilkan form berikut:

Gambar 5.10. Tampilan Form Proses Perhitungan Invers Modular

63

Apabila proses perhitungan selesai, maka sistem akan menampilkan pesan pemberitahuan seperti terlihat pada gambar berikut:

Gambar 5.11. Tampilan Pesan Pemberitahuan

3. Tampilan form “Permainan” merupakan tampilan yang berfungsi sebagai tempat pencarian solusi Chinese Remainder Theorem secara manual. Sebelum dapat mengakses form Permainan ini, maka pemakai harus memilih nama pemain yang akan digunakan terlebih dahulu. Caranya adalah dengan mengklik link “Nama Pemain”, sehingga sistem akan menampilkan form Pilih Pemain seperti terlihat pada gambar berikut.

Gambar 5.12. Tampilan Form Pilih Pemain

64

Pemakai dapat memilih nama pemain yang diinginkan dan klik tombol “Pilih” untuk melanjutkan proses. Apabila pemakai ingin memasukkan nama pemain baru, maka dapat mengklik tombol ”Tambah” sehingga sistem akan menampilkan form Tambah Pemain seperti terlihat pada gambar berikut.

Gambar 5.13. Tampilan Form Nama Pemain Isikan nama pemain yang diinginkan dan klik tombol “OK”. Setelah memilih nama pemain, maka pemain dapat mengakses link ‘Permainan’, sehingga sistem akan menampilkan form Cerita seperti terlihat pada gambar berikut.

Gambar 5.14. Tampilan Form Cerita Halaman 1

65

Gambar 5.15. Tampilan Form Cerita Halaman 2

Gambar 5.16. Tampilan Form Cerita Halaman 3

66

Gambar 5.17. Tampilan Form Cerita Halaman 4 Setelah menampilkan semua form Cerita, maka pemakai dapat mengklik tombol “Lanjut” untuk memulai proses permainan, seperti terlihat pada tampilan berikut:

Gambar 5.18. Tampilan Form Permainan

67

Apabila pemakai ingin menjawab pertanyaan ini, maka klik tombol “Jawab”. Apabila pemakai ingin melewatkan pertanyaan ini ke pertanyaan selanjutnya, maka dapat mengklik tombol “Pass”. Nilai pemain akan dikurangi 20 apabila pemain melewatkan sebuah soal. Apabila pemakai mengklik tombol “Jawab” maka sistem akan menampilkan form berikut:

Gambar 5.19. Tampilan Form Detail Permainan Pemain dapat menjawab pertanyaan dan klik tombol “Cek Jawaban & Lanjut” untuk mengecek jawaban dan melanjutkan ke langkah berikutnya. Apabila jawaban pemain benar, maka nilai pemain akan ditambah 40 dan apabila jawaban salah, maka nilai pemain akan dikurangi 10. Apabila pemain ingin melewatkan langkah ini, maka dapat mengklik tombol “Pass”. Apabila jawaban pemain benar, sistem akan menampilkan pesan pemberitahuan seperti terlihat pada gambar berikut:

68

Gambar 5.20. Tampilan Pesan Pemberitahuan untuk Jawaban Benar Apabila

jawaban

pemain

salah,

sistem

akan

menampilkan

pesan

pemberitahuan seperti terlihat pada gambar berikut:

Gambar 5.21. Tampilan Pesan Pemberitahuan untuk Jawaban Salah Setelah

semua

langkah

dijawab,

sistem

akan

menampilkan

pesan

pemberitahuan mengenai nilai yang diperoleh pemain, seperti terlihat pada gambar berikut.

Gambar 5.22. Tampilan Pesan Pemberitahuan Setelah Selesai Menjawab Semua Langkah

69

Setelah selesai permainan, pemain dapat menampilkan daftar nilai tertinggi yang diperoleh pemain, seperti terlihat pada gambar berikut:

Gambar 5.23. Tampilan High Score Terakhir, apabila pemain ingin mengetahui cara memakai aplikasi ini, maka pemain dapat mengklik link “About”, sehingga sistem akan menampilkan form berikut:

Gambar 5.23. Tampilan About

70

5.2.

Algoritma Algoritma yang digunakan untuk merancang perangkat lunak pemahaman

Chinese Remainder Theorem ini dapat dibagi menjadi 2 bagian besar yaitu : 1. Algoritma Chinese Remainder. 2. Algoritma Extended Euclidean.

5.2.1. Algoritma Chinese Remainder Algoritma ini memiliki input data yaitu : 1. Variabel array dua dimensi nArrNilai, dengan perincian dimensi pertama bernilai sebesar jumlah persamaan dan dimensi kedua bernilai sebesar 2 yaitu nilai 1 untuk bilangan sisa modulo dan nilai 2 untuk bilangan modulo. 2. Variabel nJlh merupakan jumlah persamaan. Sedangkan, output dari algoritma ini berupa nilai invers modular yang memenuhi kedua persamaan modular. Selain itu, algoritma Chinese Remainder ini juga membutuhkan algoritma Extended Euclidean untuk menghitung nilai invers modular dari sebuah persamaan modular. Prosedur kerja dari algoritma ini dapat dijabarkan seperti berikut ini : 1. Konstanta kiri pertama dari step pertama di-set = 0. 2. Konstanta kiri kedua dari step pertama di-set = 1. 3. Konstanta kanan pertama dari step pertama di-set = bilangan sisa modulo dari persamaan pertama. 4. Konstanta kanan kedua dari step pertama di-set = bilangan modulo dari persamaan pertama.

71

5. Konstanta kanan pertama dari step ke-0 di-set = bilangan sisa modulo dari persamaan pertama. 6. Konstanta kanan kedua dari step ke-0 di-set = bilangan modulo dari persamaan pertama. 7. Persamaan yang akan di-checking sekarang (disimbolkan dengan nS) di-set = 2. 8. Selama nS <= nJlh (nJlh merupakan simbol dari jumlah persamaan) lakukan proses berikut : a. Konstanta kiri pertama dari step ke-nS di-set = konstanta kiri kanan dari step ke-(ns – 1). b. Konstanta kiri kedua dari step ke-nS di-set =konstanta kanan kedua dari step ke-(nS – 1). c. Konstanta kanan pertama dari step ke-nS di-set sama dengan bilangan sisa modulo dari persamaan kedua. d. Konstanta kanan kedua dari step ke-nS di-set sama dengan bilangan modulo dari persamaan kedua. e. Konstanta kanan pertama dari step ke-nS di-set sama dengan konstanta kanan pertama dari step ke-nS dikurangi dengan konstanta kiri pertama dari step ke-nS. f. Konstanta kiri pertama dari step ke-nS di-set sama dengan nol. g. Jika sebuah karakter kiri dari konstanta kanan pertama dari step ke-nS = "" maka set cTemp1 = konstanta kanan pertama dari step ke-nS / konstanta kanan kedua dari step ke-nS.

72

h. Jika hasil bagi bulat dari cTemp1 = "0" dan sisa bagi bulat dari cTemp1 <> "0" maka set hasil bagi bulat dari cTemp1 = "-1" i. Jika tidak, jika sebuah karakter kiri dari hasil kali bulat dari cTemp1 = "-" dan sisa bagi bulat dari cTemp1 <> "0" maka hasil bagi bulat dari cTemp1 = hasil bagi bulat dari cTemp1 – 1. j. Konstanta kanan pertama dari step ke-nS = konstanta kanan pertama dari step ke-nS – konstanta kanan kedua dari step ke-nS * hasil bagi bulat dari cTemp1. k. Jika konstanta kiri kedua dari step ke-nS > "1" maka cTemp = Ex_Euclid(konstanta kanan kedua dari step ke-nS, konstanta kiri kedua dari step ke-nS). l. Konstanta kiri kedua dari step ke-nS di-set = 1. m. Konstanta kanan pertama dari step ke-nS = konstanta kanan pertama dari step ke-nS * cTemp n. Jika panjang string dari konstanta kanan pertama dari step ke-nS > panjang string dari konstanta kanan kedua dari step ke-nS maka

nMaxLen =

panjang string dari konstanta kanan pertama dari step ke-nS. Jika tidak, maka nMaxLen = panjang string dari konstanta kanan kedua dari step kenS. o. Konstanta kanan pertama dari step ke-nS = tambahkan karakter “0” sebanyak nMaxLen – Panjang string dari konstanta kanan pertama dari step ke-nS digabungkan dengan konstanta kanan pertama dari step ke-nS.

73

p. Konstanta kanan kedua dari step ke-nS = tambahkan karakter “0” sebanyak nMaxLen – panjang string dari konstanta kanan kedua dari step ke-nS digabungkan dengan konstanta kanan kedua dari step ke-nS. q. Jika ArrStep1(nS).KonsKanan(1) > nArrStep1(nS).KonsKanan(2) maka konstanta kanan pertama dari step ke-nS = konstanta kanan pertama dari step ke-nS / konstanta kanan kedua dasri step ke-nS. r. Konstanta kanan pertama dari step ke-nS = konstanta kanan pertama dari step ke- (nS – 1) + konstanta kanan kedua dari step ke-(nS – 1) * konstanta kanan pertama dari step ke-nS. s. Konstanta kanan kedua dari step ke-nS = konstanta kanan kedua dari step ke- (nS – 1). t. Inkremen nilai nS. u. Chinese_Remainder = konstanta kanan pertama dari step ke-(nS – 1)

5.2.2. Algoritma Extended Euclidean Algoritma ini memiliki sebuah input data yaitu : 1. Variabel pnValueA11 yaitu bilangan sisa modulo. 2. Variabel pnValueE yaitu bilangan modulo. Sedangkan, output dari algoritma ini berupa nilai invers dari persamaan modular tersebut. Prosedur kerja dari algoritma ini dapat dijabarkan sebagai berikut : a. bSelesai = False. b. A(1, 1) = pnValueA11. c. A(1, 2) = pnValueE.

74

d. A(2, 1) = 1 e. A(2, 2) = 0 f. A(3, 1) = 0 g. A(3, 2) = 1 h. Selama Not bSelesai, lakukan proses berikut : 1. nM = A(1, 1) \ A(1, 2) 2. Untuk nI = 1 sampai 3


nX = A(nI, 1) - (nM * A(nI, 2))




A(nI, 1) = A(nI, 2)




A(nI, 2) = nX




Jika nI = 1 dan nX = "0" maka bSelesai = True

i. Jika sebuah karakter kiri dari (A(3, 1)) <> "-" maka set Ex_Euclid = A(3, 1) j. Jika tidak, maka Ex_Euclid = FAddNum(A(3, 1), pnValueA11)

BAB VI KESIMPULAN DAN SARAN

6.1.

Kesimpulan Setelah menyelesaikan skripsi ini, penulis menarik beberapa kesimpulan

sebagai berikut : 1. Perangkat lunak yang dibuat dapat digunakan untuk membantu pemahaman terhadap proses kerja dari Chinese Remainder Theorem dan juga dilengkapi dengan permainan yang dapat digunakan untuk melatih tingkat pemahaman dari pemakai. 2. Perangkat lunak yang dibuat menyediakan fasilitas permainan untuk melatih tingkat pemahaman dari pemakai. Perangkat lunak menyediakan soal yang dibuat dengan dimulai dari nilai yang kecil sehingga mudah diselesaikan. 3. Perangkat lunak pemahaman Chinese Remainder Theorem ini mendukung perhitungan untuk bilangan yang tidak dapat disimpan dalam variabel yang bertipe data numerik, sehingga harus dibuat sebuah fungsi pendukung untuk menghitung operasi pada bilangan tersebut. 4. Perangkat lunak dapat digunakan untuk membantu menyelesaikan persamaan matematika yaitu mencari bilangan invers dari sistem kongruen linier. Proses perhitungan invers modular ini dapat diakses pada bagian pemahaman pada saat terdapat perhitungan invers modular.

75

76

6.2.

Saran Penulis ingin memberikan beberapa saran yang mungkin berguna untuk

pengembangan lebih lanjut pada perancangan perangkat lunak bantu pemahaman yaitu : 1. Disarankan untuk menambahkan animasi dan multimedia sehingga dapat meningkatkan ketertarikan dari pemakai dalam mempelajari mengenai Chinese Remainder Theorem. 2. Perangkat lunak dapat ditambahkan soal-soal latihan untuk mendukung proses pemahaman. 3. Perangkat lunak dapat dikembangkan dengan menerapkannya dalam merancang metode kriptografi yang menggunakan Chinese Remainder Theorem. 4. Perangkat lunak dapat dikembangkan sehingga mendukung peng-input-an bilangan prima yang lebih besar daripada 105.

DAFTAR PUSTAKA

Bruce Schneier, 2007, Applied Crytography, Second Edition, John Willey and Sons Inc. Ismail Besari, 2010, Matematika Universitas, Armico, Bandung. Rinaldi Munir, 2014, Matematika Diskrit, Informatika Bandung. William Stallings, 2011, Cryptography and Network Security, Third Edition. Aria Turns 2014, https://ariaturns.wordpress.com/2014/01/03/teorema-sisacina/,2014 Teorema Sisa Cina, DarylHaviz ,2011, http://darylhaviz01.blogspot.com/2011/03/nama-bilanganbesar.html Hendry,2009http://hendrydext.blogspot.com/2009/05/chinese-remaindertheorem_08.html Putra(2013),epository.usu.ac.id/bitstream/123456789/39042/4/Chapter%20II.pdf, Rubrik Bahasa, Februari 2009 https://rubrikbahasa.wordpress.com/2009/02/27/sistem-bilanganbesar/27 Yuri Andri Gani(2009P , PENERAPAN METODA CHINESE REMAINDER THEOREM PADA RSA www.cs.purdue.edu/homes/ninghui/ courses/Spring04/lectures/lect11.pdf. www.iecn.u-nancy.fr/~gaillard/DIVERS/Chinese. www.math.boun.edu.tr/instructors/karabudak/math483/notes/CRT.pdf. Remainder.Theorem/060105.chinese.remainder.theorem.pdf. www.math.ucsb.edu/~garcias/ cv/NumberTheory/NumberTheory.html. www.twocw.net/mit/NR/rdonlyres/Mathematics/18-781Spring2003/8DFEB106CB20-4B0E-A023-72BF383CDEF0/0/notes_9_10.pdf.