Integer (Bilangan Bulat)

Integer (Bilangan Bulat) “Learning is not child's play, we cannot learn without pain.” –Aristotle

Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

1

Tipe Data Integer Pada Bahasa Pemrograman •  Signed (bertanda +/-‐) •  Unsigned (bulat non-‐negaDf) Contoh: Misal suatu Dpe data integer berukuran 16-‐bit: 1.  Jika signed, maka berisi: −32768 s/d 32767 2.  Jika unsigned, maka berisi: 0 s/d 65535


2

Pembagian Bilangan Bulat a | b jika b = ac; c ∈ Z; a ≠ 0 Contoh: a habis membagi b 3 | 18 5 | 95 7 | 63


3

Teorema Sisa Pembagian (Quo:ent-‐remainder theorem)

Diberikan sembarang bilangan bulat n dan bilangan bulat posiDf d, maka ada bilangan bulat unik q dan r dimana: n = dq + r dan 0 < r < d LaDhan: Cari nilai bilangan bulat q dan r jika diketahui: a. n = 54, d = 4 b. n = -‐54, d = 4 Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

4

div dan mod Diberikan bilangan bulat n dan bilangan bulat posiDf d, maka:

n div d = q dan n mod d = r ⇔ n = dq + r dimana q dan r adalah bilangan bulat dan 0 < r < d Contoh: 9 div 4 = 2; 9 mod 4 = 1 Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

5

Greatest Common Divisor (1) Misal a dan b adalah bilangan bulat bukan nol, maka gcd(a,b), yaitu d, adalah: 1.  d adalah common divisor untuk a dan b. Dengan kata lain: d | a dan d | b

2.  Untuk semua bilangan bulat c, jika c adalah common divisor untuk semua a dan b, maka c lebih kecil atau sama dengan d. Dengan kata lain: Untuk semua bilangan bulat c, jika c | a dan c | b, maka c < d

Contoh:

GCD(45,36) = 9; GCD(80,12) = 4; GCD(12,8) = 4 Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

6

Greatest Common Divisor (2) Lemma:

1.  Jika r adalah bilangan bulat posiDf, maka gcd(r,0) = r 2.  Jika a dan b adalah bilangan bulat bukan nol, jika q dan r adalah bilangan bulat dimana a = bq + r, maka gcd(a,b) = gcd(b,r) Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

7

Algoritma Euclidean Bagaimana cara efisien dalam mencari GCD? Gunakan algoritma Euclidean.

1.  Misal A dan B adalah bilangan bulat dimana A > B > 0. 2.  Untuk mencari gcd dari A dan B, pertama cek apakah B = 0. Jika ya, maka gcd (A,B) = A (lihat lemma 1 pada slide sebelumnya). Jika Ddak, gunakan teorema quoDent-‐ remainder untuk mencari quoDent q dan remainder r. Merujuk lemma 2 pada slide sebelumnya, maka gcd(A,B) = gcd(B, r). 3.  Ulangi langkah nomor 2 sampai ditemukan hasil akhir. Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

8

Kongruensi Modulo n Ekivalensi modular: Misal a, b, c adalah sembarang bilangan bulat, dimana n > 1. Pernyataan berikut ini semuanya adalah ekivalen: 1.  2.  3.  4. 

n | (a – b) a ≡ b(mod n) a = b + kn, dimana k adalah suatu bilangan bulat a dan b memiliki sisa (non negaDf) yang sama jika dibagi dengan n 5.  a mod n = b mod n Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

9

AritmeDka Modular Misal a, b, c, d, dan n adalah bilangan bulat dengan n > 1 dan ditentukan bahwa a ≡ c(mod n) dan b ≡ d(mod n) Maka: 1.  (a + b) ≡ (c + d)(mod n) 2.  (a – b) ≡ (c – d)(mod n) 3.  ab ≡ cd(mod n) 4.  am ≡ cm(mod n) untuk semua bilangan bulat m Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

10

Kombinasi Linier Suatu bilangan bulat d dikatakan sebagai kombinasi linier dari bilangan bulat a dan b, jika dan hanya jika ada bilangan bulat s dan t dimana as + bt = d. Menulis gcd dalam bentuk kombinasi linier: Untuk semua bilangan bulat a dan b bukan nol, jika d = gcd(a,b), maka ada bilangan bulat s dan t dimana as + bt = d. LaDhan: Nyatakan gcd(330,156) sebagai kombinasi linier dari 330 dan 156. Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

11

RelaDf Prima (Coprime)

GCD(a, b) = 1 Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

12

Keberadaan Inverse Modulo n Untuk semua bilangan bulat a dan n, jika gcd(a,n) = 1, maka ada bilangan bulat s dimana as ≡ 1(mod n). Bilangan bulat s tersebut disebut inverse dari a modulo n. Contoh: 1.  Tentukan inverse dari 43 modulo 660. (Dengan kata lain, tentukan bilangan bulat s dimana 43s ≡ 1(mod 660). 2.  Tentukan inverse posiDf dari 3 modulo 40. (Dengan kata lain, tentukan bilangan bulat posiDf s dimana 3s ≡ 1(mod 40). Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

13

Keberadaan Inverse Modulo n Untuk semua bilangan bulat a dan n, jika gcd(a,n) = 1, maka ada bilangan bulat s dimana as ≡ 1(mod n). Bilangan bulat s tersebut disebut inverse dari a modulo n. Contoh: 1.  Tentukan inverse dari 43 modulo 660. (Dengan kata lain, tentukan bilangan bulat s dimana 43s ≡ 1(mod 660).


14

Konsep Dasar Kriptografi Kriptografi adalah ilmu yang mempelajari pengiriman pesan rahasia. decryp(on 2

plaintext

encryp(on

chipertext

1


15

Caesar Chiper A 01

B 02

C 03

D 04

E 05

F 06

G 07

H 08

I 09

J 10

K 11

L 12

M 13

N 14

O 15

P 16

Q 17

R 18

S 19

T 20

U 21

V 22

W 23

X 24

Y 25

Z 26

LaDhan: Gunakan Caesar chiper untuk mengenkripsi teks berikut: AYAS NAKAM OGES


16

RSA Cryptography Silahkan baca referensi dari buku teks masing – masing secara mandiri.


17

Referensi Susanna S .Epp. Discrete Mathema4cs with Applica4ons 4th Ed. Kenneth H. Rosen. Discrete Mathema4cs and Its Applica4ons 7th Ed. Rinaldi Munir. Matema4ka Diskrit edisi ke4ga. Matema(ka Komputasi -‐ Integer Agi Putra Kharisma, ST., MT.

18

Integer (Bilangan Bulat)

Recommend Documents