modul mte3143-bab 3.pdf
Post on 30-Sep-2015
99 Views
Preview:
TRANSCRIPT
-
28 MODUL MTE3114 APLIKASI MATEMATIK
28
3.1 Kapal Angkasa Mariner6 1969
Pada tahun1965, Amerika Syarikat telah melancarkan kapal angkasa Mariner4 untuk
mengambil gambar Marikh. Transmisi setiap gambar mengambil masa 8 jam. Misi
Mariner selanjut, seperti Mariner6, telah menghasilkan gambar yang lebih jelas
sebab menggunakan kod pembetulan ralat.
.
Kaedah transmisi gambar oleh Mariner6 dari Marikh ke Bumi yang digunakan pada
tahun 1969 melibatkan penggunaan grid halus yang diletakkan ke atas gambar yang
dikirim. Setiap petak atau piksel, diberi darjah kehitaman antara julat 0 hingga 63.
BAB 3 KOD DAN KRIPTOGRAFI
-
29 MODUL MTE3114 APLIKASI MATEMATIK
29
Setiap nombor ditulis sebagai urutan enam 0 dan 1. Contoh cara penulisan dalam
sistem binari (nombor asas 2) adalah seperti di bawah:
0
000000
1 000001
2 000010
3 000011
4 000100
5 000101
6 000110
7 000111
8 001000
9 001001
43 101011
63 111111
Jadi, darjah kehitaman = 43 101011.
Dalam kes Mariner6, setiap gambar dipecahkan kepada 700 x 832 petak, di mana
setiap petak dikodkan oleh 6 digit binari, setiap gambar akan mengandungi satu
urutan 6 x 700 x 832 = 3 494 400 digit binari.
Walau bagaimana pun, darjah kehitaman setiap petak mengandungi enam digit binari
manakala mesej yang dikirim sebenarnya menggunakan lebih banyak digit bagi
setiap darjah kehitaman sebenarnya 32 digit binari digunakan bagi setiap petak,
oleh yang demikian gambar akan mengandungi urutan 32 x 700 x 832 = 18 636 800
digit binari.
-
30 MODUL MTE3114 APLIKASI MATEMATIK
30
Proses Transmisi Mesej
Sungguh pun, saluran transmisi mesej yang ditunjukkan di atas mudah. Kadang-
kadang mesej yang dikirim akan diganggu oleh ralat tertentu. Sama ada saluran
transmisi yang digunakan merupakan pautan satelit, tanpa wayar atau wayar telefon,
biasanya saluran tersebut mungkin akan menambah unsur gangguan (noise) yang
menyebabkan ralat. Kejadian ini serupa dengan gangguan suara yang kita alami
semasa panggilan telefon di kawasan isyarat lemah.
Dalam contoh di atas, mesej 01101 dikirim tetapi mesej yang diterima kurang jelas.
Jadi, adalah sukar untuk menterjemahkan digit tengah dan digit terakhir yang
diterima 01?0?
Apakah yang si penerima patut buat bila menerima mesej tersebut? Jawapannya
bergantung kepada situasi. Misalnya, adalah mungkin mesej tersebut diminta dikirim
sekali lagi semasa panggilan telefon, minta disebut sekali lagi atau pun semasa
menggunakan kad kredit, kad kredit dilalui mesin kad kredit sekali lagi jika nombor
-
31 MODUL MTE3114 APLIKASI MATEMATIK
31
yang diterima kurang jelas sebab sukar diteka. Dalam kes misi angkasa lepas
Mariner, gambar tersebut tidak dapat dihantar sekali lagi dan adalah lebih praktikal
untuk mengdekod mesej seberapa yang mungkin (oleh komputer bukan oleh
manusia).
Secara am, kesan gangguan dalam saluran komunikasi akan mengakibatkan ralat
yang menyebabkan mesej yang diterima berlainan daripada apa yang dikirim. Oleh
demikian, dalam contoh Mariner6 di atas, kita dapat lihat situasi di mana 43 yang
ditransmisikan oleh kapal angkasa diterima dan diterjemahkan sebagai 11 di Bumi.
3.2 Kod Pembetulan Kesilapan
Kod pembetulan kesilapan (ralat) menangani masalah ralat dengan menggunakan
konsep lebihan (redundancy) menggunakan lebih banyak simbol yang diperlukan
untuk mesej.
Dalam bahasa biasa, lebihan kerap berlaku, di mana pengetahuan bahasa dan
konteks ianya digunakan membantu kita mengenal pasti ralat tipografikal (ejaan)
dan membetulkannya apabila dibaca.
Misalnya, jika perkataan cetakan dikirim, ia mungkin diterima sebagai cetekan atau
cetakau. Dalam konteks topik ini, memang dapat dikenal pasti dengan mudah yang
ralat tipografikal (ejaan) telah berlaku dan perkataan yang betul diteka dengan tepat
sebagai cetakan.
Misi Mariner6 telah menggunakan 6 digit binari untuk mengenkod setiap petak kecil
(piksel) dalam gambar Marikh. Apabila mengirim isyarat balik ke Bumi, Mariner6
mengirim 32 digit dengan 26 (=32-6) digit lebihan. Yang lebih mengkagumkan ialah
terjemahan betul bagi setiap rantaian yang mengandungi kurang daripada 8 ralat.
-
32 MODUL MTE3114 APLIKASI MATEMATIK
32
Jadi:
Setiap rantaian mengandungi enam 0 dan 1 rantaian tiga puluh dua 0
dan 1
rantaian dengan < 8 ralat didekodkan dengan betul
Bagaimanakah ini boleh berlaku?
Proses mengenkod mesej bermula dengan penukaran teks biasa kepada satu
rantaian nombor dengan menggunakan abjad digital berikut. Dalam kod ini, setiap
huruf (dan juga tanda isyarat) diwakili oleh urutan 0 dan 1 sepanjang 5-digit. Oleh
yang demikian, urutan-urutan tersebut merupakan nombor antara 0 dan 32 yang
ditulis dalam sistem binari (asas 2).
Dalam kest Mariner6, satu kod Reed-Muller yang kuat telah digunakan untuk
pembetulan kesilapan. Seperti yang dinyatakan, mesej 6 digit binari telah ditukar
kepada mesej 32 digit binari yang digelar sebagai katakod (codewords).
Misalnya, mesej yang dikirim mengandungi 3 digit binari. Oleh yang demikian,
terdapat 8 mesej yang mungkin, yang boleh diwakili oleh integer 0 hingga 7.
Dalam contoh ini, 5 digit lebihan akan ditambah kepada setiap mesej untuk
menghasilkan katakod yang panjangnya 8.
-
33 MODUL MTE3114 APLIKASI MATEMATIK
33
0 = 000 000 00000
1 = 001 001 10110
2 = 010 010 10101
3 = 011 011 00011
4 = 100 100 10011
5 = 101 101 00101
6 = 110 110 00110
7 = 111 111 10000
Katakod 00110110 mewakili integer 1. Jika dibandingkan dengan katakod 00000000
yang mewakili integer 0, mudah dilihat bahawa kedua-dua katakod ini berbeza di
empat tempat (ketiga, keempat, keenam dan ketujuh). Dengan cara yang sama, jika
dibandingkan 0110110 dengan katakod 01010101, dapat dilihat sekali lagi bahawa
kedua-dua katakod ini berbeza di empat tempat kali ini di tempat kedua, ketiga,
ketujuh dan kelapan.
Perhatikan yang hanya ada 8 mesej, iaitu 8 katakod daripada 28 = 256 rantaian
lapan digit binari yang mungkin. Hal ini akan dapat membantu pengesanan ralat
tetapi juga pembetulan ralat yang tunggal.
Jika 00111110 diterima, memang mudah untuk menyemak bahawa ini bukan katakod
dan ralat telah berlaku biasanya tidak pasti hanya satu ralat berlaku tetapi yang
pasti adalah sekurang-kurangnya satu ralat telah berlaku.
Sungguh pun sukar untuk mengetahui mesej asal, prinsip kemungkinan maksimum
(principle of maximum likelihood) boleh digunakan untuk mengdekod mesej yang
diterima. Ini boleh dilakukan dengan membandingkan mesej yang diterima dengan 8
katakod dan lihat yang mana satu katakod paling rapat dengan mesej yang diterima.
Apabila ini dilakukan, dapat dilihat yang katakod yang paling rapat dengan 00111110
ialah 00110110. Ia hanya berbeza di satu tempat tempat kelima (yang digariskan).
Oleh sebab setiap katakod berbeza daripada yang laing dalam tepat empat tempat,
mesej yang diterima 00111110 akan berbeza daripada yang lain dalam sekurang-
kurangnya tiga tempat.
-
34 MODUL MTE3114 APLIKASI MATEMATIK
34
Jadi, dapat diandaikan yang ralat jarang-jarang berlaku, jadi katakod yang mungkin
ditransmisikan ialah 00110110. Dalam kes ini, selagi ada satu ralat (dan ini adalah
kes yang paling mungkin) ianya dapat diperbetulkan.
Ini memang benar untuk semua kes di mana satu ralat berlaku jadi ia digelarkan
sebagai kode pembetulan ralat tunggal (single-error-correcting code).
Dalam contoh ini,
8 digit katakod
3 digit maklumat dan
5 digit lebihan.
Kadar maklumat = 8
3
Secara am,
n digit
}
} }
k digit mesej r digit semakan (lebihan)
Kadar maklumat, R = n
k.
Bagi Mariner 6, kadar maklumat R =32
6.
-
35 MODUL MTE3114 APLIKASI MATEMATIK
35
3.3 Kod Ulangan
Satu cara yang mudah untuk memperkenalkan lebihan adalah untuk mengulang semua. Jadi, jika ada mesej, ia boleh dikodkan dengan mengulang setiap digit n kali. Jika n = 5, panjang kod ulangan ialah 5.
Contoh :
S 10011 11111 00000 00000 11111 11111
U 10101 11111 00000 11111 00000 11111
S 10011 11111 00000 00000 11111 11111
I 01001 00000 11111 00000 00000 11111
E 00101 00000 00000 11111 00000 11111
Jika dikirim S = 10011 as 11111 00000 00000 11111 11111, ia akan diterima
sebagai urutan ) dan 1 yang panjangnya 25.
Kita perlu peraturan (algoritma) untuk mengdekod mesej yang diterima.
Dengan bantuan komputer mengdekod mesej, tekaan mengikut konteks tidak
dilakukan tetapi peraturan yang tepat perlu digunakan.
Misalnya, apabila mesej berikut di terima:
11011 00110 11000 10000 10111 bagaimanakah ianya didekod ?\
Algoritma Dekod bagi Kod Ulangan Panjang 5
1. Bilang digit 1.
2. Jika bilangan digit 1 3 , tulis 11111.
3. Jika bilangan digit 1 2 , tulis 00000.
Perhatikan bahawa kod ini boleh membetulkan 2 ralat tetapi ia mempunyai kad
maklumat yang sangat rendah 5
1.
Jika n = 4 (setiap digit diulang 4 kali),apakah yang berlaku jika terima 0011 ?
-
36 MODUL MTE3114 APLIKASI MATEMATIK
36
Saluran Simetri Binari
Kebarangkalian menerima simbol yang silap adalah serupa sama ada simbol 0 atau
simbol 1 dikirim.
Kebarangkalian menerima simbol yang silap = p
Misalnya, jika p = 100
1 , jadi kebarangkalian satu digit tunggal diterima secara silap
ialah 100
1 = 0.01, jadi kebarangkalian satu digit tunggal diterima secara betul ialah
100
99 = 0.99.
Dianggap semual ralat berlaku secara rawak iaitu secara tidak bersandar satu
sama lain.
Untuk memudahkan pengiraan, kod ulangan panjang 3 digunakan.
Bolehkah kebarangkalian 100
99 = 0.99 diperbaiki jika satu katakod satu digit
diterima?
Mesej dikirim
Mesej
dikodkan
Mesej mungkin diterima
Mesej didekod
0 000 000 001
010 100 0
1 111 101 011
110 111 1
-
37 MODUL MTE3114 APLIKASI MATEMATIK
37
Jika 000 dikirim,
Pengiraan kebarangkalian mesej yang mungkin diterima:
Pr (000) = 100
99 x
100
99 x
100
99 = 0.970299
Pr (001) = 100
99 x
100
99 x
100
1 = 0.009801
Pr (010) = 100
99 x
100
1 x
100
99 = 0.009801
Pr (100) = 100
1 x
100
99 x
100
99 = 0.009801
Jadi kebarangkalian mengdekod mesej sebagai 0:
Pr (0) = Pr (000) + Pr (001) + Pr (010) + Pr (100)
= 0.970299 + 3 x 0.009801
= 0.999702 .
Jadi, secara purata, kesilapan mengdekod mesej yang dikirim 0 sebagai 1 berlaku
hanya sekali setiap 100 kali, kita akan dapat ralat kurang daripada 3 setiap 10 000
(atau 1/3000) ! Ini merupak kemajuan yang hebat.
Bagi kod ulangan panjang n,
n digit
}
} }
1 digit Mesej
n 1 digit semakan
Kadar maklumat, R = n
1. Ini sangat kecil!
Kod ulangan dapat membetulkan ralat tetapi kadar maklumatnya sangat rendah!
-
38 MODUL MTE3114 APLIKASI MATEMATIK
38
Latihan
1. Anda telah menerima mesej berikut yang ditulis dengan kod ulangan
panjang 5.
00000 10010 11011 11000 01111
11110 01010 01000 01011 00001
00111 10000 01100 11100 00000
01000 11111 00111 10111 11101
01111 00010 01000 10111 10000
a) Tukar mesej ini kepada kod 5 digit binari.
b) Tukarkan kepada abjad biasa.
2. Anda telah menerima mesej berikut yang ditulis dengan kod ulangan
panjang 5.
00000 11011 01111 00100 11111
01000 11111 00100 00001 11101
11101 00100 00000 11110 01111
11111 10000 01000 00000 00100
10111 00010 10000 00111 01100
01100 10001 01010 00011 11001
01010 10111 01111 11111 00000
11111 00010 11011 01000 00000
a) Tukar mesej ini kepada kod 5 digit binari.
b) Tukarkan kepada abjad biasa.
c) Apakah mesej yang sebenar?
3. Kod ulangan panjang 3 digunakan untuk transmisi mesej. Jika kebarangkalian
membuat kesilapan dalam satu digit ialah 0.01 dan kita anggap kesilapan
berlaku secara tak bersandar satu sama lain, kirakan kebarangkalian mesej
000 yang dikirim diterima sebagai 111.
-
39 MODUL MTE3114 APLIKASI MATEMATIK
39
3.4 Kod Semakan Pariti
Kod semakan pariti tunggal merupakan ekstrem daripada kod ulangan. Berbanding
dengan kod ulangan, kod semakan pariti tunggal hanya ada satu digit semakan.
Digit semakan ini diperolehi daripada jumlah digit maklumat (mod 2).
Sebagai contoh, lihat bagaimana digit semakan dikira
A
000001 1
}
5 digit
maklumat
1 digit
semakan
B
000010 1
C
000011 0
D
000100 1
Secara am katakod ditulis sebagai c1 c2 c3 c4 c5 c6 di mana
c6 = c1 + c2 + c3 + c4 + c5 (mod 2).
Bagi kod semakan pariti tunggal,
n digit
} -- - -
}
k = n 1 digit mesej
1 digit semakan
Kadar maklumat n
k =
n
n 1 , amat tinggi!
Akan tetapi, kod semakan pariti tunggal hanya boleh mengesan bilangan ralat yang
ganjil tetapi tidak dapat membetulkannya.
-
40 MODUL MTE3114 APLIKASI MATEMATIK
40
Latihan
1. Cari katakod yang mewakili huruf berikut dalam kod semakan
pariti tunggal di atas : J , L , Q , S , G , X.
2. Tulis mesej NO ERRORS dengan kod semakan pariti tunggal.
3. Mesej berikut telah diterima dalam kod semakan pariti tunggal:
000011 000000 001111 011110 010110 001001
000000 100100 001010 100111 101001 011000 101000
a) Kesan di mana ralat telah berlaku.
b) Dekod semua huruf yang lain.
c) Cuba teka mesej yang dikirim.
-
41 MODUL MTE3114 APLIKASI MATEMATIK
41
3.5 Kod Linear Perhatikan kod linear panjang 6 berikut ada 3 digit mesej dan 3 digit semakan
Katakod panjang 6
} c1 c2 c3 c4 c5 c6
} } 3 digit mesej
3 digit semakan
boleh ditulis semula sebagai persamaan linear untuk mentakrifkan digit-digit
semakan.
Bila diberi mesej c1 c2 c3 ,
c4 = c1 + c2 (mod 2)
c5 = c1 + c3 (mod 2)
c6 = c2 + c3 (mod 2)
untuk memperolehi katakod C= [c1 c2 c3 c4 c5 c6].
=>
6
5
4
c
c
c
=
110
101
011
3
2
1
c
c
c
.
Sebagai contoh, 010 akan ditransmisikan sebagai [010101].
Latihan
Tuliskan katakod yang sepadan dengan mesej:
(i) 111 (ii) 101
(a) Berapakah mesej tiga digit yang dibentukkan?
(b) Senaraikan semua katakod bagi kod ini.
-
42 MODUL MTE3114 APLIKASI MATEMATIK
42
Persamaan Semakan Pariti
Katakod C = [c1 c2 c3 c4 c5 c6 ] menyempurnakan persamaan semakan pariti
c1 + c2 + c4 = 0 (mod 2)
c1 + c3 + c5 = 0 (mod 2)
c2 + c3 + c6 = 0 (mod 2).
Persamaan-persamaan ini dinamakan sebagai persamaan semakan pariti sebab
menyemak pariti atau kegenapan hasil tambah digit-digit dalam katakod untuk
memperolehi 0 di sebelah kanan, kita perlu dapat bilangan 1 yang genap pada
sebelah kiri setiap persamaan.
Persamaan semakan pariti juga boleh ditulis sebagai
100110
010101
001011
6
5
4
3
2
1
c
c
c
c
c
c
=
0
0
0
,
atau H CT = 0 ,
di mana H ialah matriks semakan pariti.
[CT = transpos menegak bagi vektor C ]
Apakah yang berlaku semasa transmisi katakod?
Apabila katakod C = [c1 c2 c3 c4 c5 c6] dikirim
saluran transmisi akan menambah gangguan (ralat)
E = [e1 e2 e3 e4 e5 e6]
mengakibatkan katakod diterima sebagai
R = [r1 r2 r3 r4 r5 r6]
di mana ri = ci + ei (mod 2) .
-
43 MODUL MTE3114 APLIKASI MATEMATIK
43
Latihan
1. Jika C = [100110] , E = [000101], cari R.
2. Jika R = [001000], E = [000011], cari C.
3. Jika R = [010000], C = [111000], cari E.
Biasanya, kita hanya tahu katakod yang diterima, R. Jadi masalah adalah untuk
mengetahui katakod yang dikirim C jika kita terima katakod R. Ini boleh dilakukan
dengan mencari E dahulu.
-
44 MODUL MTE3114 APLIKASI MATEMATIK
44
Mengira Sindrom
Bagi katakod yang diterima, R = [r1 r2 r3 r4 r5 r6], kita mentakrifkan sindrom, s = [s1
s2 s3] bagi R dengan
s1 = r1 + r2 + r4 (mod 2)
s2 = r1 + r3 + r5 (mod 2)
s3 = r2 + r3 + r6 (mod 2).
3
2
1
s
s
s
=
100110
010101
001011
6
5
4
3
2
1
r
r
r
r
r
r
atau
sT = H RT.
Oleh kerana digit-digit sindrom ditakrifkan oleh persamaan semakan pariti yang sama
dengan katakod, digit sindrom akan mendedahkan pola kegagalan semakan pariti.
s dinamakan sebagai sindrom R sebab ia mempamerkan simptom khas ralat
tanpa mengenal pasti sebabnya, seperti cara kita mengenal sesuatu penyakit
daripada simptomnya dan bukan sindrom (sebabnya yang sebenar) contoh SIDS
= Sudden Infant Death Syndrome.
Semua katakod mempunyai sindrom 0 = [000] sebab H CT = 0 .
Sindrom katakod yang diterima serupa dengan sindrom ralat.
Katakod yand diterima R merupakan hasil tambah katakod C dan ralat E.
R = C + E.
Jadi C = R E dan
0 = H CT = H (R E)T
= H (R T E T)
= H R T H E T
Oleh itu sT = H RT = H E T.
Jadi katakod yang diterima R mempunyai sindrom yang sama dengan ralat E.
-
45 MODUL MTE3114 APLIKASI MATEMATIK
45
Maklumat ini sangat berguna sebab ini bermakna jika R merupakan katakod yang
diterima, set ralat yang mungkin juga merupakan set vektor yang sama dengan
sindrom R.
Dari atas, jika R dan E mempunyai sindrom yang sama, kita boleh guna akas
penghujahan untuk menunjukkan bahawa jika H RT = H E T , jadi R E = C , di
mana C adalah katakod.
Bilangan perkataan dengan sindrom yang sama serupa dengan bilangan katakod.
Dalam kes ini ada 23 = 8 sindrom yang mungkin dan setiap selaras tepat dengan
88
64
8
2 6 perkataan.
Oleh itu, sebagai contoh, 8 katakod selaras tepat dengan 8 perkataan dengan
sindrom[000].
Mencari perkataan selaras dengan sindrom yang diberi
Sebab sindrom katakod yang diterima R sama dengan sindrom ralat E, satu perkara
yan perlu dilakukan untuk dekod katakod yang diterima adalah untuk mencari semua
perkataan yang mempunyai sindrom yang sama dengan R.
Misalnya, kita akan mencari semua perkataan dengan sindrom [001] bila kita
menggunakan kod linear yang ditakrifkan. Oleh itu,
r1 + r2 + r4 = 0 (mod 2)
r1 + r3 + r5 = 0 (mod 2)
r2 + r3 + r6 = 1 (mod 2).
100110
010101
001011
6
5
4
3
2
1
r
r
r
r
r
r
=
1
0
0
,
-
46 MODUL MTE3114 APLIKASI MATEMATIK
46
atau H RT =
1
0
0
= sT.
Dengan cara yang sama, kita akan dapat mencari semua perkataan yang selaras
dengan sindrom [001] dengan cara menyenaraikan semua 8 pilihan yang mungkin
bagi 0 dan 1 bagi ketiga-tiga pembolehubah yang pertama dan mencari nilai baki
tiga pembolehubah tersebut. Misalnya, jika kita mula dengan r1 = 0, r2 = 0, r3 = 0,
kita dapat lihat daripada persamaan ini, kita dapatkan tiga persamaan di mana r4 =
0, r5 = 0, r6 = 1.
Jadi salah satu daripada 8 perkataan yang selaras dengan sindrom [001] ialah
[000001].
Kita boleh memperolehi semua 8 perkataan dengan cara yang sama.Misalnya, jika
r1 = 0, r2 = 0, r3 = 1, kita dapat r4 = 0, r5 = 1, r6 = 0, yang membentuk perkataan
[001010].
Latihan
1. Cari 6 perkataan lagi yang selaras dengan sindrom [001].
2. Senaraikan semua perkataan dengan sindrom
a) [010].
b) [111].
Tatasusunan Piawai Slepian menyenaraikan semua perkataan yang selaras dengan
setiap sindrom bagi kod linear.
-
47 MODUL MTE3114 APLIKASI MATEMATIK
47
Set perkataan { [r1 r2 r3 r4 r5 r6] di mana ri = 0 atau 1, bagi i = 1, 2, , 6} membentuk ruang vektor dimensi 6 di atas Medan Galois GF(2).
Sebab semua katakod merupakan penyelesaian bagi H CT = 0, semua katakod
membentuk subruang bagi ruang vektor yang mengandungi semua perkataan.
Dimensi sub ruang ini ialah 6 3 = 3.
Khasnya, ini bermakna set katakod akan membentuk kumpulan di bawah penambahan(mod 2) dan juga hasil tambah mana-mana dua katakod merupakan satu katakod.
Latihan Berkumpulan
1. Semak bahawa hasil tambah mana-mana dua katakod merupakan katakod.
2. Pilih sindrom yang tidak sama dengan [000] pastikan semua ahli dalam
kumpulan anda memilih sindrom yang berlainan.
a) Pilih satu katakod dan tambah kepadanya setiap daripada perkataan dalam baris yang selaras dengan sindrom pilihan anda. Apakah yang anda dapati ? What do you find?
b) Dengan menggunakan sindrom yang sama, pilih katakod yang berlainan dan ulang (a).
c) Dengan menggunakan sindrom yang sama, semak yang setiap perkataan yang selaras dengan sindrom dlam Tatasusunan Piawai Slepian boleh diperolehi sebagai hasil tambah perkataan pertama dalam baris (pemimpin koset) dan katakod dalam lajur yang sama.
d) Banding jawapan a), b) dan c) dengan ahli kumpulan lain.
Dalam Tatasusunan Piawai Slepian, semua katakod disenaraikan sebagai baris pertama bermula dengan katakod [000000].
Setiap baris berikut dalam tatasusunan mengandungi satu koset katakod. Dalam setiap koset, perkataan disusun dalam setiap baris di mana perkataan pertama dalam setiap baris mempunyai bilangan 1 yang paling kurang. Perkataan pertama dalam setiap baris Tatasusunan Piawai Slepian dinamakan pemimpin koset.
Dalam baris pertama, selaras dengan sindrom [000], perkataan dalam baris tiada 1; perkataan pertama dalam setiap daripada enam baris berikut mempunyai hanya satu 1 sahaja; manakala perkataan pertama dalam baris terakhir merupakan salah satu daripada tiga perkataan dalam baris tersebut yang ada tepat dua 1.
-
48 MODUL MTE3114 APLIKASI MATEMATIK
48
Berat sesuatu perkataan ditakrifkan sebagai bilangan 1 dalam perkataan tersebut.
Tatasusunan Piawai Slepian boleh dibina bagi kod linear dengan langkah-langkah berikut:
1. Dalam baris pertama, senaraikan semua katakod yang bermula dengan 0.
2. Pilih mana satu perkataan, W, yang berat minimum weight yang bukan katakod
(tidak disenaraikan pada baris pertama) dan senaraikannya sebagai unsur
pertama dalam baris berikut.
3. Bermula dengan W, senaraikan semua unsur koset W + C, di mana C adalah
katakod, dalam urutan yang sama seperti senarai katakod dalam baris pertama.
4. Ulangi langkah 2 dan 3 dengan menggunakan perkataan baru X, di mana X tiada
dalam dua baris yang pertama.
5. Ulangi langkah 4 dengan menggunakan perkataan baru yang tiada dalam baris- baris sebelumnya sehingga semua perkataan telah disenaraikan.
Pengdekodan Perkataan yang diterima R
R = [r1 r2 r3 r4 r5 r6] boleh didekodkan dengan langkah-langkah berikut:
1. Kirakan sindrom s = [s1 s2 s3] bagi R.
Ini merupakan sindrom bagi E.
2. Guna Tatasusunan Piawai Slepian untuk mencari perkataan dengan sindrom s
dengan bilangan 1 yang paling sedikit.
Pilih perkataan ini sebagai E.
3. Kirakan C di mana C = R E.
-
49 MODUL MTE3114 APLIKASI MATEMATIK
49
Latihan 1. Cari C jika R = [101110].
[ Nota: Apabila menggunakan tatasusunan ini, kita tidak perlu mengira sindrom. Sebab R dan E mempunyai sindrom yang sama, kita hanya cari R dalam sifir ini. E merupakan perkataan dalam baris yang mengandungi R. ]
2. Cari C jika (i) R = [111111], (ii) R = [111011], (iii) R = [110011]. 3. Bekerja secara berpasangan dan jalankan langkah-langkah berikut:
[1] Pilih katakod C untuk dikirim sebagai mesej. [2] Pilih ralat E. [3] Kirakan R = C + E dan kirimkan kepada pasangan anda. [4] Dekod perkataan pasangan anda. [5] Ulang ini sebanyak tiga kali: sekali pilih E yang berat 1 (hanya satu
1 dalam perkataan); sekali dengan E = 0; dan sekali dengan E yang berat 2 (dengan dua 1 dalam perkataan). Dalam kes yang manakah anda dapat mengenal pasti katakod?
Kod Linear secara Am
Satu kod merupakan kod linear atau kod kumpulan jika katakodnya merupakan set
vektor C yang memuaskan persamaan H CT = 0, di mana H adalah matriks semakan
pariti.
Dalam kod semakan pariti tunggal , digit-digit c1, c2, c3, c4, c5, c6 dalam katakod [c1
c2 c3 c4 c5 c6 ] memuaskan persamaan semakan pariti
c6 = c1 + c2 + c3 + c4 + c5 (mod 2),
yang serupa dengan
c1 + c2 + c3 + c4 + c5 + c6 = 0 (mod 2).
Ini ditulis sebagai H CT = 0, di mana H = [111111]. Kod ulangan panjang 5 juga boleh ditakrifkan dengan menggunakan persamaan semakan pariti berikut:
c1 + c2 = 0 (mod 2)
c1 + c3 = 0 (mod 2)
c1 + c4 = 0 (mod 2)
c1 + c5 = 0 (mod 2).
-
50 MODUL MTE3114 APLIKASI MATEMATIK
50
H CT = 0, di mana H =
10001
01001
00101
00011
.
Secara am, jika kod ulangan panjang n kita akan dapat matriks semakan pariti H
yang (n 1) x n
Kod blok merupakan kod di mana setiap katakod merupakan urutan bilangan tetap,
n, simbol. Bagi kes kod linear, panjang bloknya ialah bilangan lajur dalam H
Sindrom, s, katakod yang diterima R diberi sebagai sT = H RT. Koset terdiri daripada semua perkataan yang mempunyai sindrom tertentu. Berat perkataan merujuk kepada bilangan 1 dalam perkataan tersebut.
Dalam satu koset, perkataan yang mempunyai berat yang minimum dipilih sebagaai
pemimpin koset (coset leader).
Untuk mengdekod R:
1. Kirakan sindrom s;
2. Cari pemimpin koset E; dan
3. Kirakan C = R E.
3.6 Kod Hamming
Teori kod pembetulan ralat telah bermula dengan usaha Richard Hamming dalam
1947. Sebagai seorang ahli matematik, Hamming dapat menggunakan kemudahan
komputer di Bell Telephone Laboratories untuk menjalankan pengiraan matematik.
Ketika itu, masa untuk melaksanakan program sangat lama dan apabila Hamming
datang bekerja pada hujung minggu beliau kerap menemui situasi di mana program
pengiraan terhenti kerana menemui ralat. Oleh yang demikian, Hamming memikirkan
tentang kebolehan komputer bukan sahaja untuk mengesan ralat tetapi
membetulkannya!
Pada 1950 Richard Hamming telah memperkembangkan kod Hamming yang
merupakan kod linear yang dapat membetulkan ralat tunggal.
-
51 MODUL MTE3114 APLIKASI MATEMATIK
51
H =
100110
010101
001011
sT = H RT = H ET.
Jika ralat E = [e1 e2 e3 e4 e5 e6], persamaan boleh ditulis semula sebagai
3
2
1
s
s
s
= e1
0
1
1
+ e2
1
0
1
+ e3
1
1
0
+ e4
0
0
1
+ e5
0
1
0
+ e6
1
0
0
.
Sindrom ialah hasil tambah lajur-lajur H di mana ralat-ralat saluran berlaku.
Oleh yang demikian, jika mana:
satu lajur H adalah 0 , ralat pada kedudukan tersebut tidak dapat dikesan;
dan
dua lajur H serupa, kita tidak dapat membezakan ralat tunggal yang berlaku
pada kedua-dua kedudukan tersebut
Kod linear hanya dapat membetulkan semua pola ralat tunggal jika lajur-lajur H
berbeza dan bukan sifar
Sebaliknya, jika semua lajur H berbeza dan bukan sifar, ralat tunggal pada
kedudukan berbeza akan menghasilkan sindrom yang berbeza.
Kod binari linear mampu membetulkan semua pola yang tiada lebih daripada satu
ralat saluran jika dan hanya semua lajur dalam matriks semakan pariti H berbeza
dan bukan sifar.
Pengedekodan Perkataan
Untuk mengdekodkan perkataan yang diterima R, sindrom s dikira.
Jika s ialah sifar, andaikan tiada ralat.
Jika s bukan sifar dan sama dengan salah satu lajur dalam H, andaikan ralat tunggal
telah berlaku pada kedudukan tersebut.
-
52 MODUL MTE3114 APLIKASI MATEMATIK
52
Jika s bukan sifar dan tidak sama dengan mana satu lajur dalam H , prosedur
pengdekodan ini gagal.
Kegagalan pengdekodan dan ralat hanya berlaku jika dua atau lebih ralat saluran
berlaku.
Misalnya, jika H =
101000111
011001110
101011100
011111000
.
Jika diterima perkataan R = [101000101], jadi kita dapat mengira s = [1100].
Sebab sT merupakan lajur kelima dalam H , kita andaikan E = [000010000].
Oleh itu C = R E = [101010101].
Walau bagaimana pun jika R = [101000101], kita perolehi s = [1101], dan dalam kes
ini di mana sT bukan salah satu lajur dalam H , ini bermakna terdapat 2 ralat dan prosedur pengdekodan gagal.
Latihan
Bagi matriks semakan pariti H di atas, cuba dekodkan perkataan-perkataan berikut yang diterima:
(i) R = [101001101] (ii) R = [111000101] (iii) R = [101000111]
Bagi kod pembetulan ralat tunggal, bilangan maksimum lajur bukan sifar matriks
binari yang berbeza dan bukan sifar 2r 1.
-
53 MODUL MTE3114 APLIKASI MATEMATIK
53
Kod Hamming
Lajur-lajur dalam matriks semakan pariti H , Kod Hamming terdiri daripada 2r 1
lajur bukan sifar r tuple (non-zero binary r-tuples ) yang tersusun dalam mana-mana
satu urutan.
Jika A merupakan matriks m n dengan pangkat r, dimensi ruang nol A adalah n r.
Sebab H mengandungi semua lajur bukan sifar yang mungkin, ia mengandungi
setiap satu daripada lajur-lajur matriks identiti r x r dan mempunyai pangkat r.
Jadi H merupakan matriks r x n dengan pangkat r dan dimensi subruang yang
memenuhi syarat H CT = 0 iaitu n r = k.
Oleh itu, bilangan digit mesej = k = n r = 2r 1 r.
Bagi setiap integer positif, wujud Kod Hamming dengan digit semakan r, panjang
blok n= 2r 1 dan k = n r = 2
r 1 r.
Kod ini boleh membetulkan ralat tunggal pada mana-mana satu digit. Sebab setiap
r-tuple bukan sifar wujud sebagai lajur, kegagalan pengdekodan tidak akan berlaku.
Jadi prosedur pengdekodan ralat tunggal lengkap.
Walau bagaimana pun kod ini tidak dapat mengesan lebih daripada 2 ralat.
Kadangkala digit semakan pariti yang lain akan ditambah untuk mengesan (tetapi
tidak dapat membetulkan ) 2 ralat.Lajur-lajur dalam matriks semakan pariti H boleh
disusun dalam mana-mana satu urutan.
Kadar maklumat Kod Hamming
R = n
k =
12
12r
r
r = 1
12r
r.
Bila r , R1.
Dengan membina Kod Hamming yang mempunyai panjang blok yang besar, kita
akan dapat kadar maklumat yang sangat tinggi. Sungguh pun Kod Hamming
merupakan perkembangan hebat berbanding dengan kod semakan pariti tunggal,
kod ini tidak dapat membetulkan lebih daripada dua ralat.
Sekitar 1960, Bose, Changhuri and Hocquenghan telah menemui kod pembetulan
dwi-ralat Kod BCH (double-error-correcting codes) yang lebih kompleks.
Seterusnya, kod-kod ini diperkembangkan sehingga menjadi kod pembetulan t
ralat.
-
54 MODUL MTE3114 APLIKASI MATEMATIK
54
Latihan
1.(a) Yang mana satu daripada matriks semakan pariti ini merupakan kod
pembetulan ralat tunggal? Beri sebab jawapan anda.
(i) H =
0111011100
0001000101
1100110011
1010101010
(ii) H =
110110000
000110110
000011011
011011000
(b) Yang mana satu daripada kedua matriks di atas merupakan Kod Hamming ? Beri sebab mengapa atau mengapa tidak.
2. Guna matriks (ii) daripada soalan 1 di atas untuk mengdekod setiap
daripada perkataan yang diterima berikut:
(a) R = [111101000] (b) R = [110101011]
(c) R = [100010001] (d) R = [010010010].
3. Pertimbangkan Kod-Kod Hamming yang ditakrifkan oleh tiga matriks
semakan pariti di bawah.
(i) H =
1010101
1100110
1111000
(ii) H =
1001011
0101101
0011110
-
55 MODUL MTE3114 APLIKASI MATEMATIK
55
(iii) H =
1010101
0110011
0001111
(a) Bagi setiap kod, dekodkan perkataan-perkataan berikut yang diterima:
R1 = [1110000] , R2 = [1111000] .
(b) Tunjukkan yang dua daripada tiga matriks di atas mentakrifkan kod-kod yang
serupa (identical codes). Panduan: Tunjukkan bahawa baris-baris mana satu
merupakan kombinasi linear yang lain.
3.7 Algoritma RSA Masalah Penyebaran Kunci (Key-Distribution Problem)
Dalam sistem tradisional, kunci yang diguna oleh si-pengirim untuk mengenkod mesej diguna juga oleh si-penerima untuk mengdekodnya. Oleh yang demikian, kunci tunggal ini mesti dijaga dengan baik dan dirahsiakan agar hanya dapat digunakan oleh pihak tertentu.
Dalam masyarakat moden, masih ada jumlah data yang banyak yang perlu dirahsiakan dan ini mengakibatkan keperluan penggunaan kunci bagi pengguna-pengguna kod.
Masalah penyebaran kunci ini diterangkan oleh Simon Singh dalam bukunya The Codebook (2002) seperti berikut:
a classic catch-22 situation. If two people want to exchange a secret message over
the phone, the sender must encrypt it. To encrypt the secret message the sender must
use a key, which is itself secret, so then there is the problem of transmitting the secret
key to the receiver in order to transmit the secret message. In short, before two
people can exchange a secret (an encrypted message) they must already share a
secret (the key). (pp. 189190)
Pada pertengahan tahun 70-an, Whitfield Diffie, Martin Helman dan Ralph
Merkle telah mencadangkan penggunaan cipher asimetrik (asymmetric cipher)
untuk mengatasi masalah penyebaran kunci. Mereka mencadangkan
penggunaan kunci berlainan untuk mengenkod dan mengdekod mesej.
-
56 MODUL MTE3114 APLIKASI MATEMATIK
56
Peranan Pemfaktoran
Aktiviti: Faktorkan 518 940 557
Darabkan 15 107 dengan 34 351
Aktiviti di atas menunjukkan betapa sukarnya untuk mencari faktor-faktor
hasildarab dua nombor perdana. Oleh yang demikian, konsep ini diguna untuk
menjanakan sistem pengkodan yang baru yang dinamakan sebagai Kriptografi
Kunci Umum (Public Key Cryptography).
Dalam kriptografi kunci umum, kunci untuk mengdekod mesej tidak dapat
diperolehi dengan mudah daripada kunci yang diguna untuk mengenkodnya. Ini
membolehkan pengiriman mesej secara elektronik secara selamat ke destinasi
di mana kunci umum boleh dihebahkan secara umum.
Penggunaan Aritmetik Modular
Aritmetik modular digunakan dalam banyak kriptosistem untuk menyamarkan
maklumat dengan mudah kerana fungsinya yang agak mengelirukan.
Jadual berikut menunjukkan bagaimana nilai P dapat dirahsiakan melalui
pengiraan C = P3 dalam modulo 11.
P 0 1 2 3 4 5 6 7 8 9 10
C = P3 0 1 8 27 64 125 216 343 512 729 1000
C = P3 modulo 11 0 1 8 5 9 4 7 2 6 3 10
Aritmetik modular juga dikenali sebagai aritmetik jam diperkenalkan oleh K.F.Gauss (1777-1855). Bagi sebarang nombor asli n, aritmetik modulo n berasaskan kepada pembahagian set integer Z = {, 3,2, 1, 0, 1, 2, 3, } ke dalam n kelas yang berasingan yang selaras dengan n baki yang mungkin apabila dibahagi oleh n. Misalnya, jika n =2, baki yang mungkin jika integer dibahagi oleh 2 adalah 0 atau 1. Kelas integer dengan baki 0 merupakan set nombor genap = {..., 6, 4, 2, 0, 2, 4, 6, ...} manakala kelas integer dengan baki 1 merupakan set nombor ganjil = {..., 5, 3, 1, 1, 3, 5, 7, ...}. Secara umum, semua integer dalam kelas yang sama mempunyai baki yang sama apabila terbahagi oleh modulus. Ini bermakna terdapat perbezaan antara dua integer dalam kelas yang sama juga merupakan gandaan modulus.
-
57 MODUL MTE3114 APLIKASI MATEMATIK
57
Jadi, dalam contoh di atas, apabila kita memerhatikan perbezaan antara dua nombor genap kita akan memperolehi gandaan 2 (8 2 = 6 = 3x2) dan apabila kita lihat perbezaan antara dua nombor ganjil kita juga akan mendapat gandaan 2 ( 7 ( 1) = 8 = 4x2).
Sifat Kongruen Modulo Dua integer a dan b dikatakan sebagai kongruen modulo jika a b merupakan gandaan n dan ini ditulis sebagai
a b (mod n) .
Oleh yang demikian, semua nombor genap 0 (mod 2) dan semua nombor ganjil
1 (mod 2).
Dengan perkataan lain, kita boleh mewakili setiap nombor genap (mod 2) dengan
integer 0 dan setiap nombor ganjil (mod 2) dengan 1.
Aktiviti
1. (a) Apakah baki yang mungkin bila integer dibahagi dengan 3?
(b) Bagi setiap integer berikut, tulis baki yang diperolehi selepas dibahagi
dengan 3:
(i) 7; (ii) 301; (iii) 963; (iv) 31; (v) 5; (vi) 1.
(c) Pasangan integer yang manakah yang kongruen mod 3?
2. Bekerja secara berkumpulan.
(a) Pilih mana-mana dua integer a dan b pastikan semua orang menggunakan
pasangan integer yang berbeza.
Cari integer bukan negatif terkecil a dan b di mana
a a (mod 7) dan b b (mod 7).
(b) Kirakan nilai, dengan bantuan kalkulator saintifik jika perlu:
(i) ab ; (ii) ab (mod 7) ; (iii) ab ; (iv) ab (mod 7) .
(c) Berdasarkan pengiraan kumpulan anda, apakah kesimpulan yang anda
dapati tentang apa yang berlaku dengan hasil darab aritmetik modulo?
-
58 MODUL MTE3114 APLIKASI MATEMATIK
58
Jika a a (mod n) dan b b (mod n), maka ab a b (mod n).
Contoh:
Cari X = 36 * 53 * 91 * 17 * 22 (mod 29).
Penyelesaian :
36 7 (mod 29), 53 24 (mod 29), 91 4 (mod 29), 17 17 (mod 29), dan 22 22 (mod 29).
Ini boleh ditulis semula sebagai
X = 36 * 53 * 91 * 17 * 22 (mod 29)
= 7 * 24 * 4 * 17 * 22 (mod 29)
= 168 * 68 * 22 (mod 29)
= 23 * 10 * 22 (mod 29)
= 230 * 22 (mod 29)
= 27 * 22 (mod 29)
= 594 (mod 29)
= 14.
Semak 36 * 53 * 91 * 17 * 22 = 64 936 872 dan 64 936 872 (mod 29) = 14.
[Nota: Kalkulator saintifik komputer anda juga boleh melakukan pengiraan aritmetik modulo.] Aktiviti
Cari X = 73 * 29 * 102 * 14 * 87 (mod 31) dan semak jawapan anda.
Contoh pengiraan aritmetik modulo secara berperingkat-peringkat:
Cari X = 1143 (mod 13).
Perhatikan bahawa 112 (mod 13) = 121(mod 13) = 4.
Jadi 114 (mod 13) = 42 (mod 13) = 16 (mod 13) = 3.
118 (mod 13) = 32 (mod 13) = 9 (mod 13) = 9, dan
1116 (mod 13) = 92 (mod 13) = 81 (mod 13) = 3.
1132 (mod 13) = 32 (mod 13) = 9 (mod 13) = 9.
Tidak perlu cari kuasa yang lebih tinggi bagi 11 sebab 1164 > 1143.
Perhatikan yang 1143 = 1132 * 1111 = 1132 * 118* 113 = 1132 * 118* 112 * 11.
Oleh itu 1143 (mod 13) = 1132 * 118* 112 * 11 (mod 13) = 9 * 9 * 4 * 11 (mod 13)
= 81 * 44 (mod 13) = 81 * 44 (mod 13) = 3 * 5 (mod 13)
= 15 (mod 13) = 2.
-
59 MODUL MTE3114 APLIKASI MATEMATIK
59
Teorem Kecil Fermat Fungsi Euler bagi integer m ditakrifkan sebagai bilangan integer positif yang kurang atau sama dengan m dan perdana relatif (relatively prime) kepada m.
Aktiviti
Cari (n) bagi n = 1, 2, 3, , 20.
Semak bahawa n = p x q bagi nombor-nombor perdana p dan q,
dan (n) = (p 1) (q 1)
Teorem Kecil Fermat menyatakan bahawa bagi setiap integer yang perdana relatif kepada n,
a(n) 1(mod n).
Aktiviti
Bekerja secar berkumpulan, pilih satu nilai n antara 10 dan 20.
Cari (n)
Semak bahawa a(n) 1(mod n).
Sistem Rivest-Shamir-Adleman (RSA)
Salah satu kriptosistem kunci umum yang paling awal adalah sistem RSA yang
dicipta oleh Ted Rivest, Adi Shamir dan Leonard Adleman. Sistem RSA bergantung
kepada kesukaran memfaktorkan nombor yang besar dan penggunaan aritmetik
modular serta teori nombor.
Sistem RSA boleh diterangkan seperti berikut:
Menyediakan Sistem
Pilih dua nombor perdana yang besar, p dan q, di mana panjang setiap satu 100 digit. ( Nombor perdana ini dirahsiakan.) Biar n = p x q. (Nombor n dihebahkan secara umum tetapi pengetahuan n tidak memungkinkan anda menentukan nilai p dan q kerana kesukaran memfaktorkan nombor ini.)
Fungsi Euler function (n) = (p 1)(q 1) merupakan bilangan integer antara 1 dan n yang perdana relatif kepada n iaitu, bilangan nombor integer yang faktor sepunya dengan n adalah 1. Fungsi Euler (n) mempunyai ciri bagi sebarang integer a antara 0 dan n 1 di mana
a 1 + k.(n) = a mod n .
-
60 MODUL MTE3114 APLIKASI MATEMATIK
60
Pilih integer positif rawak E < (n) , di mana E perdana relatif kepada (n). (E, seperti n, diumumkan bersama n dan E menjadi kunci umum)
Sebab pihak yang menyediakan kod ketahui rahsia nombor perdana p dan q, mereka juga ketahui nilai (n) = (p 1)(q 1), tetapi nilai ini dirahsiakan daripada orang ramai. Jadi bagi pihak yang menyediakan kod, adalah mudah untuk mencari songsang E modulo (n) iaitu nombor D di mana
D.E 1 mod (n) ,
Iaitu nombor D yang memberi
D.E = 1 + k.(n) bagi sebarang integer k.
Nombor D ini juga dirahsiakan.
Secara ringkas,
Kunci rahsia: p, q, (n), D Kunci umum: n, E.
Enkripsi
Langkah pertama adalah untuk mewakili sebarang mesej sebagai urutan integer. Setiap mesej dipecahkan kepada beberapa blok digit, setiapnya merupakan nombor yang kurang daripada n. Setiap blok boleh dienkodkan secara berasingan.
Jika P adalah blok dalam mesej iaitu integer antara 0 dan n 1.
Sekarang biarkan C = P E mod n,
Iaitu, kita naikkan kuasa P ke kuasa E dan mencari bakinya selepas dibahagi dengan n.
Dengan cara demikian, C dienkripkan atau mesej berkod yang selaras dengan mesej asal P, dan C ialah mesej yang ditransmisikan dengan apa jua kaedah (mungkin kurang selamat) yang digunakan.
Dekripsi
Untuk mengdekodkan mesej C , kita cari P secara mengira
P = C D mod n.
Oleh kerana C = P E mod n, Kita akan dapat
C D mod n = P E.D mod n = P 1 + k.(n) mod n = P mod n , sebab 0 < P< n.
-
61 MODUL MTE3114 APLIKASI MATEMATIK
61
Keberkesanan Kod RSA
Semasa kod RSA diperkembangkan, adalah dijangka yang masa untuk memfaktorkan nombor 200 digit n = p x q akan mengambil masa sejuta tahun dengan bantuan algoritma komputer terpantas di dunia ketika itu. Kini, dengan komputer yang cepat dan canggih, kaedah pengkodan sebegini mungkin akan ditewaskan pada satu masa. Oleh yang demikian, sistem-sistem kriptografi yang baru sentiasa dicipta demi menampung keperluan keselamatan dan kerahsiaan ketika menyimpan data dan transmisi maklumat digital. Minat dalam penggunaan Kriptografi Kunci Umum telah memesatkan lagi penyelidikan dan perkembangan teknik pemfaktoran nombor dan teori nombor secara umum.
Contoh Pengiraan Algoritma RSA #1: Pilih nilai p dan q (nombor perdana) p= 7, q =11 => n = 7 x 11 = 77 #2: Cari nilai (n) =(p-1)(q-1) (n) = (7-1)(11-1) = 6 x 10 =60 #3: Pilih nilai e (nombor yg relatif perdana) e = 13 #4: Cari nilai d di mana d.e = 1 mod (n) - Kaedah Euler d. 13 = 1 mod 60 60 = 4 x 13 + 1 x 8 1 = 3 1 x 2 13 = 1 x 8 + 1 x 5 = 3 1 x (5 1x3) 8 = 1 x 5 + 1 x 3 = 2x 3 1x5 5 = 1 x 3 + 1 x 2 = 2 x (8 1x5) 1 x5 3 = 1 x 2 + 1 x 1 = 2 x 8 3 x 5 2 = 2 x 1 + 0 = 2 x 8 3 (13 1x 8) = 5 x 8 3 x 13 = 5 (60 4 x 13) 3 x 13 = 5 x 60 23 x 13 (sebab nilai negatif jadi kena tukar kpd yg positif) d = 60 -23 =37 #5: Jika diberi, M =26 cari C C = Memod n = 2613 mod 77 = 75 261 mod77 = 26
262 mod77 = 676 mod77 = 60 264 mod77 = 602 mod77 = 58 268 mod77 = 582 mod77 = 53 2613 mod77= 268 264 261 mod77= 53 x 58 x 26 mod77 = 71 x 26 mod77= 75
-
62 MODUL MTE3114 APLIKASI MATEMATIK
62
#6 : Semakan guna M = Cdmod n M = 7537mod 77 = 26 751 mod77 = 75
752 mod77 = 5625 mod77 = 4 754 mod77 = 42 mod77 = 16 758 mod77 = 162 mod77 = 25 7516 mod77 = 252 mod77 = 9 7532 mod77 = 92 mod77 = 4 7537 mod77 = 7532 754 751
mod77 = 4 x 16 x 75
mod77 = 64 x 75 mod77 = 26
top related