Teori Bilangan

Teori Bilangan

  • · Teori bilangan (number theory) adalah teori yang mendasar dalam memahami algoritma        kriptografi
  • Bilangan yang dimaksudkan adalah bilangan bulat (integer)

1. Bilangan Bulat 

  • Bilangan bulat adalah bilangan yang tidak mempunyai pecahan desimal, misalnya 8, 21, 8765, -34, 0
  • Berlawanan dengan bilangan bulat adalah bilangan riil yang mempunyai titik desimal,  8.0, 34.25, 0.02.

Sifat Pembagian pada Bilangan Bulat 

  1. Misalkan  a dan  b adalah dua buah bilangan bulat dengan syarat a ¹ 0. Kita menyatakan bahwa a habis membagi b (a divides b) jika terdapat bilangan bulat c  sedemikian sehingga b = ac.
  2. Notasi: a | b  jika b = ac, c Î Z dan a ¹ 0.  (Z = himpunan bilangan bulat)
  3. Kadang-kadang pernyataan “a habis membagi b“ ditulis juga  “b  kelipatan a”.
  4. Contoh 1: 4 | 12 karena 12 ¸4 = 3 (bilangan bulat) atau 12 = 4  ´ 3. Tetapi 4 | 13 karena 13¸4 = 3.25 (bukan bilangan bulat).

2 .  Pembagi Bersama Terbesar (PBB) 

  • Misalkan  a dan  b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar (PBB – greatest common divisor atau  gcd) dari  a dan  b adalah bilangan bulat terbesar  d sedemikian sehingga  d |  a dan  d |  b. Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.
  • Contoh: Faktor pembagi 45: 1, 3, 5, 9, 15, 45;  Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36; Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, 9 PBB(45, 36) = 9.

 

 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.

3.  Relatif Prima

  • Dua buah bilangan bulat  a dan b dikatakan relatif prima jika PBB(a, b) = 1.
  • Contoh 5. 20 dan 3 relatif prima sebab PBB(20, 3) = 1. Begitu juga 7 dan 11 relatif prima karena PBB(7, 11) = 1. Tetapi 20 dan 5 tidak relatif prima sebab PBB(20, 5) = 5 ¹ 1.
  • Jika  a dan  b relatif prima, maka terdapat bilangan bulat  m dan n sedemikian sehingga :   ma + nb = 1
  •  Contoh: Bilangan 20 dan 3 adalah relatif prima karena PBB(20, 3) =1, atau dapat ditulis : 2 . 20 + (–13) . 3 = 1, dengan m = 2 dan n = –13. Tetapi 20 dan 5 tidak relatif prima karena PBB(20, 5) = 5  ¹ 1 sehingga 20 dan 5 tidak dapat karena PBB(20, 5) = 5  ¹ 1 sehingga 20 dan 5 tidak dapat dinyatakan dalam m . 20 + n . 5 = 1.

4.  Aritmetika Modulo 

  • Misalkan a adalah bilangan bulat dan m adalah bilangan bulat > 0. Operasi  a mod  m (dibaca “a modulo  m”) memberikan sisa jika a dibagi dengan m.
  • Notasi:  a mod  m =  r  sedemikian sehingga  a =  mq +  r, dengan 0 £ r < m.
  • Bilangan  m disebut  modulus atau  modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0, 1, 2, …, m – 1}

Contoh: Beberapa hasil operasi dengan operator modulo:

  1. 23 mod 5 = 3  (23 = 5 × 4 +  3)
  2.  27 mod 3 = 0  (27 = 3 × 9 + 0)
  3. 6 mod 8 = 6   (6 = 8  × 0 + 6)
  4. 0 mod 12 = 0  (0 = 12 × 0 + 0)
  5. – 41 mod 9 = 4  (–41 = 9 (–5) + 4)
  6.  – 39 mod 13 = 0  (–39 = 13(–3) + 0)

Penjelasan (v): Karena  a negatif, bagi |a| dengan m mendapatkan sisa r’. Maka a mod m = m – r’ bila r’ ¹ 0. Jadi |– 41| mod 9 = 5, sehingga  –41 mod 9 = 9 – 5 = 4.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: