ANALISIS ALGORITME FAKTORISASI PENYARING KUADRIK BESERTA IMPLEMENTASINYA SECARA PARALEL RADEN BAGUS DIMAS PUTRA

ANALISIS ALGORITME FAKTORISASI PENYARING KUADRIK BESERTA IMPLEMENTASINYA SECARA PARALEL

RADEN BAGUS DIMAS PUTRA

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ANALISIS ALGORITME FAKTORISASI PENYARING KUADRIK BESERTA IMPLEMENTASINYA SECARA PARALEL

RADEN BAGUS DIMAS PUTRA

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ABSTRACT

R BAGUS DIMAS PUTRA. Analysis of Quadratic Sieve Algorithm with Parallel Implementation supervised by SUGI GURITMAN and HENDRA RAHMAWAN. Algorithm for finding the prime factors of large composite numbers are importance because of the widespread use of public key cryptosystems whose security depends on the presumed difficulty of the factorization problem. This research uses quadratic sieve algorithm for factoring big composite numbers. Quadratic sieve is the best algorithm for factoring composite numbers bellow 100 decimal digits. The quadratic sieve is analyzed and implemented using C programming language and parallelized by functional decomposition and domain decomposition. This research uses additional libraries for parallel implementation and for computing big integer numbers, which are MPI and GMP. The implementation result is tested in a computer with four processors. The factorized composite numbers are 25, 30, and 35 digits. The objectives of this research is to measure and analyze the performance of parallel quadratic sieve algorithm using performance metrics and the complexity of the implemented quadratic sieve. This research uses two ways for parallelizing method: functional decomposition toward sieving stage and domain decomposition on sieving stage. The best result of parallel quadratic sieve is the domain decomposition on sieving stage which has an average efficiency of 91.6%. The result is not good enough because there are an additional task for changing GMP data type to MPI data type on parallel implementation. The complexity of the communication is e^((ln N ln ln N)^(1/2) 10log N + 4 (P-1))/B which means it becomes worse the higher the composite numbers are. Performance metrics also become worse because of the additional task and the communication. Keyword : complexity, GMP, MPI, parallel, quadratic sieve

Judul Penelitian

: Analisis Algoritme Faktorisasi Penyaring Kuadrik Beserta Implementasinya Secara Paralel : Raden Bagus Dimas Putra : G64080039

Nama NIM

Menyetujui: Pembimbing 1,

Pembimbing 2,

Dr. Sugi Guritman NIP. 19620927 199203 1 004

Hendra Rahmawan, S.Kom, M.T NIP. 19820501 200912 1 004

Mengetahui: Ketua Departemen,

Dr. Ir. Agus Buono, M.Si, M.Kom NIP. 19660702 199302 1 001

Tanggal Lulus:

PRAKATA

Alhamdulillah, segala puji dan syukur penulis panjatkan ke hadirat Allah subhanahu wata'ala yang telah memberikan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan penulisan skripsi yang berjudul “Analisis Algoritme Faktorisasi Penyaring Kuadrik Beserta Implementasinya Secara Paralel” yang merupakan salah satu syarat untuk menyelesaikan pendidikan program sarjana pada Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam di Institut Pertanian Bogor. Shalawat dan salam tak lupa penulis sampaikan kepada Nabi Muhammad shallallahu 'alaihi wasallam serta kepada keluarganya, sahabatnya, dan kepada para pengikutnya. Dalam menyelesaikan tulisan ini penulis mendapat bantuan dari banyak pihak. Oleh karena itu, penulis ingin menyampaikan rasa terima kasih kepada:  Bapak Dr. Sugi Guritman selaku dosen pembimbing pertama dan Bapak Hendra Rahmawan, S.Kom, M.T selaku dosen pembimbing kedua. Terima kasih atas segala pengetahuan dan bantuan serta nasehat-nasehat yang diberikan kepada penulis.  Ibunda Sahani, Ayahanda Haryanto, serta adik R Bagus Agung W K dan Rr Aprilia Putri C yang telah memberikan doa, kasih sayang, dukungan, serta motivasi untuk menyelesaikan penelitian ini.  Bapak Endang Purnama Giri, S.Kom, M.Kom selaku dosen penguji. Terima kasih atas segala bantuan yang diberikan kepada penulis.  Bapak Sony Hartono Wijaya, S.Kom, M.Kom selaku dosen pembimbing akademik serta staf pengajar dan tata usaha yang telah memberikan bantuan dan kerjasamanya selama penulis menjadi mahasiswa Ilmu Komputer angkatan 45.  Fitri Karlinda yang senantiasa memberikan doa, bantuan, dukungan, dan motivasi.  Teman-teman Ilkomerz 45 khususnya Jaka Ahmad Juliarta dan Anggi Putrantio yang telah membantu pelaksanaan seminar dan senantiasa memberikan bantuan, dukungan serta motivasi kepada penulis.  Seluruh mahasiswa Ilkom 44, 45, 46, dan 47 atas persahabatan yang luar biasa. Semoga karya ini bisa memberikan manfaat untuk perkembangan dunia kriptografi dan teknologi informasi di Indonesia.

Bogor, Desember 2012

R Bagus Dimas Putra

RIWAYAT HIDUP Penulis bernama R Bagus Dimas Putra lahir di Jakarta pada tanggal 4 Agustus 1990. Penulis merupakan anak pertama dari tiga bersaudara yang terlahir dari pasangan Haryanto dan Sahani. Pada tahun 2008, penulis menamatkan pendidikan di SMA Negeri 2 Bogor, Jawa Barat. Pada tahun yang sama penulis menempuh pendidikan ke jenjang yang lebih tinggi yaitu Institut Pertanian Bogor (IPB). Penulis masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima sebagai mahasiswa mayor Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama menjadi mahasiswa, penulis aktif sebagai asisten praktikum di berbagai mata kuliah Ilmu Komputer yang diantaranya adalah: Algoritme dan Pemrograman (2010, 2011), Organisasi Komputer (2010, 2011), Rangkaian Digital (2010, 2011), Struktur Data (2012), dan Sistem Pakar (2012). Pada tahun 2011 penulis menjadi salah satu finalis lomba Keamanan Jaringan Gemastik 4. Pada tahun 2012 penulis menjadi panitia dalam Pelatihan Nasional 2 Tim Olimpiade Komputer Indonesia sebagai asisten. Selain itu, penulis melaksanakan kegiatan Praktik Kerja Lapangan di Kantor Komunikasi dan Informatika Kota Bogor pada tahun 2011.

DAFTAR ISI Halaman DAFTAR TABEL ...........................................................................................................................vii DAFTAR GAMBAR ......................................................................................................................vii DAFTAR LAMPIRAN ...................................................................................................................vii PENDAHULUAN Latar Belakang............................................................................................................................. 1 Tujuan Penelitian ......................................................................................................................... 1 Ruang Lingkup Penelitian ........................................................................................................... 1 TINJAUAN PUSTAKA Prima dan Bilangan Komposit ..................................................................................................... 1 Teorema Dasar Aritmatika (TDA) ............................................................................................... 1 Subeksponensial .......................................................................................................................... 1 Faktorisasi Fermat ....................................................................................................................... 1 Metode Kraitchik dan Dixon ....................................................................................................... 2 Faktor Basis ................................................................................................................................. 2 Least Absolute Residue ................................................................................................................ 2 B-smooth ...................................................................................................................................... 2 Prima Relatif ................................................................................................................................ 2 Residu Kuadrik ............................................................................................................................ 2 Bergantung Linear ....................................................................................................................... 2 Penyaring Kuadrik (QS) .............................................................................................................. 2 Penyaring Kuadrik Dasar (Basic QS) .......................................................................................... 2 Pemrograman Paralel ................................................................................................................... 3 Arsitektur Komputer Paralel ........................................................................................................ 3 Distributed Memory ..................................................................................................................... 3 Metode Foster .............................................................................................................................. 4 GMP ............................................................................................................................................ 4 Message Passing Interface (MPI) ............................................................................................... 4 Blocking dan Nonblocking Communication ................................................................................ 4 Communicator ............................................................................................................................. 5 Performance Metric ..................................................................................................................... 5 METODE PENELITIAN Studi Pustaka ............................................................................................................................... 5 Analisis Algoritme Sekuensial QS .............................................................................................. 5 Implementasi Algoritme Sekuensial QS ...................................................................................... 6 Penerapan Metode Foster pada Algoritme QS ............................................................................ 6 Analisis Algoritme Paralel QS..................................................................................................... 6 Implementasi Algoritme Paralel QS ............................................................................................ 6 Perancangan Percobaan ............................................................................................................... 6 Percobaan .................................................................................................................................... 6 Analisis Kinerja ........................................................................................................................... 6 HASIL DAN PEMBAHASAN Studi Pustaka ............................................................................................................................... 6 Analisis Algoritme Sekuensial QS .............................................................................................. 7 Implementasi Algoritme Sekuensial QS ...................................................................................... 7 Penerapan Metode Foster pada Algoritme QS ............................................................................ 7 Analisis Algoritme Paralel QS..................................................................................................... 8 Implementasi Algoritme Paralel QS ............................................................................................ 8 Perancangan Percobaan ............................................................................................................... 8

v

Percobaan .................................................................................................................................... 9 Analisis Kinerja ........................................................................................................................... 9 KESIMPULAN DAN SARAN Kesimpulan ................................................................................................................................ 12 Saran .......................................................................................................................................... 12 DAFTAR PUSTAKA ..................................................................................................................... 12

vi

DAFTAR TABEL Halaman 1 2 3 4 5

Hasil Pencarian Residu Kuadrik.................................................................................................. 15 Hasil Pencarian si Positif. ............................................................................................................ 15 Hasil Pencarian si Negatif. ......................................................................................................... 15 Hasil Faktorisasi si....................................................................................................................... 16 Bentuk Biner dari Pangkat Faktor si. ........................................................................................... 17

DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Arsitektur distributed memory, multiple-CPU computer............................................................. 3 Ilustrasi Metode Foster (Quinn 2004) ........................................................................................ 4 Metode penelitian ........................................................................................................................ 5 Hasil metode Foster..................................................................................................................... 8 Waktu eksekusi percobaan 1 ....................................................................................................... 9 Waktu eksekusi percobaan 2 ....................................................................................................... 9 Waktu eksekusi 25 digit .............................................................................................................. 9 Waktu eksekusi 30 digit ............................................................................................................ 10 Waktu eksekusi 35 digit ............................................................................................................ 10 Speed up 25 digit ....................................................................................................................... 10 Speed up 30 digit ....................................................................................................................... 10 Speed up 35 digit ....................................................................................................................... 10 Efisiensi 25 digit ....................................................................................................................... 10 Efisiensi 30 digit ....................................................................................................................... 11 Efisiensi 35 digit ....................................................................................................................... 11 Efisiensi rata-rata ...................................................................................................................... 11 Cost dan overhead 25 digit........................................................................................................ 11 Cost dan overhead 30 digit........................................................................................................ 11 Cost dan overhead 35 digit........................................................................................................ 11 Cost dan overhead rata-rata....................................................................................................... 12

DAFTAR LAMPIRAN Halaman 1 Langkah-langkah penyelesaian kasus dan analisis algoritme QS. ............................................... 15 2 Penurunan fungsi waktu eksekusi algoritme QS ......................................................................... 20 3 Hasil percobaan ........................................................................................................................... 22

vii

1

PENDAHULUAN Latar Belakang Masalah dalam memfaktorisasi bilangan komposit telah membingungkan para ahli matematika selama lebih dari dua milenium (West 2007). Selain membutuhkan ketelitian yang tinggi hal tersebut juga membutuhkan waktu yang sangat lama bila memfaktorisasi bilangan komposit berdigit banyak. Pada masa kini faktorisasi bilangan komposit berdigit banyak dijadikan ajang kompetisi dengan hadiah utama sebesar $200,000. Kompetisi ini diselenggarakan oleh RSA Laboratories dan terus berlangsung hingga sekarang. Salah satu algoritme untuk memfaktorisasi bilangan komposit adalah algoritme penyaring kuadrik atau lebih sering dikenal dengan quadratic sieve (QS). Algoritme ini diperkenalkan oleh Carl Pomerance pada tahun 1982. Algoritme QS sangat tepat jika digunakan untuk memfaktorisasi bilangan komposit yang berukuran lebih sedikit dari 100 digit desimal (Pomerance 1996). Menurut hasil pembandingan Pomerance pada tahun 1996 dan beberapa penelitian lainnya algoritme ini adalah yang tercepat dalam memfaktorisasi bilangan komposit yang berukuran lebih kecil dari 100 digit desimal. Meskipun tercepat menurut hasil penelitian West pada tahun 2007 dalam tesisnya menyebutkan bahwa untuk memfaktorisasi bilangan komposit berukuran 70 digit saja membutuhkan waktu lebih dari 31.000 detik atau sekitar 9 jam jika dilakukan secara sekuensial. Salah satu metode untuk mempercepat waktu eksekusi adalah dengan menggunakan pemrosesan paralel yang bisa diterapkan secara distributed memory (tiap prosesor memiliki memorinya masing-masing), shared memory (tiap prosesor menggunakan sebuah memori secara bersama-sama), dan hybrid (distributed shared memory). Pada penelitian ini diterapkan pemrosesan paralel terhadap proses memfaktorisasi bilangan komposit menggunakan algoritme QS dengan distributed memory. Pemrosesan paralel yang digunakan adalah dengan cara domain decomposition dan functional decomposition. Tujuan Penelitian Tujuan dari penelitian ini adalah : 1. Menganalisis kompleksitas algoritme QS secara sekuensial maupun paralel. 2. Mengimplementasikan algoritme QS secara sekuensial dan paralel pada komputer

menggunakan bahasa C dengan library MPI dan GMP. 3. Menganalisis kinerja algoritme QS secara sekuensial dan paralel dengan menghitung waktu eksekusi, speed up, efisiensi, cost, dan overhead. Ruang Lingkup Penelitian Analisis teori, analisis algoritme, analisis uji perbandingan, dan implementasi algoritme penyaring kuadrik dibatasi untuk panjang bilangan komposit yang difaktorisasi adalah 25, 30, dan 35 serta jumlah proses yang dibangkitkan adalah 1, 2, 3, dan 4. Analisis performance metrics dibatasi pada waktu eksekusi, speed up, efisiensi, cost, dan overhead. Bahasa pemrograman yang digunakan adalah C dengan library tambahan MPI dan GMP.

TINJAUAN PUSTAKA Prima dan Bilangan Komposit Prima adalah suatu bilangan Intejer p ≥ 2 jika bilangan tersebut hanya dapat dibagi oleh 1 dan p. Intejer positif yang bukan prima disebut bilangan komposit (Crandall & Pomerance 2005). Teorema Dasar Aritmatika (TDA) Teorema dasar aritmatika berbunyi, "Setiap intejer N > 1 dapat dituliskan sebagai hasil kali a a beberapa bilangan prima. N = pa11 p22 … pk k dengan 𝑎𝑖 adalah intejer dan 𝑝𝑖 bilangan prima, untuk i = 1, 2,…,k" (Crandall & Pomerance 2005). Subeksponensial Subeksponensial yaitu suatu algoritme eksponensial yang memiliki kompleksitas no(1) atau pertumbuhannya seolah-olah seperti pertumbuhan polinomial berderajat tinggi serta kompleksitas ini adalah yang terkecil dalam algoritme faktorisasi (Crandall & Pomerance 2005). Faktorisasi Fermat Ide dasar algoritme Fermat untuk faktorisasi N adalah sebagai berikut. Jika N dapat dinyatakan N = x2 - y2, maka (x + y) dan (x - y) adalah faktor dari N. Ketika (x - y) > 1, maka N dikatakan mempunyai faktor non-trivial. Selanjutnya, jika N ganjil dan N = ab maka bentuk N = x2 - y2 dijamin tercapai dengan a+b a+b x= dan y = (Guritman 2010). 2

2

2 Metode Kraitchik dan Dixon Metode Kraitchik dan Dixon adalah perkembangan dari metode Fermat namun metode ini telah melakukan penyaringan sehingga pencarian menjadi lebih singkat (Guritman 2010). Proses yang dilakukan pada metode ini sama dengan metode penyaring kuadrik dasar, tetapi terdapat beberapa perbedaan yang di antaranya adalah: ketika membuat barisan prima batas nilai prima terbesar B didefinisikan sendiri, prima yang dibangkitkan tidaklah harus residu kuadrik, serta total penyaringan tidak ditetapkan sehingga pencarian dilakukan sejumlah yang diharapkan. Oleh karena itu algoritme penyaring kuadrik menyelesaikan kekurangan algoritme ini. Faktor Basis Faktor basis adalah suatu himpunan bilangan prima yang berbeda yang lebih kecil atau sama dengan dari suatu nilai basis B atau dapat dinotasikan sebagai F={p|p prima dan p ≤ B} (Guritman 2010). Least Absolute Residue Suatu bilangan b dikatakan least absolute residue dari bilangan a modulus n, dimana n adalah bilangan ganjil jika a ≡ b (mod n) dan -

n-1 2


n-1 2

(Crandall & Pomerance 2005).

B-smooth Suatu nilai b dikatakan smooth apabila pada b2 ≡ t (mod n) bilangan t merupakan least α absolute residue modulus n dan t = hi=1 pi i dimana B = {p1 ,p2 ,…,ph } adalah faktor basis dan αi > 0, untuk setiap i (Crandall & Pomerance 2005). Prima Relatif Jika GCD(a,b) = 1 maka bilangan bulat a dan b adalah bilangan prima relatif (Junaedi 1997). Bilangan a dan b tidaklah harus keduanya prima atau salah satunya. Contoh: 22 dan 15 adalah prima relatif namun 19 dan 57 serta 7 dan -7 bukan prima relatif karena hasil GCD(a,b) ≠ 1. Residu Kuadrik Untuk bilangan prima relatif a dan m dengan m positif, bilangan a adalah residu kuadrik (mod m) jika dan hanya jika x2 ≡ a(mod m) memiliki penyelesaian untuk bilangan bulat x (Crandall & Pomerance 2005). Jika tidak memiliki penyelesaian maka a adalah residu nonkuadrik (mod m). Contoh: 30 adalah residu

kuadrik terhadap 7 karena memiliki penyelesain yaitu 3 dan 4 sehingga 32 ≡ 30(mod 7) atau 42 ≡ 30(mod 7). Selain itu setiap bilangan ganjil adalah residu kuadrik terhadap 2 karena pasti memiliki solusi yaitu 1. Bergantung Linear Vektor-vektor v1 ,v2 ,… ,vn dalam ruang vektor V adalah bergantung linear jika terdapat skalar-skalar c1 ,c2 ,… ,cn yang tidak semuanya nol sehingga c1 v1 +c2 v2 +…+cn vn = 0. Contoh: misalkan x = (1,2,3)T. Vektor-vektor e1, e2, e3, x adalah bergantung linear karena e1 + 2e2 + 3e3 x = 0. Dalam hal ini c1 =1, c2 =2, c3 =3, c4 = -1 (Leon 2001). Penyaring Kuadrik (QS) Penyaring kuadrik adalah algoritme faktorisasi bilangan komposit modern yang memiliki kecepatan subeksponensial. Algoritme ini memungkinkan untuk memfaktorisasi lebih dari 50 digit yang algoritme sebelumnya hanya mampu memfaktorisasi hingga 20 digit. Penyaringan kuadrik memiliki beberapa variasi di antaranya adalah : 1. Basic QS 2. Fast matrix methods 3. Large prime variation 4. Multiple polynomials 5. Self initialization 6. Zhang’s special QS (Crandall & Pomerance 2005). Penyaring Kuadrik Dasar (Basic QS) Ide dasar metode ini sama dengan metode Kraitchik dan Dixon yang merupakan pengembangan dari metode Fermat, yang akan menjadi penekanan di sini adalah pengoptimalan pada metode penyaringan. Hal ini terkait dengan: 1. Memilih nilai B yang cukup optimal. 2. Memilih barisan prima p1 < p2 <…< pk ≤ B yang bisa mempercepat proses penyaringan. 3. Menentukan barisan pelacakan x1 , x2 ,…, xn sehingga memperbesar probabilitas bahwa semua faktor prima dari si = x2i mod N berada dalam F = p1 < p2 <…< pk . Dalam hal ini si disebut B-smooth. Secara umum langkah-langkah dari semua metode QS didasari dari metode basic QS. Pada metode lain biasanya hanya merubah bagianbagian tertentu saja misalkan pada MP-QS, metode ini merubah bentuk polinomial pada proses penyaringan dan aljabar linear. Adapun langkah-langkah metode basic QS adalah:

3 1.

Inisialisasi a. Tentukan nilai B B ~ L(N) di mana L N = e ln N ln ln N . b. Tentukan himpunan F = p p prima, p ≤ B,

2.

3.

4.

N p

=1 .

Penyaringan a. Saring barisan si = x2i - N untuk x0 = N dan x1 = xi-1 + 1 atau x1 = xi-1 - 1 yang memenuhi 𝑠𝑖 merupakan Bsmooth. Jika mencari si yang negatif, haruslah F = F ∪{-1} yang terkait dengan formulasi vektor binernya. b. Dapatkan sebanyak ( F +c) hasil saringan pasang (xi,si) dan dihimpun ke dalam himpunan S. Catatan bahwa nilai c adalah integer positif kecil (misalkan 𝑐 = 2 tergantung besarnya N). Nilai c digunakan untuk mengantisipasi terjadinya kegagalan faktorisasi pada langkah terakhir. Kalkulasi Aljabar Linear a. Untuk setiap x,s ∈ S, nyatakan s dalam representasi TDA s = p pσ(p) dengan p ∈ F secara terurut. b. Dari setiap representasi TDA dari s, definisikan vektor biner vs = [σ p mod 2] dengan panjang F bit. Catatan bahwa jika -1 ∈ F, maka bit pertama dari vs adalah “0” ketika s > 0 dan “1” ketika s < 0. c. Dari sebanyak S = F + c vektor biner definisikan matrik A berukuran S× F. d. Dari matriks A, dengan metode aljabar linear, pilih r vektor yang bergantung linear dan himpunan anggota-anggota S yang terkait yaitu H = xi1 ,si1 , xi2 ,si2 ,…, xir ,sir . Faktorisasi a. Dari himpunan H, hitung r X= k=1 xik mod N dan Y= b. c.

r k=1 sik

diperbesar (Crandall & Pomerance 2005). Contoh penyelesaian suatu kasus menggunakan algoritme penyaring kuadrik dasar (QS) dipaparkan dalam Lampiran 1 beserta analisis kompleksitasnya. Pemrograman Paralel Pemrograman paralel adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah atau operasi secara bersamaan (Jordan & Alaghband 2006). Algoritme paralel adalah sebuah urutan yang memberi tahu bagaimana cara untuk memecahkan suatu masalah menggunakan beberapa prosesor. Algoritme ini mencakup identifikasi bagian dari pekerjaan bersama ke dalam proses yang berjalan secara paralel, pengaturan akses data yang dibagi ke beberapa prosesor, pendistribusian input, output, dan data yang terkait dengan program serta koordinasi proses di berbagai tahapan pelaksanaan program paralel (Grama et al. 2003). Arsitektur Komputer Paralel Arsitektur komputer multiprocessors secara umum terbagi menjadi dua berdasarkan pemakaian memori utamanya, yaitu centralized multiprocessors atau biasa disebut juga shared memory dan distributed multicomputer atau distributed memory (Quinn 2004). Dari sebuah pandangan pemrograman, pada zaman sekarang setiap komputer pribadi memiliki lebih dari satu memori sehingga memori dan prosesor dikelompokkan bersama dan melahirkan suatu pendekatan terhadap arsitektur komputer paralel, pendekatan ini dikenal sebagai distributed shared memory (Wilkinson & Allen 2010). Distributed Memory

mod N.

Hitung g = GCD(X-Y,N). Jika 1 < g < N, maka g adalah faktor dari N. Jika g = 1 atau g = N, faktorisasi gagal. Catatan bahwa dalam kasus gagal, bisa kembali ke Langkah3 untuk mencari r vektor bergantung linear yang lain. Jika A tidak memuat himpunan vektor yang bergantung linear, maka nilai B atau c harus

Gambar 1 Arsitektur distributed memory, multiple-CPU computer Sistem paralel komputer disebut distributed multicomputer atau distributed memory karena komputer-komputer saling terhubung melalui suatu interkoneksi jaringan di mana memori

4 utama terdistribusi ke semua prosesor dan tiap prosesor memisahkan ruang alamat lokalnya (Quinn 2004). Ilustrasi arsitektur distributed memory dapat dilihat pada Gambar 1. Metode Foster Ian Foster mengemukakan empat langkah metode desain sistem paralel yang dimulai dari pembagian data ke dalam beberapa bagian, menentukan komunikasi antar bagian, mengelompokkan bagian yang memiliki komunikasi intensif dengan bagian lain, dan memetakan kelompok tersebut ke sejumlah prosesor yang ada. Empat tahapan desain tersebut adalah partitioning, communication, agglomeration, dan mapping (Quinn 2004). Ilustrasi metode Foster dapat dilihat pada Gambar 2.

yang signifikan menyumbangkan data untuk menunjukkan proses komputasi (Quinn 2004). c.

Aglomerasi (Agglomeration)

Aglomerasi adalah proses pengelompokkan task ke dalam task yang lebih besar guna meningkatkan kinerja program maupun menyederhanakan program (Quinn 2004). d.

Pemetaan (Mapping)

Pemetaan adalah proses penugasan task ke prosesor. Tujuan dari pemetaan adalah memaksimalkan kemampuan prosesor dan meminimalkan komunikasi antar prosesor (Quinn 2004). GMP GMP adalah library gratis untuk presisi aritmatika, operasi pada bilangan bulat bertanda, bilangan rasional, dan bilangan pecahan. Tidak ada batasan praktis untuk presisi kecuali memori yang tersedia pada mesin yang menjalankan GMP. GMP memiliki sangat banyak kumpulan fungsi, dan fungsi tersebut memiliki antarmuka yang sederhana. Message Passing Interface (MPI)

Gambar 2 Ilustrasi Metode Foster (Quinn 2004) a.

Partisi (Partitioning)

Partisi adalah suatu proses pembagian komputasi dan data ke dalam beberapa bagian. Ada dua cara untuk melakukan partisi, yaitu domain decomposition dan functional decomposition. Domain decomposition adalah pendekatan model algoritme paralel yang melakukan pembagian data menjadi beberapa bagian terlebih dahulu, kemudian menentukan bagaimana mengasosiasikan komputasi dengan data tersebut. Sedangkan functional decomposition melakukan pembagian komputasi terlebih dahulu (Quinn 2004). b.

Komunikasi (Communication)

Setelah melakukan partisi maka yang harus dilakukan adalah membuat suatu skema komunikasi antar bagian tersebut. Ada dua jenis komunikasi yang digunakan yaitu local communication dan global communication. Local communication adalah membuat saluran antar task ketika ada task yang membutuhkan nilai dari task lainnya. Global communication terjadi ketika ada primitif task dengan jumlah

MPI adalah sebuah standar library pengenalan dasar pemrograman sistem paralel. MPI dapat digunakan dengan berbagai bahasa pemrograman seperti bahasa C dan Fortran. Operasi utama yang dilakukan oleh standar MPI yaitu: a. Point-to-point Communication MPI point-to-point communication adalah komunikasi antar dua proses. Satu proses bertugas mengirim data atau operasi dan proses lainnya bertugas menerima data atau operasi tersebut. b. Collective Communication MPI collective communication adalah komunikasi dipanggil oleh semua proses dalam communicator dan melibatkan seluruh proses tersebut (Quinn 2004). Blocking dan Nonblocking Communication Pada umumnya setiap fungsi komunikasi pada MPI bersifat blocking communication yang artinya setiap memanggil fungsi komunikasi proses tersebut akan menunggu hingga proses-proses yang melakukan komunikasi selesai berkomunikasi baru bisa melakukan aktivitas lainnya. Selain blocking communication MPI pun menyediakan beberapa fungsi nonblocking communication yaitu fungsi komunikasi yang hanya bersifat inisialisasi saja sehingga setiap proses yang berkomunikasi tidak harus

5 menyelesaikan komunikasinya untuk melakukan kegiatan yang lain. Untuk menyelesaikan komunikasi nonblocking, MPI menyediakan fungsi penyelesaian yang bersifat blocking dan nonblocking (Quinn 2004). Communicator Communicator adalah suatu tempat yang merupakan kumpulan proses-proses yang berhubungan dalam suatu komunikasi (Quinn 2004).

METODE PENELITIAN Penelitian ini akan dikerjakan dalam beberapa tahap. Implementasi algoritme paralel penyaring kuadrik akan menggunakan metode Foster. Tahapan tersebut disesuaikan dengan metode penelitian yang dapat dilihat pada Gambar 3.

Performance Metric Performance metrics adalah salah satu cara untuk menganalisis kinerja algoritme paralel (Grama et al. 2003). Beberapa persamaan performance metric yaitu: a. Waktu Eksekusi Waktu eksekusi serial adalah waktu yang dihitung dari awal sampai akhir eksekusi pada komputer sekuensial, dilambangkan dengan Ts. Waktu eksekusi paralel adalah waktu yang dihitung ketika komputasi paralel dimulai sampai elemen proses terakhir selesai dieksekusi, dilambangkan dengan Tp. b. Speed up Speed up (S) adalah rasio dari waktu yang digunakan untuk menyelesaikan masalah dalam program sekuensial (Ts) terhadap waktu yang diperlukan untuk menyelesaikan masalah yang sama dengan program paralel (Tp). Speed up dirumuskan pada persamaaan berikut: Ts S= . Tp

c.

Efisiensi Efisiensi (E) adalah rasio antara speed up dengan banyaknya prosesor yang digunakan (p). Efisiensi dirumuskan pada persamaan berikut: S Ts E= = .

d.

Cost Cost (C) pada sistem paralel adalah hasil perkalian waktu eksekusi paralel dengan jumlah prosesor yang digunakan. Fungsi cost dirumuskan pada persamaan berikut: C = pTp. Overhead Overhead adalah kelebihan dari total waktu yang dibutuhkan oleh semua proses paralel dibandingkan proses sekuensial pada masalah yang sama. Fungsi overhead dirumuskan pada persamaan berikut: To = pTp - Ts.

p

e.

pTp

Gambar 3 Metode penelitian Studi Pustaka Pada tahap ini, kegiatan yang dilakukan adalah mengumpulkan semua informasi yang terkait dengan penelitian. Informasi tersebut didapat dari jurnal, buku, internet, dan artikel yang membahas algoritme QS dan pemrosesan paralel. Analisis Algoritme Sekuensial QS Tahap ini bertujuan untuk mengetahui struktur algoritma, langkah-langkah

6 penyelesaian suatu kasus beserta kompleksitas algoritme QS secara sekuensial.

dari implementasi algoritme sekuensial dan paralel.

Implementasi Algoritme Sekuensial QS

Analisis Kinerja

Pada tahap ini algoritme sekuensial QS diimplementasikan dengan menggunakan bahasa C dan library tambahan GMP versi 5.0.4. Fungsi-fungsi utama yang akan dibuat dalam algoritme ini adalah: 1. “Inisialisasi” sebagai fungsi pembentukan nilai B, barisan prima yang merupakan kuadratik residual dari nilai N. 2. “Penyaringan” merupakan fungsi untuk menentukan pasangan barisan yang merupakan nilai smooth dari B. 3. “Kalkulasi aljabar linear” yaitu untuk menentukan pasangan vektor bergantung linear. 4. “Faktorisasi” yaitu menentukan apakah hasil dari kalkulasi aljabar linear tersebut memiliki faktor prima dari nilai yang difaktorisasi.

Pada tahap analisis, hasil percobaan sekuensial QS akan ditentukan waktu eksekusinya dan algoritme paralel QS akan ditentukan waktu eksekusi, speed up, cost, efisiensi, dan overhead.

Penerapan Metode Foster pada Algoritme QS Pada tahap ini dirancang algoritme QS secara paralel menggunakan metode Foster dengan tahapan partisi, komunikasi, aglomerasi, dan pemetaan. Analisis Algoritme Paralel QS Tahapan ini bertujuan mengetahui kompleksitas algoritme paralel beserta kompleksitas komunikasi dari algoritme QS. Implementasi Algoritme Paralel QS Pada tahap ini algoritme paralel QS diimplementasikan dengan menggunakan bahasa C menggunakan library MPICH2. Implementasi paralel akan dilakukan dengan dua cara yaitu domain decomposition dan functional decomposition. Perancangan Percobaan Tahapan ini menentukan parameterparameter yang dibutuhkan untuk percobaan. Parameter-parameter tersebut antara lain: 1. Perangkat keras dan perangkat lunak. 2. Jumlah digit yang difaktorisasi. 3. Jumlah proses. 4. Performance Metric. Percobaan Dalam percobaan akan dicatat waktu eksekusi proses faktorisasi bilangan komposit

QS

secara

HASIL DAN PEMBAHASAN Studi Pustaka Hasil pengumpulan informasi mengenai algoritme QS dan pemrosesan paralel yang terkait tulisan ini telah dicantumkan dalam bab tinjauan pustaka dan beberapa akan dibahas di bab lainnya. Sebelum beranjak pada algoritme QS terlebih dahulu akan dijelaskan mengenai sejarah terbentuknya algoritme QS. Pada awalnya pendahulu algoritme ini adalah Metode Fermat yang memperbaiki algoritme brute force atau yang lebih dikenal dengan trial division. Fermat memiliki pemikiran yaitu pencarian faktorisasi dari perkalian dua buah bilangan prima akan lebih cepat jika dicari dari tengah karena pada umumnya hasil pencarian akan lebih dekat dengan akar nilai tersebut dibandingkan dengan awal nilai. Contoh: 7x11=77. Hasil faktorisasi 77 akan lebih cepat dicari dari akar 77 yaitu 8 dibandingkan dengan mencari dari 1. Jika mencari dari 8 proses pencarian hanya butuh dua kali yaitu 8 dan 7 sedangkan jika dari 1 akan dibutuhkan tujuh kali pencarian. Kompleksitas algoritme ini sama dengan pendahulunya namun bestcase pada algoritme ini adalah worstcase pada algoritme sebelumnya dan sebaliknya. Perbaikan dari Metode Fermat yang berujung pada algoritme QS adalah algoritme Kraitchik dan Dixon. Algoritme ini adalah algoritme pertama yang melakukan penyaringan. Ide dasar dari konsep penyaringan yaitu nilai-nilai pencarian berikutnya merupakan gabungan dari hasil-hasil pencarian sebelumnya. Sehingga untuk mencapai suatu nilai dari hasil faktorisasi, tidaklah harus mencari sampai hasil faktorisasi tersebut. Cukup dengan mengumpulkan nilai-nilai sebelumnya lalu dilakukan perhitungan hingga mendapatkan hasil faktorisasi. Langkah-langkah algoritme ini identik dengan algoritme QS namun algoritme ini memiliki beberapa kekurangan seperti yang tertera pada tinjauan pustaka dan algoritme QS menutup kekurangan tersebut.

7 Dalam implementasinya fungsi ini diberi nama saring. Perbedaannya adalah nilai z yang dipakai adalah 4. Proses pengalian anggota faktor basis telah dilakukan pada tahap inisialisasi. Proses pembuatan matriks pangkat yang seharusnya terjadi pada tahap 3 dipindahkan ke tahap ini yang bertujuan untuk optimasi pengerjaan secara paralel sehingga kompleksitasnya menjadi

Analisis Algoritme Sekuensial QS Pada dasarnya algoritme basic QS memiliki harapan waktu eksekusi L(N)1+o(N), dimana L(N) = e ln N ln ln N . Persamaan tersebut didapatkan dari hasil turunan kecepatan ketika memilih B saat proses inisialisasi. Kompleksitas dari algoritme ini yaitu no(1) dimana kompleksitas tersebut adalah turunan dari hasil waktu eksekusi tersebut. Adapun proses penurunan waktu eksekusi tertera pada Lampiran 2. Secara rinci penjelasan kompleksitas algoritme sekuensial QS yang dibuat pada tulisan ini dilampirkan pada Lampiran 1 bersamaan dengan langkah-langkah penyelesaian menggunakan algoritme QS. Adapun hasil pemaparan dari kompleksitas algoritme penyaring kuadrik dasar (QS) adalah O(e ln N ln ln N ) yang artinya sebanyak-banyaknya pencarian pada algoritme QS adalah sebesar e ln N ln ln N .

1

64e2

3.

ln N ln ln N

k+15e ln N ln ln N + . ln N ln ln N Kalkulasi aljabar linear Fungsi ini diberi nama alin_biner. Perbedaan dalam implementasinya yaitu pada tahap ini hanya melakukan operasi biner untuk mendapatkan vektor-vektor yang bergantung linear sehingga 4e ln N ln ln N

4.

komplesitasnya adalah k+ . ln N ln ln N Fakorisasi Secara garis besar, fungsi ini tidak mengalami perubahan sehingga

Implementasi Algoritme Sekuensial QS Implementasi dari algoritme QS tahapannya dilakukan indentik dengan langkah-langkah penyelesaian yang ada pada tulisan ini. Terdapat sedikit perbedaan yang bertujuan memperkecil kompleksitas dari tahapan tersebut. Perbedaan pada setiap tahapannya akan dijelaskan bersamaan dengan kompleksitas dari tahapan-tahapan tersebut dalam implementasinya. Catatan kompleksitas pada setiap tahapan sama secara big O. Adapun perbedaan tersebut adalah 1. Inisialisasi Perbedaan pertama yaitu fungsi ini dibagi menjadi 2 bagian dengan nama inisialisasi untuk segala perhitungan yang bersifat konstan dan compute_fb untuk membentuk faktor basis. Perbedaan kedua yaitu tidak ada perhitungan B sebagai batas namun langsung menghitung jumlah residu B kuadrik yang lebih kecil dari B yaitu . ln B Faktor basis dibentuk dari sebuah fungsi pada library GMP yaitu mpz_legendre B sejumlah . Hal tersebut tidak ln B mempengaruhi kompleksitas sebelumnya karena fungsi yang dibuat pada akhirnya seolah-olah tetap mecari anggota faktor basis yang besarannya kurang dari B. Perbedaan lainnya yaitu setiap anggota faktor basis langsung dikalikan pada tahap inisialisasi. Sehingga kompleksitas tahap ini menjadi 1

2.

k+3e2 ln N ln ln N + Penyaringan

1

2e2

ln N ln ln N

ln N ln ln N

.

1

4e2

ln N ln ln N

. kompleksitasnya adalah k + ln N ln ln N Jadi kompleksitas keseluruhan program sekuensial yang dibuat adalah 1

K+ .

70e2

ln N ln ln N

ln N ln ln N

1

+3e2

ln N ln ln N

+

4e ln N ln ln N ln N ln ln N

+15e

ln N ln ln N

Penerapan Metode Foster pada Algoritme QS Dalam algoritme QS proses harus dilakukan secara bertahap sehingga partisi yang optimal dilakukan adalah domain decomposition. Tahap yang paling optimal untuk dipartisi yaitu tahap penyaringan karena memiliki kompleksitas paling besar. Pada tulisan ini tidak dimungkinkan melakukan partisi secara domain decomposition pada tahap lainnya karena menggunakan fungsi-fungsi standar dari library GMP sehingga tahap lain selain penyaringan harus dilakukan secara utuh. Pada tulisan ini karena partisi domain decomposition hanya bisa dilakukan pada tahap penyaringan maka akan dilakukan juga functional decomposition terhadap tahap penyaringan dengan tahap berikutnya sehingga jika menggunakan dua proses, proses pertama akan melakukan setiap tahap kecuali tahap penyaringan dan proses kedua hanya melakukan tahap inisialisasi dan penyaringan. Jika dikerjakan menggunakan lebih dari dua proses maka proses pertama akan melakukan setiap tahap kecuali tahap penyaringan dan proses lainnya melakukan tahap inisialisasi serta akan melakukan domain decomposition pada tahap

8 penyaringan. Ilustrasi pembagian pekerjaan pada setiap proses dapat dilihat pada Gambar 4.

Pada tulisan ini jumlah data yang dikirimkan adalah log10 N byte karena data yang dikirimkan merupakan sebuah string dengan panjang log10 N. Proses pengiriman dilakukan sebanyak e ln N ln ln N kali karena pengiriman dilakukan hanya ketika nilai smooth ditemukan. Komunikasi lain yang dilakukan adalah pengiriman sebuah bilangan bulat dari proses 1 ke proses lainnya sebagai bentuk bahwa pencarian telah selesai sehingga proses lain dapat menghentikan pekerjaannya. Komunikasi ini dilakukan sebanyak P-1 pengulangan. Dalam implementasi yang dilakukan, sebuah bilangan bulat berukuran 4 byte sehingga total kompleksitas komunikasi dari algoritme ini adalah c =

e ln N ln ln N log10 N+4(P-1) B

.

Implementasi Algoritme Paralel QS

Gambar 4 Hasil metode Foster Analisis Algoritme Paralel QS Dari hasil penerapan metode Foster kompleksitas akan mengecil jika proses yang dibentuk lebih dari dua. Karena jika proses yang dibentuk hanya dua yang terjadi hanyalah perpindahan data dari proses dua ke proses satu sehingga hanya menambah kompleksitas yaitu komunikasi. Jadi kompleksitas algoritme QS secara paralel yang ideal adalah 1

K+

+

70e2

ln N ln ln N

ln N ln ln N

1

+3e2

ln N ln ln N

4e ln N ln ln N 15e ln N ln ln N + +c ln N ln ln N P-1

dimana P adalah jumlah proses dan c adalah komunikasi. Komunikasi yang digunakan dalam tulisan ini adalah pengiriman suatu nilai dari setiap proses ke proses 1. Adapun biaya saat y melakukan komunikasi data adalah dimana y B adalah jumlah data dalam byte dan B adalah bandwidth atau kecepatan pengiriman data antar proses yang dinotasikan dalam byte/detik. Perhitungan bandwidth berbeda-beda bergantung pada arsitektur paralel yang digunakan. Jika menggunakan arsitektur 1 komputer dengan banyak prosesor maka bandwidth adalah kecepatan pengiriman data antar prosesor melalui RAM. Jika menggunakan arsitektur banyak komputer maka bandwidth adalah kecepatan pengiriman data antar komputer yang bisa berupa kecepatan kabel LAN, wireless, atau internet.

Dalam implementasinya domain decomposition yang dilakukan bersifat round robin yang artinya setiap data dibagikan secara bergantian pada setiap proses. Contoh: jika ada 5 data {d1,d2,d3,d4,d5} dan 2 proses {p1,p2} secara round robin data akan dibagi menjadi {d1,d3,d5} untuk p1 dan {d2,d4} untuk p2. Terdapat pekerjaan tambahan saat terjadi komunikasi yaitu proses perubahan tipe data dari bilangan besar ke string dan dari string ke bilangan besar serta pengecekan pengiriman. Terjadi pengurangan pekerjaan yaitu pada saat pembentukan matriks pangkat karena dibuat bersamaan dengan pencarian nilai smooth. Karena proses mencari nilai smooth lebih lama dibandingkan pembentukan matriks pangkat maka nilai kompleksitas mencari matriks pangkat terbuang. Sehingga kompleksitas implementasi algoritme QS secara paralel adalah 1

K+3e2

+

e

ln N ln ln N

ln N ln ln N

+

4e ln N ln ln N ln N ln ln N

+

17e ln N ln ln N P-1

log10 N+4(P-1)

B dalam kompleksitas tersebut dapat ditafsirkan bahwa waktu eksekusi program paralel akan naik jika hanya menggunakan dua proses dibandingkan dengan implementasi secara sekuensial. Perancangan Percobaan Percobaan penelitian akan dilakukan dalam lingkungan sebagai berikut: a. Satu komputer quad core. b. Prosesor Intel Core i7-3610QM. c. Kecepatan prosesor 2.3GHz hingga 3.3GHz.

9 d. e. f.

RAM 8192 MBytes. Kecepatan RAM 667 MHz. Sistem operasi Windows 7 64bit Professional Edition. g. Aplikasi yang dibutuhkan untuk menjalankan program: MPICH2, compiler bahasa pemrograman C dengan library tambahan MPI dan GMP. Proses percobaan akan dibagi menjadi dua bagian yaitu percobaan sistem secara keseluruhan yang kemudian akan dibandingkan antara sekuensial dengan paralel dan percobaan sistem pada tahap penyaringan yang dilakukan dengan cara domain decomposition. Pada percobaan pertama parameterparameter yang digunakan adalah 1. Jumlah digit yang difaktorisasi adalah 25, 30, dan 35 digit. 2. Jumlah proses yang dibangkitkan adalah 1, 2, 3 dan 4. 3. Performance metric yang dihitung adalah waktu eksekusi, speed up, cost, efisiensi, dan overhead. Pada percobaan kedua parameter-parameter yang digunakan adalah 1. Jumlah digit yang difaktorisasi adalah 25, 30, dan 35 digit. 2. Jumlah proses yang digunakan saat melakukan penyaringan adalah 1, 2, dan 3. 3. Performance metric yang dihitung adalah waktu eksekusi, speed up, cost, efisiensi, dan overhead. Percobaan Data yang digunakan dalam penelitian ini adalah bilangan bulat positif berukuran besar yang dibentuk dari suatu aplikasi matematika untuk membentuk bilangan bulat prima berukuran besar secara acak. Data-data tersebut adalah 7299149961857474937873353 sebagai data 25 digit yang merupakan bentuk perkalian dari 2570207923343 x 2839906412071, 831688082926290986707736279471 sebagai data 30 digit yang merupakan bentuk perkalian dari 1007259158096473 x 825694237913927, dan data yang berukuran 35 digit adalah 80293214381737181784027059366179183 sebagai bentuk dari hasil perkalian 279869390409959723 x 286895305928675021. Percobaan dibagi menjadi 2 jenis. Jenis percobaan 1 yaitu waktu eksekusi keseluruhan tahap sampai mendapatkan hasil yang dilakukan dengan cara functional decomposition serta domain decomposition. Percobaan 2 yaitu waktu eksekusi pada tahap penyaringan yang dilakukan dengan cara domain decomposition. Data hasil percobaan dapat dilihat pada Lampiran 3.

Analisis Kinerja Hasil dari percobaan adalah waktu eksekusi, speed up, efisiensi, cost, dan overhead yang dipaparkan sebagai berikut. Waktu Eksekusi Hasil dari waktu eksekusi percobaan 1 dan 2 dapat dilihat pada Gambar 5 dan 6 serta perbandingan waktu eksekusi 25, 30, dan 35 digit dapat dilihat pada Gambar 7, 8, dan 9.

Gambar 5 Waktu eksekusi percobaan 1

Gambar 6 Waktu eksekusi percobaan 2 Dari Gambar 5 dan 6 dapat disimpulkan bahwa semakin tinggi jumlah digitnya maka waktu eksekusi akan semakin bertambah dan juga sebaliknya semakin banyak proses yang di bentuk maka waktu eksekusi akan semakin berkurang.

Gambar 7 Waktu eksekusi 25 digit

10

Gambar 8 Waktu eksekusi 30 digit

Gambar 10 Speed up 25 digit

Gambar 9 Waktu eksekusi 35 digit

Gambar 11 Speed up 30 digit

Pada percobaan 1 terlihat bahwa waktu eksekusi menggunakan 2 proses lebih lambat dibandingkan dengan 1 proses atau sekuensial. Hal ini dikarenakan jika menggunakan 2 proses, yang terjadi adalah paralelisasi dengan cara functional decomposition yang kompleksitasnya lebih tinggi dibandingkan dengan sekuensial. Pangkat tertinggi dari kompleksitas sekuensial adalah 15e ln N ln ln N sedangkan pada implementasi paralel adalah

17e ln N ln ln N P-1

Gambar 12 Speed up 35 digit

dan jika ln N ln ln N

jumlah proses = 2 menjadi 17e . Walaupun demikian kenaikan waktu eksekusi tidak begitu signifikan karena terjadi pengurangan waktu eksekusi yaitu ketika membuat matriks pangkat dari nilai smooth. Speed Up Speed up merupakan percepatan yang terjadi ketika ada penambahan proses. Hal ini dapat dihitung dari perbandingan waktu sekuensial dan paralel. Hasil speed up dari eksekusi data 25, 30, dan 35 digit dapat dilihat pada Gambar 10, 11, dan 12. Dari Gambar 10, 11, dan 12 dapat disimpulkan bahwa speed up yang terjadi pada percobaan 2 sudah baik karena sudah mendekati sejumlah proses yang dibentuk namun pada percobaan 1 kurang baik karena terdapat functional decomposition sehingga 1 proses menganggur dan mengakibatkan penurunan kecepatan yang signifikan.

Efisiensi Efisiensi merupakan dasar penilaian terhadap kelayakan suatu pekerjaan dilakukan secara paralel. Hasil perhitungan efisiensi dari eksekusi data 25, 30, dan 35 digit dapat dilihat pada Gambar 13, 14, 15, dan 16.

Gambar 13 Efisiensi 25 digit

11 efisiensi. Rata-rata dari keseluruhan efisiensi adalah 91.6%. Dengan kata lain proses domain decomposition pada tahap penyaringan algoritme QS 91.6% efisien untuk memfaktorisasi data sampai dengan 35 digit. Cost dan Overhead Hasil perhitungan cost dan overhead dari eksekusi data 25, 30, dan 35 digit dapat dilihat pada Gambar 17, 18, 19, dan 20. Gambar 14 Efisiensi 30 digit

Gambar 17 Cost dan overhead 25 digit Gambar 15 Efisiensi 35 digit Dari Gambar 13 ,14, dan 15 terlihat bahwa efisiensi dari percobaan 1 kurang baik hal ini dikarenakan algoritme QS harus dilakukan dengan cara bertahap. Karena percobaan 1 mengandung functional decomposition maka akan terjadi pengangguran pada sebuah proses. Sehingga dapat disimpulkan bahwa algoritme QS kurang baik jika dilakukan dengan cara functional decomposition. Gambar 18 Cost dan overhead 30 digit

Gambar 16 Efisiensi rata-rata Dari Gambar 16 dapat terlihat bahwa efisiensi rata-rata percobaan 2 sudah baik karena berada di atas 87% sehingga dapat disimpulkan bahwa algoritme QS baik jika dilakukan domain decomposition dalam tahap penyaringan. Selain itu dapat disimpulkan juga bahwa pada algoritme QS efisiensi akan semakin berkurang seiring bertambahnya suatu nilai. Hal ini dikarenakan semakin besar data yang dieksekusi maka akan semakin banyak komunikasi yang terjadi sehingga mengurangi

Gambar 19 Cost dan overhead 35 digit Cost adalah total keseluruhan waktu pada seluruh proses. Nilai cost yang baik adalah sama dengan waktu sekuensial. Sedangkan overhead adalah selisih nilai cost dengan waktu sekuensial. Overhead merupakan bentuk kelebihan waktu total keseluruhan proses dalam paralel terhadap waktu sekuensialnya. Dari Gambar 20 terlihat bahwa semakin besar datanya maka cost dan overhead yang

12 dihasilkan juga semakin besar. Hal ini dikarenakan semakin besar data yang dieksekusi maka akan semakin banyak komunikasi yang terjadi. Hal ini dapat dilihat dari kompleksitas komunikasi dari algoritme ini e ln N ln ln N log10 N+4(P-1)

adalah yang berarti B komunikasi akan tumbuh seiring dengan pertumbuhan N sehingga waktu eksekusi akan semakin bertambah yang menyebabkan cost akan semakin tinggi dan overhead juga akan bertambah sebagai imbas dari kenaikan cost.

bertambahnya N sehingga menyebabkan nilai cost dan overhead akan semakin besar jika data semakin besar. Saran Saran untuk penelitian lebih lanjut: Pada penelitian selanjutnya dapat dikembangkan menggunakan varian lain dari algoritme QS dalam memfaktorisasi bilangan besar yang memiliki waktu eksekusi jauh lebih cepat dibandingkan basic QS seperti: MP-QS, large prime variation QS, dan lain sebagainya. 2. Pada penelitian selanjutnya dapat menggunakan library lain gabungan antara MPI dan GMP sehingga proses pengiriman data tidak perlu mengubah tipe data terlebih dahulu sehingga kompleksitasnya akan menurun dan waktu eksekusi menjadi lebih cepat. 3. Pada penelitian selanjutnya dapat dikembangkan pemrograman paralel pada algoritme QS menggunakan shared memory atau gabungan MPI dan shared memory. 1.

DAFTAR PUSTAKA Crandall R, Pemorance C. 2005. Prime Number a Computational Perspective. Ed ke-2. New York: Springer. Gambar 20 Cost dan overhead rata-rata

KESIMPULAN DAN SARAN Kesimpulan Dari hasil penelitian ini dapat diambil kesimpulan sebagai berikut: 1. Kompleksitas algoritme QS secara sekuensial adalah O(e ln N ln ln N ) sedangkan kompleksitas paralelnya adalah O 2.

3.

e ln N ln ln N P

di mana P adalah jumlah

proses. Algoritme QS kurang baik jika menggunakan functional decomposition, namun baik dengan menggunakan domain decompositon pada tahap penyaringan dengan efisiensi rata-rata sebesar 91.6% untuk besar data yang difaktorisasi kurang dari sama dengan 35 digit. Kompleksitas komunikasi dari hasil implementasi paralel algoritme QS adalah e ln N ln ln N log10 N+4(P-1) B

komunikasi

yang berarti banyak akan tumbuh seiring

Grama A, Gupta A, Karypis G, Kumar V. 2003. Introduction to Parallel Computing. Harlow: Addison-Wesley. Guritman S. 2010. Faktorisasi dan Logaritme Diskret. Bogor: IPB Press. Jordan H, Alaghband G. 2006. Fundamentals of Parallel Processing. New Jersey: Prentice Hall. Junaedi F. 1997. Analisa algoritma Monte Carlo dalam rancangan kokoh [tesis]. Semarang: Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Diponegoro. Leon SJ. 2001. Aljabar Linear dan Aplikasinya. Bondan A, penerjemah; Hardani HW, editor. Jakarta: Erlangga. Terjemahan dari: Linear Algebra with Applications. Pomerance C. 1996. A tale of two sieve. http://www.ams.org/notices/199612/ [30 Des 2011].

13 Quinn MJ. 2004. Parallel Programming in C with MPI and OpenMP. San Francisco: McGraw-Hill. West AG. 2007. Bound optimization for parallel quadratic sieving using large prime variation [tesis]. Virginia: The Faculty of the Departement of Computer Science, Washington and Lee University. Wilkinson B, Allen M. 2010. Parallel Programming Teknik dan Aplikasi Menggunakan Jaringan Workstation dan Komputer Paralel. Hidayat S, Santosa YB, Hery A, Himamunanto R, penerjemah. Yogyakarta: ANDI. Terjemahan dari: Parallel Programming Techniques and Applications Using Networked Workstation Parallel Computers.

LAMPIRAN

15 Lampiran 1 Langkah-langkah penyelesaian kasus dan analisis algoritme QS. Secara rinci kompleksitas algoritme sekuensial QS yang dibuat pada tulisan ini akan dijelaskan bersamaan dengan contoh menyelesaikan permasalahan dengan algoritme QS. Contoh: misalkan p = 47 dan q = 103 sehingga N = p x q yaitu 4841. Adapun langkah-langkah penyelesaian algoritme QS yaitu: 1. Inisialisasi. Tetapkan B sebagai batas faktor basis dan menentukan barisan prima p sehingga N residu 1

kuadrik terhadap p. 𝐵 = 𝑒 2 ln 𝑁 ln ln 𝑁 yaitu 8.4 lalu cari bilangan prima sesuai ketentuan yaitu seperti yang tertera pada Tabel 1. p

N (mod p)

Residu Kuadrik

2

1

YA

3

2

TIDAK

5

1

YA

7 4 YA Tabel 1 Hasil Pencarian Residu Kuadrik. Sehingga faktor basis yang terbentuk adalah F={2,3,7}. Kompleksitas dari proses inisialisasi 1

yaitu konstan pada menghitung B dan 3𝑒 2 ln 𝑁 ln ln 𝑁 untuk pencarian faktor basis. Pada tulisan ini kompleksitas yang dicantumkan adalah kompleksitas perkiraan sesuai yang terlihat oleh kasat mata. Pada kenyataannya kompleksitas mencari p, N (mod p), dan residu kuadrik berbeda-beda sesuai algoritme yang digunakan. Pada tulisan ini perkiraan kompleksitas 1

inisialisasi yaitu k + 3𝑒 2 2.

ln 𝑁 ln ln 𝑁

dimana k adalah konstan.

Penyaringan. Saring barisan 𝑠𝑖 = 𝑥𝑖2 − 𝑁 untuk 𝑥0 = 𝑁 sebanyak 𝐹 + 𝑐 dimana c adalah konstan. Pada tulisan ini 𝑐 = 2. Pemilihan nilai 2 akan dijelaskan pada tahap selanjutnya. Sebenarnya nilai c dapat ditentukan sesuai kebutuhan, namun agar mempermudah pengertian terhadap algoritme ini nilai c dipilih 2, sehingga jumlah nilai 𝑠𝑖 yang harus disaring adalah 5. Setelah ditemukan sejumlah yang ditentukan, pasangkan xi dengan 𝑠𝑖 . Nilai 𝑠𝑖 harus merupakan Bsmooth yaitu faktor-faktor pembentuk 𝑠𝑖 harus berada pada faktor basis. Contoh: 200 merupakan B-smooth karena faktor pembentuk 200 yaitu 23 x 52. Bilangan 2 dan 5 berada dalam faktor basis sehingga 200 termasuk B-smooth. Contoh berikutnya 488 bukan merupakan B-smooth karena faktor pembentuk 488 yaitu 2 3 x 61. Karena 61 bukan anggota dari faktor basis maka 488 bukan B-smooth. Adapun hasil dari penyaringan yaitu seperti yang tertera pada Tabel 2 dan Tabel 3. i

x

si

Validasi

i

mx

si

1

70

59

FALSE

1

69

-80

TRUE

2

71

200

TRUE

2

68

-217

FALSE

3

72

343

TRUE

3

67

-352

FALSE

4

73

488

FALSE

4

66

-485

FALSE

5

74

635

FALSE

5

65

-616

FALSE

6

75

784

TRUE

6

64

-745

FALSE

7

63

-872

FALSE

8

62

-997

FALSE

9

61

-1120

TRUE

Tabel 2 Hasil Pencarian si Positif.

Validasi

Tabel 3 Hasil Pencarian si Negatif.

16 Lampiran 1 Lanjutan Pada tulisan ini cara mencari 𝑠𝑖 yang B-smooth yaitu mencari 1 yang positif lalu 1 yang negatif. Karena hanya membutuhkan 5 buah 𝑠𝑖 maka jumlah 𝑠𝑖 yang dihasilkan yaitu 3 buah positif dan 2 buah negatif. Catatan pencarian 𝑠𝑖 dapat dilakukan hanya dengan mencari yang positif saja atau negatif saja. Karena algoritme pendahulunya yaitu Metode Fermat hanya mencari ke satu arah dikarenakan jika mencari ke dua arah akan membuat pencarian lebih lama. Berbeda dengan Metode Fermat proses penyaringan ke satu arah pada algoritme QS akan membuat proses penyaringan lebih lama, karena semakin menjauhi 𝑁 nilai 𝑠𝑖 yang merupakan B-smooth akan semakin sulit ditemukan. Oleh sebab itu alangkah lebih baik proses penyaringan dilakukan ke dua arah. Pada kasus ini kita hanya perlu mencari 15 kali pencarian. Pada kasus terburuknya menurut Pomerance dan penelitian lainnya kita harus mencari sebanyak 𝑒 ln 𝑁 ln ln 𝑁 yaitu sebanyak 70 kali pencarian. Dalam kasus ini terlihat 𝑒 ln 𝑁 ln ln 𝑁 seperti 𝑁 namun sebenarnya pertumbuhan 𝑒 ln 𝑁 ln ln 𝑁 lebih lambat dibandingkan dengan 𝑁. Menurut hasil penurunan perhitungan jumlah dari 𝐹 adalah 𝐵 sebanyak . Proses validasi untuk mengecek 𝑠𝑖 yang merupakan B-smooth menggunakan ln 𝐵 algoritme sebagai berikut: a. Kalikan semua bilangan prima yang berada pada faktor basis dan simpan dalam suatu variabel misalkan T. b. Untuk setiap 𝑠𝑖 lakukan modulasi T (mod 𝑠𝑖 ) lalu kuadratkan. Lakukan sebanyak z kali. Jika menghasilkan 0 maka 𝑠𝑖 adalah B-smooth dan sebaliknya (Crandall & Pomerance 2005). Bilangan z adalah bilangan kecil yang merupakan turunan dari B. Bilangan z paling optimal saat ini jika menggunakan penyaringan kuadrik dasar adalah 6 untuk bilangan tertinggi yang layak difaktorisasi. Pada tulisan ini bilangan z yang dipakai adalah 4 karena N tertinggi yang difaktorisasi adalah berjumlah 35 digit. Akan tetapi untuk menghitung kompleksitas akan digunakan z = 6 sebagai bentuk kasus terburuk. Catatan untuk algoritme penyaring kuadrik yang lain z bisa lebih besar dari 6 karena nilai N yang difaktorisasi bisa jauh lebih besar dibandingkan dengan algoritme penyaring kuadrik dasar. Pada kenyataannya z tumbuh sesuai pertumbuhan N namun pertumbuhannya sangatlah lambat. Dengan demikian dapat disimpulkan kompleksitas penyaringan pada algoritme QS adalah 1

𝑘+

2𝑒 2

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁 1

2𝑒 2

+ 3𝑒

ln 𝑁 ln ln 𝑁

+ 18𝑒

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁

=𝑘+ + 21𝑒 ln 𝑁 ln ln 𝑁 ln 𝑁 ln ln 𝑁 dimana k adalah segala bentuk perhitungan yang bersifat konstan atau tidak terpengaruh oleh pertumbuhan N. 3.

Kalkulasi Aljabar Linear. Dari hasil saringan pasangan xi dan 𝑠𝑖 faktorkan 𝑠𝑖 terhadap faktor basis dan buat matriks pangkat dari si. Pangkat dibutuhkan untuk untuk mencari bentuk kuadrat karena 𝑠𝑖 = 𝑥𝑖2 − 𝑁 kongruen terhadap 𝑁 = 𝑥𝑖2 − 𝑠𝑖 yang artinya N akan bisa diselesaikan jika 𝑠𝑖 berbentuk kuadrat. Pada tahap ini akan dilakukan operasi perhitungan terhadap pangkat 𝑠𝑖 sehingga mendapatkan 𝑠𝑖 yang berbentuk kuadrat. Adapun hasil faktorisasi seperti yang tertera pada Tabel 4. i

si

-1

2

5

7

1

200

0

3

2

0

2

-80

1

4

1

0

3

343

0

0

0

3

4

-1120

1

5

1

1

5 784 0 4 0 2 Tabel 4 Hasil Faktorisasi si.

17 Lampiran 1 Lanjutan Untuk mendapatkan bentuk kuadrat, setiap faktor 𝑠𝑖 haruslah berpangkat genap. Dalam proses mengalikan 2 buah 𝑠𝑖 yang terjadi adalah proses penjumlahan pangkat dari setiap faktor 𝑠𝑖 tersebut. Pada proses penjumlahan terdapat tiga kondisi yaitu: pertama ganjil ditambah ganjil = genap, kedua ganjil ditambah genap adalah ganjil, dan terakhir genap ditambah genap adalah genap. Jika diperhatikan secara seksama proses penjumlahan pangkat ini sama dengan proses XOR pada bilangan biner dimana ganjil = 1 dan genap = 0. Dalam tahap ini yang dibutuhkan adalah 𝑠𝑖 berbentuk kuadrat dan tidak memerhatikan pangkat dari 𝑠𝑖 tersebut. Oleh karena itu untuk memudahkan proses pembentukan 𝑠𝑖 yang kuadrat alangkah lebih mudah pangkat dari faktor-faktor 𝑠𝑖 tersebut diubah ke dalam bentuk biner. Adapun bentuk biner dari pangkat faktor-faktor 𝑠𝑖 dapat dilihat pada Tabel 5. Setelah mendapatkan matriks biner lakukan kalkulasi aljabar linear biner untuk mendapatkan vektor-vektor yang bergantung linear. Vektor bergantung linear seperti definisinya pada tinjauan pustaka yaitu vektor yang memiliki pengali konstanta tak 0 dan menghasilkan vektor 0. Vektor 0 dalam biner yaitu suatu vektor yang semua anggotanya 0. Jika vektor 0 diibaratkan sebagai pangkat dari faktor-faktor 𝑠𝑖 , vektor 0 adalah bentuk pangkat kuadrat dari 𝑠𝑖 . i

si

-1

2

5

7

1

200

0

1

0

0

2

-80

1

0

1

0

3

343

0

0

0

1

4

-1120

1

1

1

1

5 784 0 0 0 0 Tabel 5 Bentuk Biner dari Pangkat Faktor si. Mungkin akan timbul pertanyaan "mengapa harus yang bergantung linear?" Seperti definisinya bergantung linear yaitu ada pengali tak 0 terhadap suatu vektor sehingga menghasilkan vektor 0. Dalam biner tak 0 berarti 1 yang artinya vektor bersangkutan adalah vektor yang membentuk vektor 0. Untuk lebih jelasnya mengenai bergantung linear akan dibahas dalam hasil operasi aljabar linear biner. Operasi aljabar linear biner yang dilakukan dalam tulisan ini dipaparkan dalam algoritme sebagai berikut a. Pasangkan matriks pangkat dengan matriks identitas sejumlah i. b. Lakukan operasi baris dasar sebagai berikut: 1. Pilih satu paling kiri dari matriks pangkat. 2. Pindahkan baris tersebut bersama dengan baris matriks identitas kebarisan paling atas. 3. Lakukan operasi XOR pada matriks pangkat dan identitas pada baris yang memiliki kedudukan 1 yang sama dengan yang dipilih langkah 1. 4. Ulangi langkah pertama dengan matriks baru yaitu matriks dibawah baris yang terpilih. 5. Lakukan hingga 1 yang paling kanan. Adapun ilustrasi langkah-langkah operasi baris dasar pada matriks biner adalah sebagai berikut: 1. Pasangkan matriks biner dan identitas sebagai berikut identitas i1

i2

i3

i4

i5

0

1

0

0

1

0

0

0

0

1

0

1

0

0

1

0

0

0

0

0

0

1

0

0

1

0

0

1

1

1

1

0

0

0

1

0

0

0

0

0

0

0

0

0

1

18 Lampiran 1 Lanjutan 2.

Lakukan operasi baris dasar sebagai berikut pilih baris ke 2, pindahkan ke baris pertama, lalu lakukan operasi XOR pada baris ke 4 menggunakan baris tersebut. Sehingga hasilnya adalah

1 0 0 0 0 3.

0 0 1 1 0

i1 0 1 0 0 0

i5 0 0 0 0 1

0 1 0 0 0

1 0 0 0 0

0 0 1 1 0

i1 0 1 0 1 0

identitas i2 i3 i4 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0

i5 0 0 0 0 1

Selanjutnya pilih baris ke 3 dan lakukan operasi XOR pada baris ke 4 menggunakan baris tersebut. Hasil dari operasi baris dasar tersebut adalah

1 0 0 0 0 5.

1 0 0 0 0

Selanjutnya pilih baris ke 2 dan lakukan operasi XOR pada baris ke 4 menggunakan baris tersebut. Hasil dari operasi baris dasar tersebut adalah

1 0 0 0 0 4.

0 1 0 1 0

identitas i2 i3 i4 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 1 0 0

i1 0 1 0 1 0

identitas i2 i3 i4 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0

i5 0 0 0 0 1

Karena sudah mencapai 1 yang paling kanan hentikan operasi baris dasar.

Dari hasil aljabar tersebut yang dimaksud vektor 0 adalah 2 baris terakhir pada matriks pangkat pada hasil akhir operasi baris dasar pada matriks biner. Sedangkan konstanta tak 0 pembentuk vektor 0 adalah 2 baris terakhir pada matriks identitas. Vektor-vektor bergantung linear yang dimaksud yaitu vektor-vektor pembentuk vektor 0 yang memiliki nilai 1. Contoh: pada baris ke 4 1𝑠1 + 1𝑠2 + 1𝑠3 + 1𝑠4 + 0𝑠5 = 𝟎 yang artinya 𝑠1 , 𝑠2 , 𝑠3 , dan 𝑠4 saling bergantung linear dimana c1=1, c2=1, c3=1, c4=1, dan c5=0. Disini terjawab mengapa c=2 saat penyaringan yaitu untuk mendapatkan minimal 1 pasang vektor yang bergantung linear sehingga setidaknya ada 1 vektor 0 sebagai bentuk kuadrat dari 𝑠𝑖 . Kompleksitas dari setiap faktorisasi 𝑠𝑖 pada kasus terburuknya adalah 2x+1 dimana x terburuk pada algoritme ini adalah 6. Pada kasus terburuknya setiap faktorisasi 𝑠𝑖 adalah 128 kali pembagian. Proses perubahan ke biner tidak memiliki kompleksitas karena pada kenyataannya pangkat langsung diubah ke biner saat perhitungan agar lebih cepat. Kompleksitas aljabar linear biner adalah 𝑘 + 2 𝐹 ( 𝐹 − 1)/2 + 𝐹 = k + |𝐹|2 sehingga secara keseluruhan kompleksitas dari tahap kalkulasi aljabar linear adalah 1

𝑘+

256 𝑒 2

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁

+

4𝑒 ln 𝑁 ln ln 𝑁 ln 𝑁 ln ln 𝑁

.

19 Lampiran 1 Lanjutan 4.

Faktorisasi. Ambil salah satu pasang vektor yang bergantung linear. Kalikan semua xi yang merupakan pembentuk vektor 0 atau yang memiliki ci=1 dan simpan dalam variabel X. Lakukan hal yang sama terhadap 𝑠𝑖 namun sebelum disimpan dalam suatu variable akarkan hasil perkalian tersebut dan simpan dalam variabel Y. Lakukan operasi p=GCD(X-Y,N). Jika 1< p < N, p adalah faktor dari N. Jika p = 1 atau p = N berarti faktorisasi gagal dan cari pasangan yang lain. GCD adalah fungsi mencari faktor persekutuan terbesar atau yang lebih dikenal dengan FPB. Adapun langkah algoritme GCD(A,B) yang dimaksud adalah a. A = A (mod B) b. Tukar A dan B c. Ulangi dari langkah a hingga nilai B bernilai 0 yang berarti A adalah hasil GCD(A,B). Catatan kegagalan pada tahap faktorisasi sering kali terjadi karena lupa mengakarkan hasil perkalian 𝑠𝑖 sebelum disimpan dalam variabel Y. Pada contoh kasus dalam tulisan ini jika diambil baris ke-empat dari hasil akhir operasi baris dasar pada matriks biner hasilnya adalah p = GCD(21516408-78400,4841) = 103 untuk mencari faktor lainnya cukup dengan membagi N dengan p yaitu 47. Jika yang diambil adalah baris ke-lima dari hasil akhir operasi baris dasar pada matriks biner hasilnya adalah p = GCD(75-28,4841) = 47 yang hasilnya kebetulan berlawanan dengan baris ke-empat. Adapun kompleksitas dari tahap ini adalah 2 𝐹 yaitu proses pembentukan Y dan X. Untuk proses GCD dan lainnya dianggap konstan karena hanya melakukan sedikit perhitungan. Sehingga kompleksitas tahap ini adalah 1

4𝑒 2

ln 𝑁 ln ln 𝑁

𝑘+ . ln 𝑁 ln ln 𝑁 Dengan demikian dapat disimpulkan kompleksitas total dari algoritme penyaring kuadrik dasar dalam tulisan ini adalah 1

𝐾 + 3𝑒 2

1

ln 𝑁 ln ln 𝑁

1

262 𝑒 2

+

ln 𝑁 ln ln 𝑁

2𝑒 2

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁 1

1

+ 21𝑒

ln 𝑁 ln ln 𝑁

+

4𝑒 ln 𝑁 ln ln 𝑁

256 𝑒 2

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁

+

4𝑒 ln 𝑁 ln ln 𝑁 ln 𝑁 ln ln 𝑁

1

+

4𝑒 2

ln 𝑁 ln ln 𝑁

ln 𝑁 ln ln 𝑁

.

=𝐾+ + 3𝑒 2 ln 𝑁 ln ln 𝑁 + + 21𝑒 ln 𝑁 ln ln 𝑁 . ln 𝑁 ln ln 𝑁 ln 𝑁 ln ln 𝑁 Variabel K adalah gabungan dari semua konstanta pada setiap tahap. Pangkat tertinggi dari kompleksitas tersebut adalah 21𝑒 ln 𝑁 ln ln 𝑁 . Sehingga dapat dikatakan bahwa kompleksitas algoritme penyaring kuadrik dasar (QS) adalah O(𝑒 ln 𝑁 ln ln 𝑁 ) yang artinya sebanyak-banyaknya pencarian pada algoritme QS adalah sebesar 𝑒 ln 𝑁 ln ln 𝑁 .

20 Lampiran 2 Penurunan fungsi waktu eksekusi algoritme QS Dalam memilih B yang optimal sehingga waktu eksekusi akan minimum, fakta pertama yang cukup relevan adalah probabilitas sukses bahwa suatu anggota dalam ℤ𝑁 merupakan B-smooth adalah sekitar ln 𝑁 𝑢−𝑢 dengan 𝑢 = ln 𝐵

Sebagai ilutrasi, jika N = 600377819 dan B = 100, maka peluang intejer acak dalam ℤ𝑁 merupakan B-smooth sekitar 1.5159 x 10-3. Jika penentuan barisan pelacakan megunakan Metode Fermat (𝑥1 = 𝑁 ), maka peluang sukses bahwa s adalah B-smooth menjadi lebih baik, yaitu sekitar 1

𝑢−𝑢 dengan 𝑢 = 2

ln 𝑁

ln 𝐵

Perlu diingat pula bahwa dengan pelacakaan ini, penghitung s cukup dengan 𝑠 = 𝑥 2 − 𝑁 dan 𝑠 positif. Sekarang, jika diberikan suatu nilai B, seberapa cepat waktu yang diperlukan untuk menguji bahwa satu 𝑠 adalah B-smooth untuk suatu nilai x? Pertanyaan ini perlu mendapat perhatian karena peluang sukses bahwa 𝑠 adalah B-smooth cukup kecil sehingga uji tersebut akan dilakukan berulang-ulang. Metode termudah yang terkait dengan pertanyaan tersebut adalah trial division (dengan representasi TDA). Metode tercepat adalah dengan Penyaringan Eratosthenes yang hanya melibatkan (ln ln 𝐵) operasi, namun metode ini memerlukan memori besar. Dalam penyaringan Kraitchik dan Dixon dipilih F adalah himpunan semua prima 𝑝 ≤ 𝐵, berarti 𝐹 = 𝜋 (𝐵) merupakan banyaknya semua prima kurang atau sama dengan 𝐵. Sebagaimana dinyatakan sebelumnya bahwa nilai 𝐹 terkait banyaknya vektor biner bergantung linear yang diperlukan. Jadi nilai 𝐹 yang kecil akan mempercepat proses penyaringan. Berikut ini diberikan suatu ide dasar untuk memperkecil nilai 𝐹 . Jika p adalah prima yang membagi 𝑠 = 𝑥 2 − 𝑁, maka 𝑥 2 ≡ 𝑁 (𝑚𝑜𝑑 𝑝) Ini berarti 𝑁 merupakan residu kuadratik modulo 𝑝 (Bilangan Legendre

𝑁 𝑝

= 1). Dengan

demikan, prima 𝑝 ≤ 𝐵 yang menyebabkan 𝑁 bukan residu kuadratik modulo 𝑝 tidak layak untuk dijadikan anggota 𝐹. Jadi, 𝐹 selayaknya didefinisikan sebagai 𝐹 = 𝑝/𝑝 𝑝𝑟𝑖𝑚𝑎, 𝑝 ≤ 𝐵,

𝑁 =1 𝑝

Maka berdasarkan suatu proposisi yang berbunyi "Misalkan 𝑝 prima ganjil, maka sebanyak (separuh) anggota ℤ𝑝 adalah residu kuadratik dan separuh sisanya kuadratik." Sekarang 𝐹 ~

𝜋(𝑝) 2

~

𝐵 ln 𝐵

𝑝−1 2

𝑝 −1 2

adalah nonresidu

(berkurang setengahnya).

Akhirnya, bagaimana menentukan nilai B yang terbaik? Perhatikan bahwa karena probabilitas untuk satu s merupakan B-smooth adalah 𝑢−𝑢 , harapan sukses untuk mendapat satu s yang Bsmooth adalah 𝑢𝑢 . Dengan demikian, harapan sukses untuk mendapatkan s yang B-smooth sebanyak ( 𝐹 + 1) adalah melibatkan langkah (operasi) sebanyak 𝜋(𝑝) 𝑢𝑢 𝐹 + 1 = 𝑢𝑢 +1 2 Jika pengujian s adalah B-smooth diasumsikan menggunakan Metode Penyaringan Eratosthenes dan pelacakanya menggunakan Metode Fermat, maka total langkah yang diperlukan bisa dinyatakan sebagai fungsi 𝜋 𝑝 ln 𝑁 𝑇(𝐵) = 𝑢 𝑢 + 1 (ln ln 𝐵), dengan 𝑢 = 2

~𝑢𝑢

𝐵 ln 𝐵

+ 1 (ln ln 𝐵),

2 ln 𝐵

dengan 𝑢 =

ln 𝑁 2 ln 𝐵

21 Lampiran 2 Lanjutan Dari pendefinisian fungsi ini, akan dicari (dengan pendekatan) nilai B sebagai fungsi dari N yang meminimalkan 𝑇(𝐵). Untuk penyederhanaan didefinisikan 𝑆 𝐵 = 𝑙𝑛 𝑇 𝐵 ~ 𝑢 𝑙𝑛 𝑢 + ln 𝐵 sehingga 𝑑𝑆 1 𝑑𝑢 𝑑𝑢 1 =𝑢 + ln 𝑢 + 𝑑𝐵 𝑢 𝑑𝐵 𝑑𝐵 𝐵 =

𝑑𝑢 𝑑𝐵

1 + ln 𝑢 +

1 𝐵

Kemudian, dicari bilangan kritisnya diperoleh dari persamaan 𝑑𝑆 𝑑𝑢 1 =0⇔ 1 + ln 𝑢 + = 0 𝑑𝐵 𝑑𝐵 𝐵 Karena 𝑑𝑢 𝑑 1 = ln 𝑁 𝑑𝐵 𝑑𝐵 2

ln 𝐵

−1

=

− ln 𝑁 2𝐵 ln 𝐵

2

dan ln 𝑢 = ln

ln 𝑁 = ln ln 𝑁 − ln ln 𝐵 − ln 2 2 ln 𝐵

maka persamaannya menjadi ln 𝑁 2𝐵 ln 𝐵 2 ln 𝐵

2

2

ln ln 𝑁 − ln ln 𝐵 − ln 2 + 1 =

1 𝐵

= ln ln 𝑁 − ln ln 𝐵 − ln 2 + 1

Dengan pendekatan selanjutnya diperoleh ln 𝐵 ~

1 ln 𝑁 ln ln 𝑁 2

sehingga 𝐵~ 𝑒

1 ln 𝑁 ln ln 𝑁 2

⇔ 𝐵2 ~𝑒

ln 𝑁 ln ln 𝑁

Dari hasil ini menunjukan bahwa estimasi running time adalah 𝐿(𝑁)~𝑒

ln 𝑁 ln ln 𝑁

ketika dipilih nilai B adalah 𝐵~ 𝐿(𝑁) Hasil tersebut mengabaikan proses aljabar linearnya. Dengan asumsi validitas dari semua lompatan heuristik dibuat, kita telah menggambarkan suatu algoritme deterministik untuk pemfaktoran komposit ganjil bukan berpangkat dengan waktu eksekusi 𝐿(𝑁)1+𝑜(𝑁) dan merupakan fungsi subeksponensial (Guritman 2010).

22 Lampiran 3 Hasil percobaan Jenis Percobaan

Jumlah Digit

Waktu Eksekusi Program (detik) 3 proses

4 proses

1.170

1.192

0.614

0.416

1.156

1.157

0.640

0.403

1.164

1.203

0.633

0.410

1.158

1.162

0.621

0.407

1.221

1.188

0.601

0.412

1.174

1.180

0.622

0.410

speed up

0.994

1.888

2.866

efisiensi

0.497

0.629

0.716

cost

2.361

1.865

1.638

overhead

1.187

0.692

0.465

1

25

waktu rata-rata

Jenis Percobaan

Jumlah Digit

1 proses

2 proses

Waktu Eksekusi Program (detik) 1 proses

2 proses

3 proses

4 proses

39.995

41.369

21.843

15.868

39.975

41.436

22.248

15.760

39.951

41.030

22.068

15.930

39.949

41.101

22.222

15.671

39.987

41.057

22.091

15.643

39.971

41.199

22.094

15.774

speed up

0.970

1.809

2.534

efisiensi

0.485

0.603

0.633

cost

82.397

66.283

63.098

overhead

42.426

26.312

23.126

1

30

waktu rata-rata

Jenis Percobaan

Jumlah Digit

Waktu Eksekusi Program (detik) 1 proses

2 proses

3 proses

4 proses

521.248

536.037

278.788

226.518

521.176

538.656

277.951

228.246

520.931

540.544

278.804

226.060

522.243

539.277

278.296

226.977

521.245

538.013

276.916

227.681

521.369

538.505

278.151

227.096

speed up

0.968

1.874

2.296

efisiensi

0.484

0.625

0.574

cost

1077.011

834.453

908.386

overhead

555.642

313.084

387.017

1

35

waktu rata-rata

23 Lampiran 3 Lanjutan Jenis Percobaan

Jumlah Digit

Waktu Eksekusi Program (detik) 1 proses

2 proses

3 proses

1.178

0.602

0.407

1.148

0.625

0.395

1.195

0.624

0.400

1.153

0.607

0.398

1.179

0.586

0.401

1.171

0.609

0.400

speed up

1.923

2.925

efisiensi

0.961

0.975

cost

1.218

1.201

overhead

0.047

0.030

2

25

waktu rata-rata

Jenis Percobaan

Jumlah Digit

Waktu Eksekusi Program (detik) 1 proses

2 proses

3 proses

41.352

21.827

15.852

41.410

22.232

15.743

41.014

22.052

15.905

41.084

22.206

15.655

41.042

22.062

15.626

41.180

22.076

15.756

speed up

1.865

2.614

efisiensi

0.933

0.871

cost

44.152

47.269

overhead

2.971

6.088

2

30

waktu rata-rata

Jenis Percobaan

Jumlah Digit

Waktu Eksekusi Program (detik) 1 proses

2 proses

3 proses

535.984

278.726

226.490

538.627

277.924

228.212

540.515

278.777

225.923

539.242

278.248

226.949

537.984

276.888

227.616

538.470

278.113

227.038

speed up

1.936

2.372

efisiensi

0.968

0.791

cost

556.225

681.114

overhead

17.755

142.644

2

35

waktu rata-rata

Keterangan  Jenis percobaan 1 yaitu waktu eksekusi seluruh tahap hingga mendapatkan hasil  Jenis percobaan 2 yaitu hanya waktu eksekusi ketika penyaringan