Monday, 8 July 2013

Modulo (Teori Bilangan)

Hallo sobat Berbagi Matematika :D
kali ini saya akan membahas apa itu Modulo

Sedikit ulasan
Modulo itu digunakan untuk menghitung sisa pembagian
dan bisa di terapkan untuk menghitung hari sebelum/sesudahnya dengan memperhatikan apakah tahun itu kabisat atau tidak

Contoh kasus
apabila hari ini hari minggu tanggal 25 januari 2015 maka 19 tahun kemudian 25 januari jatuh hari ?

Cara nya
19 mod 4 = 3 ( tiga sebagai sisa pembagian dari 19 dibagi 4 )

kenapa di mod 4 ? karena kabisat jatuh setiap 4 tahun sekali
nah nanti di tambah +3 hari ( karena yang di tanya hari " kemudiannya " kalau hari " sebelumnya " tinggal di kurang saja

lalu
19 mod 7 = 5 ( lima sebagai sisa pembagian dari 19 dibagi 7 )
kenapa di mod 7 ? karena dalam satu minggu terdapat 7 hari ==> nah di sini untuk menentukan hari

lalu kita tambahkan dengan hasil sebelumnya yaitu +3 maka jadinya 7+3 = 10

kan tadi di soal , 25 januari 2015 jatuh hari minggu
maka 25 januari di tahun 2034 jatuh hari ....???

caranya mudah , hasil data yang kita peroleh ditambahkan
hari minggu + 10 hari = hari rabu

jadi 25 januari tahun 2034 jatuh hari rabu

# check deh untuk pembuktiannya ^_^ :D

Keren kan ?

Yuk Cekidot .... :D
untuk menyimak teori nya

Teori Bilangan
  • Teori bilangan (number theory) adalah teori yang mendasar dalam memahami algoritma kriptografi.
  • Bilangan yang dimaksudkan adalah bilangan bulat (integer).
       Aritmatika Modulo
Aritmatika modulo (modular arithmethic) memainkan peran yang penting dalam komputasi integer, khususnya pada aplikasi kriptografi. Operator yang digunakan pada aritmatika modulo adalah mod. Operator mod, jika digunakan pada pembagian bilangan bulat memberikan sisa pembagian sebagai kembaliannya. Sebagai contoh 53 mod 5 memberikan hasil = 10 dan sisa = 3. Maka 53 mod 5 = 3.
Defenisi : Misalkan  adalah bilangan bulat dan  adalah bilangan bulat > 0. Operasi  mod  memberikan sisa jika  dibagi .


Algoritma Euclidean

  • Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat.
  • Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.
  • Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³ n). Algoritma Euclidean berikut mencari  pembagi bersama terbesar dari m dan n.
     Relatif Prima
Definisi:  Dua buah bilangan bulat  dan  dikatakan relatif prima jika FPB/GCD (x,y)=1
Contoh :
     7 dan 11 adalah relatif prima karena FPB/GCD (7,11) = 1 31 dan 268 adalah relatif prima karena FPB/GCD (31,268) = 1. 9 dan 132 bukan relatif prima karena FPB/GCD (9, 132) = 3. Jika dan relatif prima, maka dapat ditemukan bilangan bulat dan sedemikian sehingga .
Contoh: Bilangan 20 dan 3 adalah relatif prima karena FPB (20, 3)=1, atau dapat ditulis dengan dan .

Balikan Modulo (Modulo Invers) 

jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan (invers) dari amodulo m. Balikan dari a modulo m adalah bilangan bulat (a invers) sedemikian sehinggaa (a invers) kongruen 1 (mod m).

Kekongruenan Lanjar

-Kekongruenan lanjar adalah kongruen yang berbentuk ax º b (mod m) dengan madalah bilangan bulat positif, a dan b sembarang bilangan bulat, dan x adalah peubah bilangan bulat.

-Nilai-nilai x dicari sebagai berikut: ax = b + km yang dapat disusun menjadi x = (b+km)/a dengan k adalah sembarang bilangan bulat. Cobakan untuk k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat

TEOREMA (Chinese Remainder Theorem) Misalkan m1, m2, …, mn adalah bilangan bulat positif sedemikian sehingga PBB(mi , mj) = 1 untuk i < > j. Maka sistem kongruen lanjar x kongruen ak (mod mk) mempunyai sebuah solusi unik modulo m = m1 × m2 × … ×mn.

Aritmetika Modulo dan Kriptografi

Penggunaan Teori Bilangan Pada Sistem Kriptografi Merkle-Hellman (Knapsack) Kriptografi Merkle Hellman merupakan sistem kunci asimetri, yang berarti bahwa dalam sistem komunikasi diperlukan dua kunci yaitu kunci publik dan kunci privat. Sudah dijelaskan pada pembahasan sebelumnya bahwa algoritmasuperincreasing knapsack adalah algoritma yang lemah, karena chiperteks dapat didekripsi menjadi plainteksnya secara mudah dalam waktu lanjar. Sedangkan algoritma nonsuperincreasing knapsack atau normal knapsack adalah kelompok algoritma knapsack yang sulit (dari segi komputasi) karena membutuhkan waktu dalam orde eksponensial untuk memecahkannya. Namun, Martin Hellman dan Ralph Merkle menemukan cara untuk memodifikasi superincreasing knapsack menjadi non-superincreasing knapsack dengan menggunakan kunci publik (untuk enkripsi) dan kunci privat (untuk dekripsi). Kunci publik merupakan barisan non-superincreasing sedangkan kunci privat tetap merupakan barisan superincreasing.  Modifikasi dilakukan dengan menggunakan perhitungan aritmatika modulo.

Aritmetika modulo cocok digunakan untuk kriptografi karena dua alasan:
1. Oleh karena nilai-nilai aritmetika modulo berada dalam himpunan berhingga (0 sampai modulus m – 1), maka kita tidak perlu khawatir hasil perhitungan berada di luar himpunan.

2. Karena kita bekerja dengan bilangan bulat, maka kita tidak khawatir kehilangan informasi akibat pembulatan (round off) sebagaimana pada operasi bilangan riil.

Teorema 3. (The Fundamental Theorem of Arithmetic). Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan n sebagai perkalian satu atau lebih bilangan prima.

Teorema 4 (Teorema Fermat). Jika p adalah bilangan prima dan aadalah bilangan bulat yang tidak habis dibagi dengan p, yaitu PBB(a, p) = 1, maka a p–1 kongruen 1 (mod p) Fungsi Euler f

Fungsi Euler f medefinisikan f(n) untuk n >= 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n

Teorema 5. Jika n = pq adalah bilangan komposit dengan p dan q prima, maka f(n) = f(p) f(q) = (p – 1)(q – 1). Teorema 6. Jika p bilangan prima dan k > 0, maka f(p k ) = p k – p k-1 = p k-1 (p – 1) . 


Algoritma Knapsack 

Algoritma Knapsack adalah salah satu algoritma kriptografi kunci publik yang berguna untuk menjaga kerahasiaan pesa. Disebut kriptografi kunci publik (publik-key cryptography) karena kunci untuk enkripsi tidak rahasia dan dapat diketahui oleh siapapun (diumumkan ke publik), sementara kunci untuk dekripsi hanya diketahui oleh penerima pesan (karena itu rahasia).

a. General Knapsak Bentuk umum knapsack :
b. Superincreasing Knapsack Barisan superincreasing adalah suatu barisan dimana setiap nilai di dalam barisan lebih besar daripada jumlah semua nilai sebelumnya. Contoh: adalah barisan superincreasing, tetapi bukan.

Penggunaan Aritmatika Modulo dan Relatif Prima pada Knapsack 

Pada kriptografi Merkle-Hellman, kunci yang digunakan terdiri knapsack.Kunci publik merupakan ‘hard’ knapsack, sedangkan kunci privat merupakan ‘mudah’ (superincreasing knapsack), yang dikombinasikan dengan dua bilangan tambahan, yaitu pengali (multiplier) dan modulus yang digunakan untuk mengubah superincreasing knapsack menjadi hard knapsack. Bilangan-bilangan yang sama digunakan untuk mengubah jumlah dari himpunan bagian dari hard knapsack menjadi jumlah dari himpunan bagian dari superincreasing knapsackyang dapat dipecahkan dalam orde waktu polinomial.


No comments:

Post a Comment