algoritma dan bilangan bulat (matematika diskrit)

7/21/2019 Algoritma Dan Bilangan Bulat (Matematika Diskrit)

http://slidepdf.com/reader/full/algoritma-dan-bilangan-bulat-matematika-diskrit 1/68

Pertemuan ke 11



BAB V

ALGORITMA DAN BILANGAN BULATA. ALGORITMA

Sebuah masalah dipecahkan dengan mendeskripsikan

langkahlangkah pen!elesaiann!a" Uru#an pen!elesaianmasalah ini dinamakan Algoritma.

Definisi 5.1 :

Alg$ri#ma adalah uru#an langkahlangkah l$gispen!elesaian masalah !ang disusun secara sis#ema#is"

Misal % resep membua# masakan Rendang &adang



N$#asi un#uk Alg$ri#ma

Alg$ri#ma dapa# di#uliskan dalam berbagai n$#asi' misaln!adalam n$#asi kalima#kalima# deskrip#i( seper#i c$n#$h resep

masakan rendang padang"Dengan n$#asi berga!a kalima# ini' deskripsi se#iap langkahdi)elaskan dengan bahasa seharihari secara gamblang"Se#iap langkah biasan!a dia*ali dengan ka#a ker)a seper#i

+baca,' +hi#ung,' +masukkan,' +bagi,' +gan#i' dan sebagain!a'sedangkan pern!a#aan bers!ara# din!a#akan dengan+)ika -maka-,



N$#asi un#uk Alg$ri#ma

.$n#$h %

/ika ki#a akan menuliskan alg$ri#ma un#uk mencari

elemen terbesar 0maksimum1 dari sebuahhimpunan !ang berangg$#akan n buah bilanganbula#" Bilanganbilangan bula# #ersebu#

din!a#akan sebagai a 1, a 2, a 3,…a n" 2lemen#erbesar akan disimpan di dalam peubah0variabel 1 !ang bernama maks.



Alg$ri#ma cari 2lemen #erbesar %

3" Asumsikan a3 sebagai elemen #erbesar semen#ara" Simpan a3 ke

dalam maks"

4" Bandingkan maks dengan elemen a4

' )ika a4

5 maks' maka nilaimaks digan#i dengan a4

6" Ulangi langkah ke 4 un#uk elemenelemen beriku#n!a 0a6' a7' a8'

-an1

7" Berhen#i )ika #idak ada lagi elemen !ang dibandingkan " Dalamhal ini maks berisi nilai elemen #erbesar"



Selain dengan n$#asi deskrip#i(' alg$ri#ma )uga dapa#digambarkan dalam n$#asi bahasa k$mpu#er 0lebih #epa#

bahasa pemr$graman1' misaln!a dalam bahasa &ascal a#auBahasa ."Dalam bahasa &ascal' alg$ri#ma mencari elemen #erbesar di#ulispada Alg$ri#ma 5.1



Proe!"re .ari2lemenTerbesar 0a%arra!9in#eger: n % inte#er: $ar maks % in#eger1:

( Mencari elemen terbesar di dalam array a(1..n). Elemen terbesar akan

disimpan di dalam maks. Array_integer adalah tipe array yang sudah

didefinisikan di dalam program utama dengan pendeklarasian berikut :

onst Nmaks ; 3<<<: 0 ukuran maksimum arra! 1t%&e arra!9in#eger ; arra%03""Nmaks1 of inte#er

$ari % inte#er:

be#inmaks % ; a031 :

for i % ; 4 to n !o if a0i1 5 maks t'an maks % ; a0i1 :

en!:

Al#oritma 5.1



Selain dari pada i#u' ada alg$ri#ma dengan n$#asi pseudocode 0semu1 !ang lebih prak#is menuliskann!a"

N$#asi ini men!erupai n$#asi bahasa pemr$graman #ingka# #inggi'khususn!a Bahasa &ascal dan .' #e#api #idak direp$#kan dengan#anda #i#ik k$ma' indeks' ($rma# keluaran' ka#aka#a khususdan lain sebagain!a sebagaimana bahasa pemr$graman"



=eun#ungan menggunakan n$#asi pseudocode adalahlebih muda mengk$n>ersin!a a#au men#ranslasi ke bahasapemr$graman' karena #erdapa# k$resp$ndensi an#ara se#iap pseudocode dengan n$#asi bahasa pemr$graman"

Beriku# ini c$n#$h alg$ri#ma mencari elemen #erbesar dengan

menggunakan n$#asi pseud$c$de dengan mengad$psi dalamBahasa &ascal' #e#api #idak benarbenar mema#uhisemua sin#aks &ascal"



Proe!"re .ari2lemenTerbesar 0inpu# a3' a4' -' an % in#eger'

$u#pu# maks % in#eger1:

( Mencari elemen terbesar di antara elemen a1 a ! " an . Elementerbesar akan disimpan di dalam maks.

Masukan : a1 a ! " an

#eluaran : maks)

De(larasii % in#eger

Al#oritma :maks ← a%($r i ← 4 #$ n d$ i( ai 5 maks #hen

maks ←ai

endi(end($r

Al#oritma 5.2



=a#aka#a !ang digaris ba*ah adalah men!a#akan ka#a kunci !ang nan#in!a berpadanan dengan ka#a kunci pada

bahasa k$mpu#er !ang akan digunakan un#uk men#ranslasikanalg$ri#ma #ersebu#"



). )ILA*GA* )+LAT

Bilangan bula# adalah bilangan !ang #idak

mempun!ai pecahan desimal"Misaln!a ?' 43' ?@8' 67' <



Misalkan a dan b adalah 4 buah bilangan bula#dengan s!ara# a <" =i#a men!a#akan

bah*a a 'abis memba#i b )ika #erdapa#bilangan bula# c sedemikian sehingga b ; ac

N$#asi % a b )ika b ; ac' c C dan a <

SIFAT PEMBAGIAN PADA BILANGAN BULAT.

∈



Dengan ka#a lain' )ika b dibagi dengan a' maka hasilpembagiann!a berupa bilangan bula#"

=adangkadang pern!a#aan

Ea habis membagi bF di#ulis )uga Eb kelipa#an aF

.$n#$h %

7 34 karena 34 % 7 ; 6 a#au 34 ; 7 6

34 % 7 memberi hasil bagi 6 dan sisa <

Te#api 7 #idak habis membagi 36 karena 36 % 7 ; 6'48

36 % 7 memberi hasil bagi 6 dan sisa 3



T2OR2MA 2U.LID2AN

Misalkan m dan n adalah dua buah bilanganbula# dengan s!ara# n 5 <" /ika m dibagi dengan

n 0pembagi1 maka #erdapa# dua buah bilanganbula# unik H 0Hu$#ien# ; hasil bagi1 dan r 0remainder ; sisa1 sedemikian sehingga %

m n- rdengan < r n

$ % m !i$ n r % m mo! r



1. 1/0 / . 2

0 3J?@ di> J@ ;4< dan 3J?@ m$d J@ ; 7@ 1

4" 47 ; 6" ? K <6" 44 ; 6 0?1 2

Sisa pembagian #idak b$leh nega#i(' )adi c$n#$h ke 6

#idak dapa# di#ulis %44 ; 6 0@1 4 1

karena r ; 3 #idak memenuhi s!ara# r n

m = nq + r

q = m div n ,

r = m mod n

Contoh 5.1



&2MBAGI B2RSAMA T2RB2SAR

Misalkan a dan b adalah dua buah bilangan bula# #idak n$l"&embagi bersama #erbesar 0&BB1 dari a dan b adalahbilangan bula# #erbesar d sedemikian sehingga da dandb" Dalam hal ini din!a#akan &BB 0a'b1 ; d

78 memiliki (ak#$r pembagi 3' 6' 8' J' 38 dan 78

6 memiliki (ak#$r pembagi 3' 4' 6' 7' J' 34' 3?' dan 6

(ak#$r pembagi bersama dari 78 dan 6 adalah 3' 6' J !ang #erbesar adalah /

e'in##a !isim&"l(an P)) 65, 378 /



Si(a#si(a# dari pembagi bersama #erbesar din!a#akan

dengan #e$rema#e$rema beriku# %

Misalkan a' b' dan c adalah bilangan bula#"

a" /ika c adalah &BB dari a dan b' maka c 0a K b 1

b" /ika c adalah &BB dari a dan b' maka c 0a b 1

c" /ika c a ' maka c ab

Contoh 5.!

&BB dari 78 dan 6 adalah /"a1 J habis membagi 78 K 6 ;?3' a#au J 078 K 61b1 J habis membagi 78 6 ; J ' a#au J 078 61c1 J habis membagi 786;34<' a#au J 078 61



Misalkan m dan n adalah dua buah bilanganbula# dengan s!ara# n 5 < sedemikian sehingga %

m ; nH K r ' < r n

maka P)) 6m,n8 P)) 6n,r8

9onto' :



Contoh 5."

Jika 80 dibagi dengan 12 memberi hasil 6 dan sisa 8,

atau 80 = 12.6 + 8. Menurut teorema 5.3P!80, 12" = P!12, 8" = #

Jika 12 dibagi dengan 8 memberi hasil 1 dan sisa #,

atau 12 = 8.1 + #P!12, 8" = P!8, #" = #

Jika 8 dibagi dengan # memberi hasil 2 dan sisa 0,

atau 8 = #.2 + 0. Menurut teorema 5.3

P!8, #" = P!#, 0" = # # = 0.0 + #

$ari runtunan %erhitungan di atas, kita mem%eroleh bah&a

P!80, 12" = P!12, 8" = P!8, #" = P!#, 0" = #



6" ALGORITMA 2U.LID2AN

3" /ika n ; <' maka

m adalah &BB 0m'n1:

s#$p"Te#api )ika n ≠ <

lan)u#kan ke langkah 4"

4" Bagilah m dengan n dan misalkan r adalah sisan!a"6" Gan#i nilai m dengan n dan nilai n dengan r' lalu ulang

kembali ke langkah 3"



Contoh 5.#

80 = 6.12 + 8

12 = 1.8 + #

8 = 2. # + 0

'isa %embagian terakhir sebelum 0 adalah #, maka P!80, 12" = #

Menuru# #e$rema 5.3&BB dari m dan n adalah sisa tera('ir %an# ti!a( nol dari run#unan

pembagian #ersebu# &BB0?<' 341 ; 7

sisa tera('ir %an# ti!a( nol



Teorema 5. :Misalkan a dan b adalah dua buah bilangan bula# p$si#i(' maka#erdapa# bilangan bula# m dan n sedemikian sehingga

P))6a, b8 ma nb

Misaln!a &BB0?<' 341 ; ' dan 7 ; 0 3 1 " ?< K @ " 34"

disini m ; 3 dan n ; @



Contoh 5.5

()atakan P!312, *0" = 2 sebagai $om%in&'i (&n)&r dari 312 dan *0

era%kan algoritma u-lidean untuk mem%eroleh P!312, *0" = 2

312 = #.*0 + 32 !i" 32 = 312 #.*0 !/ii"

*0 = 2.32 + 6 !ii" 6 = *0 2.32 !/i"

32 = 5.6 + 2 !iii" 2 = 32 5.6 !/"

6 = 3.2 + 0 !i/"

!/" ke !/i"

2 = 32 5.!*0 2.32"

2 = 1.32 5.*0 + 10.32 2 = 11.32 5.*0 !/ii"

2 = 11.!312 #.*0" 5.*0 = 11.312 #.*0

Jadi P!"1!, *" = 2 = 11."1! #,.*m a n b



Pertemuan ke 12



7" ARITM2TI=A MODULO

Misalkan a adalah bilangan bula# dan m adalah bilanganbula# 5 <" Operasi a m$d m 0dibaca a m$dul$ m1

memberikan sisa )ika a dibagi dengan m"

Dengan ka#a lain %

a m$d m ; r sedemikian sehingga a ; mH K r'

dengan < r m



Contoh 5.*

Berapa hasil $perasi dengan $pera#$r m$dul$ %

0i1 46 m$d 8 ; 6 0karena 46 dibagi 8 memberikan hasil ; 7 dan sisa ; 6'a#au di#ulis 46 ; 8"7 K 61

0ii1 4@ m$d 6 ; < 04@ ; 6"J K <10iii1 m$d ? ; 0 ; ?"< K 10i>1 < m$d 34 ; < 0< ; 34"< K <1

0>1 73 m$d J ; 7 073 ; J081 K 710>i1 6J m$d 36 ; < 06J ; 36061 K <1

a mo! m r a m- r



=$ngruen

/ika dua buah bilangan bula# a dan b' mempun!ai sisa!ang sama )ika dibagi dengan bilangan bula# p$si#i( m'maka a dan b kongruen dalam modulo m dandilambangkan sebagai %

a≡

b 0m$d m1

/ika a #idak k$ngruen dengan b dalam m$dulus m'maka di#ulis %

a ≡ b 0m$d m1



.$n#$h %

6? m$d 8 ; 3 ' dan 36 m$d 8 ; 3

6?8;@ sisa 6 368;4 sisa 6

maka %

30≡

13 6 mo! 58



Contoh 5.-

3@ ≡ 4 0m$d 61 0 3 'abis memba#i 1 4 2 ; 15 38 % 6 ; 8 1

@ ≡ 38 0m$d 331 0 33 habis membagi @ 38 ; 44

44 % 33 ; 4134 ≡ 4 0m$d @1 0 @ #idak habis membagi 34 4 ; 3< 1@ ≡ 38 0m$d 61 0 6 #idak habis membagi @ 38 ; 44 1

Definisi !ari (on#r"en %

Misalkan a dan b adalah bilangan bula# danm adalah bilangan 5 < maka a ≡ b 0m$d m1

)ika m 'abis memba#i a b



=ek$ngruenan a ≡ b 6mo! m8 dapa# pula di#uliskan dalam hubungan a = b + km !ang dalam hal ini

sembarang ( adalah bilangan bula#"



Contoh 5.,

6? 36 0m$d 81 dapa# di#ulis sebagai 6? ; 36 K 8 " 83@ 4 0m$d 61 dapa# di#ulis sebagai 3@ ; 4 K 8 " 6 @ 38 0m$d 331 dapa# di#ulis sebagai @ ; 38 K 041 33

a b ( m

a = b + kma ≡ b 6mo! m8



Berdasarkan de(inisi ari#me#ika m$dul$ 0de(inisi 8"81' ki#a dapa# menulis

a mo! m = r sebagai a ; r 6mo! m8

Contoh 5.1

46 m$d 8 ; 6 dapa# di#ulis sebagai 23 3 0m$d 514@ m$d 6 ; < dapa# di#ulis sebagai 4@ < 0m$d 61 m$d ? ; dapa# di#ulis sebagai 0m$d ?1 < m$d 34 ; < dapa# di#ulis sebagai < < 0m$d 34173 m$d J ; 7 dapa# di#ulis sebagai 73 7 0m$d J16J m$d 36 ; < dapa# di#ulis sebagai 6J < 0m$d 361



Si(a#si(a# penger)aan hi#ung pada ari#me#ika m$dul$'

('"s"sn%a &er(alian dan &en<"mla'an'din!a#akan dalam #e$rema#e$rema beriku# %



Misalkan m adalah bilangan bula# p$si#i("1. /ika a ≡ b 0m$d m1 dan adalah sembaran#bilan#an b"lat' maka %

0i1 0a K c1 ≡ 0b K c10m$d m1

0ii1 ac ≡ bc 0m$d m1 0iii1 a& ≡ b& 0m$d m1 un#uk sua#u bilangan

bula# #ak nega#i( &

9onto' 5.11 :Misal% 3@ ≡ 4 0m$d 61 dan 3< ≡ 7 0m$d 61' maka %

3@ K 8 ≡ 4 K 8 0m$d 61 ⇔ 44 ≡ @ 0m$d 61 0#e$rema 8"8"30i11

3@ " 8 ≡ 4 " 8 0m$d 61 ⇔ ?8 ≡ 3< 0m$d 61 0#e$rema 8"8"30ii11



3@ ≡ 2 0m$d 613@6 ; 8 sisa 2 46 ; < sisa 2

44 ≡ @ 0m$d 61446 ; @ sisa 1 @6 ; 4 sisa 1

?8 ≡ 1 0m$d 61?86 ; 4? sisa 13<6 ; 6 sisa 1

mempun!ai sisa !ang sama



2. /ika a ≡ b 0m$d m1 dan ≡ ! 0m$d m1 ' maka %

0i1 0aKc1 ≡ 0bKd1 0m$d m1

0ii1 a c ≡ bd 0m$d m1

9onto' 5.11 :

Misal% 3@ ≡ 4 0m$d 61 dan 3< ≡ 7 0m$d 61' maka %

3@ K 3< ≡ 4 K 7 0m$d 61 ⇔ 4@ ≡ 0m$d61 0#e$rema 8"8"40i113@ " 3< ≡ 4 " 7 0m$d 61 ⇔ 3@< ≡ ? 0m$d 61 0#e$rema 8"8"40ii11



3@ ≡ 4 0m$d 61 3< ≡ 7 0m$d 61

3@ ≡ 2 0m$d 61

3@6 ; 8 sisa 2 46 ; < sisa 2

3< ≡ 0m$d 61

3<6 ; 6 sisa 1 76 ; 3 sisa 1

4@ ≡ 7 0m$d 614@6 ; J sisa 6 ; 4 sisa

mempun!ai sisa !ang sama

Balikan M$dul$



Balikan M$dul$

0 Mo!"lo In$ers1

/ika a dan m rela#i( prima dan m 5 3' maka dapa#di#emukan balikan 0in>ers1 dari a m$dul$ m"

Balikan dari a m$dul$ m adalah bilangan bula# sedemikian sehingga a ≡ 3 0m$d m1

Di dalam ari#me#ika bilangan riil' in$ersi 0inverse1dari &er(alian adalah &emba#ian

Misaln!a in>ersi dari a!ala' 1=



Contoh 5.1!

Ten#ukan in$ersi dari 7 0m$d J1' 3@ 0m$d @1' dan 3? 0m$d 3<1

a m&BB07' J1 ; 3' maka in>ersi dari 7 0m$d J1 ada"

J ; 4"7 K 32 " 7 K 3"J ; 3 p"a K H"m ; 3

Dari persamaan #erakhir ini ki#a per$leh 2 adalah in>ersi dari 7 m$dul$ J

4"7 ≡ 3 0m$d J1 J habis membagi 0 47 1 3 ; J

&/



%/

a m&BB03@' @1 ; 3' maka in>ersi dari 3@ 0m$d @1 ada"

3@ ; 4"@ K 6 0i1 6 ; 3@ 4"@ 0>1 @ ; 4"6 K 3 0ii1 3 ; @ 4"6 6i$8 6 ; 6"3 K < 0iii1

0>1 ke 6i$8 3 ; @ 4"03@ 4"@1 ; 3"@ 4"3@ K 7"@ ; 8"@ 4"3@

a#au 2 " 3@ K 8 " @ ; 3 p"a K H"m ; 3

Dari persamaan #erakhir ini ki#a per$leh 2 adalah in>ersi dari 3@ m$dul$ @4"3@ ≡ 3 0m$d @1 @ habis membagi 04"3@1 3 ; 68"

=arena &BB03?' 3<1 ; 4 3' maka in>ersi dari 3? 0m$d 3<1 #idak ada"0/



=ek$ngruenan Linearlan)ar

=ek$ngruenan linear adalah k$ngruen !ang berben#uk % a ≡ b 0m$d m1

Dengan m adalah bilangan bula# p$si#i(' a dan b sembarang bilanganbula#' dan adalah peubah"

Ben#uk k$ngruen linear berar#i menen#ukan nilainilai ' !ang memenuhik$k$ngruenan #ersebu#"

a ≡ b 0m$d m1 dapa# di#ulis dalam hubungan a ; b K km

!ang dapa# disusun men)adi %

a

km b

+= a

km b +=



Contoh 5.1"

Ten#ukan s$lusi dari 7 > 6 0m$d J1

=ek$ngruenan 7 > 6 0m$d J1 eki>alen dengan menemukan k dan bilangan bula# sedemikian sehingga

a

km b

+= 3 k . /

k ; 3 ; 6k ; 8 ; 34k ; 6 ; k ; @ ; 38

/adi nilainilai !ang memenuhi 7 > 6 0m$d J1adalah 6' 34' -" dan ' 38' -"



BILANGAN &RIMA

Bilangan bula# p$si#i( !ang lebih besar dari 3 !ang han!a habis dibagi$leh 3 dan dirin!a sendiri"

2, 3, 5, , 11, 13, ……..

Definisi 5. :

Bilangan bula# p$si#i( p 0p531 disebu# bilangan prima )ika pembagin!ahan!a 3 dan p

Bilangan selain bilangan prima disebu# bilangan komposit.

2 !a&at !iba#i ole' 2, , 5, !an 1, selain 1 !an 2 sen!iri.



Te$rema Pundamen#al Ari#me#ik

Se#iap bilangan bula# p$si#i( !ang lebih besar a#au samadengan 4 dapa# din!a#akan sebagai perkalian sa#u a#au

lebih bilangan prima"Misal %

J ; 6 6 0 4 buah (ak#$r prima1

3<< ; 4 4 8 8 0 7 buah (ak#$r prima1

36 ; 36 Q 3 0 1 buah (ak#$r prima1



Pak#$r &rima dari n selalu lebih kecila#au sama dengan √n

Misalkan a adalah (ak#$r prima dari n'

dengan 3 a n' maka a habis membagi n denganhasil bagi b sedemikian sehingga n ; ab"

Nilai a dan b haruslah n agar %

ab 5√n " √n ; n

9onto' 5.15 :

Tun)ukkan apakah 3@3 dan 3JJ merupakan bilangan prima a#au k$mp$si#



6i8 ? 11 ; 36'<@@" Bilangan prima !ang 3@3 adalah4' 6' 8' @' 33' 36" =arena 3@3 habis dibagi 6'maka 3@3 adalah bilangan k$mp$si#"

6ii8 ? 1// ; 37'3<@" Bilangan prima !ang 3JJ adalah4' 6' 8' @' 33' 36" =arena 3JJ #idak habis dibagi 4' 6' 8' @' 33' 36maka 3JJ adalah bilangan prima"

Contoh 5.1



Temukan semua (ak#$r prima dari 33@"

Contoh 5.1

)a#ila' 171 bert"r"tt"r"t !en#an barisan bilan#an &rima, m"lai !ari2, 3, 5, , ….

2 ti!a( 'abis memba#i 1713 'abis memba#i 171, %ait" 171=3 53/

elan<"tn%a, ba#ila' 53/ !en#an bilan#an &rima bert"r"tt"r"t,!im"lai !ari 3, 5, , ..3 ti!a( 'abis memba#i 53/5 ti!a( 'abis memba#i 53/ 'abis memba#i 53/, %ait" 53/=

elan<"tn%a, ba#ila' !en#an bilan#an &rima bert"r"tt"r"t,!im"lai !ari , 11, … 'abis memba#i , %ait" = 11

@arena 11 a!ala' bilan#an &rima, ma(a &enarian fa(tor &rima !ari 171 !i'enti(an.a!i, fa(tor &rima !ari 171 a!ala' 3, , !an 11, %ait" 171 3 > > > 11.



" =RI&TOGRAPI

Ari#me#ika m$dul$ dan bilangan prima mempun!aiban!ak aplikasi dalam ilmu k$mpu#er' salah sa#u

aplikasin!a !ang #erpen#ing adalah (ri&to#rafi"

=rip#$gra(i adalah ilmu sekaligus seni un#uk men)agakerahasiaan pesan 0 da#a a#au in($rmasi1 dengan cara

men!amarkan men)adi ben#uk !ang #idak mempun!aimakna"



Plainte(s, 9i&'erte(s, Bn(ri&si !an De(ri&si.

Plainte(s % pesan !ang dirahasiakan'

ar#in!a #eks )elas !ang dapa# dimenger#i"

9i&'erte(s % pesan hasil pen!amaran'

ar#in!a #eks #ersandi"

Bn(ri&si % &r$ses pen!amaran dari plain#eks ke cipher#eks"

De(ri&si % &r$ses pembalikan dari cipher#eks ke plain#eks"

enkripsi dekripsicipher#eksplain#eks plain#eks asal



e<ara' @ri&to#rafi

(ri

&to#

ra

=rip#$gra(i sudah lama digunakan $leh #en#ara Spar#a di unani pada permulaan #ahun 7<< SM" Mereka menggunakan ala# !angdisebu# scytale" Ala# ini #erdiri dari sebuah pi#a pan)ang dari

daun pap!rus !ang dilili#kan pada seba#ang silinder"&esan !ang akan dikirim di#ulis h$ri$n#al 0baris per baris1"Bila pi#a dilepaskan' maka huru(huru( di dalamn!a #elah#ersusun memben#uk pesan rahasia"

Un#uk membaca pesan' penerima melili#kan kembali silinder!ang diame#ern!a sama dengan diame#er silinder pengirim"Teknik krip#$gra(i seper#i ini dikenal dengan nama tran&osisii&'er' !ang merupakan me#$de enkripsi #er#ua"



@ri&to#rafer, @ri&tanalis, !an @ri&tolo#i

@ri&to#rafer: $rang !ang menggunakan enkripsi un#ukmerahasiakan pesan dan

mendeskripsikann!a kembali"

@ri&tanalis : $rang !ang mempela)ari me#$de enkripsi dancipher#eks dengan #u)uan menemukan

plain#eksn!a"

@ri&tolo#i : s#udi mengenai krip#$gra(i dan krip#analis"



*otasi Matematis

/ika cipher#eks dilambangkan dengan . dan plain#eks dilambangkandengan &' maka (ungsi enkripsi 2 meme#akan & ke .'

2 0&1 ; .&ada pr$ses kebalikann!a' (ungsi deskripsi D meme#akan . ke &'

D 0.1 ; &

=arena pr$ses enkripsi kemudian dekripsi mengembalikan pesan kepesan asal' maka kesamaan beriku# harus benar '

D 0 2 0&1 1 ; &



Alg$ri#ma =rip#$gra(i 0 .ipher1

Alg$ri#ma =rip#$gra(i 0cipher1 adalah (ungsi ma#ema#ika !angdigunakan un#uk enkripsi dan dekripsi"

=ekua#an sua#u alg$ri#ma =rip#$gra(i diukur dari ban!akn!a ker)a !ang dibu#uhkan un#uk memecahkan da#a chiper#eks men)adiplain#eks"

=rip#$gra(i m$dern #idak lagi mendasarkan kekua#an padaalg$ri#man!a" /adi alg$ri#ma #idak dirahasiakan" =ekua#ankrip#$gra(in!a #erle#ak pada kunci' !ang berupa dere#an karak#er a#au bilangan bula# !ang di)aga kerahasiaann!a"



Alg$ri#man!a memper#ukarkan pada se#iap ka#a karak#er per#amadengan karak#er kedua' karak#er ke#iga dengan karak#er keempa#dan se#erusn!a"

.$n#$h %

Plainte(s : TR+@T+R DI@RIT

9i&'erte(s : T+RT@R+ ID@IRT



=uncin!a adalah )umlah pergeseran huru( 0!ai#u 61"Susunan al(abe# se#elah digeser se)auh 6 huru( adalah %

Plainte(s : A ) 9 D B C G I @ L M * O P E R T + F H J

9i&'erte(s : D B C G I @ L M * O P E R T + F H J A ) 9

&esan %AAI ATBRIH DA* TBMA**A O)BLIH

9i&'erte(s :DJDFL DF+LA GDE PDEE)D RBOLA



Secara ma#ema#is' pada sis#em krip#$gra(i !angmenggunakan kunci =' maka (ungsi enkripsi dan dekripsimen)adi %

2@1 0 & 1 ; . dan D@2 0 . 1 ; &

=edua (ungsi ini memenuhi %

D@2 02@1 0 & 11 ; &

/ika =3 ; =4' maka alg$ri#ma krip#$gra(in!a

disebu# alg$ri#ma simetri 6 ("ni &riba!i8/ika =3 ≠ =4 ' maka alg$ri#man!a disebu#alg$ri#ma nirsimetri 6 ("ni &"bli( 8



DB6Data Encryption Standard 8

D2S dilakukan dalam 3 kali perulangan"&an)ang kunci D2S adalah ? karak#er a#au 7 bi#"Dari 7 bi# #ersebu#' han!a 8 bi# sa)a !ang dipakai dalam pr$ses enkripsi"

8 bi# #erdapa# 2 57 a#au @4"<8@"8J7"<6@"J4@"J6 kemungkinan kunci"

/ika $rang !ang #idak berhak menc$ba keseluruhan kunci #ersebu# denganmenggunakan sa#u )u#a pr$ses$r k$mpu#er !ang beker)a secara paralel'

maka dengan asumsi bah*a selama 3 de#ik dapa# dic$ba sa#u )u#akemungkinan kunci' maka seluruh kemungkinan kunci #ersebu# memerlukan*ak#u 44?7 #ahun un#uk menemukan kunci !ang benar"



Alg$ri#ma RSA6Ri$est 4 'amir 4 A!leman8

Alg$ri#ma RSA mendasarkan pr$ses enkripsi dandekripsin!a pada k$nsep bilangan prima dan ari#me#ikam$dul$"

=unci enkripsi dan dekripsi merupakan bilangan bula#"

=unci enkripsi #idak dirahasiakan' #e#api kunci dekripsibersi(a# rahasia"

Un#uk menemukan kunci dekripsi harus mem(ak#$rkansua#u bilangan n$n prima men)adi (ak#$r priman!a"



eara rin#(as, al#oritma RA a!ala'seba#ai beri("t :

&ilih dua buah bilangan prima sembarang' a dan b' )agakerahasiaan a dan b"

Wi#ung n ; a b" Nilai n #idak dirahasiakan"

Wi#ung m ; 0a 31 0b 31" Se#elah nilai m dike#ahui' a dan bdapa# dihapus"

&ilih sebuah bilangan bula# e un#uk kunci publik' dimana e rela#i(prima #erhadap m"

Bangki#kan kunci dekripsi' d dengan kek$ngruenan

ed ≡ 3 0m$d m1

&r$ses dekripsi dilakukan dengan menggunakan persamaan pi ;ci

d m$d n' !ang dalam hal ini d adalah kunci dekripsi"



ISBN 3155710

< adalah k$de kel$mp$k negara berbahasa Inggris6<38 k$de penerbi#783 k$de unik buku? karak#er u)i

=arak#er u)i didapa#kan sbb %

3"< K 4"6 K 6"< K 7"3 K 8"8 K "7 K @"8 K ?" K J"3 ; 383

/adi karak#er u)in!a adalah 383 m$d 33 ; ?

Dan 463 mo! 33 ; < a#au 463 ≡ < 0mo! 331

∑∑==

=⋅+=+=

1

10

10

1

23181015110

i

i

i

i xixix



p p

pixi

i

*11360*5#15362*1#

#08*635#3*21

1

+=++++++++=

⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅+⋅=∑=

/adi03J3 K @ p1 m$d 33 ; 8

A#au

*

18611

*

11511 −=−+= k k p

Nilainilai k !ang menghasilkan p bula# adalah k ; -' ' 3' ?' 38' 44' 4?' -

Agar &' sa' maka p haruslah memenuhi < p J"Un#uk k ; 44 didapa#kan p ; ?

0 33 " 44 1 3?@

474 3?@

8@

0

algoritma dan bilangan bulat (matematika diskrit)

Documents