ASPEK KOMPUTASI SOLUSI RESIDU KUADRATIK
MUHAMMAD MUKAFI G54103011
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
RINGKASAN MUHAMMAD MUKAFI. Aspek Komputasi Solusi Residu Kuadratik. Dibimbing oleh SUGI GURITMAN dan SISWANDI. Dalam menentukan apakah suatu kongruensi x 2 ≡ a ( mod p ) dengan a bilangan bulat dan p bilangan prima mempunyai solusi atau tidak dapat digunakan Kriteria Euler. Jika a ( p −1) / 2 ≡ 1( mod p ) maka x 2 ≡ a ( mod p ) mempunyai solusi. Jika x 2 ≡ a ( mod p ) mempunyai solusi, maka untuk mementukan solusinya dapat digunakan Algoritma RESSOL (Residue Solver). Algoritma RESSOL adalah algoritma acak (randomized algorithm) dan bukan algoritma deterministic, tetapi prosedur perhitungannya lebih praktis dan cepat. Algoritma RESSOL hanya dapat digunakan untuk mencari solusi dari x 2 ≡ a ( mod p ) dengan p prima ganjil. Tetapi dari Algoritma RESSOL tersebut dapat dikembangkan menjadi beberapa algoritma untuk mencari solusi dari x 2 ≡ a ( mod pq ) dengan p dan q prima ganjil, dan
x ≡ a (mod p ) dengan p prima ganjil dan bilangan bulat j ≥ 2 . 2
j
ASPEK KOMPUTASI SOLUSI RESIDU KUADRATIK
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : MUHAMMAD MUKAFI G54103011
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
Judul Nama NRP
: Aspek Komputasi Solusi Residu Kuadratik. : Muhammad Mukafi : G54103011
Menyetujui,
Pembimbing I
Pembimbing II
Dr. Sugi Guritman NIP. 131 999 582
Drs. Siswandi, M.Si NIP. 131 957 320
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Prof. Dr. Ir. Yonny Koesmaryono, MS NIP. 131 473 999
Tanggal Lulus : …………………..
PRAKATA Puji syukur penulis panjatkan kepada Allah SWT atas segala karunianya sehingga penulis dapat menyelesaikan tugas akhir yang berjudul Aspek Komputasi Solusi Residu Kuadratik. Shalawat dan salam semoga senantiasa tercurah kepada Rasulullah Muhammad SAW beserta keluarga, sahabat dan pengikutnya hingga akhir zaman. Tugas akhir ini saya persembahkan untuk kedua orang tua saya dan ketiga kakakku yang telah banyak memberikan dukungan yang luar biasa (terutama nasehat dan doa-doanya) sehingga karya ilmiah ini dapat terselesaikan. Keterbatasan dan ketidaksempurnaan membuat penulis membutuhkan bantuan, dukungan dan semangat dari orang-orang secara langsung ataupun tidak langsung berkontribusi besar dalam pembuatan tugas akhir ini. Oleh karena itu penulis ingin mengucapkan rasa terima kasih yang sebesar-besarnya kepada Bapak Sugi Guritman dan Bapak Siswandi yang dengan sabar telah membimbing dan mengarahkan selama penulisan karya ilmiah ini. Ibu Sri Nurdiati atas kesediaannya menjadi penguji luar dalam sidang tugas akhir penulis. Rismanto dan Arie Wijayanto yang telah membantu dalam menyelesaikan program penulis. Rian, Elis, dan Tiwi atas kesediaannya menjadi pembahas dalam seminar penulis. Tak lupa penulis ingin mengucapkan terima kasih kepada Hepy Purnomo, Syamsuri, Taufik Hidayah, Jaenudin, Indra, Cecep, Engkus, Iim dan para pengajar MCS (Walidah, Rina, Yudi, Nuqi, Novi, Lia, Dian, Arum, Fifi). Kepada Bapak Ridwan Hasan Saputra dan tim KPM (Teh Desi, Bu Anis, Bu Astri, Hirasawa, Dadan, Rahmi). Seluruh Dosen Departemen Matematika atas segala ilmu yang telah diberikan. Staf dan karyawan TU Matematika IPB. Penghuni Villa Merah (Abay, Sanggam, Tyo). Matematika angkatan 40 atas persahabatannya selama ini semoga tidak akan berakhir. Serta seluruh pihak-pihak yang tidak dapat penulis sebutkan satu per satu. Penulis mengetahui bahwa tugas akhir ini masih jauh dari kesempurnaan. Semoga tugas akhir ini dapat bermanfaat bagi penulis khususnya dan bagi pihak lain yang membutuhkan.
Bogor, Januari 2007
Muhammad Mukafi
RIWAYAT HIDUP Nama lengkap penulis adalah Muhammad Mukafi, dilahirkan di Brebes pada tanggal 7 Oktober 1984 sebagai anak keempat dari empat bersaudara. Ayah bernama Fachrur Rozi dan Ibu bernama Siti Aisyah Mu’tamiroh. Penulis menyelesaikan pendidikan Sekolah Dasar pada tahun 1997 di SD Negeri Jatibarang Kidul 1 Jatibarang Brebes, Sekolah Lanjutan Tingkat Pertama Negeri 2 Brebes tahun 2000, Sekolah Menengah Umum Negeri 1 Slawi Tegal tahun 2003, dan masuk Institut Pertanian Bogor melalui jalur USMI pada tahun 2003. Selama mengikuti perkuliahan, penulis pernah menjadi asisten dosen untuk mata kuliah Pengantar Matematika, Matematika Dasar, Kalkulus I, Kalkulus II dan Kalkulus III pada tahun 2004 - 2006. Penulis pernah menjadi anggota aktif dalam himpunan profesi Gugus Mahasiswa Matematika IPB sebagai ketua Departemen Kajian Ilmiah pada tahun 2004-2005 dan menjadi anggota Dewan Legislatif Gugus Mahasiswa Matematika pada tahun 2005-2006. Sejak tahun 2004, penulis telah bergabung dalam lembaga pendidikan Klinik Pendidikan Mipa (KPM) dan Mathematics Study Club (MSC) dan masih aktif sampai sekarang.
DAFTAR ISI Halaman I. PENDAHULUAN ..................................................................................................... 1 1.1. Latar Belakang ............................................................................................... 1 1.2. Tujuan penulisan ............................................................................................ 1 II. LANDASAN TEORI ............................................................................................... 1 2.1 Bilangan Bulat .................................................................................................. 1 2.2 Kongruensi ...................................................................................................... 3 III. PEMBAHASAN ..................................................................................................... 4 3.1 Teorema – Teorema yang Terkait Solusi Residu Kuadratik. ......................... 4 3.2 Konstruksi Algoritma RESSOL beserta Analisisnya. ........................................ 6 3.3 Mengkontruksi Algoritma untuk Mencari Solusi x 2 ≡ a ( mod pq ) dengan p dan q bilangan prima ganjil .......................................................... 10 3.4 Mengkontruksi Algoritma untuk Mencari Solusi x ≡ a (mod p ) dengan p prima ganjil dan j 2 ..................................................................... 3.5 Membandingkan waktu eksekusi Algoritma 1 dengan Algoritma RESSOL yang terkait bilangan besar................................................................................ IV. SIMPULAN DAN SARAN ....................................................................................... 4.1 Simpulan .......................................................................................................... 4.2 Saran ................................................................................................................ DAFTAR PUSTAKA .................................................................................................... LAMPIRAN ................................................................................................................... 2
j
11 14 15 15 15 15 16
DAFTAR BAGAN Halaman Bagan 1 : Algoritma mencari solusi x 2 ≡ a ( mod p ) ....................................................... 5 Bagan 2 : Algoritma RESSOL ........................................................................................ 9 Bagan 3 : Algoritma mencari akar kuadrat modulo (pq), p dan q prima ganjil .............. 11 Bagan 4 : Algoritma mencari akar kuadrat mod p j , dengan p prima ganjil dan j ≥ 2 .. 13
DAFTAR TABEL Halaman Tabel 1 : Waktu Eksekusi Algoritma 1 dan Algoritma RESSOL .................................. 14 Tabel 2 : Waktu Eksekusi Algoritma RESSOL ............................................................. 14
DAFTAR LAMPIRAN Halaman Lampiran 1 : Implementasi Algoritma 1 dengan bantuan perangkat lunak Mathematica 5.2 ...................................................................................... Lampiran 2 : Implementasi Algoritma RESSOL dengan bantuan perangkat lunak Mathematica 5.2 ...................................................................................... Lampiran 3 : Implementasi Algoritma 3 dengan bantuan perangkat lunak Mathematica 5.2 ...................................................................................... Lampiran 4 : Implementasi Algoritma 4 dengan bantuan perangkat lunak Mathematica 5.2......................................................................................... Lampiran 5 : Waktu Eksekusi Algoritma 1 dan Algoritma RESSOL dengan bantuan perangkat lunak Mahtematica 5.2 .............................................. Lampiran 6 : Waktu Eksekusi Algoritma RESSOL dengan bantuan perangkat lunak Mathematica 5.2 ......................................................................................
17 18 19 20 21 22
I. PENDAHULUAN Untuk kasus x 2 ≡ a ( mod pq ) dengan p dan q prima ganjil, terlebih dahulu dicari solusi kongruensi dari masing-masing faktor prima tersebut dengan Algoritma RESSOL, kemudian digunakan Teorema Sisa Cina untuk menemukan solusinya.
1.1 Latar Belakang Salah satu masalah dalam teori bilangan adalah masalah residu kuadratik yaitu mencari solusi dari kongruensi x ≡ a (mod n) dengan a dan n adalah suatu bilangan bulat. 2
Untuk mencari solusi dari x 2 ≡ a ( mod n ) terlebih dahulu ditentukan apakah a merupakan residu kuadratik dari n atau bukan. Masalah residu kuadratik telah dibahas sebelumnya oleh Yuliarti Ningsih (2006). Jika a merupakan residu kuadratik maka x 2 ≡ a ( mod n ) mempunyai solusi.
Untuk kasus x 2 ≡ a ( mod p j ) dengan p prima ganjil dan j ≥ 2 , terlebih dahulu diceri solusi dari x 2 ≡ a ( mod p ) dengan Algoritma RESSOL, kemudian digunakan Lemma Hensel’s untuk mencari solusinya. 1.2
Mencari solusi dari x ≡ a (mod n) lebih mudah jika n adalah bilangan prima, tetapi jika n adalah bilangan komposit yang tidak diketahui faktor primanya maka akan sulit untuk dicari solusinya. 2
1.
2.
Pencarian solusi dari x 2 ≡ a ( mod n ) dapat kita bagi menjadi beberapa kasus yaitu untuk n prima, n = p q dengan p dan q
3.
j
prima ganjil, dan n = p dengan p prima ganjil dan j bilangan bulat dimana j ≥ 2 .
Tujuan Tujuan dari penulisan ini adalah : Mempelajari teorema-teorema yang terkait dengan solusi residu kuadratik dan mengkonstruksi Algoritma 1 untuk mencari solusinya. Merekonstruksi Algoritma RESSOL beserta analisisnya. Mengkonstruksi Algoritma untuk mencari solusi x 2 ≡ a ( mod pq ) dan x 2 ≡ a ( mod p j ) dengan a dan j bilangan bulat
Untuk kasus x 2 ≡ a ( mod p ) dengan p prima ganjil dan a adalah residu kuadratik, terdapat suatu algoritma yang dapat digunakan untuk mencari solusinya yaitu Algoritma RESSOL (Residue Solver) dan Algoritma 1.
4.
( j ≥ 2)
serta p dan q prima ganjil. Membandingkan waktu eksekusi Algoritma 1 dengan Algoritma RESSOL yang terkait bilangan besar.
II. LANDASAN TEORI Definisi 2.2 [Pembagi Bersama Terbesar] Suatu bilangan bulat tak negatif d dikatakan pembagi bersama terbesar dari bilangan bulat a dan b, jika : 1. d adalah pembagi bersama dari a dan b, dan 2. Jika c dimana c|a dan c|b, maka c|d. Biasanya pembagi bersama terbesar dari a dan b dinotasikan dengan d (a, b) . [Menezes, 1997]
Pada bagian ini akan dituliskan beberapa definisi dan teorema yang digunakan sebagai landasan bagi argumen-argumen yang dituliskan pada bab-bab berikutnya. 2.1 Bilangan Bulat Himpunan Bilangan Bulat dinotasikan
.
= {..., −2, −1, 0,1, 2,... } . Definisi 2.1 [Keterbagian] Bilangan bulat b dikatakan pembagi dari bilangan bulat a (a 0) , jika ada bilangan bulat x sedemikian sehingga b ax dan ditulis a | b. Apabila b bukan pembagi dari a, maka ditulis a /| b . [Niven, 1991]
Definisi 2.3 [Relatif Prima] Bilangan a dan b dikatakan relatif prima jika (a, b) 1 dan bilangan-bilangan a1 , a2 ,..., an dikatakan relatif prima jika (a1 , a2 ,..., an )
1
1.
Bilangan bulat m disebut modulus dari kongruensi. [Menezes, 1997]
Bilangan-bilangan dikatakan a1 , a2 ,..., an relatif prima berpasangan jika (ai , a j ) 1
untuk setiap i dengan i j .
1, 2,3..., n dan j
1, 2,3..., n
Teorema 2.4 Jika a, b, c, d, dan m adalah bilangan bulat, dengan m 0 maka :
[Niven, 1991] Definisi 2.4 [Bilangan Prima]
Suatu bilangan bulat p > 1 dinamakan prima atau bilangan prima , jika pembagi dari p adalah 1 dan p itu sendiri. Bilangan bulat a > 1 yang bukan prima dinamakan bilangan komposit. [Niven, 1991] Teorema 2.1
1.
Jika p ab dan p prima maka p a atau p b .
2.
Jika p a1a2 ....an dan p prima maka
1.
Ketiga pernyataan berikut ekuivalen : i. a b(mod m) , ii. b a(mod m) , dan iii. a b 0(mod m) .
2.
Jika a maka a Jika a maka a
3. 4.
p a1 atau p a2 atau p a3 … atau p an . [Niven, 1991]
5.
Teorema 2.2 [Teorema Dasar Aritmatika]
6.
Setiap bilangan bulat n > 1 dapat difaktorkan secara tunggal ke dalam faktor-faktor yang semuanya prima, tanpa memperhatikan urutan. [Niven, 1991]
b(mod m) dan b c(mod m) c (mod m) . b(mod m) dan c d (mod m) c (mod m) b d (mod m) . Jika a b(mod m) dan c d (mod m) maka ac bd (mod m) . Jika a b(mod m) dan d | m , dengan d 0 maka a b(mod d ) . Jika a b(mod m) maka ac untuk setiap c positif.
Definisi 2.7 Modulo n]
Definisi 2.5 [Fungsi Euler Phi]
Himpunan
Fungsi Euler Phi dari n dengan n = 1, 2, 3, ... dinotasikan dengan φ(n) adalah banyaknya bilangan bulat pada interval [1,n] yang prima relatif dengan n. [Menezes, 1997]
dinotasikan
Jika p prima maka φ(p) = p – 1. Jika (m,n) = 1, maka φ(mn) = φ(m).φ(n).
3.
Jika n = p11 p22 p33 ... pkk dengan bilangan prima, maka
e
φ ( n) = n 1 −
e
1
p1
e
1−
e
1
... 1 −
[Himpunan
bilangan n
bc(mod m) [Niven, 1991]
Bilangan
bulat
modulo
Bulat n,
, merupakan suatu himpunan
dari bilangan-bilangan bulat {0,1,2,3,…, n – 1}. [Menezes, 1997] Operasi penjumlahan, pengurangan, dan perkalian bilangan bulat modulo n bersifat
Teorema 2.3 [Sifat-sifat Fungsi Euler Phi]
1. 2.
adalah
tertutup dalam
n
.
Definisi 2.8 [Invers Perkalian]
pi
Misalkan a ∈
n
. Jika ( a, n ) = 1 maka invers
perkalian dari a ( mod n ) adalah bilangan
1
bulat
p2 pk [Menezes, 1997]
x∈
n
sedemikian
sehingga
ax ≡ 1( mod n ) . Invers dari a dinotasikan a −1 . [Niven, 1991]
2.2 Kongruensi
Teorema 2.5 [Teorema Euler]
Definisi 2.6
φ m Jika ( a, m ) = 1, maka a ( ) ≡ 1( mod m ) . [Niven, 1991]
Misalkan a, b dan m bilangan bulat, dengan m 0 . Bilangan a dikatakan kongruen terhadap b modulo m, dinotasikan dengan a b(mod m) , jika m pembagi (a b) .
2
Teorema 2.6 [Teorema Fermat]
Lemma 2.9
x 2 ≡ 1( mod p )
≡ 1( mod p ) .
1.
Jika ( a, p ) = 1 maka a
2.
a ≡ a ( mod p ) untuk setiap a ∈ . [Niven, 1991]
p −1
Definisi 2.9 [Grup Perkalian dari
Grup perkalian * n
n
* n
* n
[Niven, 1991] Teorema 2.10 Misalkan p adalah bilangan prima, maka x 2 ≡ −1( mod p ) mempunyai solusi jika dan
]
adalah
{
= a∈
Jika n prima, maka Jika a ∈
n
dan b ∈
dengan p prima jika dan
hanya jika x ≡ ±1( mod p ) .
p
n
( a, n ) = 1} .
* n
[Menezes, 1997] = {a 1 ≤ a ≤ n − 1} .
* n
maka a.b ∈
hanya jika p = 2 atau p ≡ 1(mod 4) . [Niven, 1991] Teorema 2.11
* n.
Misal
a , b, m ∈
g = ( a, m ) .
bersifat tertutup terhadap perkalian.
m > 0,
dengan
Kongruensi
dan
ax ≡ b ( mod m )
Misalkan a ∈ *n . Order dari a dinotasikan ord(a) adalah bilangan bulat positif terkecil t sedemikian sehingga a t ≡ 1( mod n ) . [Menezes, 1997]
mempunyai solusi jika dan hanya jika g b . Jika kondisi tersebut dipenuhi, solusinya membentuk barisan aritmatika dengan beda m dan memberikan sebanyak g solusi (mod m ). g [Niven, 1991]
Definisi 2.11 [Generator]
Teorema 2.12 [Teorema Sisa Cina]
Definisi 2.10 [Order]
Bilangan g ∈
* n
Jika
dinamakan generator dari
m1 , m2 ,...., mr
adalah bilangan bulat
ord ( g ) = φ ( n ) . Grup perkalian
positif dimana mi relatif prima dengan m j
yang mempunyai generator dinamakan grup siklik. [Menezes, 1997]
untuk i ≠ j , dan a1 , a2 ,...., ar adalah bilangan bulat sembarang, maka sistem kongruensi x ≡ a1 ( mod m1 )
* n
jika
* n
x ≡ a2 ( mod m2 )
Teorema 2.7
Jika g adalah generator dari * n
{
}
* n
, maka
x ≡ ar ( mod mr )
= g mod n 0 ≤ i ≤ φ ( n ) − 1 . i
mempunyai solusi. Jika x0 adalah solusi dari sistem tersebut, maka x = x0 + km dengan k ∈ dan
[Menezes, 1997] Teorema 2.8
Jika p prima maka
* p mempunyai
m = m1.m2 .m3 .....mr juga solusi dari sistem tersebut. [Niven, 1991]
generator.
[Niven, 1991]
Lemma 2.13
Definisi 2.12 [Residu Kuadratik]
Misal
Bilangan c ∈ *n dinamakan residu kuadratik modulo n atau kuadrat modulo n jika ada m ∈ Ζ*n dengan m 2 ≡ c ( mod n ) . Himpunan semua residu kuadrat modulo n dinotasikan Qn. [Menezes, 1997]
a∈
* n
. Jika ord(a) = h, dan
a ≡ 1( mod n ) maka h k . k
[Niven, 1991] Akibat 2.14
( a, m ) = 1 , pembagi φ ( m ) . Jika
maka order dari a ( mod m ) [Niven, 1991]
3
Lemma 2.15
Jika a memiliki order h ( mod m ) , maka a
h ( mod m ) . h ( ,k)
memiliki order
k
[Niven, 1991]
III. PEMBAHASAN
Pada bagian pendahuluan telah disebutkan bahwa tujuan dari penulisan ini adalah mempelajari teorema-teorema yang terkait solusi residu kuadratik dan mengkonstruksi algoritma untuk mencari solusinya, merekonstruksi Algoritma RESSOL beserta analisisnya, mengkonstruksi algoritma untuk mencari solusi 2 2 j x ≡ a ( mod pq ) dan x ≡ a ( mod p ) serta
Jika ada x0 yang merupakan solusi dari
sehingga x0 ≡ g (mod p ) Dari (i) , (ii) dan (iii) diperoleh u
n
⇔g
Jika
∃x ∈ Ζ ∋ x ≡ a ( mod n ) , maka x dinamakan akar kuadrat dari a modulo n. [Menezes, 1997] 2
( p −1)
a
≡ g (mod p ) i
≡g
k
≡ 0(mod p − 1)
i ( p −1) k
i
≡ ( g p −1 ) k ≡ 1( mod p )
k
i ( p − 1) k ≡g
i ( p −1) k
≡/ 0(mod p − 1) dan
≡/ 1( mod p ) .
Dari Teorema 3.1 dapat kita ambil kasus khusus untuk n = 2 ( x 2 ≡ a ( mod p ) ) . Akibat 3.2 [Kriteria Euler] Jika p adalah bilangan prima ganjil, ( a, p ) = 1
…(i)
dan a ( p −1) / 2 ≡ 1( mod p ) maka x 2 ≡ a ( mod p ) mempunyai 2 buah solusi. Jika maka a ( p −1) / 2 ≡ −1( mod p )
x 2 ≡ a ( mod p ) tidak mempunyai solusi. [Niven, 1991] Bukti : Berdasarkan Teorema 3.1 x 2 ≡ a ( mod p )
Bukti : Karena p prima maka berdasarkan Teorema
g
mempunyai (2, p − 1) = 2 buah solusi jika
adalah generator (mod p) maka berdasarkan Teorema 2.7 ada i dimana 0 ≤ i ≤ p − 2 i
i
adalah bilangan bulat) sehingga
( p −1)
x n ≡ a ( mod p ) tidak mempunyai solusi. [Niven, 1991]
sedemikian sehingga g ≡ a (mod p )
k
berakibat a
Jika p prima, (a,p) = 1 dan ( p −1) / ( n , p −1) ≡ 1( mod p ) , maka kongruensi a
mempunyai generator. Misal
k
i
Jika k /| i maka
Teorema 3.1
p
≡ g (mod p )
i ( p − 1)
maka
k |i
(karena
Mencari solusi dari x 2 ≡ a ( mod n ) tidaklah mudah, apalagi jika n adalah bilangan komposit yang tidak diketahui faktor primanya. Jika n adalah bilangan prima, maka ada beberapa teorema yang dapat digunakan untuk mencari solusinya.
*
un
n
mempunyai solusi jika k /| i .
Misalkan a ∈ Qn . Jika
2.8,
u
…(iii)
⇔ un ≡ i (mod p − 1) Misalkan k = (n, p -1). Berdasarkan Teorema 2.11, un ≡ i (mod p − 1) mempunyai k solusi jika k | i dan tidak
Definisi 3.1 [Akar kuadrat]
x ≡ a ( mod p ) mempunyai (n, p–1) solusi. Jika a ( p −1) / ( n , p −1) ≡/ 1( mod p ) maka
( )
x ≡ a ( mod p ) ⇔ g
3.1 Teorema – Teorema yang Terkait Solusi Residu Kuadratik.
n
sehingga
0
ada u dimana 0 ≤ u ≤ p − 2 sedemikian
membandingkan waktu eksekusi algoritma yang terkait bilangan besar.
* n
( x , p) = 1 ,
x n ≡ a ( mod p ) maka
a ( p −1) / 2 ≡ 1( mod p ) . ( p −1) / 2
( p −1)
Misal , maka . b=a b =a Berdasarkan Teorema Fermat dan Lemma 2.8,
…(ii)
4
2
b =a 2
( p −1)
mempunyai akar kuadrat modulo p dan proses berhenti . Jika a ( p −1) 2 ≡ 1( mod p ) lanjut ke langkah 2.
≡ 1(mod p ) sehingga
b ≡ ±1(mod p ) . Jika b = a
( p −1) / 2
≡ −1(mod p )
maka x ≡ a ( mod p ) tidak mempunyai solusi berdasarkan Teorema 3.1. 2
Dalam mencari solusi dari x ≡ a ( mod p ) dengan p prima ganjil ada beberapa hal yang perlu diperhatikan. Jika maka solusinya adalah a ≡ 0(mod p ) x ≡ 0(mod p ) . Jika a ≡/ 0(mod p ) maka 2
adalah solusi
2
2
3.
generator tersebut adalah g. Cari i sedemikian sehingga
generator
karena
Karena
p ganjil maka x0 ≡/ − x0 (mod p )
p
,
misalkan
u
Langkah-langkah dalam algoritma tersebut dapat dilihat melalui bagan berikut ini. Mulai Bilangan prima panjil p dan a ∈ [1, p − 1]
sehingga x 2 ≡ a ( mod p ) akan mempunyai 2 solusi yang berbeda. Dalam hal x 2 ≡ a ( mod p ) mempunyai solusi, dari bukti Teorema 3.1 kita dapat menemukan solusinya apabila generator dari *
p
Solusinya adalah x ≡ g (mod p )
5.
(− x0 ) = x0 ≡ a ( mod p ) .
lainnya,
dari
g ≡ a (mod p ) dengan i = 0, 2, 4, ..., p − 1 Cari u sedemikian sehingga p −1 −1 u ≡ 2 i (mod ) 2
4.
maka solusinya ada 2. Misal x0 adalah salah
− x0
Cari
i
x 2 ≡ a ( mod p ) mungkin tidak mempunyai solusi tergantung kriteria Euler. Jika x 2 ≡ a ( mod p ) mempunyai solusi satu solusinya maka
*
2.
a
Hitung 2 (mod p )
( p −1)
diketahui.
Dalam bukti tersebut terlihat bahwa adalah x 2 ≡ a ( mod p ) solusi dari
x ≡ g (mod p ) dengan g adalah generator u
*
dari
p
,
dan u
adalah solusi
2u ≡ i (mod p − 1) ⇔ u ≡ 2
−1
i (mod
Apakah a ( p −1) 2 ≡ 1( mod p )
Tidak
Ya
x ≡ a ( mod p ) punya solusi
x ≡ a ( mod p ) tak punya solusi
2
2
dari
p −1
) 2 dengan i adalah bilangan genap sedemikian
*
Cari g = generator
sehingga g ≡ a (mod p ) . Dari uraian di atas dapat dibuat sebuah algoritma untuk mencari solusi dari x 2 ≡ a ( mod p ) .
p
i
Hitung i
g (mod p ) dengan i = 0, 2, 4,..., p − 1
Selesai
Tidak
Algoritma 1 : Mencari solusi x 2 ≡ a ( mod p ) dengan
terlebih dahulu mencari generator dari
Apakah
g ≡ a (mod p ) i
* p
.
INPUT
: Bilangan prima ganjil p dan bilangan bulat a, 1 ≤ a ≤ p-1. OUTPUT : Dua akar kuadrat a modulo p. 1.
( p −1)
Ya Hitung
Solusi adalah
x ≡ g (mod p ) u
2
Hitung a dengan Kriteria Euleur. Jika a ( p −1) 2 ≡ −1( mod p ) maka a tidak
u≡2
−1
i (mod
p −1 2
Bagan 1. Algoritma mencari solusi x 2 ≡ a ( mod p )
5
)
Contoh 1: Tentukan solusi dari x 2 ≡ 15 ( mod17 ) . Jawab : 15(17 −1) 2 ≡ 158 (mod 17) ≡ 1 (mod 17)
kuadratik yang ambil secara acak dalam Berdasarkan
17
order 2 j '( mod p ) untuk beberapa j '< j . [Niven, 1991]
i
Mencari nilai i sehingga 3 ≡ 15(mod17) i 0 2 4 6 i 1 9 13 15 3 (mod17) Dari tabel diperoleh nilai i adalah 6. 6 17 − 1 u ≡ (mod ) ≡ 3(mod 8) 2 2
Bukti :
p −1
Solusinya adalah x ≡ 3 ≡ 10(mod17) . Solusi satunya adalah − x ≡ −10 ≡ 7(mod17) .
…(2) diperoleh
2 | ( p − 1) dan p > 2. j
Ambil x = a
x =a 2
2
j −1
, karena ord(a) ≡ 2 j (mod p)
x=a
maka
Algoritma di atas tidak efisien untuk nilai p yang besar ( p > 1.000.000 ), karena untuk
2
j
2
j −1
≡ 1(mod p )
≡/ 1(mod p )
b
g ≡ a (mod p ) juga memerlukan waktu yang lama untuk nilai p > 1.000.000. i
2
j −1
tetapi
sehingga berdasarkan
Lemma 2.9 maka x = a Dengan cara yang
untuk nilai
p > 1.000.000 tidaklah mudah, kemudian mencari nilai i sedemikian sehingga
2
j −1
≡ −1(mod p ) . sama diperoleh
≡ −1(mod p ) , dan mengakibatkan
( ab )2
j −1
2
j −1
2
j −1
=a b ≡ ( −1)( −1) ≡ 1(mod p ) . Berdasarka Lemma 2.13 maka order dari ab
Oleh karena itu, di bagian berikutnya akan dibahas sebuah algoritma yang lebih efisien untuk mencari solusi dari 2 x ≡ a ( mod p ) yaitu Algoritma RESSOL.
j −1
membagi 2 sehingga order dari ab adalah 2 j 'untuk suatu j '< j . Teorema-teorema di atas menjadi landasan Algoritma RESSOL untuk mencari solusi dari x 2 ≡ a ( mod p ) dengan a ∈ Q p dan p prima ganjil.
Mencari solusi dari x 2 ≡ a ( mod p ) memang tidak mudah, tetapi ada beberapa kasus untuk nilai p tertentu yang solusinya sudah dengan ditentukan. Misal untuk p ≡ 3(mod 4) maka solusi dari
x 2 ≡ a ( mod p ) adalah
a ≡ 1(mod p ) persamaan (1) dan (2)
Dari
Jadi solusi dari x 2 ≡ 15 ( mod17 ) adalah 7 dan 10 .
p
j
ord(a) ≡ 2 j (mod p) ⇔ a 2 ≡ 1(mod p ) …(1), berdasarkan Teorema Fermat,
3
mencari g yaitu generator dari
.
Teorema 3.4 Jika a dan b relatif prima terhadap bilangan prima p, dan jika a dan b memiliki order 2 j ( mod p ) dengan j > 0 , maka ab memiliki
adalah g = 3.
*
p
diperoleh
2
berdasarkan kriteria Euler x 2 ≡ 15 ( mod 17 ) mempunyai solusi. *
Euler
x 2 ≡ ( ± z ( p −1) / 4 ) ≡ z ( p −1) / 2 ≡ −1( mod p ) .
Karena 15(17 −1) 2 ≡ 1 (mod 17) maka
Generator dari
Kriteria
*
3.2 Konstruksi Algoritma RESSOL beserta Analisisnya.
x ≡ ± a ( p +1) / 4 ( mod p )
karena ( ± a ( p +1) / 4 ) = a ( p +1) / 2 = a ( p −1) / 2 . a 2
Untuk mencari solusi x 2 ≡ a ( mod p ) dengan p prima ganjil, ada sebuah algoritma yang dapat digunakan untuk mencarinya yaitu Algoritma RESSOL (Residue Solver).
≡ a ( mod p ) .
Berdasarkan Teorema 2.9, x 2 ≡ −1( mod p ) mempunyai solusi jika dan
Dalam bagian ini penulis akan mencoba merekonstruksi Algoritma RESSOL dan menganalisisnya. Berikut ini akan dijelaskan langlah-langkah penurunan Algoritma RESSOL.
hanya jika p = 2 atau p ≡ 1(mod 4) . Untuk ( p −1) / 4
p ≡ 1(mod 4) misalkan x = ± z (mod p ) dengan z adalah suatu bilangan non residu
6
a(
Langkah pertama menghitung (mod p) dengan Kriteria Euleur. Jika
sehingga k '< k .
p −1) 2
a ( p −1) 2 ≡ −1( mod p ) maka tidak mempunyai solusi. a
Jika
( p −1)
≡ 1( mod p )
2
Algoritma ini dimulai dengan proses pengulangan. Didefinisikan
x 2 ≡ a ( mod p )
maka
untuk
menentukan solusi dari x 2 ≡ a ( mod p ) adalah mencari nilai k dan m dengan k > 0 dan m ganjil sedemikian sehingga p − 1 = 2k m . Kemudian didefinisikan : …(1) r ≡ a ( m +1) / 2 ( mod p ) Jika kedua ruas persamaan (1) dikuadratkan, maka diperoleh : r 2 ≡ a ( m +1) ( mod p )
n ≡ a m ( mod p ) , sehingga dapat r 2 ≡ na ( mod p )
ditulis :
c '≡ b 2 ( mod p ) ≡ c 2
…(2)
Jika n ≡ 1( mod p ) , maka solusinya adalah
acak
suatu
2k '
( c ')
p
.
Misal
c2
k −1
= z2
k −1 m
k
Jadi order dari c adalah tepat 2 . dapat ditulis ord(c) ≡ 2k
…(5)
n
=a
m
Dengan demikian order dari n membagi 2 . Dengan pengulangan kuadrat dapat ditentukan order dari n adalah 2k '.
Sementara itu n 2 = a 2 m = a ( ) , karena a adalah kuadratik residu mod p maka
n2
k −1
=a
( p −1) / 2
p −1 / 2
≡ 1( mod p )
≡ c2
k '1 − k −k ' 2
k −1
( mod p )
( mod p ) ≡ −1( mod p )
Jika n '≡ 1( mod p ) maka k ' '> 1 , dan kondisi ini serupa dengan ketika pengulangan dimulai, sehingga pengulangan dilakukan kembali sampai solusi diperoleh.
k
k −1
( mod p )
x ≡ ± r 'mod p) . (
= a p −1 ≡ 1( mod p ) …(6)
k −1
k' k −k ' 2
Jika k ' '= 0 , maka n '≡ 1( mod p ) , dan dengan menggunakan persamaan (12), maka solusi dari x 2 ≡ a ( mod p ) adalah
Hal ini atau
k
2k
( mod p )
Dengan demikian c ' memiliki order tepat 2k '. Karena ord(n) ≡ 2k ' dan ord(c ' ) ≡ 2k ', maka berdasarkan Teorema 3.4, order dari n '≡ c '(mod n p) adalah 2k '' dengan k ' '< k '.
c 2 ≡ 1( mod p ) . Dengan cara yang sama diperoleh 2k
2
≡ c2
p −1
= z ( p −1) / 2 ≡ −1( mod p )
≡ c
− 2k '1
( c ')
=z ≡ 1( mod p ) …(4) c =z Berdasarkan Lemma 2.13, order dari c membagi 2 k . Sementara itu, karena z adalah nonresidu kuadratik maka 2k m
2
k
bilangan tersebut adalah z. Definisikan …(3) c ≡ z m ( mod p ) Jika kedua ruas persamaan (3) dipangkatkan dengan 2k, maka diperoleh : 2k
k −k '1 −
≡ c 2 ( mod p ) ≡ 1( mod p ) . Sementara itu
bilangan *
nonresidu kuadratik di dalam
…(10)
k −k '
Jika n ≡ 1( mod p ) , maka untuk menentukan solusinya diperlukan langkah penyelesaian sebagai berikut. secara
…(9)
…(13) ≡ c 2 ( mod p ) Jika kedua ruas persamaan (13) dipangkatkan dengan 2k ', maka diperoleh :
x ≡ ± r ( mod p ) .
Ambil
…(8)
…(11) Dengan melakukan perkalian pada kedua ruas persamaan (2) oleh b 2 diperoleh : b 2 r 2 ≡ b 2 na ( mod p ) dengan menggunakan persamaan (9), (10) dan (11) diperoleh : 2 ≡ an 'mod …(12) r' p) ( Dari persamaan (8) dan (10) diperoleh
r 2 ≡ a m . a ( mod p ) .
Misalkan
k −k '1 −
( mod p ) r '≡ br ( mod p ) c '≡ b 2 ( mod p ) n '≡ c 'n ( mod p )
b ≡ c2
Langkah penyelesaian untuk menentukan x 2 ≡ a ( mod p ) solusi dari kongruensi tersusun dalam algoritma berikut ini.
…(7)
7
Algoritma 2 (Algoritma RESSOL) : Mencari akar kuadrat modulo p prima ganjil.
: Bilangan prima ganjil p dan bilangan bulat a, 1 ≤ a ≤ p – 1. OUTPUT : Dua akar kuadrat a modulo p.
2.
Hitung a ( p −1) 2 dengan Kriteria Euleur. Jika a ( p −1) 2 ≡ −1( mod p ) maka a tidak mempunyai akar kuadrat modulo p dan proses berhenti . Jika a ( p −1) 2 ≡ 1( mod p ) lanjut ke langkah 2. Cari k dan m, dengan m ganjil sehingga p − 1 = 2k m .
3.
Hitung r ≡ a ( m +1) / 2 ( mod p ) dan
4.
n ≡ a ( mod p ) . Definisikan r 2 ≡ an ( mod p )
…( i )
n ≡ 1( mod p ) ,
solusinya
Algoritma RESSOL bukanlah algoritma deterministic, tetapi prosedur perhitungannya lebih praktis dan cepat. Algoritma RESSOL mempunyai waktu eksekusi operasi.
maka
6.
* p
1
23 – 1 = 22 = 2 .11 pilih k = 1 dan m = 11
secara acak yang
(11+1) / 2
r ≡ 13
nonresidu kuadratik, dan tetapkan c ≡ z m ( mod p ) . Sehingga ord(c) = 2 k . Dengan pengulangan kuadrat diperoleh ord(n) = 2k '.
(mod 23)
≡ 13 (mod 23) ≡ 6 (mod 23) 6
Karena r ≡ 13 (mod 23) 2
12
≡ 13 .13 (mod 23) 11
k −k '1 −
( mod p ) , r '≡ br ( mod p ) , c '≡ b 2 ( mod p ) dan n '≡ c 'n ( mod p ) dengan k '< k
maka solusi dari x 2 ≡ 13 ( mod 23) adalah
8.
Kalikan kedua ruas (i) dengan c '. Dengan demikian diperoleh 2 ≡ an 'mod …(ii) r' p) (
Jadi solusi dari x 2 ≡ 13 ( mod 23) adalah 6 dan 17.
9.
Jika n '≡ 1( mod p ) , maka solusinya
7.
Tetapkan b ≡ c 2
dengan n ≡ 13 (mod 23) ≡ 1 (mod 23) 11
x ≡ 6 (mod 23) dan x ≡ −6 (mod 23) ≡ 17 (mod 23)
adalah x ≡ ± r 'mod p) . ( Jika n '≡ 1( mod p ) , lakukan pengulangan langkah (6) – (8), sampai diperoleh n '≡ 1( mod p ) .
10. Solusinya adalah x ≡ ± r 'mod p) . (
Algoritma RESSOL adalah algoritma acak (randomized algorithm) karena langkah ke-5 mensyaratkan untuk memilih bilangan nonresidu kuadratik secara acak dalam
* p
.
8
bit
[Menezes, 1997]
x 2 ≡ 13 ( mod 23) mempunyai solusi.
Jika n ≡ 1( mod p ) , lanjut langkah 5. Ambil z ∈
4
O ((lg p ) )
time)
Karena 13( 23−1) 2 ≡ 1 (mod 23) maka
adalah x ≡ ± r ( mod p ) . 5.
(running
Contoh 2. Tentukan solusi dari x 2 ≡ 13 ( mod 23) . Jawab: 13( 23−1) 2 ≡ 1311 (mod 23) ≡ 1 (mod 23) .
m
Jika
, setengah dari anggotanya
p
adalah non residu kuadratik sehingga pengambilan bilangan nonresidu kuadratik 1 dengan rata-rata mempunyai peluang 2 pengambilan adalah 2 kali percobaan.
INPUT
1.
*
Dalam
Langkah-langkah dalam Algoritma RESSOL dapat dilihat melalui bagan berikut ini. Mulai Bilangan prima ganjil p dan a ∈ [1, p − 1]
a
Tidak
Hitung 2 (mod p)
( p −1)
Apakah a ( p −1) 2 ≡ 1( mod p )
x ≡ a ( mod p ) tak punya solusi
Ya
x ≡ a ( mod p ) punya solusi
2
2
Hitung r ≡ a ( m +1) / 2 ( mod p ) dan n ≡ a m ( mod p )
Solusinya adalah x ≡ ± r ( mod p )
Apakah n ≡ 1( mod p )
Ya
Tidak
Misalkan z adalah bilangan nonresidu kuadratik yang diambil secara acak dalam
Selesai
Hitung c ≡ z
m
* p
.
( mod p )
Tetapkan b ≡ c 2
k −k '1 −
( mod p ) ,
r '≡ br ( mod p ) , c '≡ b 2 ( mod p ) , n '≡ c 'n ( mod p ) dengan k '< k
Tidak
Solusinya adalah x ≡ ± r 'mod p) (
Ya
Apakah n '≡ 1( mod p )
Hitung 2 ≡ an 'mod r' p) (
Bagan 2. Algoritma RESSOL
x 2 ≡ a ( mod pq ) ,
Algoritma RESSOL hanya dapat digunakan untuk mencari solusi dari x 2 ≡ a ( mod p ) dengan p prima ganjil. Tetapi Algoritma RESSOL ini dapat dijadikan landasan untuk mencari solusi dari
dengan p dan q prima
ganjil, dan x ≡ a (mod p ) , dengan p prima ganjil dan bilangan bulat j ≥ 2 . 2
9
j
INPUT
: Bilangan prima ganjil p dan q , dan 1 ≤ a ≤ pq – 1 OUTPUT : Empat akar kuadrat a modulo pq
3.3 Mengkontruksi Algoritma untuk Mencari Solusi x 2 ≡ a ( mod pq ) dengan p dan q bilangan prima ganjil.
1.
Untuk mencari solusi kongruensi x ≡ a ( mod pq ) , dengan p dan q prima ganjil, diawali dengan mencari terlebih dahulu solusi dari x 2 ≡ a ( mod p ) dan 2
2.
menggunakan Algoritma x 2 ≡ a ( mod q ) RESSOL. Misalkan x 2 ≡ a ( mod p ) mempunyai 2 solusi, yaitu ...(14) x ≡ r ( mod p )
x ≡ −r ( mod p )
Misalkan x ≡ a ( mod q ) solusi, yaitu x ≡ s ( mod q 2
3. 4.
...(15) mempunyai
) x ≡ − s ( mod q )
5. 2
Algoritma di atas mempunyai waktu eksekusi
...(16)
3
(running time) O ((lg p ) ) bit operasi. [Menezes, 1997]
...(17) Kombinasi dari solusi (14), (15), (16), dan (17) menghasilkan 4 buah sistem kongruensi sebagai berikut : (ii) x ≡ r ( mod p ) (i) x ≡ r ( mod p )
x ≡ s ( mod q )
(iii) x ≡ − r ( mod p ) x ≡ s ( mod q )
Contoh 3. Tentukan solusi dari x 2 ≡ 71 ( mod 77 ) . Jawab Karena 77 = 7 . 11 maka x 2 ≡ 71 ( mod 7 ) ...(i ) x 2 ≡ 71 ( mod 77 ) ⇔ 2 x ≡ 71 ( mod 11) ...(ii)
x ≡ − s ( mod q )
(iv) x ≡ −r (mod p) x ≡ − s (mod q )
(i) x 2 ≡ 71 ( mod 7 ) ≡ 1 ( mod 7 )
Dengan menggunakan Teorema Sisa Cina, sistem kongruensi (i), (ii), (iii) dan (iv) menghasilkan 4 solusi kongruensi dari x 2 ≡ a(mod pq ) dan secara berurutan dapat dituliskan sebagai (i) x1 ≡ u ( mod pq ) ,
solusiya adalah x ≡ ±1 ( mod 7 )
(ii) x 2 ≡ 71 ( mod 11) ≡ 5 ( mod 11)
solusiya adalah x ≡ ±4 ( mod 11)
Bilangan bulat yang memenuhi persamaan
(ii) x2 ≡ v ( mod pq ) ,
( iii )
Gunakan Algoritma RESSOL untuk mencari dua akar r dan –r yang merupakan solusi dari x 2 ≡ a ( mod p ) . Gunakan Algoritma RESSOL untuk mencari dua akar s dan –s yang merupakan solusi dari x 2 ≡ a ( mod q ) . Gunakan Algoritma Euclidean yang diperluas untuk mencari bilangan bulat c dan d sedemikian sehingga cp + dq = 1. x ≡ ( rdq + scp )(mod pq ) y ≡ ( rdq − scp )(mod pq ) Solusinya adalah ± x (mod pq ) dan ± y (mod pq )
7c+11d = 1 adalah c = -3 dan d = 2.
x3 ≡ −u ( mod pq ) ,
(iv) x4 ≡ −v ( mod pq ) . Keempat solusi ini merupakan solusi yang khas dari modulo pq. Langkah penyelesaian untuk menentukan solusi dari kongruensi x 2 ≡ a ( mod pq ) dengan p dan q bilangan prima ganjil tersusun dalam algoritma berikut ini.
x = 1.2.11 + 4.(-3).7 = -62
15 (mod 77)
y = 1.2.11 - 4.(-3).7 = 106
29 (mod 77)
-x = -15(mod 77)
48 (mod 77)
-y = -29 (mod 77)
62 (mod 77)
Jadi 4 solusi dari x 2 ≡ 71 ( mod 77 ) yaitu 15, 29, 48 dan 62.
Algoritma 3 : Mencari akar kuadrat modulo pq, dengan p dan q prima ganjil.
10
Langkah-langkah dalam Algoritma 3 dapat dilihat melalui bagan berikut ini.
dari polinom f ( x ) ≡ 0(mod p ) … (18), kita mulai dari solusi modulo p, kemudian p2, j
p3, sampai p . Misalkan x = c adalah sebuah solusi j
Mulai
untuk
Bilangan prima p dan q, dan a ∈ [1, pq − 1]
f ( x ) ≡ 0(mod p ) j
mencari
solusi
maka kita bisa
f ( x ) ≡ 0(mod p
dari
f ( x ) ≡ 0(mod p
Solusi dari
j +1
j +1
).
) berbentuk
x = c + tp , dengan t adalah suatu bilangan bulat yang dapat kita cari menggunakan deret Taylor’s j
RESSOL [ a, p ]
RESSOL [ a, q ]
2
f (c + tp ) = f (c ) + tp f ' (c ) + j
Apakah ada solusi
Apakah ada solusi
Ya
3
+
Ya
x ≡ r ( mod p ) x ≡ − r ( mod p )
2
).
Karena
j
j
(mod p
,
j +1
Karena maka f (c + tp ) ≡ 0(mod p ) persamaan diatas dapat kita ubah menjadi j
f ( a ) + tp f ' (c ) ≡ 0 (mod p j
j +1
).
Karena f ( x ) ≡ 0(mod p ) mempunyai solusi x = c maka kita dapatkan f (c ) … (19) tf ' (c ) ≡ − j (mod p ) p yang merupakan persamaan linear dalam t. Persamaan (19) mungkin tidak mempunyai solusi, mempunyai solusi tunggal atau mempunyai p solusi. Jika f ' (c ) ≡/ 0(mod p ) maka persamaan tersebut mempunyai tepat satu solusi. j
Solusi dari persamaan (18) dapat ditentukan dengan menggunakan Lemma Hensel’s.
untuk
Lemma Hensel’s : Misalkan f ( x ) adalah fungsi polinom dengan koefisien-koefisiennya bilangan bulat dan p
Mencari Solusi x ≡ a (mod p ) dengan p prima ganjil dan j 2. j
solusi
dan f (c ) ≡ 0(mod p ) f' (c ) ≡/ 0(mod p ) maka ada bilangan bulat t (mod p ) yang tunggal sedemikian sehingga
prima.
dari
x ≡ a (mod p ) , dengan p prima dan j ≥ 2 , dapat kita ubah bentuknya menjadi j
j
j
j
Jika
f (c + tp ) ≡ 0(mod p
x − a ≡ 0(mod p ) . Kita misalkan f fungsi polinom dengan koefisien bilangan 2
f ( x) = x − a
j +1
f ( x) .
f (c + tp ) = f (c ) + tp f ' (c )
Algoritma
mencari
n!
j +1
Bagan 3. Algoritma mencari akar kuadrat modulo (pq), p dan q prima ganjil.
Untuk
(c)
polinom berderajat 2 dalam modulus p maka deret Taylor’s tersebut menjadi
Tidak
2
( n)
x ≡ − s ( mod q )
Solusinya adalah ± x(mod n) ± y (mod n)
3.4 Mengkonstruksi
nj
t p f
polinom
y ≡ ( rdq − scp ) ( mod n )
Selesai
3!
n
+. . . +
+
x ≡ s ( mod q )
x ≡ ( rdq + scp ) ( mod n )
Tidak
2!
3j
t p f' ' ' ( c)
2j
t p f' ' (c )
dimana n adalah derajat/pangkat dari fungsi
Mencari bilangan bulat c dan d sehingga cp + dq =1
2
j
j +1
). [Niven, 1991]
bulat, f ( x ) = x − a . Untuk mencari solusi 2
11
Bukti dari Lemma Hensel’s tidak dicantumkan karena di luar jangkauan pembahasan. Jika
f' (c )
Solusi
x ≡ ±1258(mod11 ) x = 73 .
2
c2 (mod p )
Kemudian maka
3
dan
) untuk
f (c ) ≡ 0(mod p
jika
f (c + tp ) ≡ 0(mod p j
j +1
),
j +1
)
sehingga
sebuah akar c (mod p ) akan menghasilkan p
maka
seterusnya
j +1
j
buah
akar
akar
(mod p
f (c ) ≡/ 0(mod p
akan dihasilkan sebuah akar
c3 (mod p )
dan
j
j
2
Dari
x = 1258
f (c + tp ) ≡ f ( a )(mod p Taylor, semua bilangan bulat t.
menghasilkan sebuah akar c2 (mod p ) .
f' ( c2 ) ≡ f ' (c ) ≡/ 0(mod p ) .
adalah
dan f (c ) ≡ 0(mod p ) f' (c ) ≡ 0(mod p ) maka berdasarkan deret
Dari Lemma Hensel’s kita lihat bahwa sebuah akar nonsingular c (mod p )
c2 ≡ c (mod p )
yaitu
Jika
f (c ) ≡ 0(mod p ) maka bilangan bulat c disebut akar nonsingular. Jika f' (c ) 0(mod p ) dan f' (c ) ≡ 0(mod p ) maka c disebut akar singular. j
Karena
2
3
dan
0(mod p )
3
x ≡ 5(mod11 )
dari
untuk (mod p
sehingga
j
mendapatkan akar c j (mod p ) .
j +1
j +1
j +1
).
Tetapi
jika
) maka tidak ada solusi
).
Contoh 5. Tentukan solusi dari x ≡ 9(mod 27) . Jawab : 2
Dari persamaan (19) diperoleh sebuah persamaan rekursif untuk mencari solusi yaitu
x ≡ 9(mod 27) ⇔ x − 9 ≡ 0(mod 3 ) 2
c j +1 = c j − f ( c j ) ( f ' (r ) ) , −1
dengan
( f '(r ) )
−1
2
f ( x) = x − 9 f' ( x) = 2 x f' (0) ≡ 0(mod 3) Karena f ' (0) ≡ 0(mod 3) maka 0 adalah akar singular. 2
bulat sedemikian sehingga −1
3
Solusi dari x − 9 ≡ 0(mod 3) adalah x = 0.
adalah sebuah bilangan
f' (c ) ( f ' (r ) )
2
≡ 1(mod p ) .
Contoh 4.
f (0) = −9 ≡ 0(mod 3 ) , maka solusi mod 9 adalah x = 0, x = 0 + 3 = 3, x = 3 + 3 = 6 2
3
Tentukan solusi dari x ≡ 5(mod11 ) . Jawab : 2
x ≡ 5(mod11 ) ⇔ x − 5 ≡ 0(mod11 )
f (0) = −9 ≡/ 0(mod 3 ) , maka tak ada solusi mod 27
Solusi dari x − 5 ≡ 0(mod11) adalah x = ±4 (mengunakan Algoritma RESSOL)
f (3) ≡ 0(mod 3 ) , maka solusi mod 27 adalah x = 3, x = 3 + 9 = 12, x = 12 + 9 = 21
f ( x) = x − 5 f' ( x) = 2 x f' (4) ≡ 8 ≡/ 0(mod11) Karena f ' (4) ≡/ 0(mod11) maka 4 adalah akar nonsingular.
f (6) = 27 ≡ 0(mod 3 ) , maka solusi mod 27 adalah x = 6, x = 6 + 9 = 15, x = 15 + 9 = 24.
3
2
2
3
3
3
2
3
2
Jadi solusi dari x ≡ 9(mod 27) adalah x = 3, x = 6, x = 12, x = 15, x = 21 dan x = 24. 2
f' (4) = 8 ≡ 7(mod11)
Langkah penyelesaian untuk menentukan solusi dari kongruensi x 2 ≡ a ( mod p j )
c2 = c1 − f (4) f ' (4) = 4 − 11.7
= −73 ≡ 48(mod11 ) 2
dengan p bilangan prima ganjil dan bilangan bulat j ≥ 2 tersusun dalam algoritma berikut ini.
c3 = c2 − f (48) f ' (4) = 48 − 2299.7
= −16045 ≡ 1258(mod11 ) 3
12
(
Algoritma 4 :
)
j
dan rj = rj −1 − f ( rj −1 ) f ' ( r1 ) (mod p )
j
Mencari akar kuadrat modulo p , dengan p prima ganjil dan bilangan bulat j ≥ 2 .
dengan
r1 = r .
Solusinya
dari
x 2 ≡ a ( mod p j ) adalah x = ± rj (mod p ) . j
INPUT
: Bilangan prima ganjil p , bilangan
Jika f ' ( r ) ≡ 0(mod p ) lanjut ke langkah 4. Untuk k = 2, 3,..., j − 1 berlaku jika
j
bulat j ≥ 2 dan 1 ≤ a ≤ p − 1 4.
j
OUTPUT : Dua akar kuadrat a modulo p .
k
1.
2.
Tetapkan f ( x ) = x − a dan f ' ( x) = 2 x
3.
(r ) ) Jika f ' ( r ) ≡/ 0(mod p ) , tentukan ( f '
k
f ( r ) ≡ 0(mod p ) maka x ≡ r + tp dengan t = 1, 2, 3,..., p merupakan solusi
Gunakan Algoritma RESSOL untuk mencari dua akar r dan –r yang merupakan solusi dari x 2 ≡ a ( mod p ) .
dari x 2 ≡ a (mod p k +1 ) . k
f ( r ) ≡/ 0(mod p ) maka tak ada
Jika
2
solusi dari x 2 ≡ a (mod p k +1 ) .
−1
Langkah-langkah dalam Algoritma 4 dapat dilihat melalui bagan berikut ini.
Mulai Bilangan prima ganjil p, j ≥ 2 dan a ∈ [1, p − 1]
RESSOL [a, p]
Tidak
Apakah ada solusi
x ≡ r ( mod p )
Ya
x ≡ − r ( mod p )
Tetapkan f ( x) = x 2 − a dan f ' ( x) = 2 x Apakah f' (r ) ≡ 0(mod p)
Ya
k
Hitung f ( r )(mod p ) untuk k = 2, 3,..., j − 1
Tidak
Apakah
−1
Hitung ( f ' ( r )) dan
(
rj = rj −1 − f ( rj −1 )( f ' ( r ))
k
−1
) (mod p
j
f ( r ) ≡ 0(mod p ) )
Tidak
dengan r1 = r .
Ya
k
xt ≡ r + tp dengan t = 1, 2, 3, ..., p adalah
Solusi dari x 2 ≡ a (mod p k +1 )
Tak ada solusi dari x 2 ≡ a (mod p k +1 )
Solusinya adalah x ≡ ± rj (mod p j )
Selesai
Bagan 4. Algoritma mencari akar kuadrat mod p j , dengan p prima ganjil dan j ≥ 2 .
13
3.5
Membandingkan waktu eksekusi Algoritma 1 dengan Algoritma RESSOL yang terkait bilangan besar.
592085 467495 231000 611953 96620 136341 399632 541897 328426 671944 231057 1299709 601890 825496 290150 291949 3090665 5210769 14621620 15485863 14141212 12920893 5871391 9473376
Pada bagian ini akan dibandingkan waktu eksekusi Algoritma 1 dengan Algoritma RESSOL. Implementasi dari Algoritma 1 dan Algoritma RESSOL menggunakan perangkat lunak Mathematica 5.2 dapat dilihat di lampiran. Tabel 1 adalah waktu eksekusi dari Algoritma 1 dan Algoritma RESSOL menggunakan perangkat lunak Mahtematica 5.2. Nilai p adalah bilangan prima yang ditentukan terlebih dahulu, sedangkan a adalah bilangan bulat positif yang diambil secara acak dalam
* p
.
Tabel 1. Waktu Eksekusi Algoritma 1 dan Algoritma RESSOL
p
97 541
997
3571
7919
12553
104729
a
25 89 507 377 64 149 77 694 3095 1548 814 979 3962 1271 5858 5274 7087 11012 4355 8836 14229 35517 76305 49617 1630 44704
Waktu Eksekusi (detik)* Algoritma 1 Algoritma RESSOL 0,0015 0,0015 0,0016 0,0016 0,0031 0,0031 0,0024 0,0024 0,0021 0,0021 0,0047 0,0047 0,0024 0,0024 0,0069 0,0069 0,0098 0,0098 0,0081 0,0081 0,0076 0,0076 0,0151 0,0015 0,0162 0,0016 0,0153 0,0031 0,0204 0,0024 0,0315 0,0021 0,0316 0,0047 0,0167 0,0024 0,0318 0,0069 0,0319 0,0098 0,2048 0,0081 0.2817 0,0076 0,1566 0,0098 0,2505 0,0081 0,2664 0,0076 0,2813 0,0069
0,6092 1,6251 0,5782 1,3753 0,8444 1,2815 0,6256 1,2657 2,1888 1,4539 3,8138 1,2037 3,8286 2,7545 22,0474 42,5473 26,8592 13,9061 31,9062 37,2353 15,9844
0,0015 0,0016 0,0031 0,0024 0,0021 0,0047 0,0024 0,0069 0,0098 0,0081 0,0076 0,0015 0,0016 0,0031 0,0024 0,0021 0,0047 0,0024 0,0069 0,0098 0,0021
Dari data Tabel 1 dapat diambil kesimpulan bahwa waktu eksekusi Algoritma RESSOL lebih cepat dibandingkan Algoritma 1. Algoritma 1 tidak efisien untuk nilai p yang besar yaitu p > 1.000.000, sedangkan Algoritma RESSOL lebih efisien untuk nilai p yang besar. Berdasarkan hasil percobaan (Tabel 2), Algoritma RESSOL masih dapat digunakan untuk mencari solusi x ≡ a (mod p ) untuk nilai p yang sangat besar, yaitu p = 2
29.996.224.275.833.
Tabel 2. Waktu Eksekusi Algoritma RESSOL Waktu p a Eksekusi (detik)* 424613597121 0,0159 10878246026665 0,0178 5887477973699 0,0167 20786675373559 0,0206 1574940209207 0,0185 29996224275833 5641355712333 0,0194 10073237724502 0,0153 27504498309348 0,0212 7273523082800 0,0143 18488184417987 0,0134 *)menggunakan komputer P4 3,0GHz 512MB
14
IV. SIMPULAN DAN SARAN 4.1 Simpulan
5.
Berdasarkan analisis dari hasil pembahasan, diperoleh beberapa simpulan sebagai berikut : 1. Kriteria Euler menjadi landasan untuk x 2 ≡ a ( mod p ) menentukan apakah dengan p prima ganjil mempunyai solusi atau tidak. 2. Jika x 2 ≡ a ( mod p ) mempunyai solusi maka untuk mencari solusinya dapat digunakan Algoritma 1 atau Algoritma RESSOL. 3. Untuk nilai p yang besar yaitu p > 1.000.000, Algoritma 1 tidak efisien dengan waktu eksekusi yang lama. 4. Algoritma RESSOL tetap stabil meskipun untuk nilai p yang sangat besar yaitu p = 29.996.224.275.833 dengan waktu eksekusi yang cepat.
Dari Algoritma RESSOL dapat dikembangkan menjadi beberapa Algoritma yaitu Algoritma 3 untuk mencari solusi x ≡ a (mod pq ) dengan p dan q adalah bilangan prima ganjil, dan Algoritma 4 untuk mencari solusi 2
j
x ≡ a (mod p ) dengan p bilangan prima ganjil dan bilangan bulat j ≥ 2 . 2
4.2 Saran
Tema dalam karya ilmiah ini dapat diteruskan bagi yang berminat, yaitu menentukan solusi dari x ≡ a (mod n) dengan n bilangan komposit e1 e2 e3 ek ( n = p1 p2 p3 ... pk , dengan pi prima dan 2
ei bilangan bulat positif).
DAFTAR PUSTAKA Hidayat, T. 2005. Analisis Algoritma Kunci Publik Rabin. Skripsi. Departemen Matematika FMIPA IPB, Bogor
Niven, I. Zuckerman, H. S. dan Montgomery, L. H. 1991. An Introduction to The Theory of Numbers. John Wiley & Sons. Inc: New York.
Ningsih, Y. 2006. Masalah Residu Kuadratik. Skripsi. Departemen Matematika FMIPA IPB, Bogor
Menezes, A. J. Oorschot, P. C. V. dan S. Vanstone. 1997. Handbook of Applied Cryptography. CRC Press, Inc: New York.
15
LAMPIRAN
Lampiran 1. Implementasi Algoritma 1 dengan bantuan perangkat lunak Mathematica 5.2. Algoritma 1 :
Mencari solusi x 2 ≡ a ( mod p ) dengan terlebih dahulu mencari generator dari
INPUT : Bilangan prima ganjil p dan bilangan bulat a, 1 ≤ a ≤ p-1. OUTPUT : Dua akar kuadrat a modulo p. << NumberTheory`NumberTheoryFunctions` Algoritma1[a_Integer, p_Integer] := If[PrimeQ[p] = = False, Print["p bukan prima"], If[JacobiSymbol[a, p] = = -1, Print["Tak ada solusi"], If[JacobiSymbol[a, p] = = 0, {0}, {aa = Mod[a, p]; g = PrimitiveRoot[p] ; For[i = 0, i p - 1, i = 2 + i, If[PowerMod[g, i, p] = = aa, Break[] ] ; i p −1 u = Mod[ , ]; 2 2 x = PowerMod[g, u, p], Mod[-x, p] } ] ] ]
Contoh : Input : Algoritma1[24,97] Output : { 86, 11 } Input : Algoritma1[541,104729] Output : { 28205, 76524 }
17
* p
.
Lampiran 2. Implementasi Algoritma RESSOL dengan bantuan perangkat lunak Mathematica 5.2. Algoritma 2 (Algoritma RESSOL) Mencari akar kuadrat modulo p prima ganjil INPUT : Bilangan prima ganjil p dan bilangan bulat a, 1 ≤ a ≤ p – 1. OUTPUT : Dua akar kuadrat a modulo p. RESSOL[a_Integer, p_Integer] := If[PrimeQ[p] = = False, Print["p bukan prima"], If[JacobiSymbol[a, p] = = -1, Print["Tak ada solusi"], If[JacobiSymbol[a, p] = = 0, {0}, {m = p – 1 ; k=0; m m While[IntegerQ[ ], {m = , k++}] ; 2 2 aInv = PowerMod[a, -1, p] ; z = Random[Integer,{1, p-1}]; While[JacobiSymbol[z, p] 1, z = Random[Integer,{1, p-1}]; ]; c = PowerMod[z, m, p] ; m +1 r = PowerMod[a, , p] ; 2 For[i = 1, i k - 1, i++, { d = PowerMod[r2 * aInv, 2k - i - 1, p], If[Mod[d, p] = = p - 1, r = Mod[r*c, p] ], c = Mod[c2, p] }; r, Mod[-r, p] } ] ] ]
Contoh : Input : RESSOL[26951623672, 98573007539] Output : { 98338017685, 234989854 } Input : RESSOL[13, 29996224275833] Output : { 28303375151909, 1692849123924 }
18
Lampiran 3. Implementasi Algoritma 3 dengan bantuan perangkat lunak Mathematica 5.2. Algoritma 3 : Mencari akar kuadrat modulo pq, dengan p dan q prima ganjil. INPUT : Bilangan prima ganjil p dan q , dan 1 ≤ a ≤ pq – 1 OUTPUT : Empat akar kuadrat a modulo pq. Algoritma3[a_Integer, p_Integer, q_Integer]:= If[PrimeQ[p] = = False || PrimeQ[q] = = False, Print["p atau q bukan prima"], If[JacobiSymbol[a, p] = = -1 || JacobiSymbol[a, q] = = -1, Print["Tak ada solusi"], w = Ressol[a, p] 1 ;
]
]
e = Ressol[a, q] 1 ; {b, {c, d}} = ExtendedGCD[p,q] ; x = Mod[w* d* q + e* c* p, p* q] ; y = Mod[w* d* q – e* c* p, p* q] ; If[x y||x Mod[-y, pq],{x, Mod[-x, pq]},{x, y, Mod[-x, pq],Mod[-y, pq] } ]
Contoh : Input : Algoritma3[3, 23, 97] Output : { 1833, 1465, 398, 766 } Input : Algoritma3[541, 104729, 15485863] Output : { 287132176177, 519495455767, 1334686769950, 1102323490360 }
19
Lampiran 4. Implementasi Algoritma 4 dengan bantuan perangkat lunak Mathematica 5.2. Algoritma 4 :
Mencari akar kuadrat modulo p , dengan p prima ganjil dan j ≥ 2 . j
INPUT
j
: Bilangan prima ganjil p , j ≥ 2 dan a ∈ [1, p − 1] j
OUTPUT : Dua akar kuadrat a modulo p .
Algoritma4[a_Integer, p_Integer, j_Integer] := If[PrimeQ[p] = = False, Print["p bukan prima"], If[JacobiSymbol[a, p] = = -1, Print["Tak ada solusi"], If[JacobiSymbol[a, p] = = 0, If[f[x_] := x^2 - a; Mod[f[0], p^2] = = 0, sol[2] = Table[p (i - 1), {i, p}]; tempsol[n_] := Array[bb, {Length[sol[n - 1]], p}]; For[k = 3, k j, k++, For[i1 = 1, i1 Length[sol[k - 1]], i1++, If[Mod[f[sol[k - 1][[i1]]], p^k] = = 0, For[i2 = 1, i2 p, i2++, bb[i1, i2] = sol[k - 1][[i1]] + p^(k - 1)(i2 - 1) ], For[i2 = 1, i2 p, i2++, bb[i1, i2] = Null ] ] ]; ss = DeleteCases[tempsol[k], Table[Null, {p}]]; sol[k] = Union[ss[[1]], ss[[2]]]; ]; sol[j], Print["Tak ada solusi"] ], {RESSOL[a, p] ; f[1] = r ; fInvers = PowerMod[2*r, -1, p] ; f[t_] := f[t] = f[t - 1] - (f[t - 1] ^ 2 - a) fInvers ; For[i = 1, i j, i++, s = Mod[f[i], p ^ i] ] ; s, Mod[ -s, p ^ j] } ] ] ] Contoh : Input : Algoritma4[54, 101, 12] Output : { 173271594768487760705407, 953553435363481959955794 } Input : Algoritma4[112, 541, 10] Output : { 2064697425807989041443720167, 82997796719148457447487234 } Input : Algoritma4[9, 3, 10] Output : { 3, 19680, 19686, 39363, 39369, 59046 } Input : Algoritma4[49, 7, 15] Output : { 7, 678223072842, 678223072856, 1356446145691, 1356446145705, 2034669218540, 2034669218554, 2712892291389, 2712892291403, 3391115364238, 3391115364252, 4069338437087, 4069338437101, 4747561509936 }
20
Lampiran 5. Waktu Eksekusi Algoritma 1 dan Algoritma RESSOL dengan bantuan perangkat lunak Mathematica 5.2. INPUT : Bilangan prima ganjil p dan n (adalah banyaknya nilai a yang diinginkan) OUTPUT : Waktu eksekusi Algoritma 1 dan Algoritma RESSOL (dalam detik) WaktuEksekusi[p_Integer, n_Integer]:= { we = Table [ a = Random[Integer,{1, p-1}]; While[JacobiSymbol[a, p] = = -1, a = Random[Integer,{1, p-1}]; ] ; { p, a, Timing[Algoritma1[a, p]][[1]], Timing[RESSOL[a, p]][[1]]}, {n} ]; TableForm[we, TableHeadings->{Automatic,{" p"," a"," Algoritma 1"," RESSOL"}}] }
Contoh : Input : WaktuEksekusi[1299709, 7] Output : P a 1 1299709 328426 2 1299709 671944 3 1299709 231057 4 1299709 601890 5 1299709 825496 6 1299709 290150 7 1299709 291949
Algoritma 1 1,2657 2,1884 1,4539 3,8138 1,2037 3,8286 2,7545
21
RESSOL 0,0069 0,0098 0,0081 0,0076 0,0015 0,0016 0,0031
Lampiran 6. Waktu Algoritma RESSOL dengan bantuan perangkat lunak Mathematica 5.2 INPUT
: Bilangan prima ganjil p = 29.996.224.275.833 dan n (adalah banyaknya nilai a yang diinginkan) OUTPUT : Waktu eksekusi Algoritma RESSOL (dalam detik) weRessol[n_Integer]:= {p = 29996224275833 weR = Table[ a = Random[Integer,{1, p-1}]; While[JacobiSymbol[a, p] -1, a = Random[Integer,{1, p-1}]; ]; {p, a, Timing[RESSOL[a, p]][[1]]}, {n} ]; TableForm[weR, TableHeadings->{Automatic, {" p"," a"," RESSOL"}}] } Contoh : Input : weRessol[10] Output : P 1 29996224275833 2 29996224275833 3 29996224275833 4 29996224275833 5 29996224275833 6 29996224275833 7 29996224275833 8 29996224275833 9 29996224275833 10 29996224275833
a 424613597121 10878246026665 5887477973699 20786675373559 1574940209207 5641355712333 10073237724502 27504498309348 7273523082800 18488184417987
22
RESSOL 0,0159 0,0178 0,0167 0,0206 0,0185 0,0194 0,0153 0,0212 0,0143 0,0134
